DocumentCode :
1340283
Title :
Graphbots: cooperative motion planning in discrete spaces
Author :
Khuller, Samir ; Rivlin, Ehud ; Rosenfeld, Azriel
Author_Institution :
Dept. of Comput. Sci., Maryland Univ., College Park, MD, USA
Volume :
28
Issue :
1
fYear :
1998
fDate :
2/1/1998 12:00:00 AM
Firstpage :
29
Lastpage :
38
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 :
computational complexity; cooperative systems; graph theory; mobile robots; path planning; Euclidean space; cooperative motion planning; discrete spaces; geometrically simple regions; graph-structured space; graphbots; path planning; polynomial-time algorithm; robot team configuration; shortest path; simultaneous motion; Computer science; Motion planning; Navigation; Orbital robotics; Path planning; Polynomials; Robotics and automation; Robots; Robustness; Topology;
fLanguage :
English
Journal_Title :
Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on
Publisher :
ieee
ISSN :
1094-6977
Type :
jour
DOI :
10.1109/5326.661088
Filename :
661088
Link To Document :
بازگشت