Pathfinding systems that operate on uniform-cost grid maps are common in the AI literature and application areas such
as robotics and real-time video games. Typical speed-up en-hancements in such contexts include reducing the size of the search space using abstraction[Botea et al., 2004]and devel-oping new heuristics to more accurately guide search toward the goal[Sturtevant et al., 2009]. Though effective each of these strategies has shortcomings. For example, abstraction methods usually trade optimality for speed. Meanwhile, im-proved heuristics usually require significant extra memory.My research proposes to speed up grid-based pathfinding by identifying and eliminating symmetric path segments from the search space. Two paths are said to be symmetric if they are identical save for the order in which the individual moves(or steps) occur. To deal with path symmetries I decom-pose an arbitrary grid map into a set of empty rectangles and remove from each rectangle all interior nodes and possibly some from along the perimeter. A series of macro edges are then added between selected pairs of remaining nodes in or-der to facilitate provably optimal traversal through each rect-angle. The new algorithm, Rectangular Symmetry Reduction (RSR), can speed up A* search by up to 38 times on a range of uniform cost maps taken from the literature. In addition to being fast and optimal, RSR requires no significant extra memory and is largely orthogonal all existing speedup tech-niques. When compared to the state of the art, RSR often shows significant improvement across a range of benchmarks