A* Search

Basic Components:

Search space – nodes connected by actions

          Initial state

          Goal state

Cost function – cost of movement from one node to another

This yields path-cost function – g(x) – which gives cost of reaching current node from initial node

Heuristic function – estimate of cost to reach goal from given node

          This is given as h(x)

          Heuristic must be admissible, i.e., it never underestimates

Total cost estimated – f(x) = g(x) + h(x)

Data structure to hold current search information

          List, L, of leaf nodes ordered by f(x)

                   Each node consists of ::

current state info & path & path-cost [g(x)]

Algorithm:

1.     Place node containing initial state, along with empty path and g(x) = 0 on L.

2.     Examine node at head of L.  If it is not goal, goto 3; if it is goal:

a.     Stop

b.     Return path attached to that node

3.     Expand node at head of L, calling it headNode.

a.     Find all states neighboring current state

b.     Create node for each, calling it newNode

c.      Calculate g(x) for each – g(newNode) = g(headNode) + travelCost,

Where travelCost is cost of getting from one node to another

d.     Calculate h(x) for each, by applying heuristic function

e.      Let f(x) = g(x) + h(x)

f.       Place each node into L according to the value of f(x).

4.     Goto 2