Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs
Full Text: 13960-61082-1-PB.pdf
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.
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, 2020Submitted by Sabina P
