Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs
Full Text: 13960-61082-1-PB.pdfThe 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.
Citation
N. Sturtevant. "Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs". Symposium on Combinatorial Search, (ed: Jorge A. Baier, Adi Botea), pp 143-144, July 2016.Keywords: | |
Category: | In Conference |
Web Links: | AAAI |
BibTeX
@incollection{Sturtevant:SoCS16, author = {Nathan R. Sturtevant}, title = {Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs}, Editor = {Jorge A. Baier, Adi Botea}, Pages = {143-144}, booktitle = {Symposium on Combinatorial Search}, year = 2016, }Last Updated: July 05, 2020
Submitted by Sabina P