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.