Hierarchical Area-Based and Path-Based Heuristic Approaches for Multirobot Coverage Path Planning with Performance...

Area of Science:

• Robotics and Automation
• Artificial Intelligence
• Operations Research

Background:

• Multirobot Coverage Path Planning (MCPP) is crucial for surveillance but often limited by naive approaches, especially when considering robot sensing range (SR).
• Existing MCPP methods primarily focus on cleaning tasks, lacking comprehensive strategies for surveillance applications that incorporate SR.

Purpose of the Study:

• To systematically explore hierarchical designs for MCPP tailored to surveillance applications, incorporating the sensing range (SR) factor.
• To propose a general MCPP framework that comprehensively addresses both path-based and area-based structures, utilizing advanced algorithms for enhanced planning.

Main Methods:

• Developed six distinct MCPP methods: two area-based (hierarchical max-flow routing with GA or ACO for Traveling Salesman Problem (TSP) within areas) and four path-based (global-local structures using GA and ACO combinations).
• Incorporated advanced TSP solvers like Genetic Algorithms (GAs) and Ant Colony Optimization (ACO) instead of naive approaches.
• Introduced ACO- or GA-based local planning in path-based methods to improve path quality and prevent degradation in global planning outcomes.

Main Results:

• Area-based MCPP approaches demonstrated superior performance in execution time and total path length compared to path-based methods.
• Path-based MCPP methods exhibited an advantage with smaller idle times.
• The proposed area-based MCPP method excels in path planning efficiency, while the path-based MCPP method shows better coverage balance.

Conclusions:

• The choice between area-based and path-based MCPP structures depends on specific application requirements, balancing efficiency, path length, and coverage.
• Leveraging the strengths of both methodologies allows for efficient MCPP execution in surveillance tasks.
• Future work will focus on adapting these MCPP structures for diverse real-world conditions to identify the most suitable approach for specific applications.