NBS and BAE* Demos

This demo lets you explore the work performed at different meeting points for bidirectional search, as well as algorithms for bidirectional search. NBS does not assume a consistent heuristic, and does at most 2x the minimal number of expansions under this assumption. (All algorithms must be at least 2x minimal on some problems.) BAE* assumes a consistent heuristic, and thus can do better as a result.

Instructions

1. Drag to select a path and watch an algorithm run (choose NBS, BAE*, or A*)
2. Optionally toggle the heuristic to see its impact on the search
3. The red and blue plotted lines are the respective work in the forward direction. The purple line is the cumulative work by the bidirectional search that meets at that point. The green line is the work done by NBS
4. Click on the plot to see what work is done for each meeting point

Maps:

Related Videos

Selected Related Publications