AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 14

Customised Shortest Paths Using a Distributed Reverse Oracle

Authors

Arthur Mahéo,Shizhe Zhao,Afzaal Hassan,Daniel D. Harabor,Peter J. Stuckey,Mark Wallace

Monash University, Faculty of IT, Melbourne, Australia,Monash University, Faculty of IT, Melbourne, Australia,Swinburne University of Technology, Melbourne, Australia,Monash University, Faculty of IT, Melbourne, Australia,Monash University, Faculty of IT, Melbourne, Australia,Monash University, Faculty of IT, Melbourne, Australia


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Track:

Long Papers

Downloads:

Download PDF

Abstract:

We consider the design and implementation of a centralised oracle that provides commuters with customised and congestion-aware driving directions. Computing directions for a single journey is straightforward, but doing so at city-scale, in real-time, and under changing conditions is extremely challenging. In this work we describe a new type of centralised oracle which combines fast database-driven path planning with a query management system that distributes work across a small commodity cluster of networked machines. Our system allows large-scale changes to the underlying graph metric, from one query to the next, and it supports a variety of query types including optimal, bounded suboptimal, time-budgeted and k-prefix. Simulated experiments show strong results: we can provide real-time routing for all peak-hour commuter trips in the city of Melbourne, Australia.

DOI:

10.1609/socs.v12i1.18554


SOCS

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search