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...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-02-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/23/5/2560 |
| _version_ | 1827752121596903424 |
|---|---|
| author | Lin Li Dianxi Shi Songchang Jin Shaowu Yang Chenlei Zhou Yaoning Lian Hengzhu Liu |
| author_facet | Lin Li Dianxi Shi Songchang Jin Shaowu Yang Chenlei Zhou Yaoning Lian Hengzhu Liu |
| author_sort | Lin Li |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-03-11T07:10:19Z |
| format | Article |
| id | doaj.art-4f06a8227fe447dea74e8abea1f27817 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-11T07:10:19Z |
| publishDate | 2023-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-4f06a8227fe447dea74e8abea1f278172023-11-17T08:36:31ZengMDPI AGSensors1424-82202023-02-01235256010.3390/s23052560Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known EnvironmentsLin Li0Dianxi Shi1Songchang Jin2Shaowu Yang3Chenlei Zhou4Yaoning Lian5Hengzhu Liu6College of Computer, National University of Defense Technology, Changsha 410003, ChinaArtificial Intelligence Research Center (AIRC), Defense Innovation Institute, Beijing 100073, ChinaArtificial Intelligence Research Center (AIRC), Defense Innovation Institute, Beijing 100073, ChinaCollege of Computer, National University of Defense Technology, Changsha 410003, ChinaTianjin Artificial Intelligence Innovation Center (TAIIC), Tianjin 300456, ChinaCollege of Computer, National University of Defense Technology, Changsha 410003, ChinaCollege of Computer, National University of Defense Technology, Changsha 410003, ChinaCoverage 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.https://www.mdpi.com/1424-8220/23/5/2560coverage path planningDubins robotspath planning |
| spellingShingle | Lin Li Dianxi Shi Songchang Jin Shaowu Yang Chenlei Zhou Yaoning Lian Hengzhu Liu Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments Sensors coverage path planning Dubins robots path planning |
| 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 | coverage path planning Dubins robots path planning |
| url | https://www.mdpi.com/1424-8220/23/5/2560 |
| work_keys_str_mv | AT linli exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT dianxishi exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT songchangjin exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT shaowuyang exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT chenleizhou exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT yaoninglian exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments AT hengzhuliu exactandheuristicmultirobotdubinscoveragepathplanningforknownenvironments |