AO* Algorithm in Artificial Intelligence

AO* Algorithm:

Our real-life situations can’t be exactly decomposed into either AND tree or OR tree but is always a combination of both. So, we need an AO* algorithm where O stands for ‘ordered’. The AO* algorithm represents a part of the search graph that has been explicitly generated so far. AO* algorithm is given as follows:

Step-1: Create an initial graph with a single node (start node).

Step-2: Transverse the graph following the current path, accumulating node that has not yet been expanded or solved.

Step-3: Select any of these nodes and explore it. If it has no successors then call this value- FUTILITY else calculate f'(n) for each of the successors.

Step-4: If f'(n)=0, then mark the node as SOLVED.

Step-5: Change the value of f'(n) for the newly created node to reflect its successors by backpropagation.

Step-6: Whenever possible use the most promising routes, If a node is marked as SOLVED then mark the parent node as SOLVED.

Step-7: If the starting node is SOLVED or value is greater than FUTILITY then stop else repeat from Step-2.