Turn-minimizing multirobot coverage

Abstract

Multirobot coverage is the problem of planning paths for several identical robots such that the combined regions traced out by the robots completely cover their environment. We consider the problem of multirobot coverage with the objective of minimizing the mission time, which depends on the number of turns taken by the robots. To solve this problem, we first partition the environment into ranks which are long thin rectangles the width of the robot's coverage tool. Our novel partitioning heuristic produces a set of ranks which minimizes the number of turns. Next, we solve a variant of the multiple travelling salesperson problem (m-TSP) on the set of ranks to minimize the robots' mission time. The resulting coverage plan is guaranteed to cover the entire environment. We present coverage plans for a robotic vacuum using real maps of 25 indoor environments and compare the solutions to paths planned without the objective of minimizing turns. Turn minimization reduced the number of turns by 6.7% and coverage time by 3.8% on average for teams of 1-5 robots.