Problem 679900 · easy · Level 06 Heuristics & Optimization

A Lift's State, One Step at a Time

state space · state vector · simulation · matrix-vector product · difference equation

A lift car's controller thinks in steps of dt seconds. To predict where the car will be it needs two numbers, its height h (m) and its speed v (m/s): together they are the car's state. If the motor gives the car an acceleration u (m/s²) held for one step, then

h[k+1] = h[k] + dt * v[k] + dt*dt/2 * u[k]
v[k+1] = v[k] + dt * u[k]

Every linear system of this kind fits one pattern, the state-space form:

x_{k+1} = A x_k + B u_k \ \text{(the state moves on)}, \qquad y_k = C x_k \ \text{(what the sensor reads)}

Here x is the state, a list of n numbers; A is an n by n matrix (a list of rows); B and C are lists of n numbers; u is the input and y the measured output. The matrix-vector product Ax is the list whose entry i is \sum_{j=0}^{n-1} A_{ij} x_j, in Python sum(A[i][j] * x[j] for j in range(n)), and Cx is the single number \sum_{j=0}^{n-1} C_j x_j. For the lift, x = [h, v], A = [[1, dt], [0, 1]], B = [dt*dt/2, dt], and C = [1, 0] if the sensor reads the height.

Write simulate(A, B, C, x0, us) that starts from the state x0, applies the inputs us[0], us[1], ... in turn, and returns the outputs [y[0], y[1], ..., y[N]] with N = len(us): y[0] = C x0 is read before the first input, and each later y after one more step. Compute every entry of the new state from the old state; do not change x while you are still using it. Press Run with plot(simulate(...), kind="step") to see the journey.

Examples

Input:  A = [[1, 0.5], [0, 1]], B = [0.125, 0.5], C = [1, 0], x0 = [0, 0], us = [1, 1, 0, -1, -1]
Output: [0, 0.125, 0.5, 1.0, 1.375, 1.5]
Explanation: dt = 0.5 s. One second at 1 m/s², half a second coasting at 1 m/s, one second braking:
the car rises 1.5 m and stops.

Input:  A = [[1, 0.5], [0, 1]], B = [0.125, 0.5], C = [0, 1], x0 = [2, 0], us = [1, 1, 0, -1, -1]
Output: [0, 0.5, 1.0, 1.0, 0.5, 0.0]
Explanation: the same trip from a height of 2 m, but this sensor reads the speed.

Input:  A = [[0.9]], B = [0.5], C = [2], x0 = [10], us = [0, 0, 1]
Output: [20, 18.0, 16.2, 15.58]
Explanation: one state that keeps 90 % of itself each step.

Constraints

  • 1 <= n <= 6; 0 <= len(us) <= 1000
  • answers are compared with a tolerance of 1e-6

Goals

  • Describe a system by a state vector that holds everything needed to predict its future
  • Step x[k+1] = A x[k] + B u[k] with plain lists and loops
  • Read the measured output y[k] = C x[k] from the state at every step
Starting Python…