H-TD²: Hybrid Temporal Difference Learning for Adaptive Urban Taxi Dispatch
- Creators
-
Rivière, Benjamin
-
Chung, Soon-Jo
Abstract
We present H-TD²: Hybrid Temporal Difference Learning for Taxi Dispatch, a model-free, adaptive decision-making algorithm to coordinate a large fleet of automated taxis in a dynamic urban environment to minimize expected customer waiting times. Our scalable algorithm exploits the natural transportation network company topology by switching between two behaviors: distributed temporal-difference learning computed locally at each taxi and infrequent centralized Bellman updates computed at the dispatch center. We derive a regret bound and design the trigger condition between the two behaviors to explicitly control the trade-off between computational complexity and the individual taxi policy's bounded sub-optimality; this advances the state of the art by enabling distributed operation with bounded-suboptimality. Additionally, unlike recent reinforcement learning dispatch methods, this policy estimation is adaptive and robust to out-of-training domain events. This result is enabled by a two-step modelling approach: the policy is learned on an agent-agnostic, cell-based Markov Decision Process and individual taxis are coordinated using the learned policy in a distributed game-theoretic task assignment. We validate our algorithm against a receding horizon control baseline in a Gridworld environment with a simulated customer dataset, where the proposed solution decreases average customer waiting time by 50% over a wide range of parameters. We also validate in a Chicago city environment with real customer requests from the Chicago taxi public dataset where the proposed solution decreases average customer waiting time by 26% over irregular customer distributions during a 2016 Major League Baseball World Series game.
Additional Information
© 2021 IEEE. Manuscript received September 4, 2019; revised April 20, 2020 and April 22, 2021; accepted June 15, 2021. This work was supported in part by Raytheon Company and in part by the Jet Propulsion Laboratory. The authors would like to thank Salar Rahili, who proposed the use of binary log-linear learning in an early version of this work.Attached Files
Accepted Version - H-TD_Hybrid_Temporal_Difference_Learning_for_Adaptive_Urban_Taxi_Dispatch.pdf
Submitted - 2105.02138.pdf
Files
Name | Size | Download all |
---|---|---|
md5:4376037634f0f1f252f69ba00607edc8
|
976.8 kB | Preview Download |
md5:4b32ef704bdee2e277e61b48191fd695
|
1.2 MB | Preview Download |
Additional details
- Alternative title
- H-TD2: Hybrid Temporal Difference Learning for Adaptive Urban Taxi Dispatch
- Eprint ID
- 113029
- Resolver ID
- CaltechAUTHORS:20220120-890613000
- Raytheon Company
- JPL
- Created
-
2022-01-20Created from EPrint's datestamp field
- Updated
-
2022-01-20Created from EPrint's last_modified field
- Caltech groups
- GALCIT, Center for Autonomous Systems and Technologies (CAST)