Fault-tolerant distributed algorithms for autonomous mobile robots with crash faults

Abstract

We consider distributed algorithms for a system consisting of many autonomous mobile robots. Each robot asynchronously executes the same program to move to a new position, which depends on the other robots' positions obtained from its eye sensor. The system we consider includes initial crash faults such that faulty robots can make no move. We define the Active Robots Selection Problem (ARSP), and present an algorithm to solve the ARSP if a majority of the robots are nonfaulty. A technique is also proposed transforming a non-fault-tolerant algorithm to a fault-tolerant one by using the solution of the ARSP. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(2): 33–43, 1997