This study introduces a resilient and adaptive multi-robot coverage path planning approach based on the Boustrophedon Cell Decomposition algorithm, designed to dynamically redistribute coverage tasks in the event of robot failures. The proposed method ensures minimal disruption and maintains a balanced workload across operational robots through a propagation-based redistribution strategy. By iteratively reallocating the failed robot’s coverage path to neighboring robots, the method prevents any single robot from becoming overburdened, ensuring efficient task distribution and continuous environmental monitoring. Simulations conducted in five distinct environments, ranging from simple open areas to complex, obstacle-rich terrains, demonstrate the method’s robustness and adaptability. A key strength of the proposed approach is its fast and efficient task reallocation process, achieved with minimal propagation cycles, making it suitable for real-time applications even in complex scenarios. The approach reduces task variance and maintains balanced coverage throughout the mission.

In this study, we present a systematic exploration of hierarchical designs for multirobot coverage path planning (MCPP) with a special focus on surveillance applications. Unlike conventional studies centered on cleaning tasks, our investigation delves into the realm of surveillance problems, specifically incorporating the sensing range (SR) factor equipped on the robots. Conventional path-based MCPP strategies considering SR, primarily rely on naive approaches, generating nodes (viewpoints) to be visited and a global path based on these nodes. Therefore, our study proposes a general MCPP framework for surveillance by dealing with path-based and area-based structures comprehensively. As the traveling salesman problem (TSP) solvers, our approach incorporates not the naive approach but renowned and powerful algorithms such as genetic algorithms (GAs), and ant colony optimization (ACO) to enhance the planning process. We devise six distinct methods within the proposed MCPP framework. Two methods adopt area-based approaches which segments areas via a hierarchical max-flow routing algorithm based on SR and the number of robots. TSP challenges within each area are tackled using a GA or ACO, and the result paths are allocated to individual robots. The remaining four methods are categorized by the path-based approaches with global–local structures such as GA-GA, GA-ACO, ACO-GA, and ACO-ACO. Unlike conventional methods which requires a global path, we further incorporate ACO- or GA-based local planning. This supplementary step at the local level enhances the quality of the path-planning results, particularly when dealing with a large number of nodes, by preventing any degradation in global path-planning outcomes. An extensive comparative analysis is conducted to evaluate the proposed framework based on execution time, total path length, and idle time. The area-based approaches tend to show a better execution time and overall path length performance compared to the path-based approaches. However, the path-based MCPP methods have the advantage of having a smaller idle time than the area-based MCPP methods. Our study finds that the proposed area-based MCPP method excels in path planning, while the proposed path-based MCPP method demonstrates superior coverage balance performance. By selecting an appropriate MCPP structure based on the specific application requirements, leveraging the strengths of both methodologies, efficient MCPP execution becomes attainable. Looking forward, our future work will focus on tailoring these MCPP structures to diverse real-world conditions, aiming to propose the most suitable approach for specific applications.

본 연구에서는 능동 SLAM을 위한 계층적 커버리지 경로 계획 방법을 제안한다. 능동 SLAM은 SLAM에서 불확실성이 높은 영역을 재방문하여 SLAM 지도의 정확성을 향상하기 위한 로봇 경로를 계획하는 기술이다. 그러나, 불확실성이 높은 영역만 방문할 경우, 오히려 공분산의 지속적 상승으로 인해 SLAM 결과가 발산될 수 있다. 제안된 방법은 허용 가능한 불확실성을 넘지 않는 제약조건 아래에서 기존 방법보다 향상된 커버리지 경로 계획을 제안한다. 이를 위해 개미 군집 최적화 기법과 유전 알고리즘을 계층적 구조로 접근해 해결하였다. 시뮬레이션에서는 경로 길이, 불확실성 수치, 수행시간 면에서 제안한 방법과 기존 접근 방법과의 비교 및 분석을 수행하였다. 제안한 방법은 제약조건인 허용 가능한 불확실성을 넘지 않으며 동시에 짧은 경로 생성 성능을 보였다. 향후, 제안한 방법을 실시간으로 수행하여 SLAM의 공분산이 감소하고 지도가 정확히 작성됨을 보일 예정이다.

본 연구에서는 다중 로봇 커버리지 경로 계획(MCPP, Multi-robot Coverage Path Planning)을 위해 대표적인 휴리스틱(Heuristic) 기법인 유전 알고리즘(GA, Genetic Algorithm)과 개미 집단 최적화(ACO, Ant Colony Optimization)의 특징을 토대로 이들의 다양한 조합에 대한 성능 비교 연구결과를 보였다. 이를 위해, 환경, 노드 개수, 경로 생성, 수행 시간의 측면에서 ACO와 GA의 개별 특징을 분석하였다. 개별 특징을 토대로 MCPP를 위해 4가지의 ACO와 GA의 조합 구조가 선정되었고, 다양한 환경에서 이 조합 구조들이 테스트되었다. 테스트 결과로부터 각 구조의 수렴시간 및 경로 Cost 결과가 비교 분석되었다. 향후에는 이 분석 결과를 토대로 주어진 환경에 가장 적합한 MCPP 구조를 제안하는 연구를 진행할 계획이다.