Cargando…
Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments
Coverage path planning (CPP) of multiple Dubins robots has been extensively applied in aerial monitoring, marine exploration, and search and rescue. Existing multi-robot coverage path planning (MCPP) research use exact or heuristic algorithms to address coverage applications. However, several exact...
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/PMC10007483/ https://www.ncbi.nlm.nih.gov/pubmed/36904764 http://dx.doi.org/10.3390/s23052560 |
_version_ | 1784905532701671424 |
---|---|
author | Li, Lin Shi, Dianxi Jin, Songchang Yang, Shaowu Zhou, Chenlei Lian, Yaoning Liu, Hengzhu |
author_facet | Li, Lin Shi, Dianxi Jin, Songchang Yang, Shaowu Zhou, Chenlei Lian, Yaoning Liu, Hengzhu |
author_sort | Li, Lin |
collection | PubMed |
description | Coverage path planning (CPP) of multiple Dubins robots has been extensively applied in aerial monitoring, marine exploration, and search and rescue. Existing multi-robot coverage path planning (MCPP) research use exact or heuristic algorithms to address coverage applications. However, several exact algorithms always provide precise area division rather than coverage paths, and heuristic methods face the challenge of balancing accuracy and complexity. This paper focuses on the Dubins MCPP problem of known environments. Firstly, we present an exact Dubins multi-robot coverage path planning (EDM) algorithm based on mixed linear integer programming (MILP). The EDM algorithm searches the entire solution space to obtain the shortest Dubins coverage path. Secondly, a heuristic approximate credit-based Dubins multi-robot coverage path planning (CDM) algorithm is presented, which utilizes the credit model to balance tasks among robots and a tree partition strategy to reduce complexity. Comparison experiments with other exact and approximate algorithms demonstrate that EDM provides the least coverage time in small scenes, and CDM produces a shorter coverage time and less computation time in large scenes. Feasibility experiments demonstrate the applicability of EDM and CDM to a high-fidelity fixed-wing unmanned aerial vehicle (UAV) model. |
format | Online Article Text |
id | pubmed-10007483 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2023 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-100074832023-03-12 Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments Li, Lin Shi, Dianxi Jin, Songchang Yang, Shaowu Zhou, Chenlei Lian, Yaoning Liu, Hengzhu Sensors (Basel) Article Coverage path planning (CPP) of multiple Dubins robots has been extensively applied in aerial monitoring, marine exploration, and search and rescue. Existing multi-robot coverage path planning (MCPP) research use exact or heuristic algorithms to address coverage applications. However, several exact algorithms always provide precise area division rather than coverage paths, and heuristic methods face the challenge of balancing accuracy and complexity. This paper focuses on the Dubins MCPP problem of known environments. Firstly, we present an exact Dubins multi-robot coverage path planning (EDM) algorithm based on mixed linear integer programming (MILP). The EDM algorithm searches the entire solution space to obtain the shortest Dubins coverage path. Secondly, a heuristic approximate credit-based Dubins multi-robot coverage path planning (CDM) algorithm is presented, which utilizes the credit model to balance tasks among robots and a tree partition strategy to reduce complexity. Comparison experiments with other exact and approximate algorithms demonstrate that EDM provides the least coverage time in small scenes, and CDM produces a shorter coverage time and less computation time in large scenes. Feasibility experiments demonstrate the applicability of EDM and CDM to a high-fidelity fixed-wing unmanned aerial vehicle (UAV) model. MDPI 2023-02-25 /pmc/articles/PMC10007483/ /pubmed/36904764 http://dx.doi.org/10.3390/s23052560 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 Li, Lin Shi, Dianxi Jin, Songchang Yang, Shaowu Zhou, Chenlei Lian, Yaoning Liu, Hengzhu Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments |
title | Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments |
title_full | Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments |
title_fullStr | Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments |
title_full_unstemmed | Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments |
title_short | Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments |
title_sort | exact and heuristic multi-robot dubins coverage path planning for known environments |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10007483/ https://www.ncbi.nlm.nih.gov/pubmed/36904764 http://dx.doi.org/10.3390/s23052560 |
work_keys_str_mv | AT lilin exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT shidianxi exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT jinsongchang exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT yangshaowu exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT zhouchenlei exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT lianyaoning exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT liuhengzhu exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments |