Symmetry-Based Search Space Reduction For Grid Maps

Pathfinding on uniform-cost undirected grid maps is a problem commonly appearing in the literature: for example in application areas such as robotics [7] artificial intelligence [12] and video games [3, 11]. In such contexts it is often the case that queries sent to the pathfinding system need to be solved as quickly as possible. Traditionally, this requirement is met through the application of hierarchical decomposition techniques that transform the search space into a much smaller approximate representation [2, 11]. Such methods are very fast, particularly when compared to the classical A* algorithm, but have the disadvantage that solutions found in the abstract state space are often not optimal when mapped back to the original grid. An alternative speedup method is to develop better heuristics to guide the search [1, 10, 5].