While reading AI: A Modern Approach (4th ed), I have some difficulty in coming to terms with the usefulness of a satisficing search. Generally speaking, I understand that in real life situations we are often happy with a good enough solution for many problems. But when we are modeling a problem solving agent in AI, searching and executing are separate actions.

So how does finding a solution path quicker compensate for lost inefficiency in executing a suboptimal action (like in unbounded-cost search algorithm such as speedy search) -- assuming that in real world, execution costs (fuel, energy, time etc.) are usually higher than computation costs? A real world example will be helpful here.

Here is the text from the relevant following section of the book.

Section 3.5.4 Satisficing search: Inadmissible heuristics and weighted A*

(text omitted)

There are a variety of suboptimal search algorithms, which can be charaterized by the criteria for what counts as "good enough". In bounded suboptimal search, we look for a solution that is guaranteed to be within a constant factor W of the optimal cost. Weighted A* provides this guarantee. In bounded-cost search, we look for a solution whose cost is less than some constant C. And in unbounded-cost search, we accept a solution of any cost, as long as we can find in quickly.

An example of an unbounded-cost search algorithm is speedy search, which is a version of greedy best-first search that uses as a heuristic the estimated number of actions required to reach a goal, regardless of the cost of those actions. Thus for problems where all actions have the same cost it is the same as greedy best-first search, but when actions have different costs, it tends to lead the search to find a solution quickly, even if it might have a high cost.

  • $\begingroup$ I found a paper which suggests an application in real time signal processing where computational savings (time & memory) of choosing a sub-optimal path can be significant (page 15). If my knowledge grows enough in time, I might improve the question or add an answer! $\endgroup$
    – senseiwu
    Feb 3 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.