Problem 612391 · hard · Level 06 Heuristics & Optimization

A Camera Dolly That Looks Ahead

model predictive control · receding horizon · prediction · brute-force search · state space · itertools

A camera dolly runs on a straight rail. Its motor has only three settings, accelerations of -1, 0 or +1 m/s², and between shots the dolly must move to the next mark and stop there. A proportional controller would ask for settings the motor does not have. A model-predictive controller (MPC) instead uses the model x[k+1] = A x[k] + B u[k], y[k] = C x[k] to look ahead:

  1. From the current state, try every input sequence of length H (the horizon) made of the allowed levels, in the order of itertools.product(levels, repeat=H).
  2. For each, predict the states x1, ..., xH it would produce, and its cost
cost = sum over i = 1..H of   (C x_i - r)**2 + rho * u_(i-1)**2

(r is the wanted output, rho weights the effort). 3. Choose the cheapest sequence. Costs within 1e-9 of the lowest count as equal, and among those the first in the product order wins (so rounding never changes the choice). 4. Apply only its first input to the dolly (x = A x + B u), then repeat the whole search from the new state at the next step.

Planning again every step is the receding horizon: the controller always plans H steps ahead, but only ever commits to one.

Write mpc(A, B, C, x0, r, levels, H, rho, steps) that runs this loop for steps steps from x0 and returns (applied, y): the list of inputs it applied, and the output C x at the end.

Examples

Input:  A = [[1, 0.5], [0, 1]], B = [0.125, 0.5], C = [1, 0], x0 = [0, 0], r = 1.5,
        levels = [-1, 0, 1], H = 3, rho = 0.01, steps = 8
Output: ([1, 1, 0, -1, -1, 0, 0, 0], 1.5)
Explanation: dt = 0.5 s; the state is [position, speed]. Looking 1.5 s ahead is enough to see that it
must brake in time: speed up, coast, brake, and stop exactly on the mark.

Input:  the same with H = 1
Output: ([1, 1, 1, -1, -1, -1, -1, -1], 1.75)
Explanation: looking only one step ahead, it keeps accelerating while that brings it closer, brakes
too late, overshoots to 2.25 m, and is still swinging about the mark at the end.

Constraints

  • 1 <= n <= 4; 1 <= len(levels) and len(levels) ** H <= 256; 0 <= steps <= 40
  • answers are compared with a tolerance of 1e-6; the applied inputs are values from levels

Goals

  • Use the state-space model to predict the outputs of a candidate input sequence
  • Score every candidate with a cost on the tracking error and the effort, and pick the best
  • Apply only the first input and plan again at the next step (receding horizon)
Starting Python…