Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs
Lists
Only you see this
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.
BibTeX
@inproceedings{sturtevant2016generalizing,
author = {Nathan R. Sturtevant},
title = {{Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs}},
booktitle = {SOCS},
year = {2016},
doi = {10.1609/socs.v7i1.18400},
}