2021/05/05 by Benjamin Rivière, Rivière, Benjamin, Soon‐Jo Chung +1
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Smart Grid Energy Management #Systems and Control (eess.SY) #Traffic Prediction and Management Techniques #Transportation and Mobility Innovations #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2105.02138
openalex publication_date 2021/05/05 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We present H-TD2: Hybrid Temporal Difference Learning for Taxi Dispatch, a\nmodel-free, adaptive decision-making algorithm to coordinate a large fleet of\nautomated taxis in a dynamic urban environment to minimize expected customer\nwaiting times. Our scalable algorithm exploits the natural transportation\nnetwork company topology by switching between two behaviors: distributed\ntemporal-difference learning computed locally at each taxi and infrequent\ncentralized Bellman updates computed at the dispatch center. We derive a regret\nbound and design the trigger condition between the two behaviors to explicitly\ncontrol the trade-off between computational complexity and the individual taxi\npolicy's bounded sub-optimality; this advances the state of the art by enabling\ndistributed operation with bounded-suboptimality. Additionally, unlike recent\nreinforcement learning dispatch methods, this policy estimation is adaptive and\nrobust to out-of-training domain events. This result is enabled by a two-step\nmodelling approach: the policy is learned on an agent-agnostic, cell-based\nMarkov Decision Process and individual taxis are coordinated using the learned\npolicy in a distributed game-theoretic task assignment. We validate our\nalgorithm against a receding horizon control baseline in a Gridworld\nenvironment with a simulated customer dataset, where the proposed solution\ndecreases average customer waiting time by 50% over a wide range of parameters.\nWe also validate in a Chicago city environment with real customer requests from\nthe Chicago taxi public dataset where the proposed solution decreases average\ncustomer waiting time by 26% over irregular customer distributions during a\n2016 Major League Baseball World Series game.\n