TMSTC*: 旋回を最小化するマルチロボット被覆経路計画アルゴリズム
TMSTC*: A Turn-minimizing Algorithm For Multi-robot Coverage Path Planning
地図を最小単位のレンガに分割し二部グラフの最大独立集合問題として解くことで、複数ロボットの被覆経路の旋回回数を削減し、効率的に広域をカバーする手法を提案した。
著者: Junjie Lu, Bi Zeng, Jingtao Tang, Tin Lun Lam
分類: cs.RO
原文アブストラクト
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.
