Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments
Sensors · 25.02.2023 · 23 (5) · 2560
DOI: 10.3390/s23052560 ↗Kurz gefasst
Fachartikel in der Zeitschrift Sensors, online erschienen am 25.02.2023. Verfasst von Lin Li und 6 weiteren Autor:innen. Beteiligte Einrichtung: College of Computer, National University of Defense Technology, Changsha 410003, China. Die Arbeit wurde bisher 52-mal zitiert (Crossref) und nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Science and Technology Innovation 2030 Major Project, National Natural Science Foundation of China.
Abstract (Originalsprache)
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.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- College of Computer, National University of Defense Technology, Changsha 410003, China.
- Artificial Intelligence Research Center (AIRC), Defense Innovation Institute, Beijing 100073, China.
- Tianjin Artificial Intelligence Innovation Center (TAIIC), Tianjin 300456, China.
ORCID-Profile: Lin Li
Förderung
- Science and Technology Innovation 2030 Major Project
- National Natural Science Foundation of China
Zitieren
APA
Li, L., Shi, D., Jin, S., Yang, S., Zhou, C., Lian, Y., & Liu, H. (2023). Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments. Sensors, 23(5), 2560. https://doi.org/10.3390/s23052560
Vancouver
Li L, Shi D, Jin S, Yang S, Zhou C, Lian Y, et al. Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments. Sensors. 2023;23(5):2560. doi:10.3390/s23052560
BibTeX
@article{Li2023,
author = {Li, Lin and Shi, Dianxi and Jin, Songchang and Yang, Shaowu and Zhou, Chenlei and Lian, Yaoning and Liu, Hengzhu},
title = {Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments},
journal = {Sensors},
year = {2023},
volume = {23},
number = {5},
pages = {2560},
doi = {10.3390/s23052560}
}
EUVIMED