Search space reduction using swamp hierarchies

In various domains, such as computer games, robotics, and transportation networks, shortest paths may need to be found quickly. Search time can be significantly reduced if it is known which parts of the graph include “swamps”—areas that cannot lie on the only available shortest path, and can thus safely be pruned during search. We introduce an al-gorithm for detecting hierarchies of swamps, and exploit-ing them. Experiments support our claims of improved ef-ficiency, showing significant reduction in search time