A configuration space for permutation-invariant multi-robot formations

Stephen Kloder, Sourabh Bhattacharya, Seth Hutchinson

Research output: Contribution to journalConference articlepeer-review


In this paper we describe a new representation for a configuration space for formations of robots that translate in the plane. What makes this representation unique is that it is permutation-invariant, so the relabeling of robots does not affect the configuration. Earlier methods generally either pre-assign roles for each individual robot, or rely on local planning and behaviors to build emergent behaviors. Our method first plans the formation as a set, and only afterwards determines which robot takes which role. To build our representation of this formation space, we make use of a property of complex polynomials: they are unchanged by permutations of their roots. Thus we build a characteristic polynomial whose roots are the robot locations, and use its coefficients as a representation. Mappings between work spaces and formation spaces amount to building and solving polynomials. In this paper we also perform basic path planning on this new representation, and show some practical and theoretical properties. We show that the paths generated are invariant -relative to their endpoints - with respect to linear coordinate transforms, and in most cases produce reasonable, if not linear, paths from start to finish.

Original languageEnglish (US)
Pages (from-to)2746-2751
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
Issue number3
StatePublished - 2004
EventProceedings- 2004 IEEE International Conference on Robotics and Automation - New Orleans, LA, United States
Duration: Apr 26 2004May 1 2004

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'A configuration space for permutation-invariant multi-robot formations'. Together they form a unique fingerprint.

Cite this