Worksheet

U8.6 Frontiers

Mapping · University · about 30 min

What this lesson is about

The edge between what is known and what is not, and why a map with holes is still useful.

• The definition
• From cells to targets
• Watching exploration saturate
• Shadows
• When it goes wrong

Questions 6 marks in all

1. [1 mark]What does this program print?

   rows = ["FFFU",
           "FOFU",
           "FFFF",
           "UUFF"]
   H, W = len(rows), len(rows[0])
   count = 0
   for r in range(H):
       for c in range(W):
           if rows[r][c] == "F":
               for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                   rr, cc = r + dr, c + dc
                   if 0 <= rr < H and 0 <= cc < W and rows[rr][cc] == "U":
                       count += 1
                       break
   print(count)
   

2. [1 mark]Why is driving to a frontier cell guaranteed to produce new information?

   1. AIt is free, so it can be reached, and it borders a cell no beam has ever reached
   2. BIt is always the cell furthest from the robot
   3. CIt is next to an occupied cell, so the robot will see a wall
   4. DIts log odds are exactly zero

3. [1 mark]Why can a feature map not support frontier exploration?

   1. AAbsence from its list means both "not there" and "never looked", so it cannot say "unknown"
   2. BFeature maps cannot store positions accurately enough
   3. CFeature maps use too much memory for large rooms
   4. DFeature maps have no free cells to drive to

4. [1 mark]Put the frontier exploration pipeline in order.

   Number the lines 1 to 5 to put them in the right order.

   1. Group adjacent frontier cells into regions with a flood fill
   2. Discard regions smaller than the robot
   3. Score each remaining region
   4. Find every free cell with an unknown neighbour
   5. Drive to the best one

5. [1 mark]The robot alternates for ever between two frontiers of equal value on opposite sides of the room. What is the fix?

   1. AHysteresis: keep the current target until it is reached or disappears
   2. BDiscard frontier regions smaller than the robot
   3. CUse eight neighbours instead of four
   4. DLower L_MAX so the map changes its mind faster

6. [1 mark]A small post leaves a wedge of unknown behind it. Why does moving a short distance sideways often beat driving a long way forward?

   1. AA second viewpoint a little apart sees round the post and resolves nearly all of the shadow
   2. BSideways motion gives less odometry error
   3. CThe sensor has a longer range sideways
   4. DDriving forward would make the robot collide with the post

The task: what have I not seen?

Turn on the spot, building a grid as you go. Plot known, then print explored:, the fraction of cells that are no longer unknown, and frontier:, how many free cells have an unknown neighbour.

from bugbot import *
import math
connect()

CELL, W = 5.0, 40
L_OCC, L_FREE, L_MAX, FAR = 0.85, -0.4, 8.0, 170.0
START_X, START_Y = 100.0, 100.0
grid = [0.0] * (W * W)

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/u8-6-frontiers/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

1. Group your frontier cells into connected regions with a flood fill and print how many regions there are.
2. Print the centre of the nearest region bigger than three cells.
3. Work out how wide the shadow of the post is at the far wall, and check it against your map.