Canonical Orderings on Grids
Full Text: 103.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, S. Rabin. "Canonical Orderings on Grids". International Joint Conference on Artificial Intelligence (IJCAI), (ed: Subbarao Kambhampati), pp 683-689, July 2016.| Keywords: | |
| Category: | In Conference |
| Web Links: | IJCAI |
BibTeX
@incollection{Sturtevant+Rabin:IJCAI16,
author = {Nathan R. Sturtevant and Steve Rabin},
title = {Canonical Orderings on Grids},
Editor = {Subbarao Kambhampati},
Pages = {683-689},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2016,
}Last Updated: July 05, 2020Submitted by Sabina P
