Canonical Orderings on Grids

Sturtevant, Nathan R.; Rabin, Steve

Canonical Orderings on Grids

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 683-688.

Abstract

Jump Point Search, an algorithm developed for fast search on uniform cost grids, has successfully improved the performance of grid-based search. But, the approach itself is actually a set of diverse ideas applied together. This paper decomposes the algorithm and gradually reconstructs it, showing the component pieces from which the algorithm is constructed. In this process, we are able to define a spectrum of new algorithms that borrow and repurpose ideas from Jump Point Search. This decomposition opens the door for applying the ideas from Jump Point Search in other grid domains with significantly different characteristics from two dimensional grids.

Nathan R. Sturtevant, and Steve Rabin. 2016. Canonical Orderings on Grids. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 683–688. https://ijcai.org/proceedings/2016/103

@inproceedings{ijcai2016p103,
  title     = {Canonical Orderings on Grids},
  author    = {Sturtevant, Nathan R. and Rabin, Steve},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {683--688},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/103},
}

TY  - CPAPER
TI  - Canonical Orderings on Grids
AU  - Sturtevant, Nathan R.
AU  - Rabin, Steve
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 683
EP  - 688
UR  - https://ijcai.org/proceedings/2016/103
ER  -