Learning by reward
Q-learning: a table of how good each action is, filled in by trying.
Do this lesson in the simulatorNo labels this time. Nobody tells the robot what the right action is. It tries things, and afterwards something tells it how well that went: a reward. Moving forward pays a little. Turning costs a little. Bumping into something costs a lot. From nothing but that, the robot works out how to wander a cluttered mat without hitting anything. This is reinforcement learning, and the method is called Q-learning.
States and actions
The robot cannot learn about every possible position, so it summarises its situation into a few states. Here: how far the nearest thing ahead is (near, mid, far) and which side has more room (room-left, room-right). Six states. Three actions: forward for 0.2 s, spin left for 0.3 s, spin right for 0.3 s.
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
def state():
# 64 distances, 8 rows of 8
grid = tof_grid()
# cm to the nearest thing ahead
ahead = distance()
# level rows, two left columns
left_room = min(grid[16], grid[17], grid[24], grid[25])
# and two right columns
right_room = min(grid[22], grid[23], grid[30], grid[31])
a = "near" if ahead < 32 else ("mid" if ahead < 50 else "far")
return a + "-" + ("room-left" if left_room >= right_room else "room-right")
# spin anticlockwise on the spot at 40
turn_left(40)
# do this 8 times (tick counts from 0)
for tick in range(8):
# pause 0.4 s (the robot keeps doing what it was told)
wait(0.4)
print(round(heading()), "->", state())
# all motors off
stop()
The table
Q is a table with a number for every state and action: how good, as far as the robot knows so far, that action is in that state. It starts at zero. Learning means filling it in.
Choosing an action: mostly pick the best known one, but sometimes pick at random. The random ones are how it discovers anything; the fraction is called epsilon, and it shrinks as the robot learns.
The reward, and the rule
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
# random numbers
import random
random.seed(1)
ACTIONS = ["forward", "left", "right"]
def act(a):
if a == "forward":
forward(60); wait(0.25)
elif a == "left":
turn_left(100); wait(0.3)
else:
turn_right(100); wait(0.3)
bumps, was_bumped = 0, False
# do this 30 times (step counts from 0)
for step in range(30):
a = random.choice(ACTIONS)
act(a)
reward = 1.0 if a == "forward" else -0.1
hit = bumped()
# count each bump once
if hit and not was_bumped:
reward = -20.0
bumps += 1
was_bumped = hit
print(a, "reward", reward)
# all motors off
stop()
print("bumps:", bumps)
Random actions, and the reward each one earned. bumped() stays true for a third of a second after a touch, so was_bumped makes sure one bump is paid for once.
The learning rule is one line:
Q[s][a] += 0.3 * (reward + 0.8 * max(Q[s2].values()) - Q[s][a])
s is the state before the action, s2 the state after. The bracket is the surprise: what the action turned out to be worth (the reward now, plus 0.8 of the best the next state offers) minus what the table thought. Move the table's number 0.3 of the way towards the truth. The 0.8 is what makes it plan: an action that leads somewhere good is itself worth something.
What it learns
Run the task and read the table at the end. In the near states, forward ends up strongly negative and a turn is best; in far states forward wins. Nobody wrote that rule. The robot bumped into things until the table said not to.
Task: learn to wander
Let the robot learn for 88 seconds. It may bump early on; after 60 seconds it must not bump at all, and it must have driven at least 250 cm in total. Print bumps: <n> at the end.
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
bumps = 0
# do this 880 times (tick counts from 0)
for tick in range(880):
# drive forward at 60 (keeps going until the next command)
forward(60)
# pause 0.1 s (the robot keeps doing what it was told)
wait(0.1)
if bumped():
bumps += 1
# spin clockwise on the spot at 60
turn_right(60)
# pause 0.5 s (the robot keeps doing what it was told)
wait(0.5)
# all motors off
stop()
print('bumps:', bumps)
Challenges
- Keep epsilon at 0.3 for the whole run. How many bumps now?
- Add a
very-nearstate under 15 cm. Does it learn faster or slower? - Reward
forwardmore whendistance()is large, so that it learns to head for open space.