AO*is a best-first algorithm for solving a cyclic AND/OR graphs. Starting with a partial graph G containing only the initial states0 , two operations are perfor mediteratively : first, a best partial policy over G is constructed and a non-terminal tip state s reachable with this policy is expanded ; second, the value function and best policy over the updated graph are incrementally recomputed. This process continues until the best partial policy is complete. The second step, called the cost revision step, exploits the acyclicity of the AND/OR graph for recomputing the optimal costs and policy over the partial graph G in as inglepass, unlike Value Iteration. In this computation, the states outside G are regarded as terminal states with costs given by their heuristic values. When the AND/Or graph contains cycles, however, this basic costrevision operation is not adequate. In this paper, we use the AO* variant developed in (Jimen´ez&Torras2000),called CFCrev, which is based in the cost revision operation and is able to handle cycles.

1. Initialise the graph to start node
2. Traverse the graph following the current path accumulating nodes that have not yet been expanded or solved
3. Pick any of these nodes and expand it and if it has no successors call this value FUTILITY otherwise calculate only f’ for each of the successors.
4. If f’ is 0 then mark the node as SOLVED
5. Change the value of f’ for the newly created node to reflect its successors by back propagation.
6. Wherever possible use the most promising routes and if a node is marked as SOLVED then mark the parent node as SOLVED.
7. If starting node is SOLVED or value greater than FUTILITY, stop, else repeat from 2.