Volume 24 Issue 11 - Publication Date: 1 November 2005
Computing Pareto Optimal Coordinations on Roadmaps
R. Ghrist Department of Mathematics, University of Illinois, Urbana, IL 61801, USA, J. M. O’Kane, and S. M. LaValle Department of Computer Science, University of Illinois, Urbana, IL 61801, USA
We consider the coordination of multiple robots in a common environment, each robot having its own (distinct) roadmap. Our primary contribution is a classification of and exact algorithm for computing vector-valued (or Pareto) optima for collision-free coordination. We indicate the utility of newgeometric techniques from CAT(0) geometry and give an argument that curvature bounds are the key distinguishing feature between systems for which the classification is finite and for those in which it is not.
Return to Contents