We present H-TD2: 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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    H-TD2: Hybrid Temporal Difference Learning for Adaptive Urban Taxi Dispatch


    Beteiligte:

    Erschienen in:

    Erscheinungsdatum :

    01.08.2022


    Format / Umfang :

    1147173 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    TAXI DISPATCH SYSTEM AND TAXI DISPATCH METHOD

    TODATE TAKAHIRO / TANAKA TOKUHO | Europäisches Patentamt | 2016

    Freier Zugriff

    INTEGRATED TAXI DISPATCH SYSTEM

    TANIGUCHI KEIKO | Europäisches Patentamt | 2019

    Freier Zugriff

    Mobile taxi dispatch system

    FELT MICHELLE / GHARACHORLOO NADER / MOSHREFI AFSHIN | Europäisches Patentamt | 2018

    Freier Zugriff

    Taxi dispatch control system and method for taxi dispatching

    NAKAMURA KAZUTO | Europäisches Patentamt | 2021

    Freier Zugriff

    Taxi dispatch control system and method for taxi dispatching

    NAKAMURA KAZUTO | Europäisches Patentamt | 2023

    Freier Zugriff