Answers

U9.1 The configuration space

Planning · University · about 30 min

What this lesson is about

Grow the obstacles by the robot's radius and the robot becomes a point, which is the whole reason planning is tractable.

• Grow the obstacles instead
• How much to grow by
• Seeing it
• What the free space looks like

Questions 7 marks in all

1. [1 mark]A robot has a 10 cm square chassis and can turn freely. By how much, in cm to two decimal places, must the obstacles be grown so the robot is safe as a point at every heading?

   Answer: 7.07 (accept within 0.01). The circle that contains the square at any heading has radius half the diagonal, 10 x sqrt(2) / 2 = 7.07 cm. For the 7 cm BugBot the same working gives 4.95 cm.

2. [1 mark]The simulator models the 7 cm square BugBot as a 3.5 cm circle. Why is that not safe on a real robot?

   1. AThe circle fits inside the square, so a corner of the chassis can reach an obstacle the circle says is clear
   2. BThe circle is too large, so it closes gaps the robot could fit through
   3. CA circle cannot represent the heading, so the plan cannot turn
   4. D3.5 cm is smaller than one grid cell
   Answer: A. Half the side gives the inscribed circle, which is not conservative. The circle around the square, 4.95 cm, is.

3. [1 mark]What is the price of planning with the 4.95 cm circle around the square chassis?

   1. AIt occasionally refuses a gap the robot could have squeezed through straight on
   2. BIt occasionally plans a route that clips an obstacle
   3. CIt makes the configuration space four dimensional
   4. DIt makes planning time grow with the heading resolution
   Answer: A. A conservative model never plans a collision and sometimes rejects a feasible gap. That trade is almost always the right one.

4. [1 mark]For a holonomic robot with a circular footprint, why does the heading drop out of the configuration space?

   1. AA circle occupies the same area whichever way it is facing, so collisions do not depend on heading
   2. BA holonomic robot never changes its heading
   3. CThe heading is always measured separately by the IMU
   4. DPlanners cannot handle more than two dimensions
   Answer: A. C-space for a robot that slides and turns is (x, y, heading), but with a circular footprint the obstacles are the same at every heading.

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

   BLOCK = (80.0, 90.0, 40.0, 16.0)
   MARGIN = 10.0
   bx, by, bw, bh = BLOCK
   print(bw + 2 * MARGIN)
   free = 0
   for x in range(0, 200, 10):
       if not (bx - MARGIN <= x <= bx + bw + MARGIN):
           free += 1
   print(free)
   

   Answer:

   60.0
   13

   Grown by 10 cm on both sides the block spans 70 to 130, 60 cm wide. The lanes at 70, 80, 90, 100, 110, 120 and 130 all touch it, so 13 of the 20 lanes are free.

6. [1 mark]The start and the goal lie in different connected components of the free space. What will a correct planner do?

   1. AReport that there is no route
   2. BFind a route through the narrowest passage
   3. CReturn the route with the fewest collisions
   4. DKeep searching until it finds a route
   Answer: A. No planner can invent a route between components. A complete planner reports that truthfully.

7. [1 mark]A planner mysteriously fails on a map where a route looks possible by eye. What does the page say to look for first?

   1. AA narrow passage only slightly wider than the inflated robot
   2. BA heuristic that underestimates
   3. CToo few obstacles in the map
   4. DA cell size that is too small
   Answer: A. A grid can miss a narrow passage because no cell centre lands in it, and a sampling planner may take a very long time to throw a point into it.

The task: grow the obstacle, shrink the robot

from bugbot import *
connect()

BLOCK = (80.0, 90.0, 40.0, 16.0)      # x, y, width, height on the mat
MARGIN = 6.0                          # the 4.95 cm around the square, plus a little

from bugbot import *
connect()

BLOCK = (80.0, 90.0, 40.0, 16.0)      # x, y, width, height on the mat
MARGIN = 6.0                          # chassis radius 3.5 cm, plus a little

bx, by, bw, bh = BLOCK
print("inflated:", round(bw + 2 * MARGIN, 1))

# with the block grown, the robot is a point, so a lane is free unless the grown block covers it
lo, hi = bx - MARGIN, bx + bw + MARGIN
free = 0
for x in range(0, 200, 10):
    if x < lo or x > hi:
        free += 1
print("free lanes:", free)