Show Menu
Cheatography
  1. Home >
  2. Programming >

AO* Search Cheat Sheet (DRAFT) by

AO* Search Algorithm Cheatsheet

This is a draft cheat sheet. It is a work in progress and is not finished yet.

AO* search

AO* Search (Anytime Optimistic A) is a variant of the A* search algorithm, designed to find the optimal path in a graph or tree by effici­ently exploring nodes based on their heuristic cost and actual cost. It is called optimistic because it maintains a lower bound estimate of the cost from the current node to the goal node, allowing for more optimistic pruning of the search space. This lower bound estimate helps in guiding the search towards promising regions of the state space.

Key Concepts: (copy)

AO* combines the benefits of A* search with anytime algorithm proper­ties, allowing for iterative improv­ement on solution quality.
It maintains both optimistic and pessim­istic cost estimates to guide the search effici­ently.
The algorithm increm­entally refines the search space and updates the cost estimates to converge towards the optimal solution.

Advantages

 
Allows for anytime perfor­mance: Provides a solution at any point during the search, improving over time.
Guarantees optimality under certain conditions (admis­sible heuris­tic).
Effici­ently prunes the search space by focusing on nodes with promising cost estimates.
  

Working

 
The evaluation function in AO* looks like this:
f(n) = g(n) + h(n)
f(n) = The actual cost of traversal.
g(n) = the cost from the initial node to the current node.
h(n) = estimated cost from the current node to the goal state.

Complexity

 
The time complexity of AO* depends on factors such as the branching factor, the quality of the heuristic function, and the termin­ation condition.
In the worst case of an unbounded search space, the number of nodes expanded is expone­ntial in the depth of the solution (the shortest path) d: O(b^d), where b is the branching factor

Applic­ation

 
1.Path planning in robotics and artificial intell­igence.
2.Game AI for decisi­on-­making and pathfi­nding.
3.Logi­stics and
transp­ort­ation route optimi­zation.
4.Auto­mated planning and scheduling problems.