Back to Search Start Over

Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning

Authors :
Yijie Qin
Lei Fu
Dingxin He
Zhiwei Liu
Source :
Sensors, Vol 23, Iss 7, p 3596 (2023)
Publication Year :
2023
Publisher :
MDPI AG, 2023.

Abstract

In this paper, we investigate the algorithms for traversal exploration and path coverage of target regions using multiple agents, enabling the efficient deployment of a set of agents to cover a complex region. First, the original multi-agent path planning problem (mCPP) is transformed into several single-agent sub-problems, by dividing the target region into multiple balanced sub-regions, which reduces the explosive combinatorial complexity; subsequently, closed-loop paths are planned in each sub-region by the rapidly exploring random trees (RRT) algorithm to ensure continuous exploration and repeated visits to each node of the target region. On this basis, we also propose two improvements: for the corner case of narrow regions, the use of geodesic distance is proposed to replace the Eulerian distance in Voronoi partitioning, and the iterations for balanced partitioning can be reduced by more than one order of magnitude; the Dijkstra algorithm is introduced to assign a smaller weight to the path cost when the geodesic direction changes, which makes the region division more “cohesive”, thus greatly reducing the number of turns in the path and making it more robust. The final optimization algorithm ensures the following characteristics: complete coverage of the target area, wide applicability of multiple area shapes, reasonable distribution of exploration tasks, minimum average waiting time, and sustainable exploration without any preparation phase.

Details

Language :
English
ISSN :
14248220
Volume :
23
Issue :
7
Database :
Directory of Open Access Journals
Journal :
Sensors
Publication Type :
Academic Journal
Accession number :
edsdoj.fb336084d8b4e228d35117284e002ad
Document Type :
article
Full Text :
https://doi.org/10.3390/s23073596