AO* Algorithm Explained 

AO* finds solutions to problems that are divided into subproblems, some choices being independent, while others must be solved jointly.

This tutorial introduces the algorithm, works through a full problem example, and then implements it in code.

What Is the AO* Algorithms?

AO means AND-OR. AO* algorithm is an algorithm for heuristic search of a solution in AND-OR graph. The term AO* was coined by Nilsson in 1980 on the basis of work on AND-OR graph search by Martelli and Montanari in 1973 and 1978. It extends A* algorithm for search in graphs with both AND and OR nodes.

AO* is referred to as an abbreviation for Anytime Optimistic algorithm in several publications. This explanation of the meaning of AO* is inconsistent with the history of the term and its definition. First, AO* is not an anytime algorithm in the accepted meaning in AI; second, AO* is an algorithm for AND-OR graph search and not an optimistic cost estimation procedure.

Problems solvable using AO* are divided into subproblems in such a way that some of them need to choose between several options and other subproblems need to solve several parts simultaneously. Such problems appear in planning problems, in problems related to decomposition of problems, and in expert systems reasoning several conditions before making a decision.

AND-OR Graphs: OR Nodes and AND Nodes

The AND-OR graph consists of nodes and arcs, with two kinds of arcs defining different ways of solving a problem.

An OR node is solved when at least one of its child nodes is solved. The OR node is a node which has a label A, with its two child nodes B and C linked to the parent node via ordinary arcs. Solving the problem through B is enough. Solving the problem through C is enough. The algorithm will pick the node that results in the minimum cost.

An AND node is solved only when every one of its child nodes is solved. For instance, the node with the label A and two children, D and E, linked via an AND arc is the AND node. In order to solve the problem, it is necessary to solve both nodes D and E. The cost of solving an AND node will equal the sum of the cost of solving all of its children.

A single AND-OR graph can contain both node types at different points. A search algorithm must apply the OR rule at OR nodes and the AND rule at AND nodes within the same traversal.

Node Type	Solved Condition	Cost Formula	Example Structure
OR node	At least one child is solved	Minimum of (edge cost + child cost) across children	A → B, A → C
AND node	All children are solved	Sum of (edge cost + child cost) across all children	A → D and A → E

The Math Behind AO*: Heuristic and Cost Functions

For AO*, there are two types of costs assigned to each node.

The first is the h(n) which acts as an estimate of the cost required to get from the current node to the goal state. This is an estimate since it is not an actual measure of the cost but acts as an indicator of where to search for lower cost paths.

The second is f(n) = g(n)+h(n). In this equation, g(n) is the actual cost required from the initial node to the current node and h(n) is the cost required from the current node to the goal state.

The cost computation varies according to the type of node:

• For an OR node, the cost f(n) is equal to the lowest cost of c(n,n_i)+f(n_i). The cost of only one child is counted for the parent.
• For an AND node, the cost f(n) is the sum of c(n,n_i)+f(n_i) of all its children. All the children are considered to calculate the cost of the parent.

Once a node is expanded and the cost of its children nodes is calculated, the cost of the parent node is updated in the backpropagation step. Backpropagation starts from the expanded node to the start node. Backpropagation might make the algorithm think that another path is cheaper than the already selected path.

How AO* Works: Step-by-Step Procedure

AO* uses a cyclic process of selection, expansion, and cost update till the start node is solved.

1. The start node is initialized using its heuristic value. In this stage, there are no children nodes formed yet.
2. Selection of the most promising unexpanded node is done by considering the currently cheapest path from the start node towards the selected node.
3. Expansion of the selected node takes place by generation of its successor nodes with the initial heuristic values calculated for them.
4. A node is considered as solved either if it has no children or if it solves the goal itself.
5. The costs of the selected node will be back propagated upwards to the start node using the OR-node minimum criterion or the AND-node sum criterion at each node.
6. This selection process will be continued using the updated costs. The currently cheapest path may end up as being more costly than another path after expansion.
7. The process will terminate once the start node becomes solved or when no path exists to form a better solution.

A Worked Example: Tracing AO* by Hand

In this segment, AO* algorithm is followed for the given seven-node graph with cost and heuristics value. This is done since the given graph and cost value are the same as given in the program in the next segment so that the result of the output can be compared.

Graph Structure:

• A is the OR node having two options B (cost of edge 1) and C (cost of edge 1).
• B is the AND node which needs both D (cost of edge 2) and E (cost of edge 2).
• C is the OR node having two options F (cost of edge 1) and G (cost of edge 5).
• D, E, F, and G are goal nodes with a heuristic value of 0.

Initial heuristic estimates before expansion: h(B) = 2, h(C) = 3.

Step 1 — Evaluate both options at A without expanding further. f(A via B) = c(A,B) + h(B) = 1 + 2 = 3 f(A via C) = c(A,C) + h(C) = 1 + 3 = 4 The path through B has a lower estimated cost (3 versus 4), so the algorithm expands B next.

Step 2 — Expand B and compute its true cost. B is an AND node, so its cost is the sum of both children. f(B) = (c(B,D) + h(D)) + (c(B,E) + h(E)) = (2 + 0) + (2 + 0) = 4 Backpropagate this value to A: f(A via B) = c(A,B) + f(B) = 1 + 4 = 5

