Exercise 4.15 [path-planning-hc-exercise]

In this exercise, we examine hill climbing in the context of robot navigation, using the environment in Figure geometric-scene-figure as an example.

  1. Repeat Exercise path-planning-agent-exercise using hill climbing. Does your agent ever get stuck in a local minimum? Is it possible for it to get stuck with convex obstacles?

  2. Construct a nonconvex polygonal environment in which the agent gets stuck.

  3. Modify the hill-climbing algorithm so that, instead of doing a depth-1 search to decide where to go next, it does a depth-$k$ search. It should find the best $k$-step path and do one step along it, and then repeat the process.

  4. Is there some $k$ for which the new algorithm is guaranteed to escape from local minima?

  5. Explain how LRTA enables the agent to escape from local minima in this case.

View Answer