Multi-agent sensitivity enhanced iterative best response: A real-time game theoretic planner for drone racing in 3D environments

This paper presents a real-time game theoretic motion planning approach that enables an autonomous drone to race competitively against an arbitrary number of opponent drones along a 2D or 3D racecourse. Our method computes an approximate Nash equilibrium in the space of robot trajectories to maximally advance the ego robot while taking into account the opponents' intentions and responses. The core of our solution is a sensitivity enhanced iterative best response algorithm that the ego robot uses to repeatedly plan its own trajectory and infer opponents' trajectories, ultimately seeking a Nash equilibrium in the joint space of trajectories for all the drones. The algorithm includes a term that allows the ego vehicle to gain advantage by exploiting the influence of the ego drone's trajectory on the adversaries' objectives through the shared collision avoidance constraints among the vehicles. We also propose two methods for accelerating this computationally intensive iterative algorithm using (i) parallel computing with multiple CPU cores, and (ii) a neural network model that learns to predict trajectories close to the Nash equilibrium through offline training examples. Extensive simulation studies are conducted to benchmark the performance of our game theoretic planner and the statistical results show that our approach largely outperforms a baseline model predictive control algorithm that does not account for the opponents' reactions. Hardware experiments with 4 quadrotor robots on a 3D racecourse are performed to show the applicability of our method in real-time robotic systems. (C) 2020 Elsevier B.V. All rights reserved.