Projects per year
Abstract
Compressed Path Databases (CPD) are powerful database driven methods for shortest path extraction in grids and in spatial networks. Yet CPDs have two main drawbacks: (1) constructing the database requires an offline all-pairs precompute, which can sometimes be prohibitive and; (2) extracting a path requires a number of database lookups equal to its number of edges, which can be costly in terms of time. In this work, we consider how CPD methods can be improved and enhanced by: (i) contracting the input graph before preprocessing and; (ii) limiting the preprocessing step to only a selected subset of graph nodes. We also describe a new bi-directional path extraction algorithm which we call CH-CPD. In a range of experiments on road networks, we show that CH-CPD substantially improves on conventional CPDs in terms of preprocessing costs and online performance. We also report convincing query time improvements against a range of methods from the recent literature.
Original language | English |
---|---|
Title of host publication | Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling |
Editors | Susanne Biundo, Minh Do, Robert Goldman, Michael Katz, Qiang Yang, Hankz Hankui Zhuo |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 322-330 |
Number of pages | 9 |
ISBN (Electronic) | 9781713832317, 9781577358671 |
Publication status | Published - 2021 |
Event | International Conference on Automated Planning and Scheduling 2021 - Online, Guangzhou, China Duration: 2 Aug 2021 → 13 Aug 2021 Conference number: 31st https://ojs.aaai.org/index.php/ICAPS/issue/view/380 (Proceedings) |
Publication series
Name | Proceedings International Conference on Automated Planning and Scheduling, ICAPS |
---|---|
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Volume | 2021-August |
ISSN (Print) | 2334-0835 |
ISSN (Electronic) | 2334-0843 |
Conference
Conference | International Conference on Automated Planning and Scheduling 2021 |
---|---|
Abbreviated title | ICAPS 2021 |
Country/Territory | China |
City | Guangzhou |
Period | 2/08/21 → 13/08/21 |
Internet address |
|
Projects
- 4 Finished
-
Improved Constraint Reasoning for Robust Multi-agent Path Planning
Stuckey, P., Harabor, D., Le Bodic, P., Gange, G. & Koenig, S.
1/01/20 → 31/12/24
Project: Research
-
Personalised Public Transport
Harabor, D., Moser, I. & Ronald, N.
24/06/19 → 31/12/24
Project: Research
-
A Ubiquitous System for Indoor Location-Based Services
Australian Research Council (ARC)
1/01/19 → 30/10/23
Project: Research