Potential Games on Cubic Splines for Multi-Agent Motion Planning of Autonomous Agents

We present an algorithm to solve for local Nash Equilibrium trajectories in the multi-agent motion planning problem for self-interested agents. Our method models the problem as a concurrent game where each agent's action consists of choosing a cubic spline defined by a set of waypoints. We observe that with certain kinds of cost functions, the resulting game has the structure of a potential game which is guaranteed to reach an equilibrium even when each agent myopically improves their own cost without considering the costs of other agents. Our algorithm uses simultaneous gradient descent with independent per-agent step sizes to converge to local Nash Equilibrium trajectories. We demonstrate the algorithm can scale to very long horizons through simulated experiments in the electric vertical takeoff and landing vehicles (eVTOL) domain.