Distributed auction-based coverage motion planning for multiple cooperative robots

The multi-robot coverage motion planning (MCMP) problem refers to a typical task where every point of the target area must be covered by robots at least once. This paper designs a novel efficient offline algorithm to solve the MCMP problem, which is extended from the spiral-spanning tree coverage algorithm. A distributed auction mechanism is designed for the cooperative task allocation in the proposed algorithm. In this mechanism, each robot will be an auctioneer which chooses a suitable cell as an auction item form its neighbor vertexes and determines a winner robot. According to the connectedness and the balance of each robot’s graph, bidders will submit proper biddings to the auctioneer. After the auction processes, acceptable coverage trajectories can be planned rapidly. Computational experiments validate the effectiveness of the proposed MCMP algorithm. Meanwhile, the proposed algorithm is compared with the state-of-the-art algorithm named DARP. The comparative results show that the auction-based MCMP algorithm has apparent advantages in the running time and the makespans for large crowded configuration spaces.