Nonlinear receding-horizon differential game for drone racing along a three-dimensional path

In this section, we consider a quadrotor-type drone whose dynamical model is derived from reference.²⁷ The inertial frame is denoted by $(e^{i}_{1},e^{i}_{2},e^{i}_{3})$, and the body frame by $(e^{b}_{1},e^{b}_{2},e^{b}_{3})$ with origin at the drone’s center of mass, as shown in Figure 1. Attitude is parameterized by the quaternion²⁸ $q=(q_{0}\ q_{1}\ q_{2}\ q_{3})^{\rm T}\in\mathbb{R}^{4}$. The rotation matrix $Q(q)\in\mathbb{R}^{3\times 3}$ from the body frame to the inertial frame is formed as follows:

We assume that the external forces acting on the drone consist only of gravity in the $e^{i}_{3}$ direction and rotor thrusts in the $e^{b}_{3}$ direction, and each rotor generates a reaction torque that is proportional to its thrust. Then, the Newton-Euler equations describing translational motion in the inertial frame and rotational motion in the body frame for the drone are expressed as follows.

where $p_{d}=(x\leavevmode\nobreak\ y\leavevmode\nobreak\ z)^{\mathrm{T}}\in\mathbb{R}^{3}$ represents the drone’s position in the inertial frame, $\omega=(\omega_{1}\leavevmode\nobreak\ \omega_{2}\leavevmode\nobreak\ \omega_{3})^{\mathrm{T}}\in\mathbb{R}^{3}$ is the angular velocity vector in the body frame, and $u_{d}=(F_{1}\leavevmode\nobreak\ F_{2}\leavevmode\nobreak\ F_{3}\leavevmode\nobreak\ F_{4})^{\mathrm{T}}\in\mathbb{R}^{4}$ is the vector of rotor thrusts. Symbols $m$ and $J\in\mathbb{R}^{3\times 3}$ are the mass and inertia matrix of the drone, respectively, $Q_{3}(q)$ denotes the third column of $Q(q)$, $e_{a}=(1\ 1\ 1\ 1)^{\mathrm{T}}$, and $T\in\mathbb{R}^{3\times 4}$ is a matrix

with $l$ the distance from the center of mass to each rotor, and $k$ the proportion constant relating thrust to reaction toque. The time derivative of the quaternion $\dot{q}$ is given by

where $\varOmega(\omega)\in\mathbb{R}^{4\times 4}$ is the following skew-symmetric matrix

We now define the 13-dimensional state vector $x_{d}=(p_{d}^{\textrm{T}}\ \dot{p}_{d}^{\textrm{T}}\ \omega^{\textrm{T}}\ q^{\textrm{T}})^{\textrm{T}}$. Combining Eqs. (2) and (4), the state equation for the drone is given as follows:

Subsequently, in this section, we analyze the relationship between the drone’s position and the path it should follow. By formulating the dynamics of a projection point and its associated arc length, we establish a foundation for efficient path-following control. We assume that the path is given as a curve parameterized by a path parameter $\theta$ over an interval $\Theta\subset\mathbb{R}$. That is, the path is represented as the image $r(\Theta)\subset\mathbb{R}^{3}$ of a mapping $r:\Theta\to\mathbb{R}^{3}$. We assume $r$ is twice differentiable and the tangent vector $dr(\theta)/d\theta$ does not vanish for any $\theta\in\Theta$, which guarantees that $r(\theta)$ does not move backwards when $\theta$ increases. However, we do not assume that the mapping $r$ is one-to-one globally, allowing the path to go through a point multiple times. The path parameter $\theta$ is not necessarily the arc length of the path, which allows us to have explicit representations of various paths.

We define the distance $d(p_{d})$ from the drone’s position $p_{d}\in\mathbb{R}^{3}$ to the path $r(\Theta)$ by the minimum distance as

If this infimum is attained at $\theta_{d}$ in the interior of $\Theta$, then the stationary condition

