[Artificial Intelligence] Heuristic search

Heuristic search

Using Evaluation Functions

• Heuristic(evaluation) function $\hat{f}$ ,to decide which node is the best one to expand next
• Function is based on information specific to the problem domain
• Real valued function of state descriptions
• Expand next the node n having the smallest value of $\hat{f}(n)$-> best-first search or heuristic search
• Terminate when the node to be expanded next is goal node

From Arad to Bucharest

8-puzzle

• The number of misplaced tiles (not including the blank) //TODO

Admissibility of $A^{*}$

• Conditions for $A^{*}$ to find minimal cost path
  • Each node in the graph has a finite number of successors
  • All arcs in graph have costs greater than positive amount $e$
  • Optimistic estimator: for all nodes $n$ in search graph,

$\hat{h}(n) <= h(n)$

It is not difficult to satisfy lower bound condition

• Theorem
  • Under the conditions on graphs and on $\hat{h}, if there is a path with finite cost from start node to goal node, A* is guranteed to terminate with a minimal cost path to goal

More Informed

Two versions of $A^{*}$

• $A1^{*}$, $A2^{*}$, If for all non goal nodes, $\hat{h_1} < \hat{h_2}$ $A2^{*}$ is more informed than $A1^{*}$
• Theorem.
• If $A2^{*}$ is more informed then at the termination of their search on any graph, every node expanded by $A2^{*}$ is also expanded by $A1^{*}$

Heuristics for 8-puzzle

• The Manhattan Distance(not including the blank)

• In this case, only the “3”, “8” and “1” tiles are misplaced, by 2, 3, and 3 squares respectively, so the heuristic function evaluates to 8.
• In other words, the heuristic is telling us, that it thinks a solution is available in just 8 more moves.

• Notation: h(n), h(current state) = 8

• Seek an function whose $\hat{h}$ values are as close as possible to those of actual h function
• Most informed algorithm, $\hat{h} = h$

Relationships among Search Algorithms

Heuristic Functions and Search Efficiency

• 8-Puzzle
• W(n) = sum of the number of tiles in the wrong place
• Allow tile to move directly to goal square
• Sum of the distances that each tile is from its goal square
• Tiles move to an adjacent square even though there may be a tile.
• Relaxed Model

Efficiency of $A^{*}$

• Cost(length) of the path found
• Number of nodes expanded in finding the path
• Computational effort required to compute $\hat{h}$

Search Example-Image segmentation

• Graph G=(N,U): a set of nodes N and a set U of arcs $(n_i, n_j)$
• In a directed arc $n_i$ is called parent and $n_j$ is called successor
• Expansion: identifying successors of a node
• Starting (0 or root) level, last (goal) level
• Cost $c(n_i, n$j)_ associated with an arc
• Path $n_1, n_2, \dots, n_k$, with each $ni$, being a successor of $ni-1$ Cost of a path is the sum of costs of the arcs constituting the path
• Edge element defined between two neighbor pixels p and q $(x_p,y_q),(x_q,y_p)$
• Associate cost with an edge element $H:7$ $c(p,q) = H −[f(p) − f(q)]$