Step 3 — Compare the updated cost to the unexpanded alternative. The updated f(A via B) is 5. The path through C still has its original estimate of f(A via C) = 4. The path through C is now cheaper, so the algorithm switches and expands C next.

Step 4 — Expand C and compute its true cost. C is an OR node, so its cost is the minimum of its two children. f(C) = min(c(C,F) + h(F), c(C,G) + h(G)) = min(1 + 0, 5 + 0) = 1 Backpropagate this value to A: f(A via C) = c(A,C) + f(C) = 1 + 1 = 2

Step 5 — Final comparison. f(A via C) = 2 is lower than f(A via B) = 5. A is marked solved through C, and C is marked solved through F. The minimum cost solution is 2, following the path A → C → F.

This example shows a case where the path that looks cheapest before expansion (through B) is not the path with the lowest actual cost. The algorithm reaches the correct answer only after expanding both branches and backpropagating the updated costs.

AO* in Python: A Working Implementation

The following code implements AO* on the same graph used in the worked example above. Running this code produces a minimum cost of 2 and a solution path of A → C → F, matching the hand calculation in the previous section.

python
graph = {
    'A': {'type': 'OR', 'children': [('B', 1), ('C', 1)]},
    'B': {'type': 'AND', 'children': [('D', 2), ('E', 2)]},
    'C': {'type': 'OR', 'children': [('F', 1), ('G', 5)]},
    'D': {'type': 'OR', 'children': []},
    'E': {'type': 'OR', 'children': []},
    'F': {'type': 'OR', 'children': []},
    'G': {'type': 'OR', 'children': []},
}

heuristic = {'A': 0, 'B': 2, 'C': 3, 'D': 0, 'E': 0, 'F': 0, 'G': 0}

cost = {}
solved = {}
solution_graph = {}

def ao_star(node):
    if not graph[node]['children']:
        cost[node] = heuristic[node]
        solved[node] = True
        return cost[node]

    if solved.get(node, False):
        return cost[node]

    node_type = graph[node]['type']

    if node_type == 'OR':
        min_cost = float('inf')
        best_child = None
        for child, edge_cost in graph[node]['children']:
            child_cost = edge_cost + ao_star(child)
            if child_cost < min_cost:
                min_cost = child_cost
                best_child = child
        cost[node] = min_cost
        solution_graph[node] = [best_child]

    elif node_type == 'AND':
        total_cost = 0
        children_list = []
        for child, edge_cost in graph[node]['children']:
            total_cost += edge_cost + ao_star(child)
            children_list.append(child)
        cost[node] = total_cost
        solution_graph[node] = children_list

    solved[node] = True
    return cost[node]

result = ao_star('A')
print("Minimum cost:", result)
print("Solution Graph:", solution_graph)

Output:

Minimum cost: 2
Solution Graph: {'B': ['D', 'E'], 'C': ['F'], 'A': ['C']}

AO* vs. A*: Key Differences

A* and AO* both use the evaluation function f(n) = g(n) + h(n), but they apply it to different graph structures.

Dimension	A* Algorithm	AO* Algorithm
Graph type searched	OR graphs only	AND-OR graphs
Node cost rule	Minimum cost path only	Minimum for OR nodes, sum for AND nodes
Data structure	OPEN and CLOSED lists	Single GRAPH structure with pointers to successors and predecessors
Output	A single path from start to goal	A solution subgraph, which may include multiple branches
Applies to	Simple pathfinding problems	Problems that decompose into interdependent subproblems
Optimality	Optimal with an admissible heuristic	Optimal with an admissible heuristic, restricted to acyclic graphs

Where AO* Is Used

AO* is used for problems that can be divided into interdependent subproblems, where some of the elements need to be solved together.

• The automated planning system uses AO* to solve planning problems in which the plan consists of multiple dependent actions, in which the accomplishment of the plan requires the satisfaction of multiple conditions.
• The expert system employs AO* to assess decision trees involving alternative options together with required conditions.
• The problem decomposition involves solving a problem by decomposing it into a set of interrelated subproblems and merging their solutions.
• Path planning in robotics includes AO* for sequencing a set of multiple actions needed to perform a certain objective.

The literature review about AND-OR graph search states that AO* was introduced in early AI books, but it has been displaced by other methods such as LAO* in many modern algorithms due to the presence of cycles in AND-OR graphs.

Advantages and Limitations

Advantages:

• It does not expand branches whose cost exceeds the currently lowest cost estimate, resulting in a lower number of nodes evaluated overall.
• It is able to solve tasks with interrelated subproblems that cannot be expressed by algorithms using one path, such as A*.
• It outputs a subgraph instead of one path.

Limitations:

• The requirement for an admissible heuristic function in order to obtain the optimal solution; otherwise the result obtained is a sub-optimal solution.
• Normal AO* algorithm fails in handling graphs having cycles, which are handled by LAO* algorithm.
• Memory usage depends on the size of the graph, due to the fact that the graph is stored explicitly by the algorithm.

Frequently Asked Questions