Policy search on a robot

Hill climbing on a real machine: a noisy score, a fair trial, and a budget measured in seconds.

U12.4Learning, and the capstoneUniversity40 min

Do this lesson in the simulator

Fitting a model needs data with answers in it. A policy has no answers: nobody can tell the robot the right command for this situation, only how well things went afterwards. So the search has to be done by trying.

The setting

A policy is a rule from what the robot senses to what it does. Here it is as small as a policy gets: one number, a lateral command held on all the time, to cancel a chassis that slides sideways whenever it drives forward.

A trial runs the policy for a short while and returns a score. A search proposes policies and keeps what works.

score = run the policy, measure what happened
search = propose, evaluate, keep the better, repeat

Hill climbing

The simplest search that works on a robot:

value, step = start, big_step
best = score(value)
for i in range(budget):
    trial = value + step
    s = score(trial)
    if s < best:
        value, best = trial, s        # that direction is downhill, carry on
    else:
        step = -step * 0.6            # wrong way, and close: turn round, take a smaller step

It is derivative free, which matters because you have no derivative: the score comes out of a physical trial, not a formula. It has one parameter of its own, the shrink factor, and 0.5 to 0.7 is the usual range. And it converges to a local optimum only, which for one or two well-behaved parameters is usually the global one, and for a rough landscape is not.

Alternatives, all still a few lines: random search inside a box (surprisingly strong, and trivially parallel), coordinate descent for several parameters, and the cross entropy method, which keeps the best fraction of a batch and samples the next batch from their mean and spread. Anything more, such as policy gradients or Bayesian optimisation, is a different course.

The trial is where the rigour is

A score you cannot trust is worse than no score, because the search will chase the error.

  • Every trial must start from the same state. A trial that starts wherever the last one ended measures the last policy as much as this one. Drive back to the line, or design the trial so it ends where it began.
  • Make the trial reversible. Out and back is the neat trick here: the sideways leak flips sign with the forward command, so a leg out and a leg back returns the robot to where it started, and the two legs' slides can be added as magnitudes.
  • The score is noisy. Flow noise, drive jitter, a different patch of mat. If the noise in the score is comparable with the difference between two policies, one trial cannot tell them apart and the search is following coin flips. Repeat the trial and average, or make the trial longer, and know which you are doing.
  • The budget is in seconds, not evaluations. Twelve trials of 2 seconds is 24 seconds of robot time. A method that needs ten thousand evaluations is not a method you can run on hardware, and that single fact is why simulation and sim-to-real exist.

Exploration and exploitation

Every search has to divide its budget between trying something new and refining what already works. Exploit too early and you polish a mediocre policy. Explore too long and you never converge.

Hill climbing handles it with the step size: large early, when there is more to learn from a big jump, and shrinking as the evidence accumulates. Epsilon-greedy bandits handle it with a random action a fraction of the time, with the fraction decaying. The upper confidence bound rule handles it best of the simple methods: choose the option with the highest optimistic estimate, mean plus a term that grows with how little you have tried it, which explores exactly in proportion to ignorance.

Whatever the method, the trade-off does not go away. It is a property of learning from your own actions.

from bugbot import *
connect()

DT = 0.1

def turn_cmd():
    err = (imu()[0] + 180) % 360 - 180
    if abs(err) < 2.0:
        return 0
    cmd = max(18.0, min(30.0, abs(1.5 * err)))     # below 15 the drive does nothing at all
    return -cmd if err > 0 else cmd

def leg(fwd, lat, seconds):
    slide = 0.0
    for i in range(3 + int(seconds / DT)):
        drive(fwd, lat, turn_cmd())
        if i >= 3:
            slide += flow()[0] * DT
        wait(DT)
    return slide

def score(offset):
    out = leg(60, offset, 0.8)
    back = leg(-60, -offset, 0.8)
    stop()
    wait(0.2)
    return abs(out) + abs(back)

for offset in (0, 15, 30, 45):
    print("offset", offset, "slides", round(score(offset), 2), "cm")

Run this in the simulator

Four evaluations, eight seconds of robot time, and the shape of the landscape is already visible: a V with its bottom somewhere in the middle. A search is a way of finding that bottom without evaluating everywhere.

Note the rotation command in there. A robot that is quietly turning will slide sideways in the world whatever the lateral command does, and the trial would be scoring two faults at once. Hold the heading square, and the score measures the one thing the policy controls.

Why not just write the controller?

You could. Feed flow()[0] back into the lateral command and the leak is cancelled without any learning at all, and it would adapt to a change in the leak too.

That comparison is the right one to make every time, and often feedback wins. What the learned offset buys is that it works when the sensor is not available during the run, it costs nothing at run time, and it is a measurement of the machine rather than a reaction to it. What feedback buys is that it handles changes the learner never saw. Real systems use both: a learned feedforward term for what is predictable, and feedback for what is not.

Task: learn the offset that drives it straight

Hill climb the lateral offset using short out and back trials, plot score as you go, and then drive the robot at least 90 cm up into the green lane.

from bugbot import *
connect()

DT = 0.1
CMD = 60

Challenges

  1. Run the same search twice and compare the offsets it lands on. Is the difference smaller than the width of the lane?
  2. Score each policy twice and average. How much of your budget did that cost, and did the search end up anywhere better?
  3. Search over two numbers, an offset and a gain on flow()[0], by taking turns on each. What breaks first, the budget or the noise?