holds. For $\theta_{d}$ satisfying (8), we call a point $p_{p}=r(\theta_{d})$ a projection point of $p_{d}$ because (8) implies that $p_{p}$ is an orthogonal projection of $p_{d}$ onto the path, as shown in Figure 2. We also define the signed arc length $s(\theta_{0},\theta_{1})$ from $r(\theta_{0})$ to $r(\theta_{1})$ along the path as

for $\theta_{0},\theta_{1}\in\Theta$, which is negative when $\theta_{1}<\theta_{0}$. If the trajectory $p_{d}(t)$ of the drone is differentiable in time $t\in[0,t_{f}]$ $(t_{f}>0)$, we can derive ordinary differential equations for $\theta_{d}(t)$ and the corresponding arc length $\sigma(t)=s(\theta_{d}(0),\theta_{d}(t))$.

To incorporate path-following dynamics into the drone’s control framework, we augment the state vector $x_{d}$ of the drone with the path parameter $\theta_{d}$ and the arc length $\sigma$. This extension enables seamless integration of path-following errors into the control design without requiring additional optimization steps. Specifically, since the right-hand sides of the differential equations Eqs. (10) and (12) depend on $\theta_{d}(t)$, $p_{d}(t)$, and $\dot{p}_{d}(t)$, we can integrate them into the state equation of the drone. Subsequently, by augmenting the state vector as $\bar{x}_{d}=(p_{d}^{\textrm{T}}\ \dot{p}_{d}^{\textrm{T}}\ \omega^{\textrm{T}}\ q^{\textrm{T}}\ \theta_{d}\ \sigma)^{\textrm{T}}\in\mathbb{R}^{15}$, we obtain the augmented state equation for path following as follows:

Equation (14) defines the augmented state equation for the drone, including the dynamics of the projection point ($\theta_{d}$) and the associated arc length ($\sigma$). The additional terms allow the control system to directly account for path-following errors in real-time decision-making.

In this section, we first review NMPC, a widely used real-time optimization-based control approach for nonlinear systems, in a continuous-time setting.³⁰ We consider a dynamical system

where $x_{M}(t)$ is the state and $u(t)$ is the control input. To determine the control input $u(t)$ at each time instant, NMPC solves a finite-horizon optimal control problem (OCP) to minimize the following objective function with a receding horizon $[t,t+T]$ $(T>0)$.

where $x_{M}(\tau)$ and $u(\tau)$ $(t\leq\tau\leq t+T)$ represent the predicted state and control input over the horizon, respectively. They may not necessarily coincide with the actual system’s state and control input in the future.

At each time $t$, the initial value of the optimal control input minimizing the objective function (16) over the horizon $[t,t+T]$ is used as the actual control input for that time. Subsequently, NMPC defines a state feedback control law because the control input $u(t)$ depends on the current state $x_{M}(t)$ of the system that is used as the initial state in the OCP over $[t,t+T]$. NMPC can handle various control problems if the OCP is solved numerically in real time. However, it cannot handle multi-agent interactions in competitive scenarios such as drone racing. This limitation arises from the need to predict the opponent’s behavior, which is inherently uncertain. Therefore, NMPC requires simplifying assumptions about the opponent’s future trajectory, reducing its effectiveness in adversarial environments.

To explicitly model an adversarial opponent, we employ NRHDG, an extension of NMPC incorporating a differential game problem (DGP).³¹ In what follows, we limit our discussion to a two-player zero-sum DGP, where one player’s gain is exactly the other player’s loss, making it a suitable model for competitive scenarios. We consider a dynamical system described by a state equation

where $x_{D}(t)$ is the combined state of two players, $u(t)$ is the strategy (control input) for player $U$, and $v(t)$ is the strategy for player $V$. One player $U$ aims to minimize some objective function, while the other $V$ aims to maximize it. We assume that both players know the current state of the game and the state equation governing the game.

In NRHDG, we consider an objective function with a receding horizon as follows:

which models the zero-sum nature of the game. If there exists a pair of strategies $(u^{0},v^{0})$ such that

