Non-Myopic Adaptive Route Planning in Uncertain Congestion Environments
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 efficient algorithms 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. Our approach is validated by traffic data from two large Asian cities. Our congestion model is shown to be effective in modeling dynamic congestion conditions. Our routing algorithms also generate significantly faster routes compared to standard baselines, and achieve 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.
© 2015 IEEE. Manuscript received 17 Oct. 2014; revised 27 Feb. 2015; accepted 27 Feb. 2015. Date of publication 8 Mar. 2015; date of current version 3 Aug. 2015. This work was supported by Singapore National Research Foundation under its International Research Centre @ Singapore Funding Initiative and administered by the IDM Programme Office, Carnegie Mellon University's Technologies for Safe and Efficient Transportation, The National USDOT University Transportation Center for Safety (T-SET UTC) sponsored by the US Department of Transportation, National Basic Research Program of China (973 Program): 2015CB352400, and Basic Research Program of Shenzhen: JCYJ20140610152828686. The work of Yisong Yue was also supported by ONR (PECASE) N000141010672 and ONR Young Investigator Program N00014-08-1-0752. Siyuan Liu would acknowledge Google Faculty Research Award. The authors thank Emma Brunskill, Geoff Gordon, Sue Ann Hong, Lavanya Marla, and Lionel Ni for valuable discussions and support.