Skip to content Skip to navigation
Computer Science Department Colloquium
8/21/2019 10:30 am
1 Spring street, New Brunswick, Room 204

Scalable and Congestion-aware Routing for Autonomous Mobility-On-Demand via Frank-Wolfe Optimization

Kiril Solovey, Stanford University

Faculty Host: Kostas Bekris

Abstract

We consider the problem of vehicle routing for Autonomous Mobility-on-Demand (AMoD) systems, wherein a fleet of self-driving vehicles provides on-demand mobility in a given environment. Specifically, the task it to compute routes for the vehicles (both customer-carrying and empty traveling) so that travel demand is fulfilled and operational cost is minimized. The routing process must account for congestion effects affecting travel times, as modeled via a volume-delay function (VDF). Route planning with VDF constraints is notoriously challenging, as such constraints compound the combinatorial complexity of the routing optimization process. Thus, current solutions for AMoD routing resort to relaxations of the congestion constraints, thereby trading optimality with computational efficiency.

In this paper, we present the first computationally-efficient approach for AMoD routing where VDF constraints are explicitly accounted for. We demonstrate that our approach is faster by at least one order of magnitude with respect to the state of the art, while providing higher quality solutions. From a methodological standpoint, the key technical insight is to establish a mathematical reduction of the AMoD routing problem to the classical traffic assignment problem (a related vehicle-routing problem where empty traveling vehicles are not present). Such a reduction allows us to extend powerful algorithmic tools for traffic assignment, which combine the classic Frank-Wolfe algorithm with modern techniques for pathfinding, to the AMoD routing problem. We provide strong theoretical guarantees for our approach in terms of near-optimality of the returned solution.

This is joint work with Mauro Salazar and Marco Pavone. Appeared in Robotics: Science and Systems, 2019.

Bio

Kiril Solovey is a Postdoctoral Scholar supported by the Fulbright Scholars Program at the Autonomous Systems Lab, Department of Aeronautics & Astronautics, Stanford University, hosted by Prof. Marco Pavone. His research focuses on algorithmic aspects of robotics. He is particularly interested in the design and analysis of techniques for robot motion planning, multi-robot systems, and autonomous mobility on demand (AMoD). Prior to Stanford, Kiril was a Ph.D. student at Tel Aviv University working with Prof. Dan Halperin in the Computational Geometry Lab supported by the Clore Israel Foundation.