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.
-
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?
-
Construct a nonconvex polygonal environment in which the agent gets stuck.
-
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.
-
Is there some $k$ for which the new algorithm is guaranteed to escape from local minima?
-
Explain how LRTA enables the agent to escape from local minima in this case.