Citation: Li, L.; Shi, D.; Jin, S.; Yang,
S.; Zhou, C.; Lian, Y.; Liu, H. Exact
and Heuristic Multi-Robot Dubins
Coverage Path Planning for Known
Environments. Sensors 2023, 23, 2560.
https://doi.org/10.3390/s23052560
Academic Editors: Shuai Li, Dechao
Chen, Mohammed Aquil Mirza,
Vasilios N. Katsikis, Dunhui Xiao,
Predrag S. Stanimirovic and Sergio
Toral Marín
Received: 20 December 2022
Revised: 3 February 2023
Accepted: 20 February 2023
Published: 25 February 2023
Copyright: © 2023 by the authors.
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/).
Article
Exact and Heuristic Multi-Robot Dubins Coverage Path
Planning for Known Environments
Lin Li
1
, Dianxi Shi
2,3
, Songchang Jin
2,3,
*, Shaowu Yang
1,
*, Chenlei Zhou
3
, Yaoning Lian
1
and Hengzhu Liu
1
1
College of Computer, National University of Defense Technology, Changsha 410003, China
2
Artificial Intelligence Research Center (AIRC), Defense Innovation Institute, Beijing 100073, China
3
Tianjin Artificial Intelligence Innovation Center (TAIIC), Tianjin 300456, China
* Correspondence: jsc04@tsinghua.org.cn (S.J.); shaowu.yang@nudt.edu.cn (S.Y.)
Abstract:
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.
Keywords: coverage path planning; Dubins robots; path planning
1. Introduction
As one sub-problem of robot path planning, coverage path planning (CPP) aims to
determine the optimal paths between the start and goal points to cover all regions while
avoiding obstacles and satisfying intrinsic robot limitations [
1
,
2
]. CPP is common in several
applications, including small-scale household tasks such as floor cleaning or lawn mowing
and large-scale operations such as search and rescue and environmental monitoring [
3
].
Due to the limited sensing range, calculating speed, and energy supply, many practical
coverage applications cannot be achieved by a single robot [
4
]. Thus, a series of multi-robot
CPP (MCPP) algorithms have been proposed to improve coverage efficiency and enhance
robustness. Meanwhile, MCPP faces the challenges of collaborative control, intelligent
decision-making, and logistical management [1,5].
Real-world MCPP applications, such as aerial monitoring [6], marine exploration [7],
and automatic farming [
8
,
9
], typically involve multiple aerial (fixed-wing aircraft), ground
(wheel robots), and autonomous underwater/surface vehicles. These vehicles are typically
governed by the Dubins vehicle model [
10
], which allows them to move at a fixed speed and
turn with a limited turning radius. As the foundation of many practical applications, MCPP
oriented towards Dubins robots (Dubins MCPP) has received growing attention in recent
years. Thus, this paper focuses on the Dubins MCPP problem of known environments.
MCPP problem has been proven to be NP-hard [
11
]. Various MCPP works have
been proposed to address the MCPP problem, and the related reviews can be found
Sensors 2023, 23, 2560. https://doi.org/10.3390/s23052560 https://www.mdpi.com/journal/sensors
