Eliminating Path Symmetries From Uniform-cost Grid Maps

Daniel Harabor (ANU - Research School of Computer Science)

CS HDR MONITORING

DATE: 2011-05-20
TIME: 09:30:00 - 10:00:00
LOCATION: NICTA Boardroom
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
My research proposes new techniques for speeding up grid-based pathfinding by identifying and explicitly dealing with symmetries in the search space. Together with my co-authors I have developed two different algorithms to accomplish this: Rectangular Symmetry Reduction (RSR) and Jump Point Search (JPS). RSR is an offline graph pruning technique which facilitates fast exploration of empty areas by decomposing a grid map into a set of empty rectangles. JPS, can be described as an online graph pruning method which speeds up pathfinding by selectively expanding only certain nodes on a grid map called jump points. Both RSR and JPS are entirely orthogonal to existing speedup techniques. Results to date have shown that both RSR and JPS yield state-of-the-art performance, in many cases improving average search times for a search algorithm such as A* by an order of magnitude and more.