Suppose that actions can have arbitrarily large (finite unbounded) negative cost

Question

Suppose that actions can have arbitrarily large (finite unbounded) negative costs; explain why this possibility would force any optimal algorithm to explore the entire state space. Does it help if we insist that step costs must be greater than or equal to some negative constant c? Consider both trees and graphs. 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? 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, within the context of state-space search, why humans do not drive round scenic loops indefinitely, and explain how to define the state space and operators for route finding so that artificial agents can also avoid looping. Can you think of a real domain in which step costs are such as to cause looping?

Explanation / Answer

a)

Any algorithm that is optimal must find the path with the lowest cost. With the possibility of arbitrarily large negative costs introduced, an optimal solution would have to explore each and every path in the state space to ensure that another path did not contain a negative number that would make it optimal. As a trivial example suppose a path existed to reach a goal state that had a path cost of zero.

Without negative path costs one could safely assume this is the optimal path. However with negative path costs the algorithm would have to explore all other alternatives to find a path that might be negative (and if multiple negative paths exist it would have to find the most negative). For example, uniform-cost search is optimal for positive path costs. However when negative path costs are introduced it's algorithm must be modified since expanding the lowest path cost node is no longer trivial.

b)

It does help if we insist that step costs must be greater than or equal to negative constant c. Now we can figure out the state space because if c is the best case scenario, then paths x can be improved by multiplying c and x with cx. This means the worst path are anything but cx.

c)

If there is no net change to the state and these actions have a negative cost, then the agent will go in a continuous loop.

d)

It would be impractical to drive around scenic loops all the time. We only really want to visit scenic routes once. In order to make it so that we only visit it at most a couple of time, we alter the state space. The state space should have a type of counter that adds plus one each time you visit each spot. This way you can set a limit of how many times you want to visit a route.

e)

A real domain looping can be going into work 9- everyday.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.