Problem 547344 · hard · Level 05 Advanced Algorithms & Graphs

Tune a Ball on a Beam by Its Poles

pole placement · PD control · state space · eigenvalues · numpy · settling time · overshoot · computation delay

A ball rolls on a beam whose tilt alpha (radians) a servo sets. Tilting the beam accelerates the ball along it at c * alpha m/s², with c = 5 * 9.81 / 7 (a solid ball rolling without slipping). A computer samples the ball's position x (m) and speed v (m/s) every T seconds and runs a PD controller, alpha_cmd = -(Kp * x + Kd * v), to bring the ball to the centre x = 0. Computing takes one sample, so each command reaches the servo one sample later. With the tilt held between samples, one step of the loop is exactly

x[k+1]     = x[k] + T * v[k] + c * T*T / 2 * alpha[k]
v[k+1]     = v[k] + c * T * alpha[k]
alpha[k+1] = -(Kp * x[k] + Kd * v[k])        (the command computed at step k, applied at k+1)

That is s[k+1] = M s[k] for the state s = [x, v, alpha] and the 3 by 3 matrix

M = [[1,   T,   c*T*T/2],
     [0,   1,   c*T    ],
     [-Kp, -Kd, 0      ]]

The loop's poles are the eigenvalues of M (the roots of its characteristic polynomial): numpy.linalg.eigvals(M).

You are given lists of candidate gains. For every pair, Kp from Kp_list in the outer loop and Kd from Kd_list in the inner loop, predict the response from the poles:

  • radius r: the largest |z|. Skip the pair if r >= 1 (unstable).
  • settling time: ln(0.02) / ln(r) * T seconds (the slowest pole down to 2 %).
  • overshoot: for every pole with |z| >= 1e-9 and angle θ = |angle of z| > 0, the estimate 100 * |z| ** (π / θ) per cent; take the largest of these (0 if there are none). Skip the pair if it is above max_overshoot.

Return (Kp, Kd, settling_time) for the remaining pair with the smallest settling time (the first one in the loop order on a tie), or None if every pair was skipped.

Examples

Input:  T = 0.02, Kp_list = [10, 20, 30, 40], Kd_list = [2, 2.5, 3, 3.5], max_overshoot = 5
Output: (20, 2.5, 0.25997265382410545)
Explanation: (20, 2.5) has a complex pair of radius 0.740 at 0.306 rad and a real pole at 0.588:
settling in 0.26 s with an overshoot estimate of 4.5 %. Nothing else on the grid settles faster;
(30, 3) and (30, 3.5) come close (about 0.30 s) but are predicted to overshoot by 19 % and 27 %.

Input:  T = 0.02, Kp_list = [10, 20, 30, 40], Kd_list = [2, 2.5, 3, 3.5], max_overshoot = 4
Output: (10, 2, 0.3263096684629896)
Explanation: (20, 2.5) is now 0.5 % over the limit; the next fastest pair that is calm enough is
(10, 2), whose complex poles are so close to the real axis that their overshoot is near 0.

Input:  T = 0.1, Kp_list = [2, 5, 10, 20, 40], Kd_list = [1, 2, 3, 5, 8], max_overshoot = 5
Output: None
Explanation: sampled every 0.1 s, with a sample of delay, no pair is both stable and calm.

Constraints

  • 0 < T <= 0.5; up to 30 gains in each list
  • no test has a pair within 1e-6 of a limit (radius 1, or the overshoot limit)
  • answers are compared with a tolerance of 1e-6; a list is accepted in place of the tuple

Goals

  • Build the closed-loop state matrix of a sampled plant with a PD controller and one sample of delay
  • Find the closed-loop poles as the eigenvalues of that matrix
  • Predict settling time and overshoot from the poles and pick the fastest gains that respect an overshoot limit
Starting Python…