Cheatography

AO* Search Cheat Sheet (DRAFT) by creedorian

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.

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.