polimd/Artificial Intelligence/lesson_06.md

AI - lesson 06

Francesco Arrigoni

28 October 2015

Informed search strategies

Evaluation function $f(n)$ types

Greedy best first

$$f(n)=h(n)$$ $h(n)$ is called heuristic function and is an estimate of how far is a node from the goal

example

• The nodes of the graph are cities and the heuristic function can be the cartesian distance of the cities

• In the game of 15 an heuristic can be an estimate of the number of moves needed to complete the game

By definition the heuristic function is defined over nodes, but commonly are defined over a state, in fact the heuristic function of two nodes referring to the same node is the same.

According to how heuristic functions are defines, there can be loops in greedy best first

Optimality

This strategy is not optimal in general

Complexity

Setting a not clever heuristic function, this strategy is equivalent to the depht first
But with a good heuristic function, we can exploit this to achieve better results. time:$O(b^m)$ space:$O(b^n)$

$A^*$

In this case the evaluation function is defined as $f(n)=g(n)+h(n)$ $g(n)$ is the cost for going from the root to node n $h(n)$ is an estimation of the costs for going from node n to the goal g

Doing so $f(n)$ is the estimated cost of the solution passing through n

Optimality

$A^*$ is optimal when using tree search, that is when the heuristic function is admissible $h^()$ is admissible when $\forall n\;h(n)\le h^(n)$ The heuristic function never overestimates the cost of reaching a node.

Returning to the road example:
The straight distance (line of sight) between two cities is a valid heuristic by definition, in fact the real distance can not be smaller than this.

example

$$f(g_2)=g(g_2)+h(g_2)>c^$$ $$f(n)=g(n)+h(n)\le c^$$ $$f(n)\le c^*<f(g_2)$$

An Heuristic function is consistent if for every node that is a successor of n $$\foralln,n' h(n)\le c(n,n')+h(n')$$

Consistency of heuristic function implies admissibilitu

• $f(n) is not decreasing along every path

$A^*$ will choose nodes from the frontier with value that in a non decreasing order.

Complexity

• Time complexity $O(\square^{|h-h^*|})

If the heuristic function is always zero, $A^*$ degerates in uniform cost.

If we have a perfect heuristic function, the time complexity is constant $A^$ is called optimally efficient, this means that given a fixed heuristic function. $A^$ is guaranteed to expand the minimum number of nodes