Multi-Robot Coordination in an Adversarial Graph-Traversal Game

Abstract

This paper studies coordinated behaviors which arise when a team of robots must traverse hazardous environments in the presence of an adversary. We formulate the scenario as a novel non-cooperative stochastic game in which the "blue" team of robots moves in an environment modeled by a time-varying graph, attempting to reach some goal with minimum cost, while the "red" player controls how the graph changes to maximize the cost. In addition to a numerical method to compute the Nash equilibrium, we also present novel theoretical analysis on security strategies that provides performance bounds in a more computationally efficient way. Through numerical simulations, we demonstrate the emergence of beneficial coordinated behavior, where the robots split up and/or synchronize to traverse risky edges.