The one dimensional random pairing problem in a cellular robotic system

A cellular robotics system which is essentially characterized by having no centralized control, no centralized database, no shared memory, and no synchronous clock is considered. Each robot in the system executes an identical internal algorithm and is equipped with limited sensing power. A typical reconfiguration problem, the pairing problem, for such an autonomous robotic system on a one-dimensional grid is studied. The global goal of the system is to self-organize into units of physically adjacent pairs separated by empty seats. The use of randomization in the decision-making process of each robot allows the evolution of the system to be modeled as a Markov chain, where each state represents a nonuniform random walk. The chain is absorbing, showing that the desired configuration will be reached with probability one