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. Pavone, A. Saberi, M. Schiffer, and M. Tsao, “Online Hypergraph Matching with Delays,” 2021.

    Abstract:

    @article{TsaoEtAl2021,
      author = {Pavone, Marco and Saberi, Amin and Schiffer, Maximilien and Tsao, Matthew},
      title = {Online Hypergraph Matching with Delays},
      year = {2021}
    }
    
  2. 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, Marco and Saberi, Amin and Schiffer, Maximilian and Tsao, Matthew},
      title = {Online Hypergraph Matching with Delays},
      booktitle = {The Conference on Web and Internet Economics (WINE)},
      year = {2020},
      address = {Beijing, China},
      month = dec,
      owner = {mwtsao},
      url = {http://arxiv.org/abs/2009.12022}
    }
    
  3. 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}
    }
    
  4. 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, 2020. (In Press)

    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}},
      year = {2020},
      note = {In Press},
      url = {/wp-content/papercite-data/pdf/Brown.Rossi.ea.TCNS20.pdf},
      keywords = {press},
      owner = {rabrown1},
      timestamp = {2021-01-13}
    }
    
  5. 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}
    }
    
  6. 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}
    }
    
  7. 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},
      note = {In Press},
      address = {Berkeley, California},
      month = jul,
      url = {https://arxiv.org/pdf/1901.02577.pdf},
      owner = {apoorva},
      timestamp = {2019-04-10}
    }
    
  8. 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}
    }
    
  9. 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 = {In Press. {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}
    }
    
  10. M. Tsao, R. Iglesias, and M. Pavone, “Stochastic Model Predictive Control for Autonomous Mobility on Demand,” Available at: \urlhttps://arxiv.org/pdf/1804.11074.pdf.

    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}
    }