EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments

Lin Li iD, Dianxi Shi, Songchang Jin, Shaowu Yang, Chenlei Zhou, Yaoning Lian, Hengzhu Liu

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

Dubins robotscoverage path planningpath planning

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}
}
Kostenlos starten →