Problem 578842 · medium · Level 05 Advanced Algorithms & Graphs

The Root Locus of a Lawnmower's Steering

root locus · poles · proportional gain · numpy · stability · damping

A robotic lawnmower steers along a wire buried at the edge of the lawn. Its steering is a discrete plant B(z) / A(z) (coefficient lists, lowest power of z^-1 first, as in Level 4), and a proportional gain K closes the loop, so the closed-loop poles are the roots of

A(z) + K * B(z)        (add the lists coefficient by coefficient, padding b with zeros)

Every value of K gives a different set of poles. Drawn for all gains at once, the paths the poles travel are called the root locus; the engineer reads off it which gain to use. Here you build it as a table. For each gain K in gains, find the poles with numpy.roots (the list, read highest power of z first, is the same list) and summarise them by two numbers:

  • radius: the largest pole radius |z|, which decides stability (below 1) and how fast the slowest part dies away;
  • angle: the largest angle |angle of z| of any pole, in degrees (0 to 180), which says how fast the loop rings: 0 means no oscillation, 180 a sign flip every sample. Use abs(math.degrees(cmath.phase(z))), and skip poles with |z| < 1e-9: a pole at the origin has no direction (its computed angle is noise).

Write root_locus(a, b, gains) that returns a list with one tuple (K, radius, angle) per gain, in the order of gains. For a picture, collect the real and imaginary parts of every pole over a long list of gains and press Run with plot(reals, imags, kind="scatter").

Examples

Input:  a = [1, -1.6, 0.63], b = [0, 0.1], gains = [0, 2, 20, 40]
Output: [(0, 0.9, 0.0), (2, 0.7937253933193771, 28.125505702055698),
         (20, 0.7937253933193773, 104.59449121791113), (40, 2.1, 180.0)]
Explanation: K = 0 leaves the mower's own poles, 0.9 and 0.7. At K = 2 they have met and split
into a complex pair: faster (radius 0.79) but ringing at 28° per sample. Along the circle of
radius sqrt(0.63) the angle grows with K; by K = 40 the pair has met again on the negative axis
and split into -0.3 and -2.1: unstable.

Constraints

  • a[0] = 1 and b[0] = 0 (the plant cannot react within the same sample), len(b) <= len(a)
  • no gain in the tests puts two poles exactly on top of each other
  • answers are compared with a tolerance of 1e-6; lists are accepted in place of tuples

Goals

  • Recompute a loop's poles for each gain in a list, a root locus as a table
  • Summarise each gain's poles by their largest radius and their largest angle
  • See how raising the gain first speeds a loop up, then makes it ring, then unstable
Starting Python…