4.2b.3 A-Star Search

A* Search

A Search* is a search algorithm that expands the frontier node with the lowest estimated total cost, where $f(n)=g(n)+h(n)$. Here, $g(n)$ is the actual path cost from the start to $n$ as used in UCS, and $h(n)$ is the estimated cost from $n$ to a goal. Like Greedy and UCS, it uses a priority queue, but its ordering is by $f(n)$.

A* is both complete and optimal when the heuristic is admissible and consistent, where

• Admissibility ensures that the algorithm never overestimates the true cost to the goal, such that for any node $n$, it holds that$0\le h(n)\le h^{\ast }(n)$, where $h^{\ast }(n)$ is the true minimal cost from $n$ to the goal.
• Consistency ensures that $f(n)$ is nondecreasing along paths, such that for every transition $n\stackrel{a}{\to }n’$ with step cost $c(n,a,n’)$, it holds that $h(n)\le c(n,a,n’)+h(n’)$, where $n^{\prime }$ is the next node after action $a$ has been applied to it.

A*‘s worst-case time and space complexity are exponential in the depth of the solution, but in practice, a good heuristic can dramatically reduce the number of expanded nodes. It is one of the most widely used search algorithms in AI because it combines the efficiency of heuristic guidance with the guarantees of UCS.

Proof

Implementation