Search Space Reduction Using Swamp Hierarchies

However, there are many domains, work that is perhaps closest to ours is the "dead-end heuristic" such as map-based searches (common in GPS navigation, introduced by Björnsson and Halldórsson (2006). They computer games, and robotics) where the entire use a preprocessing phase to identify areas that are deadends, state-space is given explicitly. Optimal paths for such domains and create an abstract graph whose nodes are these can be found relatively quickly with simple heuristics, areas. Initially, the search is performed on the abstracted especially when compared to the time it takes to explore graph. The areas that were not visited during the search exponentially large combinatorial problems. Relative on the abstracted graph are then ignored when the search is quickness, however, might still not be fast enough in certain performed in the original search space. In addition to identifying real-time applications, where further improvement towards dead-ends, our approach also identifies (and prunes, high-speed performance is especially valued.