Using Figure 3.31 as your environment:

• Show step-by-step how hill-climbing search would help the robot reach G from S.
  • Decide whether h() or g() is better suited for this.
• 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 with it, and then repeat the process. Show every step.
  • You can explain the methodology while showing an exemplary demo with k=2.
• Is there some k for which the modified version is guaranteed to avoid local minima?

G S. Figure 3.31 A scene with polygonal obstacles. S and G are the start and goal states. G S. Figure 3.31 A scene with polygonal obstacles. S and G are the start and goal states