Graphbots: Cooperative Motion Planning in Discrete Spaces
.
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}
}