Yang Shuqi

Informed Search

 
    Idea

    Use an evaluation function $f(n)$ for each node $n$

    Cost estimate -> Expand node with lowest evaluation/cost first

    Implementation

    Frontier = priority queue ordered by nondecreasing cost $f$

    Evaluation function

    $f(n)=h(n)$ (heuristic function) = estimated cost of cheapest path from $n$ to goal

    Idea

    Expands the node that appears to be closest to goal

    Complete Yes (if $b$ is finite, because it’s a queue)
    Optimal No (e.g. a triangle with length 1, 2, 2)
    Time $O(b^m)$, but a good heuristic can reduce complexity substantially
    Space Max size of frontier $O(b^m)$

    $m$ is the depth of the solution

    Idea

    Avoid expanding paths that are already expensive

    Evaluation function

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

    $g(n)$: cost of reaching $n$ from start node

    $h(n)$: cost estimate from $n$ to goal

    $f(n)$: estimated cost of cheapest path through $n$ to goal

    Heuristics

    Admissible Heuristics

    $h(n)$ is admissible, if $\forall n$, $h(n) ≤ h^*(n)$

    $h^*(n)$: true cost to reach the goal state from $n$

    Never overestimates cost to reach goal

    Theorem

    If $h(n)$ is admissible, then $A^$ using *tree search​ is optimal.

    Consistent Heuristics

    $h(n)$ is consistent, if for every node $n$ and every successor $n’$ of $n$ generated by any action $a$, $h(n) ≤ d(n, n’) + h(n’)$

    $f(n)$ is non-decreasing along any path

    Theorem

    If $h(n)$ is consistent, then $A^$ using *graph search​ is optimal.

    Stronger claim: when $A^*$ selects a node $n$ for expansion, the shortest path to $n$ has been found.

    Complete Yes (if there is a finite no. of nodes with $f(n)≤f(G)$)
    Optimal Yes
    Time $O(b^{h^(s_0)-h(s_0)})$ where $h^(s_0)$ is actual cost of getting from root to goal
    Space Max size of frontier $O(b^m)$

    Admissible vs. Consistent Heuristics

    Consistent => Admissible

    Admissible ≠> Consistent

    Dominance

    If $h_2(n)≥h_1(n)$ for all $n$ (both admissible), then $h_2$ dominates $h_1$. It follows that $h_2$ incurs lower search cost than $h_1$.

    The path to goal is irrelevant; the goal state itself is the solution.

    Local search algorithms

    Maintain single “current best” state and try to improve it

    Advantages

    • very little/constant memory
    • find reasonable solutions in large state space

    Use of heuristic function to improve “current” state

    Problem

    Depending on initial state, can get stuck in local maxima

    Non-guaranteed fixed

    • sideway moves

    • random restarts

    Search