AO* Search (And-Or) Graph – Artificial Intelligence


AO* Search (And-Or) Graph, Advantages and Disadvantages – Artificial Intelligence – Artificial Intelligence

The Depth-first search and Breadth-first search given earlier for OR trees or graphs can be easily adopted by AND-OR graph. The main difference lies in the way termination conditions are determined since all goals following an AND node must be realized; whereas a single goal node following an OR node will do. So for this purpose, we are using AO* algorithm.

Like A* algorithm here we will use two arrays and one heuristic function.

OPEN: It contains the nodes that have been traversed but yet not been marked solvable or unsolvable.

CLOSE: It contains the nodes that have already been processed.

h(n): The distance from the current node to the goal node.

AO* Search Algorithm

Step 1: Place the starting node into OPEN.

Step 2: Compute the most promising solution tree say T0.

Step 3: Select a node n that is both on OPEN and a member of T0. Remove it from OPEN and place it in CLOSE

Step 4: If n is the terminal goal node then leveled n as solved and leveled all the ancestors of n as solved. If the starting node is marked as solved then success and exit.

Step 5: If n is not a solvable node, then mark n as unsolvable. If starting node is marked as unsolvable, then return failure and exit.

Step 6: Expand n. Find all its successors and find their h (n) value, push them into OPEN.

Step 7: Return to Step 2.

Step 8: Exit.

Advantages of AO* Star

  • It is an optimal algorithm.
  • If traverse according to the ordering of nodes.
  • It can be used for both OR and AND graph.

Disadvantages of AO* Star

  • Sometimes for unsolvable nodes, it can’t find the optimal path.
  • Its complexity is than other algorithms.


This article discusses AO* Search (And-Or) Graph, Advantages, and Disadvantages – Artificial Intelligence – Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.

Leave a Comment

Your email address will not be published. Required fields are marked *