Improving the combination of JPS and Geometric Containers

Yue Hu, Daniel Harabor, Long Qin, Quanjun Yin, Cong Hu

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

The JPS family of grid-based pathfinding algorithms can beimproved with preprocessing methods such as GeometricContainers. However, such enhancements require a Dijkstrasearch for every node in the grid and the space and time costsof all this additional computation can be prohibitive. In thiswork we consider an alternative approach where we run Dijk-stra only from every node where a jump point is located. Wealso compute and store geometric containers only for thoseoutgoing edges which are consistent with the diagonal-firstordering in JPS. Since the number of jump points on a gridis usually much smaller than the total number of grid cells,we can save up to orders of magnitude of time and space.In addition to improving preprocessing overheads, we alsopresent a partial expansion strategy which can improve theperformance of online search by reducing the total number ofoperations on the open list.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling
EditorsJ. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages209-213
Number of pages5
Volume29
Publication statusPublished - 5 Jul 2019
EventInternational Conference on Automated Planning and Scheduling 2019 - Berkeley, United States of America
Duration: 13 Jul 201915 Jul 2019
Conference number: 29th
https://icaps19.icaps-conference.org/

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2019
Abbreviated titleICAPS 2019
CountryUnited States of America
CityBerkeley
Period13/07/1915/07/19
Internet address

Cite this

Hu, Y., Harabor, D., Qin, L., Yin, Q., & Hu, C. (2019). Improving the combination of JPS and Geometric Containers. In J. Benton, N. Lipovetzky, E. Onaindia, D. E. Smith, & S. Srivastava (Eds.), Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (Vol. 29, pp. 209-213). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ojs/index.php/ICAPS/article/view/3478/3346