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

Michael De Denus*, John Anderson, Jacky Baltes

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationRoboCup 2009
Subtitle of host publicationRobot Soccer World Cup XIII
Number of pages12
Publication statusPublished - 2010
Externally publishedYes
Event13th RoboCup International Symposium 2009 - Graz, Austria
Duration: 2009 Jun 292009 Jul 5

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5949 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th RoboCup International Symposium 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Heuristic formation control in multi-robot systems using local communication and limited identification'. Together they form a unique fingerprint.

Cite this