We propose an online 3-D planning algorithm for a drone to race competitively against a single adversary drone. The algorithm computes an approximation of the Nash equilibrium in the joint space of trajectories of the two drones at each time step, and proceeds in a receding horizon fashion. The algorithm uses a novel sensitivity term, within an iterative best response computational scheme, to approximate the amount by which the adversary will yield to the ego drone to avoid a collision. This leads to racing trajectories that are more competitive than without the sensitivity term. We prove that the fixed point of this sensitivity enhanced iterative best response satisfies the first-order optimality conditions of a Nash equilibrium. We present results of a simulation study of races with 2-D and 3-D race courses, showing that our game theoretic planner significantly out-performs a Model Predictive Control (MPC) racing algorithm. We also present results of multiple drone racing experiments on a 3-D track in which drones sense each others' relative position with on-board vision. The proposed game theoretic planner again out-performs the MPC opponent in these experiments where drones reach speeds up to 1.25m/s
To be successful in multi-player drone racing, a player must not only follow the race track in an optimal way, but also avoid collisions with the opponents. Since unveiling one's own strategy to the adversaries in not desirable, this requires each player to independently predict the other players future actions. Nash equilibria are a powerful tool to model this and similar multi-agent coordination problems in which the absence of communication impedes full coordination between the agents. In this project, we propose a novel receding horizon planning algorithm that, exploiting sensitivity analysis within an iterated best response computational scheme, can approximate Nash equilibria in real time. The planner only requires the players positions which can be obtained by exploiting onboard GPS (for the ego robot) and a vision-based estimation algorithm (for the opponent). Our solution effectively competes against alternative strategies in a large number of drone racing simulations and can be implemented on real hardware.
Results and videos on multiple (an arbitrary number of) robots can be viewed on the following webpage.
R. Spica, Cristofalo, E., Wang, Z., Montijano, E., and Schwager, M., “A Real-Time Game Theoretic Planner for Autonomous Two-Player Drone Racing”, IEEE Transactions on Robotics (T-RO), Accepted, May 2020
R. Spica, D. Falanga, E. Cristofalo, E. Montijano, D. Scaramuzza, and M. Schwager, "A Real-Time Game Theoretic Planner for Autonomous Two-Player Drone Racing", Robotics: Science and Systems (RSS), 2018
Z. Wang, R. Spica, and M. Schwager, "Game Theoretic Motion Planning for Multi-Robot Racing", in Proceedings of the International Symposium on Distributed Autonomous Robotics Systems (DARS), 2018