Ski Race

A skier begins at position and must ski through gates to position , where skiing downhill is in the direction of increasing position. The gates are parallel and run perpendicular to the direction. For each for there is a gate centered at with a width of .
Efficiently find the shortest path through all gates.

Example

Consider the starting position and ending position and gates

Then the course looks like

ski course

Solution

Let be the position of the skier at . Then for the skier to go through the gate at , our constraint on must be .

The length of the shortest path taken between adjacent gates and is . Then we can formulate our optimization problem as

For simplicity, we can define , , and to write

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

Let be , with , so , , and so on. Rearranging, this means . Then we can neatly relate and by , See np.tril where is a lower triangular matrix with ones for entries. Then our optimization problem becomes

Now the objective is the sum of the norms of , which is convex in . 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

solution