# Question: In this exercise we will examine hill climbing in the

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

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

b. Construct a non-convex polygonal environment in which the agent gets stuck.

c. Modify the hill-climbing algorithm so that, instead of doing a depth-i 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.

d. Is there some k for which the new algorithm is guaranteed to escape from localminima?

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

b. Construct a non-convex polygonal environment in which the agent gets stuck.

c. Modify the hill-climbing algorithm so that, instead of doing a depth-i 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.

d. Is there some k for which the new algorithm is guaranteed to escape from localminima?

**View Solution:**## Answer to relevant Questions

Compare the performance of A and RBFS on a set of randomly generated problems in the 8-puzzle (with Manhattan distance) and TSP (with MSTâ€”see Exercise 4.8) domains. Discuss your results. What happens to the performance of ...Give precise formulations for each of the following as constraint satisfaction problems:a. Rectilinear floor-planning: find non-overlapping places in a large rectangle for a number of smaller rectangles.b. Class scheduling: ...Consider the following logic puzzle: In five houses, each with a different color, live 5 persons of different nationalities, each of whom prefer a different brand of cigarette, a different drink, and a different pet. Given ...Consider carefully the interplay of chance events and partial information in each of the games in Exercise 6.10.a. For which is the standard expectiminimax model appropriate? Implement the algorithm and run it in your ...Prove each of the following assertions: a. α is valid if and only if True | = α. b. For any a, False | = α. c. α | = β if and only if the sentence (α → β) is valid. d. α ...Post your question