Ghrist, Robert; Lavalle, Steven M. Nonpositive curvature and Pareto optimal coordination of robots. (English) Zbl 1181.58013 SIAM J. Control Optim. 45, No. 5, 1697-1713 (2006). Summary: Given a collection of robots sharing a common environment, assume that each possesses a graph (a one-dimensional complex also known as a roadmap) approximating its configuration space and, furthermore, that each robot wishes to travel to a goal while optimizing elapsed time. We consider vector-valued (or Pareto) optima for collision-free coordination on the product of these roadmaps with collision-type obstacles. Such optima are by no means unique: in fact, continua of Pareto optimal coordinations are possible. We prove a finite bound on the number of optimal coordinations in the physically relevant case where all obstacles are cylindrical (i.e., defined by pairwise collisions). The proofs rely crucially on perspectives from geometric group theory and CAT(0) geometry. In particular, the finiteness bound depends on the fact that the associated coordination space is devoid of positive curvature. We also demonstrate that the finiteness bound holds for systems with moving obstacles following known trajectories. Cited in 13 Documents MSC: 58E17 Multiobjective variational problems, Pareto optimality, applications to economics, etc. 49J27 Existence theories for problems in abstract spaces 49K27 Optimality conditions for problems in abstract spaces 68T40 Artificial intelligence for robotics 70E60 Robot dynamics and control of rigid bodies Keywords:CAT(0) geometry; Pareto optimality; configuration space; nonpositive curvature PDFBibTeX XMLCite \textit{R. Ghrist} and \textit{S. M. Lavalle}, SIAM J. Control Optim. 45, No. 5, 1697--1713 (2006; Zbl 1181.58013) Full Text: DOI Link