holds for any strategies $u$ and $v$, $(u^{0},v^{0})$ is called a saddle-point solution. The saddle-point solution $(u^{0},v^{0})$ ensures that both players adopt optimal strategies, balancing minimization by player $U$ and maximization by player $V$. In particular, the player $U$ can achieve a lower value of the objective function if $V$ chooses a different strategy from $v^{0}$. Therefore, $U$ can use the initial value of a saddle-point solution $u^{0}$ for the DGP as the actual input to the system regardless of the control input of $V$, which also defines a state feedback control law for $U$. This property makes NRHDG suitable for dynamic problems in competitive scenarios such as drone racing. Although the necessary conditions for a saddle-point solution of a DGP are identical to the stationary conditions for an OCP,³¹ numerical solution methods for NMPC are not necessarily applicable to NRHDG if they are tailored for minimization, for instance, involving line searches. However, there are some methods that are applicable to both NMPC and NRHDG.^{6, 32, 33}

This section describes the construction of the objective functions for NMPC and NRHDG that balance the following two key racing objectives.

1. 1.

   Path following: Ensure that the drone progresses efficiently along the predefined three-dimensional path, minimizing deviations while allowing flexibility for dynamic maneuvers. This flexibility avoids strict convergence to the path, which can hinder competitive behaviors such as overtaking or obstructing.

2. 2.

   Overtaking and obstructing: Enable the ego drone to dynamically switch between overtaking a preceding opponent and obstructing a following opponent, depending on the race scenario. These behaviors are achieved while ensuring collision avoidance and maintaining competitive efficiency.

We first design an objective function for NMPC to achieve the above objectives. Subsequently, we modify it to define an objective function for NRHDG.

In NRHDG, the ego drone minimizes an objective function (18) while assuming that the opponent maximizes the same objective function. Furthermore, the ego drone assumes that the opponent is also governed by the same augmented state equation (14). Unlike NMPC, which assumes a fixed prediction model for the opponent, NRHDG explicitly models the opponent’s strategy as a dynamic, adversarial behavior. By incorporating a zero-sum game framework, NRHDG enables the ego drone to optimize its performance against the opponent that actively counters its actions. We denote the state vector and the input vector of the opponent by $\bar{x}_{op}$ and $u_{op}$, respectively, which consist of the opponent’s variables corresponding to those of $\bar{x}_{d}$ and $u_{d}$. We also denote the state vector of the entire system as $x_{D}=(\bar{x}_{d}^{\textrm{T}}\ \bar{x}_{op}^{\textrm{T}})^{\textrm{T}}$. We now define the stage cost and the terminal cost for NRHDG as

The stage cost $L_{D}$ in (27) includes terms for both the ego drone and the opponent, reflecting the adversarial nature of the interaction. The terminal cost $\varphi_{D}$ in (28) evaluates the terminal state of the game, ensuring that each drone’s strategy aligns with the race objectives. These costs create a zero-sum strategic behaviors where the ego drone minimizes its cost while maximizing the opponent’s. At each time $t$, the ego drone determines its control input $u_{d}$ by solving the NRHDG problem subject to the 30-dimensional state equation for $x_{D}$.

This section assesses the effectiveness of the proposed NRHDG compared to the baseline NMPC in competitive drone racing scenarios. We focus on the following two key aspects.

1. 1.

   Overtaking performance: The ability of the following drone to maximize its progress while overtaking the preceding drone.

2. 2.

   Obstructing performance: The ability of the preceding drone to minimize the following drone’s progress while being overtaken.

These metrics reflect both offensive (overtaking) and defensive (obstructing) capabilities of the controllers in adversarial races. For notation, we label NMPC as controller $M$ and NRHDG as controller $D$. In a race denoted by $\text{Race}(B,A)$, the drone using controller $B$ starts ahead, while the drone using controller $A$ starts behind.

