Problem 639114 · medium · Level 06 Heuristics & Optimization

Placing the Lift's Two Poles by Hand

pole placement · state feedback · characteristic polynomial · trace and determinant · Cramer's rule · complex numbers

The lift's state is x = [height, speed] and the controller uses u = -K x = -(k1 * height + k2 * speed). The closed loop A - B K has two poles, and you want them at two chosen places p1, p2 (two real numbers, or a complex pair re ± im j). For a 2 by 2 matrix M the characteristic polynomial is

z^2 - trace(M) z + det(M)        with trace = M[0][0] + M[1][1],   det = M[0][0]*M[1][1] - M[0][1]*M[1][0]

and the polynomial with roots p1, p2 is z^2 - (p1 + p2) z + p1 p2. Writing out A - B K (with A = [[a11, a12], [a21, a22]], B = [b1, b2], K = [k1, k2]) gives

trace(A - B K) = (a11 + a22) - (b1 k1 + b2 k2)
det(A - B K)   = det(A) - k1 (b1 a22 - b2 a12) - k2 (b2 a11 - b1 a21)

(the k1 k2 terms cancel). Matching both coefficients gives two linear equations for k1 and k2:

b1 * k1                 + b2 * k2                 = (a11 + a22) - (p1 + p2)
(b1 a22 - b2 a12) * k1  + (b2 a11 - b1 a21) * k2  = det(A) - p1 p2

Solve them with Cramer's rule: for m11 k1 + m12 k2 = r1, m21 k1 + m22 k2 = r2 with d = m11 m22 - m12 m21, the answer is k1 = (r1 m22 - m12 r2) / d and k2 = (m11 r2 - m21 r1) / d. If d is 0 the input cannot reach one of the modes and no gains work (d is minus the determinant of the controllability matrix [B, AB]).

Write place_two(A, B, poles) that returns [k1, k2], or None if |d| < 1e-12. p1 + p2 and p1 * p2 are real for a complex pair; use complex(...).real to get plain floats.

Examples

Input:  A = [[1, 0.5], [0, 1]], B = [0.125, 0.5], poles = [0.5, 0.6]
Output: [0.7999999999999998, 1.5999999999999999]
Explanation: the lift with dt = 0.5 s; errors shrink by half and by 40 % a step.

Input:  A = [[1, 0.5], [0, 1]], B = [0.125, 0.5], poles = [0, 0]
Output: [4.0, 3.0]
Explanation: both poles at 0, "deadbeat": from any start the lift is exactly on target after two steps.

Input:  A = [[1, 0.5], [0, 1]], B = [0.125, 0.5], poles = [(0.7+0.2j), (0.7-0.2j)]
Output: [0.52, 1.0700000000000003]

Input:  A = [[0.9, 0], [0, 0.8]], B = [1, 0], poles = [0.5, 0.5]
Output: None
Explanation: the input never reaches the second state, whose pole stays at 0.8.

Constraints

  • poles holds two real numbers or a complex-conjugate pair
  • answers are compared with a tolerance of 1e-6; a tuple is accepted in place of the list

Goals

  • Write the characteristic polynomial of a 2 by 2 closed loop A - B K from its trace and determinant
  • Match it to the polynomial with the wanted poles, giving two linear equations for the gains
  • Solve them with Cramer's rule, and recognise the case no gains can solve
Starting Python…