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...

Descripción completa

Detalles Bibliográficos
Autores principales: Qin, Yijie, Fu, Lei, He, Dingxin, Liu, Zhiwei
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