Search Visualizations

If you're interested in videos of these algorithms in action, you can find those here .

Click on the image on the left for a full resolution version in encapsulated post-script. If you end up using the images for lectures or presentations, or if you have suggestions for new visualizations, I'd love to hear about it.

All of the images on this page are licensed under a Creative Commons Attribution 3.0 Unported License. Use them however you want, just acknowledge the original images as mine.
Image Description
EES expansion order on grids The image on the left shows the expansion order of Explicit Estimation Search on a 4-connected grid path-finding problem. Black cells are obstacles, white cells were unexpanded. Cells which are yellow were expanded very early in the search, while cells that are red were expanded later on.
EES expansion order on grids The image on the left shows the rule by which Explicit Estimation Search selected a node for expansion on a 4-connected grid path-finding problem. Black cells are obstacles, white cells were unexpanded. Nodes expanded in order to raise the lower bound on optimal solution cost are colored in blue, those expanded to pursue the shortest w-admissible solution are colored in red, and nodes expanded because they were estimated to lead to optimal cost solutions are colored in green. See the paper or the talk for a more detailed explanation of the expansion order.
Uniform cost expansion order on grids The image to the left shows the expansion order of uniform cost search on a 4-connected grid path-finding problem. Black cells are obstacles, white cells were unexpanded. Cells which are yellow were expanded very early in the search, while cells that were red were expanded later on. You can see the search radiating evenly outward from the start state.
A* expansion order on grids The image to the left shows the expansion order of A* on a 4-connected grid path-finding problem. Black cells are obstacles, white cells were unexpanded. Cells which are yellow were expanded very early in the search, while cells that were red were expanded later on. You can see the search radiating outward from the start state, the heuristic causing the frontier to be skewed towards the goal.
Weighted A* expansion order on grids The image to the left shows the expansion order of weighted A* on a 4-connected grid path-finding problem. Black cells are obstacles, white cells were unexpanded. Cells which are yellow were expanded very early in the search, while cells that were red were expanded later on. The image shown here is weighted A* running with a weight of 1.3, but the link goes to an archive containing a larger collection of weights. There you can see that as the weight is increased the number of nodes the search examines decreases steadily.
A* epsilon expansion order on grids The image to the left shows the expansion order of A* epsilon on a 4-connected grid path-finding problem. Black cells are obstacles, white cells were unexpanded. Cells which are yellow were expanded very early in the search, while cells that were red were expanded later on. The image shown here is A* epsilon running with a weight of 1.2, but the link goes to an archive containing a larger collection of weights.
Revised Dynamically Weighted A* The image to the left shows the expansion order of Revised Dynamically Weighted A* on a 4-connected grid path-finding problem. Black cells are obstacles, white cells were unexpanded. Cells which are yellow were expanded very early in the search, while cells that were red were expanded later on. The image shown here is A* epsilon running with a weight of 1.8, but the link goes to an archive containing a larger collection of weights.
Anytime A* on Grids This shows where Anytime A* spends its effort when solving a 4-connected grid path-finding problem. Black cells are obstacles, white cells were never expanded during the search. Cells which are yellow were expanded very few times by the algorithm, and as the color becomes redder, the cell was expanded multiple times. This shows that Anytime A* spends a lot of time examining states near the goal, which is at the center of the right hand side of the image.
Anytime Repairing A* on Grids This shows where Anytime Repairing A* spends its effort when solving a 4-connected grid path-finding problem. Black cells are obstacles, white cells were never expanded during the search. Cells which are yellow were expanded very few times by the algorithm, and as the color becomes redder, the cell was expanded multiple times. Much of the bias present in Anytime A* has been removed.
Restarts Weighted A* on Grids This shows where Restarts Weighted A* spends its effort when solving a 4-connected grid path-finding problem. Black cells are obstacles, white cells were never expanded during the search. Cells which are yellow were expanded very few times by the algorithm, and as the color becomes redder, the cell was expanded multiple times. Nearly all of the bias present in the previous two algorithms has been removed.
A* epsilon effort on Grids This shows where A* epsilon is spending its effort when solving a 4-connected grid path-finding problem. Black cells are obstacles, white cells were never expanded during the search. Cells which are yellow were expanded very few times by the algorithm, and as the color becomes redder, the cell was expanded multiple times. The large number of re-expansions near the start of the search is the result of repeated flushing of the focal list, a phenomena we describe here.