# Spline-Based Minimum-Curvature Trajectory Optimization for Autonomous Racing

Haoru Xue1, Tianwei Yue2 and John M. Dolan1 1 Haoru Xue and John M. Dolan are
with the Robotics Institute, Carnegie Mellon University {haorux,
<EMAIL_ADDRESS>Tianwei Yue is with the Language Technologies
Institute, Carnegie Mellon University<EMAIL_ADDRESS>Codes:
https://github.com/HaoruXue/spline-trajectory-optimization

###### Abstract

We propose a novel B-spline trajectory optimization method for autonomous
racing. We consider the unavailability of sophisticated race car and race
track dynamics in early-stage autonomous motorsports development and derive
methods that work with limited dynamics data and additional conservative
constraints. We formulate a minimum-curvature optimization problem with only
the spline control points as optimization variables. We then compare the
current state-of-the-art method with our optimization result, which achieves a
similar level of optimality with a 90% reduction on the decision variable
dimension, and in addition offers mathematical smoothness guarantee and
flexible manipulation options. We concurrently reduce the problem computation
time from seconds to milliseconds for a long race track, enabling future
online adaptation of the previously offline technique.

##  I INTRODUCTION

###  I-A Offline Trajectory Optimization in Autonomous Racing

Offline trajectory optimization (OTO) is widely used in modern autonomous
racing. By leveraging sophisticated prior knowledge of the race track
(geometries, friction conditions, etc.) and knowledge of the race car (tire
model, power train, etc.), an optimization program can be run in a reasonable
time frame to achieve best lap time. The result can then significantly reduce
the online computation load in sample-based planning [14] and model predictive
control [12].

Recent advancements in high-speed autonomous racing present new challenges and
opportunities for evaluating OTO algorithms. Lack of prior race car and race
track data is a significant challenge for university-level research and racing
development. For example, although autonomous race cars in the Indy Autonomous
Challenge (IAC) have reached a top speed of over 320 km/h, the teams still
have limited access to critical data such as tire model parameters and load
transfer characteristics, especially in the earlier stages of development,
when estimation of these parameters is not viable with the limited data
gathered. Therefore, a simple trajectory optimization algorithm should account
for this data-scarce use case and support early development efforts.

OTO is often used to generate a reference safety set in the development phase
of an autonomous race car, which is often desired when the handling limit of
the vehicle is yet to be determined. Instead of directly applying an
experimental tire model as the optimization limit, it is often desired to work
with more conservative handling constraints. The traction circle (ellipse, or
diamond) is an intuitive and effective alternative to the raw tire parameters.
By controlling the maximum acceptable lateral and longitudinal acceleration in
each direction as hyper-parameters, an OTO approach can generate different
trajectories subjected to additional dynamics constraints. In addition, the
track geometry constraints can be altered to impose extra track limits, and
generate trajectories that pass through the non-optimal part of the race
track, which provides a planning and control reference when the vehicle is
forced into these regions.

###  I-B Related Work

Prior to autonomous racing, the generation of an optimal velocity profile
given a fixed trajectory was first studied in the motorsports domain. Quasi-
steady state (QSS) approaches have been developed since the 1980s
[2][3][4][13]. The full trajectory is broken down into small segments, through
which the race car is assumed to have steady-state behavior. The algorithm
starts with segments corresponding to peak curvature on the trajectory, which
are considered the "bottlenecks". The algorithm then proceeds to generate a
full velocity profile entering and exiting these bottlenecks, considering only
the neighboring vehicle states subject to the dynamic limits, until the
velocity profiles of these bottlenecks meet each other [6]. This method is
known for its robustness and fast run time, but it fails to capture transient
effects such as load transfer characteristics and damper dynamics [6]. We
adopt a similar method in our work, whose algorithm will be formally proposed
in a later section.

The optimization of the trajectory geometry in autonomous racing has been
studied in Braghin et al. and Kapania et al. with the "minimum curvature"
heuristic, which states that an optimal racing trajectory minimizes the sum of
curvatures around the track to minimize lap time [1] [11]. Heilmeier et al.
extend the idea to a quadratic programming (QP) formulation with improvements
to the curvature calculation. They also apply spline interpolation to the
noisy raw data and the final output to obtain a smooth trajectory [9]. Their
work was extensively used by the TUM team in recent high-speed autonomous
racing events such as Roborace and IAC. However, to guarantee that the
continuity of the trajectory during and after optimization is at least $C^{2}$
(continuous position, velocity, and acceleration), it is insufficient to
optimize with respect to discrete samples along the trajectory (3.0 m interval
in [9]), although spline interpolation could be applied in postprocessing.

###  I-C Goal and Scope of This Work

In our work, we propose a new optimization formulation for minimum-curvature
OTO based on B-splines that ensures the continuity of the trajectory
throughout the optimization iterations. We also consider the unavailability of
sophisticated race car and race track dynamics in early-stage autonomous
racing development, and derive methods that work with limited dynamics data
and additional conservative constraints.

We introduce the math related to the B-spline and our cost function in Section
II. We then formulate the optimization problem in Section III, and discuss the
QSS algorithm to calculate the velocity profile, which is used to evaluate the
generated trajectory. Finally, in Section IV, we compare the optimization
results with previous works.

##  II BACKGROUND

A single B-spline of order $n$ is a parametrized curve, denoted as
$B_{i,n}(x)$. It can be uniquely constructed from a series of nondescending
knot points $t_{0},t_{1},\dots,t_{N}$, subjected to

$\displaystyle\sum_{i=1}^{N-n}B_{i,n}(x)=1$ (1)

A B-spline has non-zero values only in the range of knot vectors $t_{i}<x\leq
t_{i+n}$. Higher-order B-splines can be recursively defined.

$\displaystyle B_{i,n+1}(x)$
$\displaystyle=w_{i,n}(x)B_{i,n}(x)+(1-w_{i+1,n}(x))B_{i+1,n}(x)$
$\displaystyle\text{where }w_{i,k}(x)$
$\displaystyle=\begin{cases}\frac{x-t_{i}}{t_{i+k}-t_{i}},&t_{i+k}\neq
t_{i}\\\ 0,&\text{otherwise}\end{cases}$ (2)

The resulting basis functions are $C^{n-2}$ continuous and overlap throughout
the knot sequence, which is visualized in fig. 1.

Figure 1: Visualization of basis functions $B_{i,n}(x)$ of order 2 to 5 [10]

These basis functions allow us to define a spline on $t_{0},t_{N}$ that is a
linear combination of the basis functions:

$\displaystyle T_{n}(x)=\sum_{i=1}^{N-n}\alpha_{i}B_{i,n}(x)$ (3)

The weights $\alpha_{0}\dots\alpha_{N-n}$ are also known as control points,
which can be visualized in fig. 2. We use $S=N-n$ to denote the number of
control points. The shape of the curve can be manipulated by moving the
control points while keeping the basis functions constant. The movement of the
control points is the main subject of interest in this work, and we aim to
derive an optimization formulation that optimizes their placement to form a
curvature-optimal trajectory for autonomous racing.

To extend the 1D B-spline to handle a trajectory in the 2D plane, we take two
sets of control points to parameterize the $x$ and $y$ coordinates separately
on the same basis functions. That is, given a trajectory
$T(t):\mathbb{R}\rightarrow\mathbb{R}^{2}$ and a sequence of control points
$\mathbf{z}=[\alpha_{1},\dots,\alpha_{S},\beta_{1},\dots,\beta_{S}]^{T}$

$\displaystyle
T(t,\mathbf{z})=(\sum_{i=1}^{S}\alpha_{i}B_{i,n}(t),\sum_{i=1}^{S}\beta_{i}B_{i,n}(t))$
(4)

where $\alpha_{i},\beta_{i}$ respectively denote the $x$ and $y$ coordinates
of the control point. Conventionally, we use $t\in[0.0,1.0]$ to parameterize
the trajectory and denote progress along the track. We can also denote the two
resulting 1D B-splines as $T_{x}(t.\mathbf{z}),T_{y}(t,\mathbf{z})$.

Since we will be optimizing with respect to the control points, it is useful
to take the derivative of a spline with respect to the control points, which
is simply the corresponding basis function.

$\displaystyle\frac{\partial
T(t,\mathbf{z})}{\partial\alpha_{i}}=\frac{\partial
T(t,\mathbf{z})}{\partial\beta_{i}}=B_{i,n}(t)$ (5)

The curvature of a B-spline trajectory, as of any parametric curve equation,
can be calculated as [9]

$\displaystyle
k(t)=\frac{T_{x}^{\prime}(t)T_{y}^{\prime\prime}(t)-T_{y}^{\prime}(t)T_{x}^{\prime\prime}(t)}{(T_{x}^{\prime}(t)^{2}+T_{y}^{\prime}(t)^{2})^{\frac{3}{2}}}$
(6)

B-Splines have certain advantageous properties for trajectory optimization
problems with respect to the control point movements. First, each control
point can manipulate a piece of segment holistically. Intuitively, given the
same knots $t_{0}\dots t_{n}$, a control point has a longer influence range
along the curve as the degree of the B-spline increases. Visually in Fig. 1,
the basis function corresponding to that control point spans more intervals of
knots. Second, since the basis function is evaluated to zero outside of its
intervals according to (II), we can perform partial optimizations to a
specific section of the trajectory without affecting the others. Lastly, the
resulting trajectory from the control point movements is guaranteed to have
the same order of continuity as the original trajectory since it is still a
B-spline of the same order.

These features of B-splines make them suitable for autonomous racing
applications. For a vehicle to have continuous velocity and acceleration
profiles, the trajectory should be at least $C^{2}$ continuous, subject to
additional curvature constraints since vehicle kinematics is not
omnidirectional. To optimize the vehicle’s trajectory through a specific
segment of the race track, we can control the scope of the optimization by
controlling the number of control points to be included in the optimization
problem, and obtain results that are perhaps more locally optimized for a
particular turn, or more globally optimized through a combination of turns.

##  III METHOD

###  III-A Generating and Evaluating a Spline Trajectory

As an example, in this work we will use the Monza Circuit, which is a 5.8 km
(3.6 mile) long race track used in the Indy Autonomous Challenge. It has a
combination of long straights, high-speed turns, and chicanes. We will also
show experiments on an other race track in a later section.

We obtain the race track geometries from satellite images and geographical
surveys. We represent the track using a reference center line, with left and
right offsets to denote the distances to the track boundaries at every
waypoint. We then draw a cubic B-spline interpolation of the reference center
line using the least square periodic spline interpolation algorithm discussed
in [7], which forms a closed-loop spline on $t\in[0.0,1.0]$.

Figure 2: Turn 1 and 2 of Monza Circuit after interpolation

We then discretize the trajectory by taking waypoints at a constant 3-meter
interval. This is done by performing a numerical integration to calculate the
length of the trajectory:

$\displaystyle
L(t_{\min},t_{\max})=\int_{t_{\min}}^{t_{\max}}{T_{x}^{\prime}(t)^{2}+T_{y}^{\prime}(t)^{2}dt}$
(7)

and solving a subsequent root-finding problem to find $t_{i}$ such that the
trajectory advances by 3 $\mathrm{m}$.

$\displaystyle t_{i}=\operatorname*{argmin}_{t_{i}}\quad{L(t_{i-1},t_{i})-3}$
(8)

We note that the optimization is done on the continuous spline, and these
discretization points are simply used for sampling the curvature throughout
the trajectory. The discrete trajectory is also useful in the evaluation
process to be described below.

###  III-B Configuring the Vehicle Parameters

As the main constraint on vehicle dynamics, we use a traction ellipse, which
considers the longitudinal and lateral accelerations of the vehicle when
accelerating, braking and cornering, or a combination of them. To characterize
the shape of the ellipse, four parameters are used, which correspond to the
maximum longitudinal acceleration, longitudinal deceleration, and left and
right lateral accelerations. For the purpose of autonomous racing development,
these parameters are easily adjustable to impose additional safety constraints
within tire limits. For race cars with asymmetrical setups, such as those
racing on an oval racing circuit, the left and right lateral accelerations can
be adjusted separately. In our example, shown in Fig. 3, we impose a maximum
acceleration of 10 $\mathrm{m}\text{\,}{\mathrm{s}}^{-2}$, deceleration of -20
$\mathrm{m}\text{\,}{\mathrm{s}}^{-2}$, and symmetric maximum cornering load
of $\pm 15$ $\mathrm{m}\text{\,}{\mathrm{s}}^{-2}$.

Figure 3: Geometry of traction ellipse used as constraint (blue), and actual
tire constraints (red, simulated)

###  III-C Simulating a Spline Trajectory

We perform a simulation for the best lap time on the spline trajectory to
obtain the velocity profile, which will be used in the evaluation. The QSS
algorithm starts by examining the curvature profile of the discretized
trajectory and using the minimum-curvature points as constraints for this
simulation. The relationship between the vehicle’s tangential velocity $v$ and
curvature $k$ satisfies

$\displaystyle v=\sqrt{a_{lat}/k}$ (9)

where $a_{lat}$ is the lateral acceleration. Therefore, to maximize vehicle
velocity through the bottleneck, the vehicle should have zero longitudinal
acceleration to maximize lateral acceleration according to the traction
ellipse.

After obtaining this initial condition, the algorithm proceeds to generate an
entry and exit velocity profile around the bottleneck points, until the two
profiles of two bottlenecks converge. The trajectory is then further adjusted
to ensure a smooth acceleration and velocity transition at the meeting points.
Fig. 4 shows a baseline simulation done on the reference center line
trajectory, with a heatmap indicating the velocity levels that the vehicle can
achieve in various sections of the track.

Figure 4: Example simulation on the center line trajectory. The heatmap shows
the velocity levels (m/s) at individual track sections.

###  III-D Spline-Based Minimum Curvature Problem

Building on [1] and [9], we consider the minimum-curvature optimization
problem with respect to all control point coordinates $\mathbf{z}$.

$\displaystyle\min_{\mathbf{z}}\quad\sum_{j=1}^{M}k_{j}^{2}(t)$ (10)

where $k_{1}\dots k_{M}$ are the curvatures of the discretization points
within the span of the corresponding basis function of $\mathbf{z}$. The
difference from the previous work in the formulation is the optimization
variable, which is the lateral movements of individual discretization points
in the previous work, but is replaced with the control point placements in our
work. This reduces the dimension of the decision variable from $M$, the number
of discretization points, to $2S$, twice the number of control points. For
Monza Circuit with 3-meter interval discretization, the dimension reduces from
1932 to 204.

We then substitute (6) into (10) and omit the constant terms in the problem.
Discarding the $(t,\mathbf{z})$ notation in $T(t,\mathbf{z})$ for simplicity,
we arrive at a similar QP formulation to that in Heilmeier et al. [9]:

$\displaystyle\min_{z}\quad T_{x}^{\prime\prime
T}P_{xx}T_{x}^{\prime\prime}+T_{y}^{\prime\prime
T}P_{xy}T_{x}^{\prime\prime}+T_{y}^{\prime\prime T}P_{yy}T_{y}^{\prime\prime}$
(11)

where

$\displaystyle P_{xx}$ $\displaystyle=\begin{bmatrix}\frac{(T_{y_{1}})^{\prime
2}v_{1}}{((T_{x_{1}})^{\prime 2}+(T_{y_{1}})^{\prime 2})^{3}}&0&\cdots&0\\\
0&\ddots&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\frac{(T_{y_{M}})^{\prime 2}v_{M}}{((T_{x_{M}})^{\prime
2}+(T_{y_{M}})^{\prime 2})^{3}}\end{bmatrix}$

$\displaystyle P_{xy}$
$\displaystyle=\begin{bmatrix}\frac{-2(T_{x_{1}})^{\prime}(T_{y_{1}})^{\prime}v_{1}}{((T_{x_{1}})^{\prime
2}+(T_{y_{1}})^{\prime 2})^{3}}&0&\cdots&0\\\ 0&\ddots&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\frac{-2(T_{x_{M}})^{\prime}(T_{y_{M}})^{\prime}v_{M}}{((T_{x_{M}})^{\prime
2}+(T_{y_{M}})^{\prime 2})^{3}}\end{bmatrix}$ $\displaystyle P_{yy}$
$\displaystyle=\begin{bmatrix}\frac{(T_{x_{1}})^{\prime
2}v_{1}}{((T_{x_{1}})^{\prime 2}+(T_{y_{1}})^{\prime 2})^{3}}&0&\cdots&0\\\
0&\ddots&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\frac{(T_{x_{M}})^{\prime 2}v_{M}}{((T_{x_{M}})^{\prime
2}+(T_{y_{M}})^{\prime 2})^{3}}\end{bmatrix}$

We now need to correlate $T_{x}^{\prime\prime}$ and $T_{y}^{\prime\prime}$
with the location of the $j$-th control point
$z_{j}=\begin{bmatrix}\alpha_{j}&\beta_{j}\end{bmatrix}^{T}$ through the
second-order derivative of the underlying B-spline basis. These lower-order
bases also have a recursive closed-form solution and can be treated as
constants [5].

$\displaystyle T_{x}^{\prime\prime}$
$\displaystyle=\sum_{i=1}^{j-1}\frac{d^{2}B_{i,n}(t)}{dt^{2}}x_{i}+\frac{d^{2}B_{j,n}(t)}{dt^{2}}x_{j}+\sum_{i=j+1}^{S}\frac{d^{2}B_{i,n}(t)}{dt^{2}}x_{i}$
$\displaystyle:=F_{x}+\frac{d^{2}B_{j,n}(t)}{dt^{2}}x_{j}$ (12a)
$\displaystyle T_{y}^{\prime\prime}$
$\displaystyle=\sum_{i=1}^{j-1}\frac{d^{2}B_{i,n}(t)}{dt^{2}}y_{i}+\frac{d^{2}B_{j,n}(t)}{dt^{2}}y_{j}+\sum_{i=j+1}^{S}\frac{d^{2}B_{i,n}(t)}{dt^{2}}y_{i}$
$\displaystyle:=F_{y}+\frac{d^{2}B_{j,n}(t)}{dt^{2}}y_{j}$ (12b)

This shows that the relation between $T_{x}^{\prime\prime}$ and $x_{j}$, or
$T_{y}^{\prime\prime}$ and $y_{j}$, is affine. If optimization is done with
respect to all the control points at once, then $F_{x}$ and $F_{y}$ reduces to
zero, since (12a) and (12b) now become

$\displaystyle T_{x}^{\prime\prime}$
$\displaystyle=\sum_{i=1}^{S}\frac{d^{2}B_{i,n}(t)}{dt^{2}}x_{i}$ (13a)
$\displaystyle T_{y}^{\prime\prime}$
$\displaystyle=\sum_{i=1}^{S}\frac{d^{2}B_{i,n}(t)}{dt^{2}}y_{i}$ (13b)

In which $\\{x_{0},\dots,x_{S}\\}$ and $\\{y_{0},\dots,y_{S}\\}$ are all
decision variables.

Figure 5: Optimization visualization at Monza Turn 8-10. The figure on the
left visualizes the movements of the control points which shift the center
line spline into a minimum-curvature spline. The figure on the right compares
the optimization results of ours and [9].

Substituting (13a) and (13b) into (11), we can formulate this problem as a
standard QP.

$\displaystyle\quad\min_{\mathbf{z}}\quad\frac{1}{2}\mathbf{z}^{T}Hz+g^{T}\mathbf{z}$
(14a) where $\displaystyle\vspace{-1cm}H$
$\displaystyle=B_{x}^{T}P_{xx}B_{x}+B_{y}^{T}P_{xy}B_{x}+B_{y}^{T}P_{yy}B_{y}$
(14b) $\displaystyle g$
$\displaystyle=(F_{x}^{T}P_{xx}B_{x}+F_{y}^{T}P_{xy}B_{y}+F_{y}^{T}P_{yy}B_{y})+$
$\displaystyle\quad(B_{x}^{T}P_{xx}F_{x}+B_{y}^{T}P_{xy}F_{x}+B_{y}^{T}P_{yy}F_{y})^{T}$
(14c) and where $\displaystyle B_{x}$
$\displaystyle=\begin{bmatrix}\mathbf{B}_{2}&\mathbf{0}^{M\times
S}\end{bmatrix}^{T}$ (14d) $\displaystyle B_{y}$
$\displaystyle=\begin{bmatrix}\mathbf{0}^{M\times
S}&\mathbf{B}_{2}\end{bmatrix}^{T}$ (14e) $\displaystyle\mathbf{B}_{2}$
$\displaystyle=\begin{bmatrix}\frac{d^{2}B_{1,n}}{dt^{2}}(t_{1})&\cdots&\frac{d^{2}B_{S,n}}{dt^{2}}(t_{1})\\\
\vdots&\ddots&\vdots\\\
\frac{d^{2}B_{1,n}}{dt^{2}}(t_{M})&\cdots&\frac{d^{2}B_{S,n}}{dt^{2}}(t_{M})\end{bmatrix}$
(14f)

Note that (14c) is evaluated to zero when considering all the control points
since $F_{x}=F_{y}=\mathbf{0}$.

Figure 6: Optimization visualization at Putnam Road Course, Indiana, USA. The
left figure shows the movement of the control points and the optimal
trajectory shape as a result. The right figure compares ours and Heilmeier et
al.’s trajectory through the chicane.

Finally, we obtain the constraints for the optimization, which is the distance
to the left and right boundaries. For the i-th discretization point, we use
$\mathbf{l}=\begin{bmatrix}l_{0}&\cdots&l_{M}\end{bmatrix}^{T}$ and
$\mathbf{r}=\begin{bmatrix}r_{0}&\cdots&r_{M}\end{bmatrix}^{T}$ to denote the
center line’s distances to the left and right boundaries. Then we use a local
frenet frame approximation to find the distance between the optimized
discretization point and the original center line. This is done by applying a
rigid body transformation to the boundary point from the fixed map frame into
the center line’s local frame.

$\displaystyle A^{2M\times 2S}$
$\displaystyle=\begin{bmatrix}\mathbf{B}&\mathbf{0^{M\times S}}\\\
\mathbf{0^{M\times S}}&\mathbf{B}\end{bmatrix}$

$\displaystyle R^{M\times 2M}$
$\displaystyle=\begin{bmatrix}\begin{matrix}\cos\theta_{1}&0&0\\\
0&\ddots&0\\\
0&0&\cos\theta_{M}\end{matrix}&\begin{matrix}\sin\theta_{1}&0&0\\\
0&\ddots&0\\\ 0&0&\sin\theta_{M}\end{matrix}&\end{bmatrix}$ where
$\displaystyle\mathbf{B}$
$\displaystyle=\begin{bmatrix}B_{1,n}(t_{1})&\cdots&B_{S,n}(t_{1})\\\
\vdots&\ddots&\vdots\\\ B_{1,n}(t_{M})&\cdots&B_{S,n}(t_{M})\end{bmatrix}$

and where $\theta_{i}\quad\forall i\in\\{1,\dots,M\\}$ denotes the orientation
of the center line at discretization point $p_{i}$. The linear constraint is
therefore

$\displaystyle\mathbf{r}\leq RA\mathbf{z}\leq\mathbf{l}$

Breaking down this equation, $A\mathbf{z}$ computes the discretization
coordinates from the control points, which is rotated by $R$ to compute its
projection on the left or right side of the center line.

Now we have all the components for our constrained QP problem, which we can
solve with qpOASES [8].

$\displaystyle\min_{\mathbf{z}}\quad$
$\displaystyle\frac{1}{2}\mathbf{z}^{T}H\mathbf{z}+g^{T}\mathbf{z}$ s.t.
$\displaystyle\mathbf{r}\leq RA\mathbf{z}\leq\mathbf{l}$ (15)

##  IV RESULTS

Before presenting the results, it is beneficial to discuss the evaluation
metrics for OTO methods. Since this is an open-loop offline method, it is
insufficient to show the end trajectory achieved by a vehicle driving on the
track, since there are other processes down the pipeline such as online
dynamic planning and optimal control calculations. These modules also have a
significant impact on the outcome of the experiment. Therefore, we will
directly compare the OTO result with the current state-of-the-art method in
minimum-curvature optimization in [9] to see if our method has achieved our
objectives, which is to offer an alternative minimum-curvature optimization
formulation for autonomous racing that uses significantly fewer decision
variables, guarantees continuity and still offers a trajectory comparable to
previous work.

To this end, we will perform minimum-curvature optimization using our
formulation and Heilmeier et al. formulation [9]. The discretization intervals
are the same in both experiments. We then simulate lap times with the QSS
simulation method described in III.A to show that we have reached comparable
results with the previous work.

We first compare the overall lap time performance of our method with the
reference center line and Heilmeier et al. [9] in Table I. The optimization
algorithms produce 7.65% (ours) and 8.94% (Heilmeier et al.) lap time
reduction, respectively, offering comparable maximum velocity and acceleration
profiles. The percentage difference of the metrics is shown in the right
column, which suggests that we achieved a level of optimality similar to [9].
However, our result produces a $C^{2}$ continuous B-spline curve that can be
easily re-discretized and even artificially manipulated afterwards by dragging
the control points, which is a very useful feature in the developmental stage
of autonomous racing, whereas [9] only produces a discretized trajectory with
no guarantee of continuity level due to its discrete decision variables. We
also see a significant reduction in the dimension of the decision variable.
Our QP problem has 204 decision variables (102 control points), down from 1932
using [9] with a 3 $\mathrm{m}$ discretization interval. The resulting QP
computation time is 3.8 $\mathrm{ms}$, down from 8.225 $\mathrm{s}$ using [9].
This shows that our method not only gives a more compact formulation that
captures the essence of the minimum-curvature problem, but also enables the
possibility of adopting such method in online planning on a very long track.

Looking turn by turn, Fig. 5 zooms in on the optimization at turns 8-10. The
control points of the center-line spline are shifted to form a minimum
curvature trajectory. For turn 7 in the zoomed-in section, we are able to
optimize the full trajectory with only four control points.

TABLE I: Simulation Results on Monza | Center | Heilmeier | Ours | Delta
---|---|---|---|---
| Line | et al. |  | (%)
Lap Time $(s)$ | 131.33 | 119.59 | 121.28 | -1.4
Ave Speed $(m/s)$ | 43.72 | 48.60 | 47.73 | 1.8
Max Speed $(m/s)$ | 93.69 | 95.12 | 94.33 | 0.8
Min Speed $(m/s)$ | 6.04 | 10.51 | 9.44 | 11.3
Max Lat G $(m/s^{-2})$ | 13.96 | 13.78 | 14.48 | -4.8
Max Throttling $(m/s^{-2})$ | 9.74 | 9.62 | 9.68 | -0.6
Max Braking $(m/s^{-2})$ | -19.87 | -19.27 | -19.85 | -2.9

We then move on to a different race track and apply the same OTO method to see
how our method transfers to a new track. Fig. 6 visualizes the optimization
results done on Putnam Road Course, Indiana, USA, which is a test track of the
Indy Autonomous Challenge. The zoomed-in portion of the graph visualizes the
movement of control points which leads to a curvature-optimal trajectory.
Table II shows metrics similar to I, in which comparable lap time reduction of
13.9% and 15.67% are respectively achieved by [9] and our work. The difference
in the simulation metrics between ours and [9] remains close, suggesting that
the outcome of the optimization is very comparable.

TABLE II: Simulation Results on Putnam Road Course | Center | Heilmeier | Ours | Delta
---|---|---|---|---
| Line | et al. |  | (%)
Lap Time $(s)$ | 79.63 | 68.55 | 66.91 | 2.4
Ave Speed $(m/s)$ | 36.36 | 41.57 | 42.75 | -2.7
Max Speed $(m/s)$ | 73.93 | 86.54 | 88.07 | -1.7
Min Speed $(m/s)$ | 8.02 | 13.83 | 12.0 | 15.2
Max Lat G $(m/s^{-2})$ | 15.0 | 15.0 | 15.0 | 0.0
Max Throttling $(m/s^{-2})$ | 9.75 | 9.18 | 9.52 | -3.6
Max Braking $(m/s^{-2})$ | -16.95 | -17.84 | -18.22 | -2.1

##  V CONCLUSIONS

We present a B-spline OTO method for autonomous racing which solves a minimum-
curvature optimization problem. Compared to previous works which only output a
discretized trajectory, this work outputs a fully parameterized trajectory of
$C^{2}$ continuity, which ensures a smooth control profile for high-speed
vehicle handling. The algorithm also considers the data scarcity of early-
stage autonomous motorsports development and requires minimum vehicle dynamics
data. Compared to previous work [9], the dimension of the problem is
significantly reduced from thousands of discretization points down to a few
dozens of control knot points. The problem computation time is also
drastically reduced as a result. This enables future work to explore the
online application of minimum-curvature OTO for autonomous racing.

## References

  * [1] F. Braghin, F. Cheli, S. Melzi, and E. Sabbioni.  Race driver model.  Computers & Structures, 86(13):1503–1516, July 2008.
  * [2] D L Brayshaw and M F Harrison.  A quasi steady state approach to race car lap simulation in order to understand the effects of racing line and centre of gravity location.  Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, 219(6):725–739, June 2005.  Publisher: IMECHE.
  * [3] D L Brayshaw and M F Harrison.  Use of numerical optimization to determine the effect of the roll stiffness distribution on race car performance.  Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, 219(10):1141–1151, October 2005.  Publisher: IMECHE.
  * [4] Danilo Cambiaghi, Marco Gadola, Luca Manzo, and David Vetturi.  A Tool for Lap Time Simulation.
  * [5] Carl d. Boor.  A Practical Guide to Splines.  Springer Verlag, New York, 1978.
  * [6] Nicola Dal Bianco, Enrico Bertolazzi, Francesco Biral, and Matteo Massaro.  Comparison of direct and indirect methods for minimum lap time optimal control problems.  Vehicle System Dynamics, 57(5):665–696, May 2019.
  * [7] P Dierckx.  Algorithms for smoothing data with periodic and parametric splines.  Computer Graphics and Image Processing, 20(2):171–184, October 1982.
  * [8] Hans Joachim Ferreau, Christian Kirches, Andreas Potschka, Hans Georg Bock, and Moritz Diehl.  qpOASES: a parametric active-set algorithm for quadratic programming.  Mathematical Programming Computation, 6(4):327–363, December 2014.
  * [9] Alexander Heilmeier, Alexander Wischnewski, Leonhard Hermansdorfer, Johannes Betz, Markus Lienkamp, and Boris Lohmann.  Minimum curvature trajectory planning and control for an autonomous race car.  Vehicle System Dynamics, 58(10):1497–1527, October 2020.
  * [10] Tammo Jan Dijkema.  B-Spline Basis Function, March 2011.
  * [11] Nitin R. Kapania, John Subosits, and J. Christian Gerdes.  A Sequential Two-Step Algorithm for Fast Generation of Vehicle Racing Trajectories.  Journal of Dynamic Systems, Measurement, and Control, 138(9), June 2016.
  * [12] T. Novi, A. Liniger, R. Capitani, and C. Annicchiarico.  Real-time control for at-limit handling driving on a predefined path.  Vehicle System Dynamics, 58(7):1007–1036, July 2020.  Publisher: Taylor & Francis _eprint: https://doi.org/10.1080/00423114.2019.1605081.
  * [13] Blake Siegler, Andrew Deakin, and David Crolla.  Lap Time Simulation: Comparison of Steady State, Quasi- Static and Transient Racing Car Cornering Strategies.  Proceedings of the 2000 SAE Motorsports Engineering Conference & Exposition, page 361, November 2000.
  * [14] Moritz Werling, Julius Ziegler, Sören Kammel, and Sebastian Thrun.  Optimal trajectory generation for dynamic street scenarios in a Frenét Frame.  In 2010 IEEE International Conference on Robotics and Automation, pages 987–993, May 2010.  ISSN: 1050-4729.