Matt Tsao

Matt Tsao


Matt is a Ph.D student in the department of Electrical Engineering at Stanford University, also affiliated with the Stanford Autonomous Systems Laboratory. Prior to Stanford, he obtained a BS in Electrical Engineering with highest honors from the University of Illinois at Urbana Champaign with a focus in Learning Theory and Information Theory.

Matt’s current research involves developing robust algorithms for control of fleets of autonomous cars using ideas from statistics and learning theory.

In his free time, Matt enjoys listening to music, swimming, and solving puzzles.

Awards:

  • NSF Graduate Research Fellowship (2016)

ASL Publications

  1. M. Tsao, K. Yang, K. Gopalakrishnan, and M. Pavone, “Private Location Sharing for Decentralized Routing Services,” in Proc. IEEE Int. Conf. on Intelligent Transportation Systems, Macau, China, 2022. (In Press)

    Abstract: Data-driven methodologies offer many exciting upsides, but they also introduce new challenges, particularly in the realm of user privacy. Specifically, the way data is collected can pose privacy risks to end users. In many routing services, a single entity (e.g., the routing service provider) collects and manages user trajectory data. When it comes to user privacy, these systems have a central point of failure since users have to trust that this entity will not sell or use their data to infer sensitive private information. With this as motivation, we study the problem of using location data for routing services in a privacy-preserving way. Rather than having users report their location to a central operator, we present a protocol in which users participate in a decentralized and privacy-preserving computation to estimate travel times for the roads in the network in a way that no individuals’ location is ever observed by any other party. The protocol uses the Laplace mechanism in conjunction with secure multi-party computation to ensure that it is cryptogrpahically secure and that its output is differentially private. The protocol is computationally efficient and does not require specialized hardware; all it needs is GPS, which is included in most mobile devices. A natural question is if privacy necessitates degradation in accuracy or system performance. We show that if a road has sufficiently high capacity, then the travel time estimated by our protocol is provably close to the ground truth travel time. We validate the protocol through numerical experiments which show that using the protocol as a routing service provides privacy guarantees with minimal overhead to user travel time.

    @inproceedings{Tsao2022a,
      author = {Tsao, M. and Yang, K. and Gopalakrishnan, K. and Pavone, M.},
      booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}},
      title = {Private Location Sharing for Decentralized Routing Services},
      year = {2022},
      address = {Macau, China},
      month = oct,
      keywords = {press},
      url = {https://arxiv.org/pdf/2202.13305.pdf}
    }
    
  2. M. Tsao, “Techniques for Efficient and Responsible Operation of Mobility Systems,” PhD thesis, Stanford University, Dept. of Electrical Engineering, Stanford, California, 2022.

    Abstract: Transportation is a necessary resource for many societies around the world. While advances in data science provide promising tools for personalized, adaptive and more efficient mobility services, they also bring new challenges in equal measure. In this dissertation I will discuss algorithm design for two such challenges faced by modern mobility services. First, I will discuss techniques for operating ridehailing and ridesharing systems in settings with incomplete information, which often arise due to the on-demand nature of such services. In particular, I will show both in theory and in practice how ideas from model predictive control, online optimization and machine learning can be used to effective serve existing customers while also adequately preparing for unknown future demand. Second, I will highlight some privacy concerns that arise from the sharing of mobility data that is often required for modern data-driven algorithms. To address some of these concerns, I present techniques based on multiparty computation and differential privacy to effectively use location data to improve routing services in a privacy-preserving way.

    @phdthesis{Tsao2022,
      author = {Tsao, M.},
      school = {{{Stanford University, Dept. of Electrical Engineering}}},
      title = {Techniques for Efficient and Responsible Operation of Mobility Systems},
      year = {2022},
      address = {Stanford, California},
      month = jun,
      url = {https://stacks.stanford.edu/file/druid:cq614xb8649/mwtsao_thesis_22_v2_submission_6_1_2022-augmented.pdf}
    }
    
  3. D. Jalota, K. Solovey, M. Tsao, S. Zoepf, and M. Pavone, “Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment,” in Proc. Int. Conf. on Autonomous Agents and Multiagent Systems, 2022. (In Press)

    Abstract: System optimum (SO) routing, wherein the total travel time of all users is minimized, is a holy grail for transportation authorities. However, SO routing may discriminate against users who incur much larger travel times than others to achieve high system efficiency, i.e., low total travel times. To address the inherent unfairness of SO routing, we study the β-fair SO problem whose goal is to minimize the total travel time while guaranteeing a β≥1 level of unfairness, which specifies the maximal ratio between the travel times of different users with shared origins and destinations. To obtain feasible solutions to the β-fair SO problem while achieving high system efficiency, we develop a new convex program, the Interpolated Traffic Assignment Problem (I-TAP), which interpolates between a fair and an efficient traffic-assignment objective. We then leverage the structure of I-TAP to develop two pricing mechanisms to collectively enforce the I-TAP solution in the presence of selfish homogeneous and heterogeneous users, respectively, that independently choose routes to minimize their own travel costs. We mention that this is the first study of pricing in the context of fair routing. Finally, we use origin-destination demand data for a range of transportation networks to numerically evaluate the performance of I-TAP as compared to a state-of-the-art algorithm. The numerical results indicate that our approach is faster by several orders of magnitude, while achieving higher system efficiency for most levels of unfairness.

    @inproceedings{JalotaSoloveyEtAl2022,
      author = {Jalota, D. and Solovey, K. and Tsao, M. and Zoepf, S. and Pavone, M.},
      title = {Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment},
      booktitle = {{Proc. Int. Conf. on Autonomous Agents and Multiagent Systems}},
      year = {2022},
      note = {In Press},
      keywords = {press},
      owner = {devanshjalota},
      timestamp = {2022-03-01}
    }
    
  4. M. Tsao, K. Yang, S. Zoepf, and M. Pavone, “Trust but Verify: Cryptographic Data Privacy for Mobility Management,” IEEE Transactions on Control of Network Systems, vol. 9, no. 1, pp. 50–61, 2022.

    Abstract: The era of Big Data has brought with it a richer understanding of user behavior through massive data sets, which can help organizations optimize the quality of their services. In the context of transportation research, mobility data can provide Municipal Authorities (MA) with insights on how to operate, regulate, or improve the transportation network. Mobility data, however, may contain sensitive information about end users and trade secrets of Mobility Providers (MP). Due to this data privacy concern, MPs may be reluctant to contribute their datasets to MA. Using ideas from cryptography, we propose an interactive protocol between a MA and a MP in which MA obtains insights from mobility data without MP having to reveal its trade secrets or sensitive data of its users. This is accomplished in two steps: a commitment step, and a computation step. In the first step, Merkle commitments and aggregated traffic measurements are used to generate a cryptographic commitment. In the second step, MP extracts insights from the data and sends them to MA. Using the commitment and zero-knowledge proofs, MA can certify that the information received from MP is accurate, without needing to directly inspect the mobility data. We also present a differentially private version of the protocol that is suitable for the large query regime. The protocol is verifiable for both MA and MP in the sense that dishonesty from one party can be detected by the other. The protocol can be readily extended to the more general setting with multiple MPs via secure multi-party computation.

    @article{TsaoYangZoepfPavone2021,
      author = {Tsao, M. and Yang, K. and Zoepf, S. and Pavone, M.},
      journal = {{IEEE Transactions on Control of Network Systems}},
      title = {Trust but Verify: Cryptographic Data Privacy for Mobility Management},
      year = {2022},
      number = {1},
      pages = {50-61},
      volume = {9},
      url = {https://arxiv.org/abs/2104.07768}
    }
    
  5. M. Pavone, A. Saberi, M. Schiffer, and M. Tsao, “Online Hypergraph Matching with Delays,” Operations Research, Dec. 2021. (In Press)

    Abstract: We study an online hypergraph matching problem inspired by ridesharing and delivery applications. The vertices of a hypergraph are revealed sequentially and must be matched within d timesteps of their reveal, otherwise they will leave the system in favor of an outside option. Hyperedges can contain at most k vertices and are revealed to the algorithm once all of its vertices have arrived, and can only be included into the matching before any of its vertices leave the system. We study utility maximization and cost minimization objectives in this model. In the utility maximization setting, we show that the optimal competitive ratio is 1/d whenever k >= 3, and is achievable in polynomial-time for any fixed k. For the cost minimization setting, we assume costs are monotone, which is a natural assumption in ridesharing and delivery problems. When k = 2, we show that the optimal competitive ratio for deterministic algorithms is \frac32 and is achieved by a polynomial-time thresholding algorithm. When k>2, we show that a polynomial-time randomized batching algorithm is (2 - 1/d)log k-competitive, and it is NP-hard to achieve a competitive ratio better than \log k - O (\log \log k).

    @article{TsaoEtAl2021,
      author = {Pavone, M. and Saberi, A. and Schiffer, M. and Tsao, M.},
      title = {Online Hypergraph Matching with Delays},
      journal = {Operations Research},
      year = {2021},
      note = {In press},
      comment = {This manuscript was first submitted to Operations Research on 01-27-2021. The first round of revision was submitted on 08-10-2021. The paper was accepted by Operations Research on 12-21-2021.},
      keywords = {press},
      month = dec,
      owner = {mwtsao},
      timestamp = {2021-08-10}
    }
    
  6. K. Yang, M. Tsao, X. Xu, and M. Pavone, “Real-Time Control of Mixed Fleets in Mobility-on-Demand Systems,” in Proc. IEEE Int. Conf. on Intelligent Transportation Systems, Indianapolis, IN, USA, 2021.

    Abstract: Automated vehicles (AVs) are expected to be beneficial for Mobility-on-Demand (MoD), thanks to their ability of being globally coordinated. To facilitate the steady transition towards full autonomy, we consider the transition period of AV deployment, whereby an MoD system operates a mixed fleet of automated vehicles (AVs) and human-driven vehicles (HVs). In such systems, AVs are centrally coordinated by the operator, and the HVs might strategically respond to the coordination of AVs. We devise computationally tractable strategies to coordinate mixed fleets in MoD systems. Specifically, we model an MoD system with a mixed fleet using a Stackelberg framework where the MoD operator serves as the leader and human-driven vehicles serve as the followers. We develop two models: 1) a steady-state model to analyze the properties of the problem and determine the planning variables (e.g., compensations, prices, and the fleet size of AVs), and 2) a time-varying model to design a real-time coordination algorithm for AVs. The proposed models are validated using a case study inspired by real operational data of a MoD service in Singapore. Results show that the proposed algorithms can significantly improve system performance.

    @inproceedings{YangTsaoEtAl2021,
      author = {Yang, K. and Tsao, M. and Xu, X. and Pavone, M.},
      title = {Real-Time Control of Mixed Fleets in Mobility-on-Demand Systems},
      booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}},
      year = {2021},
      note = {{Extended Version, Available} at \url{https://arxiv.org/abs/2008.08131}},
      address = {Indianapolis, IN, USA},
      month = sep,
      url = {https://arxiv.org/pdf/2008.08131},
      owner = {ykd07},
      timestamp = {2021-06-15}
    }
    
  7. R. A. Brown, F. Rossi, K. Solovey, M. Tsao, M. T. Wolf, and M. Pavone, “On Local Computation for Network-Structured Convex Optimization in Multi-Agent Systems,” IEEE Transactions on Control of Network Systems, vol. 8, no. 2, pp. 542–554, 2021.

    Abstract: A number of prototypical optimization problems in multi-agent systems (e.g., task allocation and network load-sharing) exhibit a highly local structure: that is, each agent’s decision variables are only directly coupled to few other agent’s variables through the objective function or the constraints. In this paper, we develop a rigorous notion of "locality" that quantifies the degree to which agents can compute their portion of the global solution of such a distributed optimization problem based solely on information in their local neighborhood. We build upon the results of Rebeschini and Tatikonda (2019) to develop a more general theory of locality that fully captures the importance of problem data to individual solution components, as opposed to a theory that only captures response to perturbations. This analysis provides a theoretical basis for a rather simple algorithm in which agents individually solve a truncated sub-problem of the global problem, where the size of the sub-problem used depends on the locality of the problem, and the desired accuracy. Numerical results show that the proposed theoretical bounds are remarkably tight for well-conditioned problems.

    @article{BrownRossiEtAl2020,
      author = {Brown, R. A. and Rossi, F. and Solovey, K. and Tsao, M. and Wolf, M. T. and Pavone, M.},
      title = {On Local Computation for Network-Structured Convex Optimization in Multi-Agent Systems},
      journal = {{IEEE Transactions on Control of Network Systems}},
      volume = {8},
      number = {2},
      pages = {542-554},
      year = {2021},
      url = {/wp-content/papercite-data/pdf/Brown.Rossi.ea.TCNS20.pdf},
      owner = {rabrown1},
      timestamp = {2021-08-31}
    }
    
  8. M. Pavone, A. Saberi, M. Schiffer, and M. Tsao, “Online Hypergraph Matching with Delays,” in The Conference on Web and Internet Economics (WINE), Beijing, China, 2020.

    Abstract: We study an online hypergraph matching problem with delays, motivated by ridesharing applications. In this model, users enter a marketplace sequentially, and are willing to wait up to d timesteps to be matched, after which they will leave the system in favor of an outside option. A platform can match groups of up to k users together, indicating that they will share a ride. Each group of users yields a match value depending on how compatible they are with one another. As an example, in ridesharing, k is the capacity of the service vehicles, and d is the amount of time a user is willing to wait for a driver to be matched to them. We present results for both the utility maximization and cost minimization variants of the problem. In the utility maximization setting, the optimal competitive ratio is 1/d whenever k is at least 3, and is achievable in polynomial-time for any fixed k. In the cost minimization variation, when k = 2, the optimal competitive ratio for deterministic algorithms is 3/2 and is achieved by a polynomial-time thresholding algorithm. When k>2, we show that a polynomial-time randomized batching algorithm is (2 - 1/d) log k-competitive, and it is NP-hard to achieve a competitive ratio better than log k - O(log log k).

    @inproceedings{TsaoEtAl2020,
      author = {Pavone, M. and Saberi, A. and Schiffer, M. and Tsao, M.},
      booktitle = {The Conference on Web and Internet Economics (WINE)},
      title = {Online Hypergraph Matching with Delays},
      year = {2020},
      address = {Beijing, China},
      month = dec,
      owner = {mwtsao},
      url = {http://arxiv.org/abs/2009.12022}
    }
    
  9. M. Tsao, K. Solovey, and M. Pavone, “Sample Complexity of Probabilistic Roadmaps via Epsilon-nets,” in Proc. IEEE Conf. on Robotics and Automation, Paris, France, 2020.

    Abstract: We study fundamental theoretical aspects of probabilistic roadmaps (PRM) in the finite time (non-asymptotic) regime. In particular, we investigate how completeness and optimality guarantees of the approach are influenced by the underlying deterministic sampling distribution \mathcalX and connection radius r>0. We develop the notion of (δ,ε)-completeness of the parameters \mathcalX,r, which indicates that for every motion-planning problem of clearance at least δ>0, PRM using \mathcalX,r returns a solution no longer than 1+εtimes the shortest δ-clear path. Leveraging the concept of ε-nets, we characterize in terms of lower and upper bounds the number of samples needed to guarantee (δ,ε)-completeness. This is in contrast with previous work which mostly considered the asymptotic regime in which the number of samples tends to infinity. In practice, we propose a sampling distribution inspired by ε-nets that achieves nearly the same coverage as grids while using significantly fewer samples.

    @inproceedings{TsaoSoloveyETAL2020,
      author = {Tsao, M. and Solovey, K. and Pavone, M.},
      title = {Sample Complexity of Probabilistic Roadmaps via Epsilon-nets},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2020},
      address = {Paris, France},
      month = may,
      url = {https://ieeexplore.ieee.org/document/9196917},
      timestamp = {2020-02-25}
    }
    
  10. M. Salazar, M. Tsao, I. Aguiar, M. Schiffer, and M. Pavone, “A Congestion-aware Routing Scheme for Autonomous Mobility-on-Demand Systems,” in European Control Conference, Naples, Italy, 2019.

    Abstract: We study route-planning for Autonomous Mobility-on-Demand (AMoD) systems that accounts for the impact of road traffic on travel time. Specifically, we develop a congestion-aware routing scheme (CARS) that captures road-utilization-dependent travel times at a mesoscopic level via a piecewise affine approximation of the Bureau of Public Roads (BPR) model. This approximation largely retains the key features of the BPR model, while allowing the design of a real-time, convex quadratic optimization algorithm to determine congestion-aware routes for an AMoD fleet. Through a real-world case study of Manhattan, we compare CARS to existing routing approaches, namely a congestion-unaware and a threshold congestion model. Numerical results show that CARS significantly outperforms the other two approaches, with improvements in terms of travel time and global cost in the order of 20%.

    @inproceedings{SalazarTsaoEtAl2019,
      author = {Salazar, M. and Tsao, M. and Aguiar, I. and Schiffer, M. and Pavone, M.},
      title = {A Congestion-aware Routing Scheme for Autonomous Mobility-on-Demand Systems},
      booktitle = {{European Control Conference}},
      year = {2019},
      address = {Naples, Italy},
      month = nov,
      url = {/wp-content/papercite-data/pdf/Salazar.Tsao.ea.ECC19.pdf},
      owner = {samauro},
      timestamp = {2020-03-08}
    }
    
  11. J. Zgraggen, M. Tsao, M. Salazar, M. Schiffer, and M. Pavone, “A Model Predictive Control Scheme for Intermodal Autonomous Mobility-on-Demand,” in Proc. IEEE Int. Conf. on Intelligent Transportation Systems, Auckland, New Zealand, 2019.

    Abstract: This paper presents a routing algorithm for intermodal Autonomous Mobility on Demand (AMoD) systems, whereby a fleet of self-driving cars provides on-demand mobility in coordination with public transit. Specifically, we present a time-variant flow-based optimization approach that captures the operation of an AMoD system in coordination with public transit. We then leverage this model to devise a model predictive control (MPC) algorithm to route customers and vehicles through the network with the objective of minimizing customers’ travel time. To validate our MPC scheme, we present a real-world case study for New York City. Our results show that servicing transportation demands jointly with public transit can significantly improve the service quality of AMoD systems. Additionally, we highlight the differences of our time-variant framework compared to existing mesoscopic, time-invariant models.

    @inproceedings{ZgraggenTsaoEtAl2019,
      author = {Zgraggen, J. and Tsao, M. and Salazar, M. and Schiffer, M. and Pavone, M.},
      title = {A Model Predictive Control Scheme for Intermodal Autonomous Mobility-on-Demand},
      booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}},
      year = {2019},
      address = {Auckland, New Zealand},
      month = nov,
      url = {/wp-content/papercite-data/pdf/Zgraggen.Salazar.ea.ITSC19.pdf},
      owner = {samauro},
      timestamp = {2020-02-12}
    }
    
  12. A. Sharma, J. Harrison, M. Tsao, and M. Pavone, “Robust and Adaptive Planning under Model Uncertainty,” in Int. Conf. on Automated Planning and Scheduling, Berkeley, California, 2019.

    Abstract: Planning under model uncertainty is a fundamental problem across many applications of decision making and learning. In this paper, we propose the Robust Adaptive Monte Carlo Planning (RAMCP) algorithm, which allows computation of risk-sensitive Bayes-adaptive policies that optimally trade off exploration, exploitation, and robustness. RAMCP formulates the risk-sensitive planning problem as a two-player zero-sum game, in which an adversary perturbs the agent’s belief over the models. We introduce two versions of the RAMCP algorithm. The first, RAMCP-F, converges to an optimal risk-sensitive policy without having to rebuild the search tree as the underlying belief over models is perturbed. The second version, RAMCP-I, improves computational efficiency at the cost of losing theoretical guarantees, but is shown to yield empirical results comparable to RAMCP-F. RAMCP is demonstrated on an n-pull multi-armed bandit problem, as well as a patient treatment scenario.

    @inproceedings{SharmaHarrisonEtAl2019,
      author = {Sharma, A. and Harrison, J. and Tsao, M. and Pavone, M.},
      title = {Robust and Adaptive Planning under Model Uncertainty},
      booktitle = {{Int. Conf. on Automated Planning and Scheduling}},
      year = {2019},
      address = {Berkeley, California},
      month = jul,
      url = {https://arxiv.org/pdf/1901.02577.pdf},
      owner = {apoorva},
      timestamp = {2019-04-10}
    }
    
  13. M. Tsao, D. Milojevic, C. Ruch, M. Salazar, E. Frazzoli, and M. Pavone, “Model Predictive Control of Ride-sharing Autonomous Mobility on Demand Systems,” in Proc. IEEE Conf. on Robotics and Automation, Montreal, Canada, 2019.

    Abstract: This paper presents a model predictive control (MPC) approach to optimize routes for Ride-sharing Autonomous Mobility-on-Demand (RAMoD) systems, whereby self-driving vehicles provide coordinated on-demand mobility, possibly allowing multiple customers to share a ride. Specifically, we first devise a time-expanded network flow model for RAMoD. Second, leveraging this model, we design a real-time MPC algorithm to optimize the routes of both empty and customer-carrying vehicles, with the goal of optimizing social welfare, namely, a weighted combination of customers’ travel time and vehicles’ mileage. Finally, we present a real-world case study for the city of San Francisco, CA, by using the microscopic traffic simulator MATSim. The simulation results show that a RAMoD system can significantly improve social welfare with respect to a single-occupancy AMoD system, and that the predictive structure of the proposed MPC controller allows it to outperform existing reactive ride-sharing coordination algorithms for RAMoD.

    @inproceedings{TsaoMilojevicEtAl2019,
      author = {Tsao, M. and Milojevic, D. and Ruch, C. and Salazar, M. and Frazzoli, E. and Pavone, M.},
      title = {Model Predictive Control of Ride-sharing Autonomous Mobility on Demand Systems},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2019},
      address = {Montreal, Canada},
      month = may,
      url = {/wp-content/papercite-data/pdf/Tsao.ea.ICRA19.pdf},
      owner = {samauro},
      timestamp = {2020-02-12}
    }
    
  14. M. Tsao, R. Iglesias, and M. Pavone, “Stochastic Model Predictive Control for Autonomous Mobility on Demand,” in Proc. IEEE Int. Conf. on Intelligent Transportation Systems, Maui, Hawaii, 2018.

    Abstract: This paper presents a stochastic, model predictive control (MPC) algorithm that leverages short-term proba- bilistic forecasts for dispatching and rebalancing Autonomous Mobility-on-Demand systems (AMoD), i.e. fleets of self-driving vehicles. We first present the core stochastic optimization problem in terms of a time-expanded network flow model. Then, to ameliorate its tractability, we present two key relaxations. First, we replace the original stochastic problem with a Sample Average Approximation, and provide its performance guaran- tees. Second, we divide the controller into two submodules. The first submodule assigns vehicles to existing customers and the second redistributes vacant vehicles throughout the city. This enables the problem to be solved as two totally unimodular linear programs, allowing the controller to scale to large problem sizes. Finally, we test the proposed algorithm in two scenarios based on real data and show that it outperforms prior state-of-the-art algorithms. In particular, in a simulation using customer data from the ridesharing company DiDi Chuxing, the algorithm presented here exhibits a 62.3 percent reduction in customer waiting time compared to state of the art non- stochastic algorithms.

    @inproceedings{TsaoIglesiasEtAl2018,
      author = {Tsao, M. and Iglesias, R. and Pavone, M.},
      title = {Stochastic Model Predictive Control for Autonomous Mobility on Demand},
      booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}},
      year = {2018},
      note = {{Extended Version, Available} at \url{https://arxiv.org/pdf/1804.11074}},
      address = {Maui, Hawaii},
      month = nov,
      url = {https://arxiv.org/pdf/1804.11074.pdf},
      owner = {rdit},
      timestamp = {2018-07-12}
    }
    
  15. M. Tsao, R. Iglesias, and M. Pavone, “Stochastic Model Predictive Control for Autonomous Mobility on Demand.”

    Abstract: This paper presents a stochastic, model predictive control (MPC) algorithm that leverages short-term probabilistic forecasts for dispatching and rebalancing Autonomous Mobility-on-Demand systems (AMoD), i.e. fleets of self-driving vehicles. We first present the core stochastic optimization problem in terms of a time-expanded network flow model. Then, to ameliorate its tractability, we present two key relaxations. First, we replace the original stochastic problem with a Sample Average Approximation, and characterize the performance guarantees. Second, we divide the controller into two submodules. The first submodule assigns vehicles to existing customers and the second redistributes vacant vehicles throughout the city. This enables the problem to be solved as two totally unimodular linear programs, allowing the controller to scale to large problem sizes. Finally, we test the proposed algorithm in two scenarios based on real data and show that it outperforms prior state-of-the-art algorithms. In particular, in a simulation using customer data from the ridesharing company DiDi Chuxing, the algorithm presented here exhibits a 62.3 percent reduction in customer waiting time compared to state of the art non-stochastic algorithms.

    @unpublished{TsaoIglesiasEtAl,
      author = {Tsao, M. and Iglesias, R. and Pavone, M.},
      title = {Stochastic Model Predictive Control for Autonomous Mobility on Demand},
      note = {{{Extended version of ITSC 2018 paper. Available at }\url{https://arxiv.org/pdf/1804.11074.pdf}}},
      howpublished = {Available at: \url{https://arxiv.org/pdf/1804.11074.pdf}},
      owner = {mwtsao},
      timestamp = {2018-07-24}
    }