Online On-Demand Multi-Robot Coverage Path Planning
share
We present an online centralized path planning algorithm to cover a large, complex, unknown workspace with multiple homogeneous mobile robots. Our algorithm is horizon-based, synchronous, and on-demand. The recently proposed horizon-based synchronous algorithms compute the paths for all the robots in each horizon, significantly increasing the computation burden in large workspaces with many robots. As a remedy, we propose an algorithm that computes the paths for a subset of robots that have traversed previously computed paths entirely (thus on-demand) and reuses the previously computed paths for the other robots. We formally prove that the algorithm guarantees the complete coverage of the unknown workspace. Experimental results show that our algorithm scales to hundreds of robots in large workspaces and consistently outperforms a state-of-the-art online multi-robot centralized coverage path planning algorithm.We also perform ROS+Gazebo simulations in five 2D grid benchmark workspaces with 10 Quadcopters and one real experiment with two Quadcopters in an outdoor experiment, to establish the practical feasibility of our algorithm.
READ FULL TEXT