Problem 605525 · medium · Level 06 Heuristics & Optimization

Two Rooms, One Radiator

controllability · controllability matrix · rank · uncontrollable mode · stabilisability · numpy · singular value decomposition

Two rooms share a wall, and one radiator heats them. With the temperatures above outside as the state, a model per minute is x[k+1] = A x[k] + B u[k]. Can the radiator steer both temperatures wherever it likes? If the radiator heats the two rooms exactly equally and the rooms are alike, it can raise both, but it can never change the difference between them: that difference just fades by itself, at its own rate, whatever the controller does. Such a part of the motion is an uncontrollable mode.

The test: starting from 0, after n steps the input can only have reached the combinations of B, A B, A^2 B, ..., A^(n-1) B. Put them side by side as the columns of the n by n controllability matrix W. The system is controllable when W has full rank n. To find the rank, and what lies outside, use the singular value decomposition U, S, Vt = numpy.linalg.svd(W):

  • the rank r is the number of singular values S[i] > 1e-9 * S[0] (0 if S[0] is 0, which happens when B is all zeros);
  • the last n - r columns of U, U2 = U[:, r:], span the directions no input reaches. The motion there obeys its own small matrix A2 = U2.T @ A @ U2 (an (n-r) by (n-r) matrix), and its eigenvalues are the uncontrollable modes.

An uncontrollable mode of radius below 1 fades by itself, and the system can still be stabilised by feedback (it is stabilisable); one of radius 1 or more can never be fixed.

Write reachable(A, B) that returns (r, radii): the rank of W, and the radii |z| of the uncontrollable modes, largest first (an empty list when the system is controllable).

Examples

Input:  A = [[0.9, 0.05], [0.05, 0.9]], B = [0.1, 0]
Output: (2, [])
Explanation: the radiator is in room 0, but heat leaks through the wall, so it can set both.

Input:  A = [[0.9, 0.05], [0.05, 0.9]], B = [0.1, 0.1]
Output: (1, [0.8500000000000004])
Explanation: heating both alike: the difference between the rooms fades by 0.85 a minute on its own.

Input:  A = [[0.9, 0], [0, 0.95]], B = [0.1, 0]
Output: (1, [0.9499999999999997])
Explanation: no wall coupling: room 1 just cools, at 0.95 a minute.

Input:  A = [[1.1, 0], [0, 0.5]], B = [0, 1]
Output: (1, [1.1])
Explanation: a mode that grows by 10 % a step and that no input touches: not stabilisable.

Constraints

  • 1 <= n <= 5; one input
  • in the tests the singular values are clearly separated: each is either above 1e-6 * S[0] or below 1e-12 * S[0]
  • answers are compared with a tolerance of 1e-6

Goals

  • Build the controllability matrix [B, AB, ..., A^(n-1) B] and find its rank
  • Find the modes no input can move, from the part of the state space the input never reaches
  • Decide whether feedback can stabilise a system whose modes are not all controllable
Starting Python…