A* Search and Heuristics

Heuristic:

  • a function that estimates how close a state is to a goal

  • designed for a particular search problem

Greedy Search:

  • expand the node that looks like it is closest to the goal

A* Search:

  • Combines UCS (g) and Greedy (h)

    • orders by the sum: f(n) = g(n) + h(n)

  • Is A* Optimal?

    • not guaranteed

Admissible Heuristic

  • slow down bad plans but never outweigh true costs

  • h is admissible if 0 ≤ h(n) ≤ h*(n)

    • where h*(n) is the optimal cost to a nearest goal

Creating Admissible Heuristics:

  • Ex: 8 puzzle

    • 9! states

    • can move the tiles to the empty spots

    • assume cost of 1 per tile move

    • possible heuristics:

      • # of tiles in the wrong place

        • why is this admissible?

          • its an underestimate

        • relaxed-problem heuristic

      • what if any tile could move anywhere without regard to the other tiles?

        • total manhattan distance

        • h(start) = 3+1+2+… = 18

      • actual cost

        • Is this admissible?

          • yes

  • As heuristics get closer to the true cost, you will expand fewer nodes but usually do more work per node to compute the heuristic itself

Trivial Heuristics, Dominance:

  • Dominance: h ≥ h if:

    • ∀n : ha(n) ≥ hc(n)

  • heuristics form semi-lattice:

    • max of admissible heuristics is admissible

    • h(n) = max[ha(n) , hc(n)]

  • trivial heuristics

    • bottom of lattice is the zero heuristic

    • top lattice is the exact heuristic

Graph Search:

  • idea: never expand a state twice

  • how to implement:

    • tree search + set of expanded states ('“closed sets”)

    • expand the search tree node-by-node but…

      • before expanding a node, check to make sure its state has never been expanded before

      • if not new, skip it, if new add it to the closed set

  • store the closed set AS A SET, not a list!!

  • Can graph search wreck completeness?

    • no

  • Is this optimal?

    • no

Consistency of Heuristics:

  • idea: estimated heuristic costs ≤ actual costs

    • h(A) ≤ actual cost from A to G

    • h(A) - h(C) ≤ cost(A to C)

Optimality:

  • Tree Search:

    • A* is optimal if heuristic is admissible

    • UCS is a special case (h = 0)

  • Graph Search:

    • A* is optimal if heuristic is consistent

    • UCS optimal (h = 0 is consistent)

  • Consistency implies admissibility