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

2 Citations (Scopus)

Abstract

The JPS family of grid-based pathfinding algorithms can be improved with preprocessing methods such as Geometric Containers. However, such enhancements require a Dijkstra search for every node in the grid and the space and time costs of all this additional computation can be prohibitive. In this work we consider an alternative approach where we run Dijkstra only from every node where a jump point is located. We also compute and store geometric containers only for those outgoing edges which are consistent with the diagonal-first ordering in JPS. Since the number of jump points on a grid is 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 also present a partial expansion strategy which can improve the performance of online search by reducing the total number of operations 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
ISBN (Electronic)9781577358077
Publication statusPublished - 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/
https://ojs.aaai.org/index.php/ICAPS/issue/view/239 (Proceedings)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume29
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

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

Cite this