3.5 On page 76, we said that we would not consider problems with negative path costs. In this exercise, we explore this in more depth.

a. Suppose that a negative lower bound c is placed on the cost of any given step—that is, negative costs are allowed, but the cost of a step cannot be less than

c. Does this allow uniform-cost search to avoid searching the whole tree?

b. Suppose that there is a set of operators that form a loop, so that executing the set in some order results in no net change to the state. If all of these operators have negative cost, what does this imply about the optimal behavior for an agent in such an environment?

c. One can easily imagine operators with high negative cost, even in domains such as route- finding. For example, some stretches of road might have such beautiful scenery as to far outweigh the normal costs in terms of time and fuel. Explain, in precise terms, why humans do not drive round scenic loops indefinitely, and explain how to define the state space and I operators for route-finding so that artificial agents can also avoid looping.

d. Can you think of a real domain in which step costs are such as to cause looping?