An algorithmic pipeline to plan conflict-free coverage paths for multiple robots on grids.

Extended Spanning-Tree Coverage (ESTC) for Single-Robot CPP

In summary, ESTC works by 1) initiating a self-connecting local path for each hypervertex (i.e., square grid) and 2) pairwisely connecting local paths according to a spanning tree of the hypergraph (i.e., 4-way connected square grid graph). 

This results in a closed single-robot path with complete coverage for any 4-way connected grid graph (formed by the black circles).

The hyperedge weight definition makes the ESTC path on a minimum spanning tree the optimal "circumnavigating" STC[1]-like single-robot coverage path, and bounded-suboptimal among all kinds of single-robot coverage paths on the grid graph.

Local-Search Framework for Large-Scale MCPP (LS-MCPP)

LS-MCPP[2] integrates three types of neighborhood operators and utilizes ESTC as a subroutine for single-robot coverage path planner, enhancing its ability to solve MCPP even in complex environments with incomplete hypervertices. It aims to optimize coverage paths by iteratively refining subgraphs and their corresponding coverage paths, ensuring both efficiency and completeness in coverage solutions. 

LS-MCPP employs grow operators on less-costly subgraphs to assign them new vertices to cover, deduplicate operators on more-costly subgraphs to eliminate unnecessary duplication, and exchange operators to balance path costs between subgraphs with a large cost difference. They are designed to attain a cost-equilibrium MCPP solution with a low makespan.

LS-MCPP also periodically calls a deduplication function to achieve a low-makespan solution, by removing 1) U-turns with duplications and 2) the regions forming valid deduplicate operators.

Deconflicting MCPP Solutions via Priority-Based Search

The MCPP problem formulation does not inherently prevent collisions among robots. In an MCPP solution with a small makespan, robots typically cover different regions and are distributed across the grid, which lowers the likelihood of conflicts. However, certain regions remain prone to congestion and conflicts, particularly around clustered root vertices or narrow corridors that only allow one robot to pass at a time.

 To resolve these potential conflicts, we formulate the deconflicting task as a variant of MAPF. Specifically, we develop a two-level hierarchical planner, following standard MAPF practices: The high-level planner employs Priority-Based Search (PBS)[3] to assign priorities among pairs of conflicting robots; The low-level planner is a novel algorithm that plans a continuous-time path with safe-interval path planning [4] for each robot that avoids conflicting with any higher-priority robots.

Our key extensions from standard MAPF lie in 1) our treatment of non-uniform edge weights, which translate to variable time costs for robot actions, and 2) an adaptive approach of the low-level planner for time-efficient single-robot path planning with multiple goals.

In essence, for the low-level planner, the chaining approach plans a path of space-time states for each goal in the coverage path consecutively and concatenates them. The multi-label approach plans a path of space-time-label states holistically, where the label is an additional dimension of the search space therefore enabling to backtrack when encountering "dead-end" situations. The adaptive approach also considers space-time-label state space yet with a limited window size, which greatly reduces the state space yet still has the ability of backtracking.

Simulations on MCPP and Deconflicted LS-MCPP Solutions

We show a comparison between different types of MCPP solutions as well as the Deconflicted LS-MCPP solution, with their makespans reported in the captions. We briefly describe the above methods for an MCPP instance with k robots:

VOR: it partitions the grid graph into k subgraphs by generating the Voronoi diagram on the root vertex sets, and then uses ESTC to generate a single-robot coverage path for each of the k robots.

MFC [5]: it heuristically finds a set of k covering subtrees on the corresponding hypergraph (opt. ratio of 4), and uses ESTC to generate a single-robot coverage path for each robot (opt. ratio of 16 for certain cases).

MIP [6]: it optimally (highly computationally demanding!) finds a set of k covering subtrees on the corresponding hypergraph, and then uses ESTC to generate a single-robot coverage path for each robot (opt. ratio of 4 for certain cases).

MSTC* [7]: it greedily finds cutting points to partition a single-robot ESTC path to k segments for the robots.

Two Pepper Robots Performing the Coverage Task

We employed 2 Pepper robots, named Cayenne and Cumin, each with a square bounding box of 0.55 meters, to verify the above planning pipeline. The 2D grid graph represents the indoor environment as a 10x6 map with each grid unit sized at 0.65 meters. The graph is weighted with edge weights randomly generated according to their max velocity constraints. Both Peppers can have omnidirectional movement driven by velocity commands.

Given the set of conflict-free trajectories resulting from our planning pipeline, we generate an action sequence consisting of move, turn, and wait actions between consecutive states for each Pepper. A centralized scheduler is employed to sequentially send actions to the corresponding Pepper, maintaining a positional tolerance of 0.01 meters and a rotational tolerance of 0.02 radians. It synchronizes the discrepancies between the nominal time costs and the actual time costs for the actions, as the move and turn action time costs are not precise in practice.

Some More Simulations on the Final Deconflicted LS-MCPP Solutions

References

[1] Gabriely, Yoav, and Elon Rimon. "Spanning-tree based coverage of continuous areas by a mobile robot." Annals of mathematics and artificial intelligence 31 (2001): 77-98. 

[2] Tang, Jingtao, and Hang Ma. "Large-Scale Multi-Robot Coverage Path Planning via Local Search." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 16. 2024.

[3] Ma, Hang, et al. "Searching with consistent prioritization for multi-agent path finding." Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019. 

[4] Phillips, Mike, and Maxim Likhachev. "Sipp: Safe interval path planning for dynamic environments." 2011 IEEE international conference on robotics and automation. IEEE, 2011. 

[5] Zheng, Xiaoming, et al. "Multirobot forest coverage for weighted and unweighted terrain." IEEE Transactions on Robotics 26.6 (2010): 1018-1031.

[6] Tang, Jingtao, and Hang Ma. "Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Heuristics." IEEE Robotics and Automation Letters (2023).

[7] Tang, Jingtao, Chun Sun, and Xinyu Zhang. "MSTC∗: Multi-robot coverage path planning under physical constrain." 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021.

[8] Sturtevant, Nathan R. "Benchmarks for grid-based pathfinding." IEEE Transactions on Computational Intelligence and AI in Games 4.2 (2012): 144-148.