Navigation and route planning

Learn

What you’ll learn

• Dead reckoning and why it drifts
• The wall follower (right-hand rule) for mazes
• How robots plan the shortest route: flood fill and A*

Dead reckoning

Work out position from movement: “I drove 50 cm and turned 90°, so I’m here.” It needs encoders or a gyro, and small errors add up, so robots correct it with landmarks, walls or lines.

Wall following (right-hand rule)

Keep your right hand on the wall and walk. In a maze whose walls are all connected, you’ll always reach the exit. It’s easy to code with a side distance sensor:

Situation	Action
Wall ahead	Turn left
No wall on the right (gap)	Turn right gently, into the gap
Too close to the right wall	Steer left a little
Otherwise	Go straight

It isn’t the shortest route, though.

Shortest routes

• Flood fill: used by Micromouse robots. Number each square by its distance from the goal (goal = 0, neighbours = 1, …). Then always move to a neighbouring square with a lower number.
• A* (A-star): explores the most promising squares first, using distance-so-far plus an estimate of distance-to-go. Used in games, warehouse robots and sat-navs.
• Both need a map: the robot explores first, then plans.

Examples

Example: the right-hand rule in code

function loop() {
  if (distance() < 15) motors(-40, 40);             // wall ahead: turn left
  else if (distanceRight() > 30) motors(60, 40);    // gap on the right: gentle right
  else if (distanceRight() < 12) motors(40, 60);    // too close: steer left
  else motors(60, 60);
}

This reached the goal in the RoboLearn maze in about 55 seconds when we tested it.

Example: flood fill numbers

 4 3 2 3
 5 ■ 1 ■
 6 ■ 0 1     (0 = goal, ■ = wall)

From the 6 in the corner, step to 5, 4, 3, 2, 1, 0: always to a lower number.

Practice

Try it

Maze

▶ Run↺ Reset

Your code (JavaScript)Load starter code

Robot commands

• motors(left, right): wheel power, −100 to 100
• lineLeft(), lineRight(): true over the black line
• distance(): cm to the nearest thing ahead (max 200)
• distanceLeft(), distanceRight(): cm to the sides
• linePosition(): where the line is, −1 (left) to 1 (right), or null
• millis(): milliseconds since Run
• print(value): show a message below
• setup() runs once; loop() runs 50 times a second

Solve itEasy

Use the right-hand rule code from the Examples tab to reach the green goal.

FasterMedium

Tune the speeds and distances to reach the goal in under 45 s.

Left-hand ruleHard

Rewrite the follower to use the left wall instead. Is it faster or slower in this maze, and why? Mirror every turn and use distanceLeft(). In this maze it’s slower: the left-hand route runs along the outer wall and visits more dead space before reaching the goal. Which hand is faster depends on the maze.

Quick check

1. Why does dead reckoning drift?

Small measurement errors add upThe maze movesBatteries chargeIt doesn’t

2. The right-hand rule always…

Finds the shortest routeReaches the exit in a maze with connected wallsNeeds a cameraFails

3. In flood fill, a robot moves to a neighbour with…

A higher numberA lower numberThe same numberAny number

Check my answers