AO* ALGORITHM

1. Let G consists only to the node representing the initial state call this node INTT. Compute h' (INIT).

2. Until INIT is labeled SOLVED or hi (INIT) becomes greater than FUTILITY, repeat the following procedure.

(I) Trace the marked arcs from INIT and select an unbounded node NODE.

(II) Generate the successors of NODE . if there are no successors then assign FUTILITY as h' (NODE). This means that NODE is not solvable. If there are successors then for each one called SUCCESSOR, that is not also an ancester of NODE do the following

    (a) add SUCCESSOR to graph G

    (b) if successor is not a terminal node, mark it solved and assign zero to its h ' value.

    (c) If successor is not a terminal node, compute it h' value.

(III) propagate the newly discovered information up the graph by doing the following . let S be a set of nodes that have been marked SOLVED. Initialize S to NODE. Until S is empty repeat the following procedure;

   (a) select a node from S call if CURRENT and remove it from S.

    (b)compute h' of each of the arcs emerging from CURRENT , Assign minimum h' to CURRENT.

    (c) Mark the minimum cost path a s the best out of CURRENT.

    (d) Mark CURRENT SOLVED if all of the nodes connected to it through the new marked are have been labeled SOLVED.

    (e) If CURRENT has been marked SOLVED or its h ' has just changed, its new status must be propagate backwards up the graph . hence all the ancestors of CURRENT are added to S.