This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in ISI Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ghrist, R. Articles by LaValle, S. M. Search for Related Content Social Bookmarking                   What's this?

Computing Pareto Optimal Coordinations on Roadmaps

Department of Mathematics, University of Illinois, Urbana, IL 61801, USA, ghrist{at}math.uiuc.edu

Jason M. O'Kane

Department of Computer Science, University of Illinois, Urbana, IL 61801, USA, jokane{at}cs.uiuc.edu

Steven M. LaValle

Department of Computer Science, University of Illinois, Urbana, IL 61801, USA, lavalle{at}cs.uiuc.edu

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 new geometric 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.

Key Words: motion planning • optimality • coordination spaces • roadmaps • multiple robots

CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?