Optimal Routing for Autonomous Taxis using Distributed Reinforcement Learning

Abstract

In this paper, a learning-based optimal transportation algorithm for autonomous taxis and ridesharing vehicles is introduced. The goal is to design a mechanism to solve the routing problem for a fleet of autonomous vehicles in real-time in order to maximize the transportation company's profit. To solve this problem, the system is modeled as a Markov Decision Process (MDP) using past customers data. By solving the defined MDP, a centralized high-level planning recommendation is obtained, where this offline solution is used as an initial value for the real-time learning. Then, a distributed SARSA reinforcement learning algorithm is proposed to capture the model errors and the environment changes, such as variations in customer distributions in each area, traffic, and fares, thereby providing an accurate model and optimal policies in real-time. Agents are using only their local information and interaction, such as current passenger requests and estimates of neighbors' tasks and their optimal actions, to obtain the optimal policies in a distributed fashion. The agents use the estimated values of each action, provided by distributed SARSA reinforcement learning, in a distributed game-theory based task assignment to select their conflict-free customers. Finally, the customers data provided by the city of Chicago is used to validate the proposed algorithms.

Files

Additional details