Simulating a Smart Robot

1Learning by trying

Nobody gives a toddler a map of the house; she learns where the kitchen is by walking around, bumping into things and remembering what worked. A robot can learn in a similar way. Instead of being told the route to its charging dock, a cleaning robot tries moves, receives a small penalty for every move and for every bump, and a reward when it reaches the dock. Over many attempts it learns which move is best in each place. Trying this on a real robot would mean thousands of bumps, so it is done in a simulation first. This is how AI improves a robot's behaviour, and it is this unit's key competence.

2Robot simulators

Professional robots are developed in simulators that model physics, sensors and motors in 3-D. Webots (open source since 2018) and Gazebo (open source, widely used with the Robot Operating System, ROS) are free; CoppeliaSim is free for education. For Arduino robots, Tinkercad and Wokwi from unit 5 simulate the circuit and code. Every simulator is simpler than reality, so behaviour learned in simulation must be checked on the real robot: engineers call the difference the reality gap.

In this lesson the simulator is a short Python program. The world is a 5 × 5 classroom with desks; the robot starts in the top-left corner and its dock is in the bottom-right corner.

3How Q-learning updates its estimates

After each move from state $ss$ with action $aa$, landing in $s^{\mathrm{\prime }}s\text{'}$ with reward $rr$, the robot nudges its estimate towards what it has just seen:

$$Q(s,a)\leftarrow Q(s,a)+\alpha (r+\gamma \underset{a^{\mathrm{\prime }}}{\max }Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})-Q(s,a))Q(s,\; a)\; \backslash leftarrow\; Q(s,\; a)\; +\; \backslash alpha\; \backslash left(\; r\; +\; \backslash gamma\; \backslash max\_\{a\text{'}\}\; Q(s\text{'},\; a\text{'})\; -\; Q(s,\; a)\; \backslash right)$$

The learning rate $\alpha \backslash alpha$ (here 0.5) sets how far each nudge goes. The discount factor $\gamma \backslash gamma$ (here 0.9) makes rewards that come sooner worth more than rewards later. To keep discovering better routes, the robot takes a random move 20% of the time (exploration, $\epsilon =0.2\backslash varepsilon\; =\; 0.2$) and its best-known move otherwise (exploitation).

4The simulation and the learning

This program contains the simulated world (step), the learning (train) and a test of the learned policy (greedy_path). It uses a fixed random seed, so it gives the same results every time. It was run with python3.

import random

# A cleaning robot must learn the way to its charging dock (G) in a classroom with desks (#)
ROOM = ["S....",
        ".##..",
        ".#..#",
        "...#.",
        "#...G"]
ROWS, COLS = len(ROOM), len(ROOM[0])
ACTIONS = {"^": (-1, 0), "v": (1, 0), "<": (0, -1), ">": (0, 1)}
START, GOAL = (0, 0), (4, 4)

def step(state, action):
    """The simulated world: returns the new state and the reward."""
    r, c = state[0] + ACTIONS[action][0], state[1] + ACTIONS[action][1]
    if not (0 <= r < ROWS and 0 <= c < COLS) or ROOM[r][c] == "#":
        return state, -5                  # bumped into a wall or desk: stays put
    if (r, c) == GOAL:
        return (r, c), 10                 # reached the dock
    return (r, c), -1                     # every move costs a little battery

def train(episodes=300, alpha=0.5, gamma=0.9, epsilon=0.2, seed=3):
    rng = random.Random(seed)
    Q = {(r, c): {a: 0.0 for a in ACTIONS} for r in range(ROWS) for c in range(COLS)}
    history = []
    for _ in range(episodes):
        state, steps = START, 0
        while state != GOAL and steps < 200:
            if rng.random() < epsilon:                      # explore
                action = rng.choice(list(ACTIONS))
            else:                                           # use what it has learned
                action = max(Q[state], key=Q[state].get)
            new, reward = step(state, action)
            best_next = 0.0 if new == GOAL else max(Q[new].values())
            Q[state][action] += alpha * (reward + gamma * best_next - Q[state][action])
            state, steps = new, steps + 1
        history.append(steps)
    return Q, history

def greedy_path(Q):
    state, path = START, [START]
    while state != GOAL and len(path) < 50:
        state, _ = step(state, max(Q[state], key=Q[state].get))
        path.append(state)
    return path

if __name__ == "__main__":
    Q, history = train()
    for a, b in ((0, 10), (10, 50), (50, 100), (100, 300)):
        print(f"episodes {a + 1:3}-{b:3}: average {sum(history[a:b]) / (b - a):5.1f} moves")
    path = greedy_path(Q)
    print("learned route:", len(path) - 1, "moves")
    for r in range(ROWS):
        print(" ".join("G" if (r, c) == GOAL else "#" if ROOM[r][c] == "#"
                       else max(Q[(r, c)], key=Q[(r, c)].get) for c in range(COLS)))

Output:

episodes   1- 10: average  36.3 moves
episodes  11- 50: average  10.3 moves
episodes  51-100: average   9.9 moves
episodes 101-300: average  10.2 moves
learned route: 8 moves
v < < < <
v # # v ^
v # v < #
> > v # ^
# > > > G

In the first episode the robot wandered for 147 moves. Within about a dozen episodes it needed 8 to 16, and the policy it ended with reaches the dock in 8 moves, the shortest possible. During training the average stays near 10 rather than 8, because one move in five is still a deliberate random experiment. For comparison, a robot that only ever moves at random needed about 223 moves on average to reach the dock (1000 simulated runs).

5Hands-on: make the robot learn

1. Run qlearn.py and check the output matches the lesson.
2. Move the desks: change ROOM so that the old route is blocked, and run it again. How many moves is the new learned route? Is it the shortest? (Check with the breadth-first search from lesson 2.)
3. Change epsilon to 0.0 and then 0.5. Record the average moves for episodes 101 to 300 and the length of the learned route. Explain the differences.
4. Remove the −5 bump penalty (make it −1). Does the robot still learn? Does it learn as fast?
5. (Extension) Add a "wet floor" square with reward −3 and see whether the robot learns to avoid it.

Check: you can explain every change in your results using the update rule and the rewards.