Contacts:
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)
Currently at Lyft
ASL Publications
-
D. Jalota, M. Tsao, and M. Pavone, “Catch Me If You Can: Combatting Fraud in Artificial Currency Based Government Benefits Programs,” 2024. (Submitted)
Abstract: Artificial currencies have grown in popularity in many real-world resource allocation settings. In particular, they have gained traction in government benefits programs, e.g., food assistance or transit benefits programs, that provide support to eligible users in the population, e.g., through subsidized food or public transit. However, such programs are prone to two common fraud mechanisms: (i) misreporting fraud, wherein users can misreport their private attributes to gain access to more artificial currency (credits) than they are entitled to, and (ii) black market fraud, wherein users may seek to sell some of their credits in exchange for real money. In this work, we develop mechanisms to address these two sources of fraud in artificial currency based government benefits programs. To address misreporting fraud, we propose an audit mechanism that induces a two-stage game between an administrator and users, wherein the administrator running the benefits program can audit users at some cost and levy fines against them for misreporting their information. For this audit game, we first investigate the conditions on the administrator’s budget to establish the existence of equilibria and present a linear programming approach to compute these equilibria under both the signaling game and Bayesian persuasion formulations. We then show that the decrease in misreporting fraud corresponding to our audit mechanism far outweighs the spending of the administrator to run it by establishing that its total costs are lower than that of the status quo with no audits. To highlight the practical viability of our audit mechanism in mitigating misreporting fraud, we present a case study on Washington D.C.’s federal transit benefits program where the proposed audit mechanism even demonstrates several orders of magnitude improvement in total cost compared to a no-audit strategy for some parameter ranges.
@inproceedings{JalotaTsaoEtAl2023, author = {Jalota, D. and Tsao, M. and Pavone, M.}, title = {Catch Me If You Can: Combatting Fraud in Artificial Currency Based Government Benefits Programs}, year = {2024}, url = {https://arxiv.org/abs/2402.16162}, keywords = {sub}, owner = {devanshjalota}, timestamp = {2024-07-02} } -
M. Tsao, K. Gopalakrishnan, K. Yang, and M. Pavone, “Privacy-Aware Control of Cyber Physical Systems,” in Smarter Cyber Physical Systems: Enabling Methodologies and Application, CRC Press, 2023. (Submitted)
Abstract: In this chapter, we will discuss some of the privacy related challenges that have arisen in data-driven cyber-physical systems. While user data can help data-driven systems improve their efficiency, safety, and adaptability, the way that this data is collected and analyzed can lead to privacy risks to users. If left unaddressed, potential privacy risks may deter users from contributing their data to cyber-physical systems, thereby limiting the effectiveness of data-driven tools employed by the systems. To ensure that users are protected from privacy risks and feel comfortable sharing their data with cyber-physical systems, this chapter discusses how differential privacy and cryptography, techniques originally developed for privacy in health care and computer systems respectively, can be used to conduct data analysis and optimization with principled privacy guarantees in cyber-physical systems. Along the way, we will discuss and compare the properties, strengths weaknesses of these approaches. We will also show why these techniques address many of the privacy-related issues that arise when using data anonymization and data aggregation, two of the most common approaches to privacy-aware data sharing.
@incollection{TsaoGopalakrishnanEtAl2023b, author = {Tsao, M. and Gopalakrishnan, K. and Yang, K. and Pavone, M.}, title = {Privacy-Aware Control of Cyber Physical Systems}, booktitle = {Smarter Cyber Physical Systems: Enabling Methodologies and Application}, year = {2023}, publisher = {{CRC Press}}, note = {Submitted}, keywords = {sub}, owner = {gkarthik}, timestamp = {2022-12-06} } -
M. Tsao, K. Gopalakrishnan, K. Yang, and M. Pavone, “Differentially Private Stochastic Convex Optimization for Network Routing Applications,” in Proc. IEEE Conf. on Decision and Control, Singapore, 2023.
Abstract: Network routing problems are common across many engineering applications. Computing optimal routing policies requires knowledge about network demand, i.e., the origin and destination (OD) of all requests in the network. However, privacy considerations make it challenging to share individual OD data that would be required for computing optimal policies. Privacy can be particularly challenging in standard network routing problems because sources and sinks can be easily identified from flow conservation constraints, making feasibility and privacy mutually exclusive. In this paper, we present a differentially private algorithm for network routing problems. The main ingredient is a reformulation of network routing which moves all user data-dependent parameters out of the constraint set and into the objective function. We then present an algorithm for solving this formulation based on a differentially private variant of stochastic gradient descent. In this algorithm, differential privacy is achieved by injecting noise, and one may wonder if this noise injection compromises solution quality. We prove that our algorithm is both differentially private and asymptotically optimal as the size of the training set goes to infinity. We corroborate the theoretical results with numerical experiments on a road traffic network which show that our algorithm provides differentially private and near-optimal solutions in practice.
@inproceedings{TsaoGopalakrishnanEtAl2023, author = {Tsao, M. and Gopalakrishnan, K. and Yang, K. and Pavone, M.}, title = {Differentially Private Stochastic Convex Optimization for Network Routing Applications}, booktitle = {{Proc. IEEE Conf. on Decision and Control}}, year = {2023}, address = {Singapore}, doi = {10.1109/CDC49753.2023.10383207}, url = {https://ieeexplore.ieee.org/abstract/document/10383207/}, owner = {somrita}, timestamp = {2024-02-29} } -
D. Jalota, K. Solovey, M. Tsao, S. Zoepf, and M. Pavone, “Balancing Fairness and Efficiency in Traffic Routing via Interpolated Traffic Assignment,” Autonomous Agents and Multi-Agent Systems, vol. 37, no. 32, pp. 1–40, 2023.
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.
@article{JalotaSoloveyEtAl2023, 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}, journal = {{Autonomous Agents and Multi-Agent Systems}}, volume = {37}, number = {32}, pages = {1--40}, year = {2023}, keywords = {pub}, asl_url = {https://link.springer.com/article/10.1007/s10458-023-09616-7}, owner = {devanshjalota}, timestamp = {2024-02-29} } -
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, 2022.
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{TsaoYangEtAl2022, author = {Tsao, M. and Yang, K. and Gopalakrishnan, K. and Pavone, M.}, title = {Private Location Sharing for Decentralized Routing Services}, booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}}, year = {2022}, doi = {10.1109/ITSC55140.2022.9922387}, month = oct, url = {https://arxiv.org/abs/2202.13305}, owner = {gkarthik}, timestamp = {2022-11-21} } -
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.}, title = {Trust but Verify: Cryptographic Data Privacy for Mobility Management}, journal = {{IEEE Transactions on Control of Network Systems}}, volume = {9}, number = {1}, pages = {50--61}, year = {2022}, keywords = {pub}, url = {https://arxiv.org/abs/2104.07768} } -
M. Pavone, A. Saberi, M. Schiffer, and M. Tsao, “Online Hypergraph Matching with Delays,” Operations Research, vol. 70, no. 4, pp. 2194–2212, 2022.
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}}, volume = {70}, number = {4}, pages = {2194-2212}, year = {2022}, 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 = {pub}, owner = {mwtsao}, timestamp = {2021-08-10} } -
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.
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}, owner = {devanshjalota}, timestamp = {2022-03-01} } -
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} } -
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} } -
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} } -
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} } -
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} } -
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, owner = {samauro}, timestamp = {2020-03-08}, url = {/wp-content/papercite-data/pdf/Salazar.Tsao.ea.ECC19.pdf} } -
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} } -
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} } -
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} } -
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} }