DocumentCode :
414428
Title :
Exact Pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap
Author :
Chitsaz, Hamidreza ; O´Kane, Jason M. ; LaValle, Steven M.
Author_Institution :
Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA
Volume :
4
fYear :
2004
fDate :
April 26-May 1, 2004
Firstpage :
3981
Abstract :
We present an algorithm that computes the complete set of Pareto-optimal coordination strategies for two translating polygonal robots in the plane. A collision-free acyclic roadmap of piecewise-linear paths is given on which the two robots move. The robots have a maximum speed and are capable of instantly switching between any two arbitrary speeds. Each robot would like to minimize its travel time independently. The Pareto-optimal solutions are the ones for which there exist no solutions that are better for both robots. The algorithm computes exact solutions in time O(mn2 log n), in which m is the number of paths in the roadmap, n is the number of coordination space vertices. An implementation is presented.
Keywords :
Pareto optimisation; collision avoidance; minimisation; mobile robots; multi-robot systems; piecewise linear techniques; Pareto optimal coordination; acyclic roadmap; arbitrary speeds; collision avoidance; mobile robots; piecewise linear paths; polygonal robots; travel time minimisation; Computer networks; Computer science; Mobile robots; Orbital robotics; Piecewise linear techniques; Processor scheduling; Remotely operated vehicles; Road accidents; Robot kinematics; Space exploration;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Robotics and Automation, 2004. Proceedings. ICRA '04. 2004 IEEE International Conference on
ISSN :
1050-4729
Print_ISBN :
0-7803-8232-3
Type :
conf
DOI :
10.1109/ROBOT.2004.1308892
Filename :
1308892
Link To Document :
بازگشت