Recently, centralized receding horizon online multi-robot coverage path
planning algorithms have shown remarkable scalability in thoroughly exploring
large, complex, unknown workspaces with many robots. In a horizon, the path
planning and the path execution interleave, meaning when the path planning
occurs for robots with no paths, the robots with outstanding paths do not
execute, and subsequently, when the robots with new or outstanding paths
execute to reach respective goals, path planning does not occur for those
robots yet to get new paths, leading to wastage of both the robotic and the
computation resources. As a remedy, we propose a centralized algorithm that is
not horizon-based. It plans paths at any time for a subset of robots with no
paths, i.e., who have reached their previously assigned goals, while the rest
execute their outstanding paths, thereby enabling concurrent planning and
execution. We formally prove that the proposed algorithm ensures complete
coverage of an unknown workspace and analyze its time complexity. To
demonstrate scalability, we evaluate our algorithm to cover eight large $2$D
grid benchmark workspaces with up to 512 aerial and ground robots,
respectively. A comparison with a state-of-the-art horizon-based algorithm
shows its superiority in completing the coverage with up to 1.6x speedup. For
validation, we perform ROS + Gazebo simulations in six 2D grid benchmark
workspaces with 10 quadcopters and TurtleBots, respectively. We also
successfully conducted one outdoor experiment with three quadcopters and one
indoor with two TurtleBots.

提出一种非基于时间限制的集中式算法，可以实现并发规划和执行，从而在大规模工作区中完成完整覆盖，无需浪费机器人和计算资源。