# Ski Race

A skier begins at position $(x_0, y_0)$ and must ski through $n$ gates to position $(x_{n+1}, y_{n+1})$, where skiing downhill is in the direction of increasing $x$ position. The gates are parallel and run perpendicular to the $x$ direction. For each $x_i$ for $i = 1, \cdots, n$ there is a gate centered at $y_i$ with a width of $c_i$.
Efficiently find the shortest path through all $n$ gates.

## Example

Consider the starting position $(x_0, y_0) = (0, 4)$ and ending position $(x_{n+1}, y_{n+1}) = (24, 4)$ and gates

$i$ $x_i$ $y_i$ $c_i$
$1$ $4$ $5$ $3$
$2$ $8$ $4$ $2$
$3$ $12$ $6$ $2$
$4$ $16$ $5$ $1$
$5$ $20$ $7$ $2$

Then the course looks like ## Solution

Let $p_i$ be the $y$ position of the skier at $x_i$. Then for the skier to go through the gate at $x_i$, our constraint on $p_i$ must be $p_i \in [ y_i - \frac{c_i}{2} , y_i + \frac{c_i}{2} ]$.

The length of the shortest path taken between adjacent gates $x_i$ and $x_{i+1}$ is $\sqrt{ (x_{i+1} - x_i)^2 + (p_{i+1} - p_i)^2 }$. Then we can formulate our optimization problem as

For simplicity, we can define $p = \begin{bmatrix} p_0 \\ \vdots \\ p_{n+1} \end{bmatrix}$, $y = \begin{bmatrix} y_0 \\ \vdots \\ y_{n+1} \end{bmatrix}$, and $c = \begin{bmatrix} 0 \\ c_1 \\ \vdots \\ c_n \\ 0 \end{bmatrix}$ to write

This isn’t efficiently solvable yet, however, because the objective isn’t convex in $p$. But we can make the problem convex with the following reduction:

Let $d_i$ be $p_i - p_{i-1}$, with $d_0 = p_0 = y_0$, so $d_1 = p_1 - p_0$, $d_2 = p_2 - p_1$, and so on. Rearranging, this means $p_i = \sum_{j=0}^i d_j$. Then we can neatly relate $p$ and $d$ by $p = L d$, See np.tril where $L$ is a lower triangular matrix with ones for entries. Then our optimization problem becomes

Now the objective is the sum of the $\ell_2$ norms of $\begin{bmatrix} x_i - x_{i-1} \\ d_i \end{bmatrix}$, which is convex in $d$. Also, the constraints are all affine, so this is a convex optimization problem.

We can apply our solution to the above values:

import numpy as np
from cvxpy import Variable, Minimize, Problem, norm, hstack

x = np.array([0, 4, 8, 12, 16, 20, 24])
y = np.array([4, 5, 4, 6, 5, 7, 4])
c = np.array([0, 3, 2, 2, 1, 2, 0])
L = np.tril(np.ones((7, 7)))

dy = Variable(7)

objective = sum(
norm(hstack((x[i] - x[i-1], dy[i])))
for i in range(1, 7)
)
constraints = [
L * dy >= y - c / 2,
L * dy <= y + c / 2,
]
problem = Problem(Minimize(objective), constraints)
problem.solve()

p = L @ dy.value
path = np.column_stack((x, p))
path_length = problem.value
print(f"Path length: {path_length}")
print("Path:")
print(path)

Path length: 24.573423483752443
Path:
[[ 0.          4.        ]
[ 4.          4.37494654]
[ 8.          4.749936  ]
[12.          5.12493412]
[16.          5.49999986]
[20.          6.        ]
[24.          4.        ]]


which we can visualize 