Tutorial 1-2: Rendezvous on Faulty Autonomous Mobile Robots

摘要

The autonomous mobile robots system is one of the distributed systems such that communications between robots are done by observations of all the other robots' locations and state transitions are done by changing their locations on two-dimensional space or graphs etc. Recent years, this system has attracted a lot of researchers in distributed systems and some kind of fundamental problems like pattern forming, flocking, or graph exploring etc. have been concerned. One of the main objectives in this research area is to reveal relationship between the system models and its solvability of the problems. The system model consists of wide variety of abilities such as observation, mobility, multiplicity, synchronicity, memory, and so on. Differences of these factors sensitively influence the problem solvability; it is very similar to conventional distributed systems. In this talk, the relationship between faulty robot models and their solvability of the rendezvous problem is focused on. The faulty robot model means that, for example, an observation mechanism equipped with each robot returns inaccurate coordinates of other robots' locations. The rendezvous problem is one of the agreement problem and to make all robots meet or gradually converge at a single point which is not predefined. To investigate the relationship between faulty models and the solvability of the rendezvous problem is fundamental and interesting for theoretical point of view on the autonomous mobile robot system. Especially, I will pick up inaccurate compasses (observation mechanism) and Byzantine fault robot model as faulty models, and present the relationships between them and solvability of the rendezvous problem through introducing recent works.