论文标题
TMSTC*：用于多机器人覆盖路径计划的转向最小化算法
TMSTC*: A Turn-minimizing Algorithm For Multi-robot Coverage Path Planning
论文作者
论文摘要
覆盖路径计划是移动机器人的主要应用程序，它要求机器人沿着计划的路径覆盖整个地图。对于大规模任务，多个机器人的覆盖路径计划受益匪浅。在本文中，我们描述了基于MSTC*的改进的多机器人覆盖路径计划（MCPP）算法的跨度跨越树覆盖星（TMSTC*）。作为树的分支，我们的算法将地图划分为最小砖块，从而将问题转化为找到两部分图的最大独立集。然后，我们将砖块与贪婪的策略联系起来，以形成一棵树，旨在减少相应的环绕覆盖路径的转弯数。我们的实验结果表明，我们的方法使多个机器人比其他流行算法更快地完成了弯道，从而完成了地形覆盖任务。
Coverage path planning is a major application for mobile robots, which requires robots to move along a planned path to cover the entire map. For large-scale tasks, coverage path planning benefits greatly from multiple robots. In this paper, we describe Turn-minimizing Multirobot Spanning Tree Coverage Star(TMSTC*), an improved multirobot coverage path planning (mCPP) algorithm based on the MSTC*. Our algorithm partitions the map into minimum bricks as tree's branches and thereby transforms the problem into finding the maximum independent set of bipartite graph. We then connect bricks with greedy strategy to form a tree, aiming to reduce the number of turns of corresponding circumnavigating coverage path. Our experimental results show that our approach enables multiple robots to make fewer turns and thus complete terrain coverage tasks faster than other popular algorithms.
