Theory of Distributed Anonymous Mobile Robots Formation and Agreement Problems

摘要

A system consisting of multiple mobile robots in which the robots can see eachother by their eye sensors but are not equipped with any communication system, can be viewed as a distributed system in which the components (i.e., robots) can 'communicate' with each other only by means of their moves. We use this system to investigate, through a case study of a number of problems on the formation of geometric figures in the plane, the power and limitations of the distributed control method for mobile robots. In the distributed control method, each robot, at infinitely many unpredictable time instants, observes the positions of all the robots and moves to a new position determined by the given algorithm. The robots are anonymous in the sense that they all execute the same algorithm and they cannot be distinguished by their appearances. The robots are not necessarily synchronous, so they may not always observe their positions simultaneously. Furthermore, initially the robots do not have a common x-y coordinate system. The problems we discuss include (1) converging the robots to a single point, (2) moving the robots to a single point, (3) agreement on a single point, (4) agreement on the unit distance, (5) agreement on direction, and (6) leader election. We develop algorithms for solving some of these problems under various conditions. Some impossibility results are also presented. (AN).