Heuristic Search Algorithms

• A heuristic estimates how close a state is to a goal.
• Heuristics are designed for particular search problems and examples include Manhattan distance and Euclidean distance for pathing.

Informed Search

• Informed search strategies include heuristics, greedy search, A* search and graph search.

Heuristic functions

• The straight-line distance to Bucharest from various cities are:
  • Arad (366), Bucharest (0), Craiova (160), Dobreta (242), Eforie (161), Fagaras (178), Giurgiu (77), Hirsova (151), Iasi (226), Lugoj (244), Mehadia (241), Neamt (234), Oradea (380), Pitesti (98), Rimnicu Vilcea (193), Sibiu (253), Timisoara (329), Urziceni (80), Vaslui (199), Zerind (374).

Greedy Search

• In greedy search, the node expanded is the one that seems closest to the goal.
• A greedy search strategy expands a node believed to be closest to the goal state, using a heuristic to estimate the distance to the nearest goal.
• Greedy search is not optimal because the resulting path to Bucharest may not be the shortest.
• It can get stuck or take a badly-guided path.

A* Search

• Uniform-cost search orders by path cost (backward cost).
• Greedy search orders by goal proximity (forward cost).
• A* Search orders by the sum of path cost and goal proximity: f(n) = g(n) + h(n).
• With A* search, termination should occur when you dequeue a goal, not when you enqueue it.

A* Optimality

• Actual bad goal cost can be less than estimated good goal cost and estimated costs need to be less than actual costs for optimality.

Admissible heuristics

• Admissible heuristics are optimistic and therefore slow down bad plans but never outweigh true costs.
• A heuristic h is admissible if 0 ≤ h(n) ≤ h*(n), where h*(n) is the true cost to the nearest goal.
• Coming up with admissible heuristics is a significant part of using A* in practice.

Optimality of A* Tree Search

• If A is an optimal goal node, B is a suboptimal goal node and h is admissible, then A will exit the fringe before B.
• In A* tree search, imagine B is on the fringe.
• Some ancestor n of A is on the fringe too (maybe A!).
• n will be expanded before B because f(n) is less or equal to f(A) and f(A) is less than f(B).
• All ancestors of A expand before B, A expands before B and A* search is optimal.

UCS vs A*

• Uniform-cost search expands equally in all directions.
• A* search expands mainly toward the goal and hedges it bets to ensure optimality.

Creating Admissible Heuristics

• Most of the work in solving hard search problems optimally is in coming up with admissible heuristics.
• Admissible heuristics are often solutions to relaxed problems, where new actions are available.
• Inadmissible heuristics can also be useful.

8 Puzzle

• An example of a problem is the 8-puzzle where:
  • The states are the arrangement of tiles, and how many there are.
  • The actions possible are based on the space on the board.

8 Puzzle I

• A possible heuristic for the 8 puzzle is the number of tiles misplaced.
• The minimum number of steps is h(start) =8
• 112 nodes need to be expanded to find a solution where the optimal path has four steps, 6,300 nodes when it has 8 steps and 3.6x nodes when it has 12 steps
• This type of problem is relaxed problems

8 Puzzle II

• In an easier 8-puzzle, any tile could slide any direction at any time, ignoring other tiles.
• An admissible heuristic could be the Total Manhattan distance, with an average of 13 nodes expanded for 4 steps, 39 for 8 steps, and 227 for 12 steps. The minimum number of steps is h(start) = 3 +1+2+ = 18 ...

8 Puzzle III

• Using the actual cost as a heuristic:
  • It is admissible.
  • It saves on nodes expanded.
  • The problem is the increase in work needed.
• There is a trade-off between quality of estimate and work per node; as heuristics get closer to the true cost, you expand fewer nodes, but more work per node is done to compute the heuristic itself.

Consistency of Heuristics

• The main idea is that estimated heuristic costs are less than or equal to actual costs.
• Admissibility means heuristic cost ≤ actual cost to goal.
• Consistency means heuristic "arc" cost ≤ actual cost for each arc (h(A) – h(C) ≤ cost(A to C)).
• Consequences of consistency: The f value along a path never decreases (h(A) ≤ cost(A to C) + h(C)) and A* graph search is optimal.

Optimality of A* Search

• Tree A* is optimal with an admissible heuristic.
• Graph A* is optimal with a consistent heuristic.
• With h=0, the same proof shows that UCS is optimal.

Search and Models

• Search operates over models of the world.
• The agent doesn't actually try all the plans out in the real world.
• Planning is all in simulation.
• Your search is only as good as your models.