Path selection and coordination for multiple robots via Nash equilibria

We present a method for analyzing and selecting time-optimal coordination strategies for n robots whose configurations are constrained to lie on a C-space roadmap (which could, for instance, represent a Voronoi diagram). We consider independent objective functionals, associated with each robot, together in a game-theoretic context in which maximal Nash equilibria represent the favorable strategies. Within this framework additional criteria, such as priority or the amount of sacrifice one robot makes, can be applied to select a particular equilibrium. An algorithm that determines all of the maximal Nash equilibria for a given problem is presented along with several computed examples for two and three robots