A and AO Search Techniques

Definition

A* Search:
A* is an informed best-first search algorithm that selects the next node to expand based on the evaluation function:

$$f(n) = g(n) + h(n)$$

where:

• $g(n)$ is the actual cost from the start node to node $n$
• $h(n)$ is the estimated cost from node $n$ to the goal

A* is optimal and complete when the heuristic $h(n)$ is admissible.

AO* Search:
AO is an informed search algorithm used for solving problems represented as AND-OR graphs*. It finds the least-cost solution subgraph by repeatedly expanding the most promising partial solution and updating costs until the entire solution graph is resolved.

---

Main Content

1. First Concept

A* search and its evaluation function

A* combines the cost already incurred with an estimate of the remaining cost. This makes it more intelligent than uninformed search because it prioritizes paths that appear both cheap so far and promising toward the goal.

The formula: $$f(n) = g(n) + h(n)$$ helps A* choose the node with the smallest expected total path cost.

Example:
If a node has:

• $g(n) = 5$ from start
• $h(n) = 3$ estimated to goal
  then: $$f(n) = 5 + 3 = 8$$ A* prefers nodes with lower $f(n)$.

#### Role of heuristic in A\ - * The quality of A* depends heavily on the heuristic. A good heuristic should be:

• Admissible: never overestimates the true cost
• Consistent: estimated cost obeys triangle-like inequality

Better heuristics reduce the number of expanded nodes and improve efficiency. If the heuristic is exact, A* becomes extremely fast because it directly guides the search toward the goal.

2. Second Concept

AO* search and AND-OR graphs

AO is used when a problem can be broken into different choices and subproblems. In an OR node, only one of the child branches must be solved. In an AND node*, all child branches must be solved to complete that part of the problem.

This structure is common in tasks like:

• theorem proving
• expert systems
• planning with subgoals

Simple representation:

  Start
    |
    OR
   /  \
  A    B
      / \
     AND AND
      |   |
      C   D

Here, choosing B may require solving both C and D.

#### Least-cost solution subgraph in AO\ - * AO does not just find a path; it finds a solution graph*. It estimates the cost of partial solutions and updates the best choice as new information is discovered.

Cost propagation is important:

• For OR nodes, choose the minimum-cost child
• For AND nodes, add the costs of all required children

This helps AO* identify the most promising combination of subproblems instead of exploring every possibility blindly.

3. Third Concept

#### Comparison of A* and AO\ - * Although both are heuristic search methods, they solve different kinds of problems:

• A* works on single-path search problems
• AO* works on problem decomposition in AND-OR graphs

A returns the best route from start to goal, while AO returns the best solution graph covering all necessary subgoals.

A* is suitable for:

• route planning
• robot navigation
• shortest path problems

AO* is suitable for:

• task planning
• logic-based problem solving
• structured decision problems

Optimality and termination

Both algorithms can be optimal under proper conditions:

• A* is optimal if the heuristic is admissible
• AO* is optimal if heuristic estimates are accurate enough and costs are correctly updated

However, AO* is more complex because it must deal with partial solutions, node marking, and backtracking when a better subgraph is found.

---

Working / Process

1. Start with the initial state and heuristic values

In A, place the start node in the open list and compute $f(n)=g(n)+h(n)$. In AO, begin with the root of the AND-OR graph and estimate the cost of each alternative and subproblem.

2. Select the most promising node or partial solution

A expands the node with the lowest $f$-value. AO expands the most promising marked node in the current best solution graph. This choice is made using heuristic evaluation and current cost estimates.

3. Update costs and continue until the goal or complete solution graph is found

In A, once the goal node is selected from the open list, the optimal path is traced back. In AO, cost values are propagated upward, and the marked solution subgraph is revised until all required nodes are solved.

A* process sketch:

Start -> generate neighbors -> compute f values -> pick lowest f -> repeat -> goal

AO* process sketch:

Root -> expand best choice -> mark solution branches -> update costs upward -> repeat -> solved graph

---

Advantages / Applications

Efficient search using heuristics

Both A and AO reduce unnecessary exploration by using heuristic estimates, which saves time and computational effort compared to exhaustive search.

Optimal solution capability

When used with admissible heuristics and correct cost handling, these algorithms can produce optimal solutions. This makes them highly valuable in academic and practical AI systems.

Real-world applications

A is used in GPS navigation, robotics, games, and shortest-path routing. AO is used in automated reasoning, planning systems, diagnosis, and expert systems where solving a problem requires solving multiple dependent parts.

---

Summary

• A* is a heuristic search method for finding the least-cost path.
• AO* is a heuristic search method for finding the least-cost solution graph in AND-OR problems.
• Both use heuristic estimates to improve efficiency over blind search.
• Important terms to remember: heuristic, admissible, optimality, AND node, OR node, solution graph