AAAI Publications, Ninth Annual Symposium on Combinatorial Search

Font Size: 
Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs
Nathan R. Sturtevant

Last modified: 2016-06-20

Abstract


The Jump Point Search (JPS) algorithm is designed explicitly for search on grids; it uses grid-specific properties to reduce symmetry and provide faster optimal search without pre-computation. Recent work has broken the algorithm down into three components: a best-first search, a canonical ordering of states, and a jumping policy. This paper shows how a canonical ordering can be built on general graphs and used in a similar manner to the canonical ordering of JPS. This approach is able to significantly reduce the number of states generated by an A* search, but more work is needed to optimize and fully characterize the correctness of the approach.

Keywords


search; heuristic; canonical ordering

Full Text: PDF