A Caltech Library Service

Adaptive Collective Routing Using Gaussian Process Dynamic Congestion Models

Liu, Siyuan and Yue, Yisong and Krishnan, Ramayya (2013) Adaptive Collective Routing Using Gaussian Process Dynamic Congestion Models. In: Proceedings of the 19th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining. Association of Computing Machinery , New York, pp. 704-712. ISBN 978-1-4503-2174-7. (Unpublished)

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We consider the problem of adaptively routing a fleet of cooperative vehicles within a road network in the presence of uncertain and dynamic congestion conditions. To tackle this problem, we first propose a Gaussian Process Dynamic Congestion Model that can effectively characterize both the dynamics and the uncertainty of congestion conditions. Our model is efficient and thus facilitates real-time adaptive routing in the face of uncertainty. Using this congestion model, we develop an efficient algorithm for non-myopic adaptive routing to minimize the collective travel time of all vehicles in the system. A key property of our approach is the ability to efficiently reason about the long-term value of exploration, which enables collectively balancing the exploration/exploitation trade-off for entire fleets of vehicles. We validate our approach based on traffic data from two large Asian cities. We show that our congestion model is effective in modeling dynamic congestion conditions. We also show that our routing algorithm generates significantly faster routes compared to standard baselines, and achieves near-optimal performance compared to an omniscient routing algorithm. We also present the results from a preliminary field study, which showcases the efficacy of our approach.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Yue, Yisong0000-0001-9127-1989
Additional Information:© 2014 ACM, Inc. This research was supported by the T-SET University Transportation Center sponsored by US DoT Grant No. DTRT12-G-UTC11 and the Singapore National Research Foundation under its International Research Centre @ Singapore Funding Initiative and administered by the IDM Programme Office. Yisong Yue was also supported in part by ONR (PECASE) N000141010672 and ONR Young Investigator Program N00014-08-1-0752. The authors also thank Emma Brunskill, Geoff Gordon, Sue Ann Hong, Lavanya Marla, and Lionel Ni for valuable discussions and support regarding this work.
Funding AgencyGrant Number
Department of TransportationDTRT12-G-UTC11
Singapore National Research FoundationUNSPECIFIED
Office of Naval Research (ONR)N000141010672
Office of Naval Research (ONR)N00014-08-1-0752
Subject Keywords:Collective routing; Gaussian Process; Dynamic congestion model
Classification Code:H.2.8 Database applications: Data mining I.2.6 Artificial Intelligence: Learning - parameter learning
Record Number:CaltechAUTHORS:20140910-105714525
Persistent URL:
Official Citation:Liu, S., Yue, Y., & Krishnan, R. (2013). Adaptive collective routing using gaussian process dynamic congestion models. Paper presented at the Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, Chicago, Illinois, USA.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49540
Deposited By: Jason Perez
Deposited On:11 Sep 2014 20:48
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page