A Start Search

Informed or Heuristic Search Artificial Intelligence

A* Search

Use knowledge about the problem domain to explore the search space more efficiently Domain knowledge is contained in a heuristic (evaluation) function

CS 4633/6633 Artificial Intelligence

CS 4633/6633 Artificial Intelligence

Heuristic Functions

Heuristic: problem-specific knowledge that reduces expected search effort. Heuristic functions evaluate the relative desirability of expanding a node. Heuristics are often estimates of the distance, or cost, from the current state to the goal Time spent evaluating the heuristic function must be recovered by a reduction in search time.

¡ ¡ ¡ ¡

Notation

h(n) = estimated cost of the cheapest path from the state at node n to a goal state Require that h(n) = 0 if n is a goal state

CS 4633/6633 Artificial Intelligence

CS 4633/6633 Artificial Intelligence

Examples

1 7 6 2 8 3 4 5 3 6 1 4 7 2 5 8

Best-first search

Nodes on frontier (or fringe) of search tree are stored in open list Implement open list as a priority queue in which nodes are sorted according to some heuristic evaluation function The node that is expanded next is the one that seems “best” according to the evaluation function

Initial State

Goal

Heuristic Function 1: Number of misplaced tiles Heuristic Function 2: Total Manhattan distance

CS 4633/6633 Artificial Intelligence

CS 4633/6633 Artificial Intelligence

Greedy Search

Korf calls this “pure heuristic search” in his survey paper The priority queue is sorted in increasing order of h(n) The frontier node that is thought to be “closest” to the goal state is always expanded next

CS 4633/6633 Artificial Intelligence

Characteristics of Greedy Search

Resembles depth-first search (prefers a single path until it hits a dead-end.) Not optimal. Why? Not complete. Why? Worst case time complexity O(bm) where m is the maximum depth of search Space complexity same as time...