Informed (or heuristic) search strategies

It is also called heuristic search: it uses additional informations beyond problem definition.

• $f(n)$ is the evaluation function, It extracts from the frontier the nodes with minimum path cost. $f:Nodes\rightarrow \mathbb{R}$

• $g(n)$ is the path cost function, which is the cost to reach a node $n$ from the initial state. If $f(n)=g(n)$ then we get UCS.

• $h(n)$ is the heuristic function, which is an estimation of the cost of the cheapest path from node $n$ to a goal node.

Informed search strategies differ basing on the choice of $f(n)$.

• $f(n)=g(n)$: UCS (uninformed).

• $f(n)=h(n)$: Greedy BFS. Greedy because we will select nodes of the frontier basing on our estimation of the cost to reach the goal.

• $f(n) = g(n) + h(n)$: it represent the whole path from the root node to the goal node, passing trough n. It is called A search*.

Properties of heuristic functions

#### Admissibility (tree-search)

$h(n)$ is admissible if it never overestimates the cost of the cheapest path to get to the goal node, which means that:

$$\forall s \in S, \hspace{0.3em} h(s) \le C^*(s)$$

Where $C^*(s)$ is the minimum cost to get from $s$ to a goal state. How do we find an admissible heuristic? An admissible heuristic can usually be seen as the cost of an optimal solution to a relaxed problem, obtained by removing constraints).

Tree-search is complete and optimal iff $h(s)$ is admissible.

Consistency (graph-search)

$h(n)$ is consistent (or monotonic) if for every pair of nodes $n$ and $n'$ of the search tree such that $n$' is a successor of $n$:

With $c()$ which is the cost function.

Graph-search is complete and optimal iff $h(s)$ is complete.

Notes on $h(n)$

If asked to find a proper heuristic for a state space problem, it is useful to think in terms of what is the total cost of getting from the initial state to the goal state (so basically by reasoning in general about the actions we have got to perform in order to get to the goal).

Greedy BFS (GBFS)

$f(n)=h(n)$

We decide which nodes to extract first basing on their heuristic function value. Similar to UCS in this regard but we're checking heuristic value instead of cost.

Properties

• Not complete (it is if $m < \infin$ for tree-search, and if $|S|< \infin$ for graph-search)

• $T(n)=S(n)=O(b^m)$

Node generation/extraction

1. Node generation: add node to frontier (choosing the node with smallest $h$)

2. Node extraction: is it goal? Yes -> stop. Otherwise:

   Is it in the closed list? Yes -> skip it. Otherwise -> add it to closed list, expand.

A*

$f(n)=g(n)+h(n)$

Node extraction/generation

1. Node generation: add node to frontier

2. Node extraction: is it goal? Yes -> stop. Otherwise -> expand.

Notes

• A* can be either tree-search mode, or graph-search mode. The latter has the closed list implementation.

• A* is optimally efficient if no other optimal algorithm is guaranteed to expand fewer nodes than A* using the same heuristic.

• Weighted A*: A* variant with the following evaluation function:

  $$f(n)=g(n)+W*h(n), \hspace{0.3em} W > 1$$