Accession Number : ADA303910

Title :   A Theory of Distributed Anonymous Mobile Robots Formation and Agreement Problems.

Descriptive Note : Technical rept.,

Corporate Author : WISCONSIN UNIV-MILWAUKEE DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Personal Author(s) : Suzuki, Ichiro ; Yamashita, Masafumi

PDF Url : ADA303910

Report Date : 15 JUL 1994

Pagination or Media Count : 38

Abstract : A system consisting of multiple mobile robots in which the robots can see each other 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)

Descriptors :   *ROBOTS, ALGORITHMS, POSITION(LOCATION), ROBOTICS, SYSTEMS ENGINEERING, DISTRIBUTED DATA PROCESSING, MOTION, DIRECTION FINDING, PROBLEM SOLVING, CASE STUDIES, MOBILE, COORDINATES, CONVERGENCE, HEURISTIC METHODS, SYSTEMS ANALYSIS, COMPUTER VISION, CONTROL THEORY, RANGE(DISTANCE).

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE