Heuristic formation control in multi-robot systems using local communication and limited identification

Groups of individuals often use formations as a means of providing orderly movement while distributing members in a manner that is advantageous to the group's activities. A particular formation may offer a defensive advantage over moving individually, for example, exposing only some of the agents to the proximity of enemies, or might increase group abilities by allowing individuals to limit perceptual focus to one small part of the environment. Formations are used throughout the natural world and in many organized human groups, and are equally valuable to multi-robot systems. Most formation control in multi-robot systems is extremely limited compared to the formations we see in nature: formations are precisely defined, and mechanisms for forming and maintaining formations often require unique labels for individuals and broadcast communication. In this paper, we explore a method for creating heuristic formations - where agents create an overall formation, but forgiveness exists for small variations in form - using only local rules for creating formations and allowing only local communication. Our approach defines relative positions in terms of a probability given the position of one's nearest neighbor, and improves on prior work by assuming that all agents do not begin knowing the unique labels of others in the group. The approach also assumes heterogeneity in sensing, in that agents may not be able to perceive the unique labels of others, and thus may require assistance from those who can. This assumptions make formations robust to the failure of individual agents, and allow previously unknown agents to join an existing formation. An evaluation of this approach is illustrated using Player/Stage, a commonly accepted simulation package for multi-robot systems, for controlled experimentation.