Chapter 3_Informed (Heuristic) Search

Evaluation Function

• for each node on the fringe returns a number that signifies the promise or the potential of that node

• One key type of knowledge it uses is an estimate of the cheapest path cost from the current state to a goal.

Informed Search

• Also called directed or heuristic search;

• tries to reduce the amount of search that must be done by making intelligent choices for the nodes that are selected for expansion.

• The nodes, which are likely to lead to a good solution, are placed towards the front.

• Uses problem-specific knowledge to find solutions faster.

Heuristic Function

• Calculates an estimate of the cheapest path cost from a state to the goal.

• Evaluates the promise of a state;

• the next node to expand is chosen using this value.

• Does not evaluate operators

• doesn't indicate which operator is most promising.

• Problem-specific;

• different functions are designed or learned for different domains.

• Quality (accuracy) is important for real-life application of the technique.

• can also refer to any technique that may improve average-case performance without necessarily improving worst-case performance.

Heuristics

• From the Greek "heuriskein" (to find, discover);

• defined as "the study of the methods and rules of discovery and invention."

Best-first search,

Greedy best-first search,

A* search,

IDA* search

Informed Search Techniques (4)

Best-First Search

• Uses an evaluation function and always chooses the next node with the best score.

• Exhaustive — it should eventually try all possible paths.

• Uses a queue, but takes the best node (or sorts the queue ascending and takes the first) instead of the first node in line.

• Successors of the best node are evaluated (scored) and added to the list.

• A cost function f(n) is applied to each node;

  • nodes with smaller f(n) values are expanded earlier.

Greedy Search

• Expands the node with the smallest estimated cost to reach the goal (appears closest to the goal).

• Each choice is locally optimized — optimal only when viewed in isolation.

• Similar to depth-first search;

  • tends to follow a single path to the goal.

• Often performs very well and finds good (not always optimal) solutions quickly.

• With a well-chosen heuristic, can perform well with reasonable time and space demands.

A* Search

• Combines uniform cost search and greedy search:

• uses a priority (cost)-ordered queue like uniform cost search,

• and an evaluation function like greedy search to determinate the ordering.

A* Search Properties

• If all costs are positive and the heuristic is admissible, A* terminates and finds the shortest path.

• Like BFS, A* can use a lot of memory — one of its biggest issues, potentially remembering an exponential number of nodes.

Iterative deepening A* (IDA),

Memory-bounded A (MA),

Simplified memory-bounded A (SMA),

Recursive best-first search (RBFS),

Dynamic A (D*)

A* Search Variants (5)

Iterative Deepening A* (IDA*)

• Combines iterative deepening search with A*.

• The space is searched depth-first for successively larger bounds on f(n).

• Complete and optimal like iterative deepening,

• but has linear space requirements compared to A*.

• Does repeated depth-first searches, not limited by a simple depth bound.

• A path is discontinued if its f value exceeds a cutoff value.

• The first cutoff is the heuristic value of the start node;

• later cutoffs use the lowest f(n) among nodes visited but not expanded previously.

Simplified Memory-Bounded A* (SMA*)

• Places a size limit on the queue

• uses memory fully to avoid re-expanding previously expanded nodes.

• Discards least-promising nodes when needed to keep the queue within the size limit,

• while retaining enough information to quickly regenerate them if needed.

• If memory is full and a new node must be generated:

  • remove the highest f-value leaf from the queue,

• and remember the f-value of the best "forgotten" child in each parent node.