CHAPTER 3 - Informed (Heuristic) Search

evaluation function

The ordering in heuristic search is determined by an __________ ________, which for each node on the fringe returns a number that signifies the promise or the potential of that node.

Cheapest

One of the most important kinds of knowledge to use when constructing an evaluation function is an estimate of the cost of the ________ path from the (current) state to a goal state

Informed search

(also called directed search and 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.

heuristic functions

Functions that calculate such estimates are called _________ ________. We should note that in the AI field the word 'heuristic' is not only in the context of 'heuristic functions' but also used for any techniques that might improve the average case performance but does not necessarily improve worst-case performance.

heuristic functions

used to evaluate the promise of a state. We choose, which node to expand next using the heuristic value of its state. They do not evaluate operators, i.e. if several operators can be used to expand a node, heuristic functions do not say which operator is the most promising one

Problem-specific

Heuristic functions are _______-________. We usually design (or learn) different functions for different problem domains. There are a variety of search techniques that rely on the estimate provided by a heuristic function. In all cases - the quality (accuracy) of the heuristic is important for the real-life application of the technique

Best first, greedy best first, a, ida

4 of the most important informed search techniques (bgai)

Heuristics

(Greek heuriskein = find, discover) can be defined as "the study of the methods and rules of discovery and invention"

Heuriskein - greek word origin of heuristics

Best first search

type of informed search. uses an evaluation function and always chooses the next node to be that with the best score. However, it is exhaustive, in that it should eventually try all possible paths. It uses a queue as in breadth/depth first search, but instead of taking the first node off the agenda (and generating its successors) it will take the best node (or will arrange ascending the queue and then will take the first node).

greedy search

In this type of informed search, the idea is to expand the node with the smallest estimated cost to reach the goal (or the node which appears to be closest to the goal). In an informal way, an algorithm follows this search if it makes a series of choices, and each choice is locally optimized, or, in other words, when viewed in isolation, that step is performed optimally. Similar to depth first search, it tends to follow a single path to the goal.

A* search

combines the uniform cost search and the Greedy search in the sense that it uses a priority (or cost) ordered queue (like uniform cost) and it uses an evaluation function (like Greedy) to determinate the ordering

Iterative deepening, memory bounded, simplified memory bounded, recursive best first, dynamic

5 variants of the a* search (IMSRD)

IDA*

If the idea of iterative deepening search is combined with A, an algorithm called ____ is obtained. The space is searched depth first for successively larger bounds on the heuristic function f(n). Like iterative deepening, it is complete and optimal but it has linear space requirements while compared to A.

SMA*

places a size limit on the queue. it makes full use of memory to avoid expanding previously expanded nodes. It discards the least-promising nodes from the queue, if it needs to, in order to keep the queue within the size limit. However, it keeps enough information to allow these discarded paths to be quickly re-generated should they ever be needed.

SMA*

It works as follows: if memory is full and we need to generate an extra node then:

• Remove the highest f-value leaf from the queue

• Remember the f-value of the best 'forgotten' child in each parent node.