### 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.

### Summary

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.