Game Theoretic Controller Synthesis for Multi-Robot Motion Planning-Part II: Policy-based Algorithms

Abstract

This paper presents the problem of distributed feedback motion planning for multiple robots. The problem of feedback multi-robot motion planning is formulated as a differential non-cooperative game. We leverage the existing sampling-based algorithms and value iterations to develop an incremental policy synthesizer. The proposed algorithm makes use of an iterative best response algorithm to incrementally improve the estimate of value functions of the individual robots in the multi-robot motion-planning setting. We show the asymptotic convergence of the limiting policies induced by the proposed Feedback iNash-Policy algorithm for the underlying non-cooperative game. Furthermore, we show that the value iterations allow estimation of the cost-to-go functions for the robots without the requirement on convergence of the value functions for the sampled graph at any particular iteration.