A pattern formation algorithm for a set of autonomous distributed robots with agreement on orientation along one axis

Abstract

A set of autonomous distributed robots is a group of robots that each function independently but cooperatively. In this paper we treat the pattern formation problem for a set of autonomous distributed robots. The pattern formation problem involves having a set of robots take up a certain pattern (a formation) given that their initial states place them in arbitrary locations. The robots used in this research function in an asynchronous manner iterating through a cycle of four modes of behavior: wait, observe, compute, and move. The robots cannot record information relating to the previous cycle (the results of observations or computations). In addition, the robots cannot be distinguished by their external appearance and all of the robots execute the same algorithm. In Ref. 1 it was shown that a pattern formation algorithm could be constructed for an odd number of robots with agreement on one axis if an observational constraint assumption was fulfilled. In this paper we show that a pattern formation algorithm can be constructed even when this observational constraint assumption does not hold. © 2006 Wiley Periodicals, Inc. Syst Comp Jpn, 37(10): 89–100, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20331