Cargando…
Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning
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 s...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
MDPI
2023
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10099348/ https://www.ncbi.nlm.nih.gov/pubmed/37050656 http://dx.doi.org/10.3390/s23073596 |
_version_ | 1785025031952138240 |
---|---|
author | Qin, Yijie Fu, Lei He, Dingxin Liu, Zhiwei |
author_facet | Qin, Yijie Fu, Lei He, Dingxin Liu, Zhiwei |
author_sort | Qin, Yijie |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-10099348 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2023 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-100993482023-04-14 Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning Qin, Yijie Fu, Lei He, Dingxin Liu, Zhiwei Sensors (Basel) Article 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. MDPI 2023-03-30 /pmc/articles/PMC10099348/ /pubmed/37050656 http://dx.doi.org/10.3390/s23073596 Text en © 2023 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). |
spellingShingle | Article Qin, Yijie Fu, Lei He, Dingxin Liu, Zhiwei Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning |
title | Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning |
title_full | Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning |
title_fullStr | Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning |
title_full_unstemmed | Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning |
title_short | Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning |
title_sort | improved optimization strategy based on region division for collaborative multi-agent coverage path planning |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10099348/ https://www.ncbi.nlm.nih.gov/pubmed/37050656 http://dx.doi.org/10.3390/s23073596 |
work_keys_str_mv | AT qinyijie improvedoptimizationstrategybasedonregiondivisionforcollaborativemultiagentcoveragepathplanning AT fulei improvedoptimizationstrategybasedonregiondivisionforcollaborativemultiagentcoveragepathplanning AT hedingxin improvedoptimizationstrategybasedonregiondivisionforcollaborativemultiagentcoveragepathplanning AT liuzhiwei improvedoptimizationstrategybasedonregiondivisionforcollaborativemultiagentcoveragepathplanning |