Hosted Pages



Pathfinding Benchmarks



Grid-Based Path Planning Competition



AAAI 2017 Job Fair


AAAI 2017 Workshop on what's next for AI in games


Archived Pages


AAAI16 Student Activities

AAAI15 Student Activities

MAPF 2012 Workshop

AIIDE 2011

GIGA 2011

SoCS 2010

A* Variants

There are many simple variants of the A* algorithm. A*'s performance can be varied by changing the heuristic used, but many other variants arise when changing the weighting on the g-cost and h-cost of a node. Suppose we are sorting nodes in the OPEN list by:

By varying w1 and w2 we can get different behavior. This page has videos for the following variants: Note that these videos speed up over time. If not, some algorithms would take quite a long time to run.

Dijkstra's Algorithm

Dijkstra's algorithm searches uniformly without regard to the heuristic. Thus, when the search starts, you can see it moves outward from the start state in a uniform circle. Dijkstra's algorithm must expand almost every state in the entire map to solve this problem. Dijkstra's algorithm is guaranteed to find the optimal path.

Pure Heuristic Search

Pure heuristic search only looks at heuristic values, and the heuristic values start relatively low, so the search effort first focuses on states near the goal. It eventually makes its way around to the goal. In this example Pure Heuristic Search expands the same states as A*, it just expands them in a different order. Additionally, Pure Heuristic Search will likely not find the optimal path to the goal.

A*

A* is guaranteed to find the optimal path to the goal. Given a consistent heuristic, it is also optimal, in that another algorithm given the same information (heuristic and successor function) cannot do better than A*. In practice many approaches outperform A* because they use better heuristics, do not return optimal solutions, or take advantage of other state-space specific properties.

Weighted A*

Weighted A* focuses its search effort on states with low heuristic values, but does not completely ignore the g-costs like Pure Heuristic Search does. As a result, Weighted A* begins with a much "flatter" search than other algorithms. Once the search proceeds around the map, it quickly finds the goal. Weighted A* does not find optimal paths.

A* with Differential Heuristics

Differential heuristics (also called ALT) can be combined to greatly reduce the work performed by A*. In this example we see that far fewer states are expanded, and that the search is fairly well focused from the start to the goal. The cost is that the heuristics have a larger overhead and may not be valid if the map changes.

Permission is granted to download and use these videos for non-commercial use. If you are using them, please let me know: sturtevant at cs . du . edu.

Downloads

Dijkstra
Pure Heuristic Search
A*
Weighted A* (weight = 10)
A* with 10 differential heurisitcs


© Nathan Sturtevant, All rights reserved.