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 language | English |
|---|---|
| Title of host publication | Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling |
| Editors | J. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava |
| Place of Publication | Palo Alto CA USA |
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Pages | 209-213 |
| Number of pages | 5 |
| ISBN (Electronic) | 9781577358077 |
| Publication status | Published - 2019 |
| Event | International Conference on Automated Planning and Scheduling 2019 - Berkeley, United States of America Duration: 13 Jul 2019 → 15 Jul 2019 Conference number: 29th https://icaps19.icaps-conference.org/ https://ojs.aaai.org/index.php/ICAPS/issue/view/239 (Proceedings) |
Publication series
| Name | Proceedings International Conference on Automated Planning and Scheduling, ICAPS |
|---|---|
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Volume | 29 |
| ISSN (Print) | 2334-0835 |
| ISSN (Electronic) | 2334-0843 |
Conference
| Conference | International Conference on Automated Planning and Scheduling 2019 |
|---|---|
| Abbreviated title | ICAPS 2019 |
| Country/Territory | United States of America |
| City | Berkeley |
| Period | 13/07/19 → 15/07/19 |
| Internet address |
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver