Factorization of Multi-Agent Planning, from Sampling-based Methods to Dynamic Games

Modern robotics often entails multiple embodied agents operating in a shared environ- ment. But making optimal decisions in such cases results to be much harder than the single-agent counterpart, often the complexity grows almost exponentially in the num- ber of agents. In this talk I’ll present the idea of factorization and its application to sampling based multi-agent motion planning and to dynamic games. The idea of factor- ization hinges on the observation that from certain states onward, the solutions of different (sub)groups of players can be computed independently. Importantly this does not require the players to be “fully decoupled”. We first instantiate this concept for multi-agent sampling-based algorithms requiring only minimal changes to state-of-the-art algorithms. As we are able to decouple (i.e., factorize) different subsets of agents to independent lower dimensional search spaces we incrementally build a lean hypergraph which preserves com- pleteness and convergence properties of the original algorithm while, at its best, allowing to curb the growth in dimensionality of the search space from exponential to linear in the number of agents. Similarly, the same concepts can be applied also to dynamic games, allowing to compute equilibria for cases which become quickly intractable otherwise. To this end, we validate our findings in realistic autonomous driving scenarios showing that already for a 4-player intersection we have a reduction of game nodes and solving time close to 99%.