Pattern generation in cellular robotic systems

A computational model of cellular robotic systems (CRSs) is introduced. It employs a large (but finite) number of autonomous robots operating on a cellular space under distributed control. No synchronous clock or shared memory is assumed. Robots in such systems have to cooperate to accomplish prespecified global tasks under the government of a protocol. The problem of robots in a CRS spatially rearranging themselves to form desired patterns within the field of operation is discussed. Example protocols that generate alternating and arbitrarily predefined patterns in one-dimensional linear arrangements and protocols that make robots seal one side or all sides of two-dimensional grids are presented. Mathematical proofs of the correctness of these protocols have been obtained. A Sun-Unix based simulation platform has been implemented upon which the pattern forming protocols are exercised