FT-MSTC*: An Efficient Fault Tolerance Algorithm for Multi-robot Coverage Path Planning

Abstract

Fault tolerance is very important for multi-robot systems, especially for those operated in remote environments. The ability to tolerate failures, allows robots effectively to continue performing tasks without the need for immediate human intervention. In this paper, we present a new efficient fault tolerance algorithm for multi-robot coverage path planning (mCPP). The entire coverage path is considered as a topological task loop. The ideal mCPP problem is handled by partitioning this task loop and assign each partition to individual robot. When a faulty robot is detected, we use an optimization method to minimize the overall maximum coverage cost while considering both the tasks accomplished before robot failures and the remaining tasks. We perform various experiments for regular grid maps and real field terrains. We compare our algorithm against other coverage path planning algorithms and our algorithm outperforms existing spiral-STC-based methods in terms of the overall maximum coverage cost.