Optimal motion planning for multiple robots having independent goals

This work makes two contributions to geometric motion planning for multiple robots: 1) motion plans are computed that simultaneously optimize an independent performance measure for each robot; 2) a general spectrum is defined between decoupled and centralized planning, in which we introduce coordination along independent roadmaps. By considering independent performance measures, we introduce a form of optimality that is consistent with concepts from multiobjective optimization and game theory literature. Previous multiple-robot motion planning approaches that consider optimality combine individual performance measures into a scalar criterion. As a result, these methods can fail to find many potentially useful motion plans. We present implemented, multiple-robot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: 1) coordination along fixed, independent paths; 2) coordination along independent roadmaps; 3) general, unconstrained motion planning. Computed examples are presented for all three problem classes that illustrate the concepts and algorithms.