To evaluate the overtaking performance, we compare each pair of two races, $\text{Race}(A,M)$ and $\text{Race}(A,D)$, for $A\in\{M,D\}$. This means that we set the leading controller to be the same in both races and compare the progress of the drone starting from the rear position. To compare controllers fairly, the race settings, such as the initial lead and weight coefficients in the objective functions, are set to be the same between both races. Moreover, the race settings are chosen so that the controller starting from the rear position eventually overtakes the opponent starting ahead in all races, which enables us to make a quantitative comparison between different controllers in different races. The controller achieving more progress while overtaking against the same controller $A$ has better overtaking performance. Here, we measure the progress of a drone by its path parameter and define a symbol, $\text{Prog}_{\text{rear}}(B,A)$, to represent the progress of controller $A$ at a certain time in $\text{Race}(B,A)$. A larger value of $\text{Prog}_{\text{rear}}(B,A)$ indicates better overtaking performance by the rear-position drone (controller $A$). That is, if the relationship $\text{Prog}_{\text{rear}}(B,A_{1})>\text{Prog}_{\text{rear}}(B,A_{2})$ holds most of the time in both races, $A_{1}$ makes its progress more effectively than $A_{2}$ and has better overtaking performance than $A_{2}$. Since NRHDG (controller $D$) explicitly models the opponent’s behavior and optimizes against the worst-case scenarios, it will outperform NMPC (controller $M$). Therefore, we can expect NRHDG to have better overtaking performance than NMPC as follows.

which means NRHDG (controller $D$) achieves more progress than NMPC (controller $M$) when overtaking the same controller $A$.

A similar discussion can be made for obstructing performance. To evaluate obstructing performance, we compare each pair of two races, $\text{Race}(M,A)$ and $\text{Race}(D,A)$ for $A\in\{M,D\}$. This implies that we set the controller starting from the rear position to the same in two races and observe the difference between the two races. Specifically, the controller that more effectively slows the progress of the rear-position drone $A$ has better obstructing performance. Therefore, a lower value of $\text{Prog}_{\text{rear}}(B,A)$ indicates better obstructing performance of the front-position drone (controller $B$). That is, if the relationship $\text{Prog}_{\text{rear}}(B_{1},A)<\text{Prog}_{\text{rear}}(B_{2},A)$ holds most of the time in the two races, $B_{1}$ obstructs the progress of $A$ more effectively than $B_{2}$ and has better obstructing performance than $B_{2}$. Therefore, the following relationship should hold between NRHDG (controller $D$) and NMPC (controller $M$).

which means NRHDG obstructs the progress of controller $A$ better than NMPC.

Subsequently, the relationships in (29) and (30) imply

where the first and second inequalities in (31) are obtained from (29) and (30), respectively, with $A=D$, and those in (32) are obtained from (30) and (29), respectively, with $A=M$. Finally, (31) and (32) imply

If the relationships in (29) and (30) or (31)–(33) hold in numerical simulations, NRHDG is more suitable for drone racing than NMPC.

We simulate races on a three-dimensional path

depicted in Figure 6. This path tests the controllers’ ability to handle complex three-dimensional environments with varying curvature and torsion. The sinusoidal path includes sharp turns and gradual slopes, challenging the drones’ path-following and maneuvering capabilities. The rear drone starts at $r(0)$, and the front drone starts at $r(1)$. The physical parameters of the drones in the simulation are shown in Table 1, which are based on the Parrot MamboFly platform.³⁴ The weight coefficients and constants in the objective functions of NMPC and NRHDG are shown in Table 2. We assigned different input weights to represent a speed advantage for the rear drone ($b=20$) and a slower response for the front drone ($b=40$).

We implemented NRHDG and NMPC with a continuation-based real-time optimization algorithm, C/GMRES,³⁵ and its automatic code generation tool, AutoGenU for Jupyter.^36†††https://ohtsukalab.github.io/autogenu-jupyter The C/GMRES finds a stationary solution to an optimal control problem without any line searches and is also applicable directly to NRHDG problems. AutoGenU for Jupyter generates C++ code and a Python package for updating the solution with C/GMRES. Then, those codes for NRHDG and NMPC can be used together for simulation of drone racing. We conducted numerical simulations on a PC (CPU: Core i9-12900 2.4 GHz, RAM: 16 GB, OS: Ubuntu 22.04.2 LTS on WSL2, hosted by Windows 11 Pro) to demonstrate the feasibility of real-time implementation. The simulation ran for 20 s, with a horizon length $T$ of 0.4 s and a control cycle of 1 ms. The average computation times per update were 0.8 ms for NRHDG and 0.5 ms for NMPC, both of which are within the control cycle.