Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs

Proceedings of the International Symposium on Combinatorial Search, 9

Volume

Vol. 9 No. 1 (2016): Ninth Annual Symposium on Combinatorial Search

Short Papers

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.

10.1609/socs.v7i1.18400