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.

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

在线并发多机器人覆盖路径规划

Online Concurrent Multi-Robot Coverage Path Planning

Path Planning methods for autonomous control of Unmanned Aerial Vehicle (UAV)
swarms are on the rise because of all the advantages they bring. There are more
and more scenarios where autonomous control of multiple UAVs is required. Most
of these scenarios present a large number of obstacles, such as power lines or
trees. If all UAVs can be operated autonomously, personnel expenses can be
decreased. In addition, if their flight paths are optimal, energy consumption
is reduced. This ensures that more battery time is left for other operations.
In this paper, a Reinforcement Learning based system is proposed for solving
this problem in environments with obstacles by making use of Q-Learning. This
method allows a model, in this particular case an Artificial Neural Network, to
self-adjust by learning from its mistakes and achievements. Regardless of the
size of the map or the number of UAVs in the swarm, the goal of these paths is
to ensure complete coverage of an area with fixed obstacles for tasks, like
field prospecting. Setting goals or having any prior information aside from the
provided map is not required. For experimentation, five maps of different sizes
with different obstacles were used. The experiments were performed with
different number of UAVs. For the calculation of the results, the number of
actions taken by all UAVs to complete the task in each experiment is taken into
account. The lower the number of actions, the shorter the path and the lower
the energy consumption. The results are satisfactory, showing that the system
obtains solutions in fewer movements the more UAVs there are. For a better
presentation, these results have been compared to another state-of-the-art
approach.

本文论述了如何使用基于强化学习的 Q-learning 算法来解决具有障碍物的环境下，多 UAV 自主控制的路径规划问题。实验表明，该系统在实现完全覆盖目标区域的同时，能够以较少的动作数节约路径长度和能源消耗。