Customised shortest paths using a distributed reverse oracle

Arthur Maheo; Shizhe Zhao; Afzaal Hassan; Daniel Harabor; Peter Stuckey; Mark Wallace

Customised shortest paths using a distributed reverse oracle

Arthur Maheo, Shizhe Zhao, Afzaal Hassan, Daniel Harabor, Peter Stuckey, Mark Wallace

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

1 Citation (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)
Editors	Hang Ma, Ivan Serina
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	79-87
Number of pages	9
ISBN (Electronic)	9781577358701, 9781713834557
Publication status	Published - 2021
Event	International Symposium on Combinatorial Search 2021 - Online, Guangzhou, China Duration: 26 Jul 2021 → 30 Jul 2021 Conference number: 14th https://ojs.aaai.org/index.php/SOCS (Proceedings)

Publication series

Name	14th International Symposium on Combinatorial Search, SoCS 2021
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Number	1
Volume	12

Conference

Conference	International Symposium on Combinatorial Search 2021
Abbreviated title	SoCS 2021
Country/Territory	China
City	Guangzhou
Period	26/07/21 → 30/07/21
Internet address	https://ojs.aaai.org/index.php/SOCS (Proceedings)

Keywords

Real-time Search
Real-life Applications
Time, Memory
And Solution Quality Trade-offs

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

354635667-oaFinal published version, 261 KB

https://ojs.aaai.org/index.php/SOCS/article/view/18554

Cite this

Maheo, A., Zhao, S., Hassan, A., Harabor, D., Stuckey, P., & Wallace, M. (2021). Customised shortest paths using a distributed reverse oracle. In H. Ma, & I. Serina (Eds.), Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021) (pp. 79-87). (14th International Symposium on Combinatorial Search, SoCS 2021; Vol. 12, No. 1). Association for the Advancement of Artificial Intelligence (AAAI). https://ojs.aaai.org/index.php/SOCS/article/view/18554

Maheo, Arthur ; Zhao, Shizhe ; Hassan, Afzaal et al. / Customised shortest paths using a distributed reverse oracle. Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021). editor / Hang Ma ; Ivan Serina. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2021. pp. 79-87 (14th International Symposium on Combinatorial Search, SoCS 2021; 1).

@inproceedings{e00641f54c69437c8567c42d40e3cf82,

title = "Customised shortest paths using a distributed reverse oracle",

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.",

keywords = "Real-time Search, Real-life Applications, Time, Memory, And Solution Quality Trade-offs",

author = "Arthur Maheo and Shizhe Zhao and Afzaal Hassan and Daniel Harabor and Peter Stuckey and Mark Wallace",

note = "Funding Information: Research at Monash University is funded by the Australian Research Council under grants DP190100013, DP200100025 and by a gift from Amazon. Publisher Copyright: Copyright {\textcopyright} 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; International Symposium on Combinatorial Search 2021, SoCS 2021 ; Conference date: 26-07-2021 Through 30-07-2021",

year = "2021",

language = "English",

series = "14th International Symposium on Combinatorial Search, SoCS 2021",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

number = "1",

pages = "79--87",

editor = "Hang Ma and Ivan Serina",

booktitle = "Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)",

address = "United States of America",

url = "https://ojs.aaai.org/index.php/SOCS",

}

Maheo, A, Zhao, S, Hassan, A, Harabor, D , Stuckey, P & Wallace, M 2021, Customised shortest paths using a distributed reverse oracle. in H Ma & I Serina (eds), Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021). 14th International Symposium on Combinatorial Search, SoCS 2021, no. 1, vol. 12, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 79-87, International Symposium on Combinatorial Search 2021, Guangzhou, China, 26/07/21. <https://ojs.aaai.org/index.php/SOCS/article/view/18554>

Customised shortest paths using a distributed reverse oracle. / Maheo, Arthur; Zhao, Shizhe; Hassan, Afzaal et al.

Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021). ed. / Hang Ma; Ivan Serina. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2021. p. 79-87 (14th International Symposium on Combinatorial Search, SoCS 2021; Vol. 12, No. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Customised shortest paths using a distributed reverse oracle

AU - Maheo, Arthur

AU - Zhao, Shizhe

AU - Hassan, Afzaal

AU - Harabor, Daniel

AU - Stuckey, Peter

AU - Wallace, Mark

N1 - Conference code: 14th

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Real-time Search

KW - Real-life Applications

KW - Time, Memory

KW - And Solution Quality Trade-offs

UR - http://www.scopus.com/inward/record.url?scp=85124611568&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:85124611568

T3 - 14th International Symposium on Combinatorial Search, SoCS 2021

SP - 79

EP - 87

BT - Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)

A2 - Ma, Hang

A2 - Serina, Ivan

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

T2 - International Symposium on Combinatorial Search 2021

Y2 - 26 July 2021 through 30 July 2021

ER -

Maheo A, Zhao S, Hassan A, Harabor D , Stuckey P , Wallace M. Customised shortest paths using a distributed reverse oracle. In Ma H, Serina I, editors, Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2021. p. 79-87. (14th International Symposium on Combinatorial Search, SoCS 2021; 1).

Customised shortest paths using a distributed reverse oracle

Abstract

Publication series

Conference

Keywords

UN SDGs

Access to Document

Other files and links

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Personalised Public Transport

Cite this

Customised shortest paths using a distributed reverse oracle

Abstract

Publication series

Conference

Keywords

UN SDGs

Access to Document

Other files and links

Projects

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Personalised Public Transport

Cite this