Graphbots: Cooperative Motion Planning in Discrete Spaces

Samir Khuller, Ehud Rivlin, and Azriel Rosenfeld.
Graphbots: cooperative motion planning in discrete spaces.
Man and Cybernetics Systems, 28(1):29--38, 1998

Online Version

A pdf version is available for download.

Abstract

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 motion-planning 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

Keywords

Co-authors

Bibtex Entry

@article{KhullerRR98a,
  title = {Graphbots: cooperative motion planning in discrete spaces},
  author = {Samir Khuller and Ehud Rivlin and Azriel Rosenfeld},
  year = {1998},
  journal = {Man and Cybernetics Systems},
  volume = {28},
  number = {1},
  pages = {29--38},
  keywords = {Graphs; Motion planning},
  abstract = {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 motion-planning 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}
}