Artificial Intelligence : Unit - 2 Part - 8 : AO* (And-Or Star) Algorithm

 

UNIT - II

Topic: AO* (And-Or Star) Algorithm

---

Part A: Introduction

---

✅ What is AO* Algorithm?

AO* (And-Or Star) is an informed search algorithm used for problem-solving in AND-OR graphs where a solution may require solving multiple sub-problems together.

Unlike A*, which deals with simple linear paths (OR choices), AO* handles situations where solving a problem may need solving more than one subproblem (AND branches).

---

Part B: AND-OR Graph Overview

---

✅ What is an AND-OR Graph?

• An AND-OR graph represents a hierarchical problem structure.
• Nodes represent states or sub-goals.
• Edges represent actions or transitions.

There are two types of nodes:

Node Type	Meaning
OR Node	The solution can be found by choosing any one of the child nodes
AND Node	The solution requires solving all child nodes together

---

✅ Example:

         A

       /   \

      B     C

           / \

          D   E

• Node A is an OR node → you can solve A by solving either B or C.
• Node C is an AND node → you can solve C only by solving both D and E.

---

Part C: How AO Algorithm Works*

---

✅ AO* uses:

• Heuristics (just like A*)
• A cost function to estimate cost of solving subproblems
• A best-first search strategy using f(n) = g(n) + h(n)

---

Step-by-Step Working of AO* Algorithm

1. Start at the root node
2. Expand the most promising node using a heuristic function
3. If it’s an AND node, expand all of its children
4. Calculate the costs and update parent node's path cost
5. Mark nodes as solved if all their subproblems are solved
6. Backtrack and propagate solution costs upward
7. Stop when the goal node is solved with the minimum cost

---

Part D: AO* Algorithm Pseudocode (Simplified)

AO*(node):

  if node is a goal:

    mark node SOLVED

    return cost

  if node is not yet expanded:

    expand node

  for each successor:

    if AND node:

      cost = sum of children's cost

    if OR node:

      cost = minimum of all child costs

  choose best path (AND/OR)

  update node’s cost

  if all successors are solved:

    mark node SOLVED

  propagate the cost to parent nodes

---

✅ Real-Life Example:

Imagine you want to build a house:

• Goal: Build House (Node A)
• To build it, you can:
• Option 1 (B): Buy a ready-made house (OR)
• Option 2 (C): Build yourself (AND)
• Requires:
• Get land (D)
• Construct (E)

Here, Node C is an AND node, and the decision depends on cost and feasibility.

---

Part E: Features of AO*

Feature	Description
Search Type	Informed search (uses heuristics)
Graph Type	AND-OR Graph
Explores	Multiple paths with both AND & OR relationships
Updates	Cost information is updated dynamically
Goal	Find the most cost-effective solution to the problem

---

Part F: Advantages and Disadvantages

Advantages	Disadvantages
✅ Efficient for problems with multiple dependencies	❌ Complex to implement compared to A*
✅ Uses heuristics to reduce search effort	❌ May not work well without accurate heuristic
✅ Handles non-linear and hierarchical problems	❌ Requires AND-OR graph modeling

---

✅ Applications of AO* Algorithm

• Expert Systems – where solving a problem needs sub-decisions (e.g., Medical Diagnosis)
• Automated Planning – robot task planning
• Problem Reduction – where the main problem is split into subproblems
• Decision Trees – with complex decision-making structures

---

Part G: AO* vs A* Algorithm

Feature	A* Search	AO* Search
Search Type	Informed (Linear paths)	Informed (AND-OR Graphs)
Structure	Tree	Graph with AND/OR nodes
Solves linear problems?	✅ Yes	✅ Yes
Solves subtask chains?	❌ No	✅ Yes (Problem Reduction)
Optimal?	✅ Yes (with admissible h(n))	✅ Yes (with admissible and consistent heuristic)

---

📝 Summary

• AO* is an informed search algorithm for solving problems modeled using AND-OR graphs.
• It works by choosing the most promising path using heuristics and solving all required subproblems.
• AO* is ideal for situations where the solution requires solving multiple dependent tasks.
• It is optimal and complete if the heuristic used is admissible.

Think of AO* as “not just choosing a good path—but solving everything that path depends on.”