Page 390 - Introduction to AI Robotics

10.8 Exercises
Exercise 10.2 373
Represent your indoor environment as a regular grid with a 10cm scale. Write down
the rule you use to decide how to mark a grid element empty or occupied when there
is a small portion overlapping it.
Exercise 10.3
Define path relaxation.
Exercise 10.4
Consider a regular grid of size 20 by 20. How many edges will a graph have if the
neighbors are

a. 4-connected?
b. 8-connected?
Exercise 10.5
Convert a meadow map into a graph using:
a. the midpoints of the open boundaries, and
b. the midpoints plus the 2 endpoints.
Draw a path from A to B on both graphs. Describe the differences.

Exercise 10.6
Apply the A* search algorithm by hand to a small graph to find the optimal path
between two locations.
Exercise 10.7
What is a heuristic function?

Exercise 10.8
Apply wavefront propagation to a regular grid.
Exercise 10.9
Subgoal obsession has been described as a problem for metric planners. Can hybrid
systems which use topological planning exhibit subgoal obsession?
Exercise 10.10
Trulla uses a dot product of 0 or less to trigger replanning, which corresponds to

90 from the desired path. What are the advantages or disadvantages of 90 ?What
would happen if Trulla used 45 or 135 ?
Exercise 10.11
Describe the difference between continuous and event-driven replanning.Which would
be more appropriate for a planetary rover? Justify your answer.