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

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

TL;DR

This paper introduces two novel algorithms, EDM and CDM, for multi-robot coverage path planning (MCPP) specifically for Dubins robots (vehicles with fixed speed and turning radius). EDM provides an optimal solution for small environments by formulating the problem as a Mixed Integer Linear Program (MILP), while CDM offers a near-optimal, computationally efficient solution for larger areas by balancing tasks using a credit model and a tree-partition strategy.

What Problem Does This Paper Address?

Multi-robot coverage path planning (MCPP) is crucial for tasks like aerial monitoring, marine exploration, and search and rescue, where a single robot is insufficient. However, existing MCPP methods often struggle with the specific kinematic constraints of Dubins robots (fixed speed, limited turning radius), which prevent them from reversing or making sharp turns. Furthermore, exact MCPP algorithms can be computationally prohibitive for large areas, while heuristic methods often face a trade-off between accuracy and complexity. This paper aims to bridge this gap by proposing solutions that are both kinematically feasible for Dubins robots and scalable to different environment sizes.

Methods

The paper presents two distinct algorithms:

  • Exact Dubins Multi-Robot Coverage Path Planning (EDM): This algorithm tackles the MCPP problem by formulating it as a Mixed Integer Linear Program (MILP). It first represents the environment as a graph where vertices are cell endpoints and edges are Dubins paths between them. The MILP then searches the entire solution space to find the shortest possible Dubins coverage paths for all robots, guaranteeing optimality for smaller environments.
  • Heuristic Credit-Based Dubins Multi-Robot Coverage Path Planning (CDM): For larger and more complex scenarios, CDM offers a heuristic approach. It involves three main components:
  • Initial Partition: The environment is divided into initial partitions using a regional growth strategy based on a credit model.
  • Partition Refinement: A credit-based task allocation mechanism and a tree-partition strategy are employed to rebalance tasks among robots, ensuring a more equitable workload distribution and maintaining partition connectivity.
  • Path Planning: A single-robot Dubins solver is then applied to each refined partition to generate the actual coverage paths. This approach prioritizes balancing accuracy with computational efficiency.

Datasets

The paper does not introduce new datasets. Instead, it uses simulated environments of varying sizes and complexities, including:

  • Four small-scale scenes (10m x 10m x 10m) with obstacles.
  • Four larger-scale environments (multi-cell, farm, rural Quebec, cave) with different dimensions and shapes, adapted from existing literature.
  • A high-fidelity fixed-wing UAV model in Simulink for feasibility testing.

Key Insights and Ideas

  • MILP for Optimal Dubins Paths: Formulating the Dubins MCPP problem as an MILP allows for the guarantee of finding the absolute shortest coverage path, which is crucial for small, critical missions where optimality is paramount.
  • Credit Model for Task Balancing: The credit model in CDM is an effective way to dynamically reallocate tasks between robots, preventing imbalances and ensuring that no single robot is overloaded, especially in complex scenarios.
  • Tree-Partitioning for Connectivity: The tree-partition strategy in CDM is vital for maintaining the connectivity of robot partitions, preventing robot collisions, and simplifying control, which is a common challenge in MCPP.
  • Trade-off between Exactness and Scalability: The paper successfully demonstrates that an exact approach (EDM) is suitable for small, optimal solutions, while a heuristic approach (CDM) is necessary for scalability and efficiency in larger environments.

Key Results

  • Small Scenes: EDM consistently achieved the least coverage time in small-scale environments compared to Milpflow, DCRC, and CDM.
  • Large Scenes: CDM demonstrated shorter coverage times and significantly less computation time than the heuristic DCRC algorithm across various large-scale environments, especially as the number of robots increased.
  • Feasibility: Both EDM and CDM were successfully validated on a high-fidelity fixed-wing UAV model, showing their applicability to real-world robotic systems with Dubins kinematic constraints.

Limitations and Future Work

  • Limitations:
    • The EDM algorithm's computational complexity makes it impractical for large-scale environments.
  • The paper focuses on known environments; dynamic or unknown environments are not addressed.
  • The current work assumes homogeneous Dubins robots.
  • Future Work:
    • Extending the algorithms to handle online coverage in unknown environments.
  • Applying the proposed methods to real-world Dubins robots.
  • Investigating MCPP for heterogeneous robots with different kinematic constraints.

Summary updated

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.
BibTeX
@inproceedings{li2023exact,
  author = {Lin Li and Dianxi Shi and Songchang Jin and Shaowu Yang and Chenlei Zhou and Yaoning Lian and Hengzhu Liu},
  title = {{Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments}},
  booktitle = {Sensors},
  year = {2023},
  url = {https://openreview.net/forum?id=8BIxGm6WsH},
}
Figure