Share

## The AO* algorithm

Question

in progress
0

Artificial Intelligence & Machine Learning
3 years
2018-11-19T02:35:57+00:00
2018-11-19T02:35:57+00:00 1 Answer
190 views
Advanced 0
## Answer ( 1 )

The AO* algorithm: Step 1: Place the start node s on open

Step 2: Using the search tree constructed thus far, compute the most promising solution tree T1

Step 3:Select a node n that is both on open and a part of T1. Remove n from open and place it on closed

Step 4: If n is terminal goal node, label n as solved. If the solution of n results in any of n’s ancestors being solved, label all the ancestors as solved. If the start node s is solved, exit with success where T1 is the solution tree. Remove from open all nodes with a solved ancestor

Step 5: If n is not a solvable node, label n as unsolvable. If the start node is labeled as unsolvable, exit with failure. If any of n’s ancestors become unsolvable because n is, label them unsolvable as well. Remove from open all nodes with unsolvable ancestors

Otherwise, expand node n generating all of its successors. For each such successor node that contains more than one sub-problem, generate their successors to give individual sub-problems. Attach to each newly generated node a back pointer to its predecessor. Compute the cost estimate h* for each newly generated node and place all such nodes that do not yet have descendants on open. Next recomputed the values oh h* at n and each ancestors of n

Step 7: Return to step 2