Graphbots: Cooperative motion planning in discrete spaces

Samir Khuller*, Ehud Rivlin, Azriel Rosenfeld

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Most previous theoretical work on motion planning for a group of robots has addressed the problem of path planning for the individual robots sequentially, in geometrically simple regions of Euclidean space (e.g., a planar region containing polygonal obstacles). In this paper, we define a version of the motionplanning problem in which the robots move simultaneously. We establish conditions under which a team of robots having a particular configuration can move from any start location to any goal destination in a graph-structured space. We show that for a group of robots that maintain a fixed formation we can find the shortest path in polynomial time, and we give faster algorithms for special kinds of environments.

Original languageEnglish (US)
Pages (from-to)29-38
Number of pages10
JournalIEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
Issue number1
StatePublished - 1998


  • Graphs
  • Motion planning

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Graphbots: Cooperative motion planning in discrete spaces'. Together they form a unique fingerprint.

Cite this