Source-linked AI summary
A Real-Time Game Theoretic Planner for Autonomous Two-Player Drone Racing
Riccardo Spica, Davide Falanga, Eric Cristofalo, Eduardo Montijano, Davide Scaramuzza, Mac Schwager
TL;DR
Multi-player drone racing requires agents to predict one another’s reactive strategies while competing without communication. The paper develops a sensitivity-aware iterated-best-response planner with vision-based opponent tracking, demonstrating real-time operation and effective simulation and hardware performance. Its main limitations are nonconvex local minima and assumptions about the opponent’s planning strategy and cost function.
Problem
Multi-player racing requires strategic interaction and prediction of reactive opponents without communication, beyond single-robot time-trial planning.
Method
The paper combines sensitivity analysis with an iterated best response algorithm for receding-horizon Nash planning and adds vision-based opponent pose estimation.
Results
The planner and estimation strategy run in real time, with performance demonstrated in extensive simulations and real-hardware experiments.
Takeaways & Limitations
The approach can model and exploit opponent reactions while producing practical online motion planning for two-player drone racing.
Takeaways & Limitations
Nonconvex optimization can converge to local minima, and assuming a similar opponent strategy can produce overly conservative trajectories.
Abstract
from arXiv · showhide
To be successful in multi-player drone racing, a player must not only follow the race track in an optimal way, but also compete with other drones through strategic blocking, faking, and opportunistic passing while avoiding collisions. Since unveiling one's own strategy to the adversaries is 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 paper, 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. We also describe a vision-based pipeline that allows each player to estimate its opponent's relative position. We demonstrate that our solution effectively competes against alternative strategies in a large number of drone racing simulations. Hardware experiments with onboard vision sensing prove the practicality of our strategy.
II. INTRODUCTION
The paper addresses multi-player drone racing, where autonomous agents must compete strategically while avoiding collisions without communicating policies. It proposes game-theoretic, receding-horizon planning with opponent modeling and evaluates the approach in simulation and hardware experiments.
- II. INTRODUCTION: Multi-player drone racing adds strategic blocking, faking, and passing to the usual navigation and control challenges.
- II. INTRODUCTION: Without communication, robots must predict other agents’ reactive behavior, including reactions induced by reciprocal collision avoidance.
- II. INTRODUCTION: The planner combines receding-horizon control, iterated best responses, and sensitivity analysis to account for opponents’ reactions.
- II. INTRODUCTION: If the algorithm converges, its output satisfies necessary Nash-equilibrium conditions, and it runs at 20Hz on standard hardware.
- II. INTRODUCTION: The approach is evaluated against alternative strategies in many simulations and in hardware experiments using two quadrotors on an indoor circular course.
D. Game theoretic control using a Nash information pattern
The paper uses a symmetric-information Nash model for noncommunicating racing agents and develops a track- and vision-based formulation for their interaction. Game theory is computationally challenging, motivating efficient heuristics for real-time robotic control.
- D. Game theoretic control using a Nash information pattern: Nash information models fit racing settings where agents have symmetric information rather than an imposed leader or information advantage.
- D. Game theoretic control using a Nash information pattern: Game-theoretic control remains limited by computational complexity, so the paper treats game theory as inspiration for efficient heuristics.
- D. Game theoretic control using a Nash information pattern: The approach models two-player drones flying at constant altitude on a parameterized track with bounded speed, track width, and inter-drone distance.
- D. Game theoretic control using a Nash information pattern: Each drone uses a calibrated monocular camera to detect a known spherical marker and estimate the opponent’s relative and world-frame position.
- D. Game theoretic control using a Nash information pattern: Because collision constraints require access to the opponent’s strategy, the race is formulated as a noncooperative zero-sum differential game.
V. GAME THEORETIC FORMULATION
The game-theoretic formulation treats each player’s strategy as constrained by its own dynamics and shared collision avoidance, then seeks Nash equilibria through best-response structure. Nonconvexity can produce multiple equilibria and makes exact online computation difficult.
- V. GAME THEORETIC FORMULATION: The continuous planning problem is discretized over a horizon with piecewise-constant control inputs.
- V. GAME THEORETIC FORMULATION: Each player’s admissible strategy depends on the opponent’s strategy through shared collision-avoidance constraints.
- V. GAME THEORETIC FORMULATION: A Nash equilibrium is characterized as a fixed point of the best-reply map, where neither player can improve unilaterally.
- V. GAME THEORETIC FORMULATION: Because collision constraints make the problem nonconvex, multiple equilibria may exist, such as left- versus right-side overtaking, and exact computation may be too costly online.
A. Numerical resolution of Nash equilibria
The planner approximates Nash equilibria through iterated best responses, enhanced by sensitivity analysis to capture how one player's strategy affects the opponent's outcome under collision constraints.
- Iterated best response alternates each player's optimization while holding the opponent's current strategy fixed.
- A fixed iteration count trades game-theoretic fidelity against computational cost, with each player independently running the procedure without communication.
- Sensitivity analysis approximates the opponent-dependent optimal value and modifies the cost function to capture strategic effects at equilibrium.
- Converged iterations satisfy the necessary conditions for a Nash equilibrium when both players have identical payoff functions.
- Active collision constraints can make obstructing the opponent beneficial, whereas inactive constraints reduce the game to independent optimal-control problems.
B. Numerical resolution of players’ optimization
Each player's nonlinear optimization is approximated through sequential convex QCLP problems, while local optimization enables online computation despite non-convex collision constraints.
- The feasible set is well posed under the system dynamics, bounded inputs, finite sampling time, and feasible initial conditions.
- The optimization problem is nonlinear and non-convex, so optimal-solution uniqueness cannot be guaranteed.
- Local optimization is used to meet online-control timing requirements, potentially sacrificing optimality because non-convexity can produce suboptimal local solutions.
- Sequential convex QCLP approximations linearize selected constraints and the sensitivity-based cost around the current strategy estimate.
- The inner optimization terminates after a maximum iteration count or when consecutive solutions differ by less than a threshold.
C. Alternative control strategies
The experiments compare the proposed controller against alternative control strategies to assess its effectiveness.
- The experiments evaluate the proposed controller by having it compete against alternative control strategies.
1) Model predictive control (MPC):
The MPC baseline predicts an opponent traveling along the track at constant maximum speed, then solves a single classical optimal-control problem.
- The MPC strategy assumes the opponent follows a straight-line trajectory at constant maximum linear velocity along the local track direction.
- Using that prediction, the controller solves the resulting problem as a single classical optimal-control problem with a locally optimal numerical solution.
2) Reciprocal velocity obstacles (RVO):
RVO is described as a collision-avoidance benchmark that follows a reference velocity while respecting track obstacles. Its velocity combines track-direction following with center-line keeping, and the robot actively maintains opponent visibility through camera yaw control.
- 2) Reciprocal velocity obstacles (RVO):: RVO uses polygonal track obstacles and a reference velocity with maximum norm to avoid collisions while following the course.The reference direction is computed from the local track geometry.
- 2) Reciprocal velocity obstacles (RVO):: The planner trades off following the local track direction against staying near the center line using a free parameter ρ.
- 2) Reciprocal velocity obstacles (RVO):: Because camera field of view is limited, each robot uses yaw to actively maintain visibility of its opponent.
- 2) Reciprocal velocity obstacles (RVO):: Aligning the camera axis with the relative bearing vector keeps the opponent centered in the image.
- 2) Reciprocal velocity obstacles (RVO):: The desired yaw angle and angular velocity are computed from planned or predicted trajectories and consecutive trajectory samples.
VI. OPPONENT POSITION ESTIMATION
The paper estimates each opponent’s relative position from onboard camera and inertial sensing, maintains that estimate with a Kalman filter, and uses it for game-theoretic planning. Simulations show that the planner can block effectively, outperform RVO, and compete with MPC, while also exposing cautious overtaking behavior in some cases.
- VI. OPPONENT POSITION ESTIMATION: Opponent state estimation fuses camera and inertial measurements, maintains a relative-state belief with a Kalman filter, and supplies its expected value to the planner.The vision pipeline segments a known colored sphere and uses calibrated camera geometry to recover its 3D position.
- A. Simulations: 900 simulations found RVO to be the least effective strategy, with robots using it losing all races regardless of initial placement or maximum-speed advantage.The authors attribute this to RVO’s reactive control, which lacks the extended planning horizon used by GTP and MPC.
- A. Simulations: GTP and MPC are identical when robots do not interact; their difference lies in how they model and respond to the opponent.
- A. Simulations: When GTP was faster than MPC, it overtook MPC in approximately 30% of races despite MPC’s advantageous starting position.The planner often overestimated MPC as another GTP player, producing overly cautious sideways motion during overtaking.
- A. Simulations: When GTP was slower, it defended its initial advantage in the vast majority of races by moving sideways to block MPC.MPC could not use the same reactive blocking strategy because it did not properly model opponent reactions.
- A. Simulations: Against RVO, GTP generally won with slightly larger average separation and a much narrower final-distance distribution, especially while defending an initial advantage.The authors associate cautious overtaking with the less pronounced improvement when GTP plays offensively.
B. Experiments
The planner was implemented on real quadrotors with onboard state estimation, opponent tracking, and continuous trajectory replanning. Hardware experiments demonstrated real-time operation, while the authors note limitations from local optimization, opponent-model assumptions, and restricted overtaking space.
- Experiments: The hardware setup fused inertial measurements with wireless motion-capture ego poses in an onboard Extended Kalman Filter.The quadrotors used PX4-based low-level control, onboard computation, and Optitrack-supported state estimation.
- Experiments: Each robot continuously replanned its own and predicted opponent trajectory while estimating the opponent through onboard vision.The experiments visualized planned trajectories, predicted opponent trajectories, and camera-based tracking results.
- Experiments: The indoor track was too narrow for overtaking, but the blue robot still planned attempted passes and anticipated sideways blocking by its opponent.Both robots were limited to 0.6 m/s, with a 0.6 m minimum separation on a square track with rounded corners.
- Experiments: The planner and vision-based estimation strategy ran in real time and were demonstrated experimentally on real hardware.The paper reports onboard tests with two quadrotors and real-time performance for both planning and estimation.
- Limitations: Local optimization can sacrifice optimality, and assuming a similarly intelligent opponent can produce overly conservative trajectories.The authors propose mixed-integer optimization and online opponent-policy learning as directions for addressing these weaknesses.
APPENDIX
The appendix develops sensitivity-based optimality calculations and connects converged iterated best responses to necessary Nash-equilibrium conditions. The derivations rely on KKT conditions and assumptions about active constraints and shared constraint structure.
- Sensitivity analysis: The appendix studies how an optimal outcome changes when a scalar parameter in the constrained optimization problem changes.It defines x*(c) as the optimizer and s*(c) as the associated optimal outcome, then analyzes their variation around c.
- Sensitivity analysis: Differentiating the KKT conditions yields the sensitivity relation used to track how the optimum changes with the parameter.The proof isolates terms from the KKT system and differentiates identities that hold for every parameter value.
- Sensitivity analysis: The sensitivity proof extends to multiple joint constraints and parameter-independent constraints, while inequality constraints require a locally unchanged active set.Active inequalities can be treated as equalities and inactive constraints ignored under that assumption.
- Nash conditions: Applying KKT conditions to the game formulation gives necessary Nash conditions when the iterative algorithm converges and the players satisfy the stated shared-constraint requirements.The appendix analyzes conditions involving active constraints and their associated multipliers for both players.
- Nash conditions: The Nash-condition derivation requires matching constraint values and compatible active-constraint sets across the two players.The appendix states equality of relevant constraint functions and common active constraints as sufficient conditions for the remaining KKT relations.
C. Proof of (18)
This proof analyzes the optimizer as a function of an opponent-related parameter and differentiates its necessary optimality condition. The resulting sensitivity argument establishes how the corresponding solution changes with that parameter.
- C. Proof of (18): The proof treats the parameter pN_i as fixed and studies how the solution s_i changes as pN_i varies.For each parameter value, the corresponding solution satisfies a necessary optimality condition.
- C. Proof of (18): Because the necessary-condition expression is zero for every pN_i, its derivative with respect to pN_i is also zero.This differentiation step provides the sensitivity relation used in the proof of (18).
- C. Proof of (18): The proof concludes by using the differentiated optimality condition to characterize how the solution responds to changes in the parameter.The argument follows the same parameter-sensitivity logic introduced for the preceding optimization problem.