Rick Zhang

ASL Publications

R. Zhang, F. Rossi, and M. Pavone, “Analysis, Control, and Evaluation of Mobility-on-Demand Systems: a Queueing-Theoretical Approach,” IEEE Transactions on Control of Network Systems, vol. 6, no. 1, pp. 115–126, 2019.
[BibTeX] [Abstract]

Abstract: This paper presents a queueing-theoretical approach to the analysis, control, and evaluation of mobility-on-demand (MoD) systems for urban personal transportation. A MoD system consists of a fleet of vehicles providing one-way car sharing service and a team of drivers to rebalance such vehicles. The drivers then rebalance themselves by driving select customers similar to a taxi service. We model the MoD system as two coupled closed Jackson networks with passenger loss. We show that the system can be approximately balanced by solving two decoupled linear programs and exactly balanced through nonlinear optimization. The rebalancing techniques are applied to a system sizing example using taxi data in three neighborhoods of Manhattan. Lastly, we formulate a real-time closed-loop rebalancing policy for drivers and perform case studies of two hypothetical MoD systems in Manhattan and Hangzhou, China. We show that the taxi demand in Manhattan can be met with the same number of vehicles in a MoD system, but only require 1/3 to 1/4 the number of drivers; in Hangzhou, where customer demand is highly unbalanced, higher driver-to-vehicle ratios are required to achieve good quality of service.
```
@article{ZhangPavone2018,
  author = {Zhang, R. and Rossi, F. and Pavone, M.},
  title = {Analysis, Control, and Evaluation of Mobility-on-Demand Systems: a Queueing-Theoretical Approach},
  journal = {{IEEE Transactions on Control of Network Systems}},
  volume = {6},
  number = {1},
  pages = {115-126},
  year = {2019},
  doi = {10.1109/TCNS.2018.2800403},
  url = {/wp-content/papercite-data/pdf/Zhang.Rossi.Pavone.TCNS18.pdf},
  owner = {frossi2},
  timestamp = {2017-12-30}
}
```
R. Iglesias, F. Rossi, R. Zhang, and M. Pavone, “A BCMP Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems,” Int. Journal of Robotics Research, vol. 38, no. 2–3, pp. 357–374, 2019.
[BibTeX] [Abstract]

Abstract: In this paper we present a queuing network approach to the problem of routing and rebalancing a fleet of self-driving vehicles providing on- demand mobility within a capacitated road network. We refer to such systems as autonomous mobility-on-demand systems, or AMoD. We first cast an AMoD system into a closed, multi-class BCMP queuing network model capable of capturing the passenger arrival process, traffic, the state- of-charge of electric vehicles, and the availability of vehicles at the stations. Second, we propose a scalable method for the synthesis of routing and charging policies, with performance guarantees in the limit of large fleet sizes. Third, we validate the theoretical results on a case study of New York City. Collectively, this paper provides a unifying framework for the analysis and control of AMoD systems, which provides a large set of modeling options (e.g., the inclusion of road capacities and charging constraints), and subsumes earlier Jackson and network flow models.
```
@article{IglesiasRossiEtAl2017,
  author = {Iglesias, R. and Rossi, F. and Zhang, R. and Pavone, M.},
  title = {A {BCMP} Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems},
  journal = {{Int. Journal of Robotics Research}},
  year = {2019},
  volume = {38},
  number = {2--3},
  pages = {357--374},
  url = {/wp-content/papercite-data/pdf/Iglesias.Rossi.Zhang.Pavone.IJRR18.pdf},
  owner = {rdit},
  timestamp = {2018-05-06}
}
```
F. Rossi, R. Zhang, Y. Hindy, and M. Pavone, “Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms,” Autonomous Robots, vol. 42, no. 7, pp. 1427–1442, 2018.
[BibTeX] [Abstract]

Abstract: This paper considers the problem of routing and rebalancing a shared fleet of autonomous (i.e., self-driving) vehicles providing on-demand mobility within a capacitated transportation network, where congestion might disrupt throughput. We model the problem within a network flow framework and show that under relatively mild assumptions the rebalancing vehicles, if properly coordinated, do not lead to an increase in congestion (in stark contrast to common belief). From an algorithmic standpoint, such theoretical insight suggests that the problem of routing customers and rebalancing vehicles can be decoupled, which leads to a computationally-efficient routing and rebalancing algorithm for the autonomous vehicles. Numerical experiments and case studies corroborate our theoretical insights and show that the proposed algorithm outperforms state-of-the-art point-to-point methods by avoiding excess congestion on the road. Collectively, this paper provides a rigorous approach to the problem of congestion-aware, system-wide coordination of autonomously driving vehicles, and to the characterization of the sustainability of such robotic systems.
```
@article{RossiZhangEtAl2017,
  author = {Rossi, F. and Zhang, R. and Hindy, Y. and Pavone, M.},
  title = {Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms},
  journal = {{Autonomous Robots}},
  volume = {42},
  number = {7},
  pages = {1427--1442},
  year = {2018},
  doi = {10.1007/s10514-018-9750-5},
  url = {/wp-content/papercite-data/pdf/Rossi.Zhang.Hindy.Pavone.AURO17.pdf},
  owner = {frossi2},
  timestamp = {2018-08-07}
}
```
R. Zhang, F. Rossi, and M. Pavone, “Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms,” in Robotics: Science and Systems, 2016.
[BibTeX] [Abstract]

Abstract: This paper considers the problem of routing and rebalancing a shared fleet of autonomous (i.e., self-driving) vehicles providing on-demand mobility within a capacitated transportation network, where congestion might disrupt throughput. We model the problem within a network flow framework and show that under relatively mild assumptions the rebalancing vehicles, if properly coordinated, do not lead to an increase in congestion (in stark contrast to common belief). From an algorithmic standpoint, such theoretical insight suggests that the problem of routing customers and rebalancing vehicles can be decoupled, which leads to a computationally-efficient routing and rebalancing algorithm for the autonomous vehicles. Numerical experiments and case studies corroborate our theoretical insights and show that the proposed algorithm outperforms state-of-the-art point-to-point methods by avoiding excess congestion on the road. Collectively, this paper provides a rigorous approach to the problem of congestion-aware, system-wide coordination of autonomously driving vehicles, and to the characterization of the sustainability of such robotic systems.
```
@inproceedings{ZhangRossiEtAl2016,
  author = {Zhang, R. and Rossi, F. and Pavone, M.},
  title = {Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms},
  booktitle = {{Robotics: Science and Systems}},
  year = {2016},
  doi = {10.15607/rss.2016.xii.032},
  month = jul,
  url = {http://arxiv.org/pdf/1603.00939.pdf},
  owner = {bylard},
  timestamp = {2017-01-28}
}
```
R. Zhang, “Models and Large-Scale Coordination Algorithms for Autonomous Mobility-on-Demand,” PhD thesis, Stanford University, Dept. of Aeronautics and Astronautics, Stanford, California, 2016.
[BibTeX] [Abstract]

Abstract: Urban mobility in the 21st century faces significant challenges, as the unsustainable trends of urban population growth, congestion, pollution, and low vehicle utilization worsen in large cities around the world. As autonomous vehicle technology draws closer to realization, a solution is beginning to emerge in the form of autonomous mobility-on-demand (AMoD), whereby fleets of self-driving vehicles transport customers within an urban environment. This dissertation introduces a systematic approach to the design, control, and evaluation of these systems. In the first part of the dissertation, a stochastic queueing-theoretical model of AMoD is developed, which allows both the analysis of quality-of-service metrics as well as the synthesis of control policies. This model is then extended to one-way car sharing systems, or human-driven mobility-on-demand (MoD) systems. Based on these models, closed-loop control algorithms are designed to efficiently route empty (rebalancing) vehicles in very large systems with thousands of vehicles. The performance of the algorithms and the potential societal benefits of AMoD and MoD are evaluated through case studies of New York City and Singapore using real-world data. In the second part of the dissertation, additional structural and operational constraints are considered for AMoD systems. First, the impact of AMoD on traffic congestion with respect to the underlying structural properties of the road network is analyzed using a network flow model. In particular, it is shown that empty rebalancing vehicles in AMoD systems will not increase congestion, in stark contrast to popular belief. Finally, the control of AMoD systems with additional operational constraints is studied under a model predictive control framework, with a focus on range and charging constraints of electric vehicles. The technical approach developed in this dissertation allows us to evaluate the societal benefits of AMoD systems as well as lays the foundation for the design and control of future urban transportation networks.
```
@phdthesis{Zhang2016,
  author = {Zhang, R.},
  title = {Models and Large-Scale Coordination Algorithms for {Autonomous} {Mobility-on-Demand}},
  school = {{Stanford University, Dept. of Aeronautics and Astronautics}},
  year = {2016},
  address = {Stanford, California},
  month = jun,
  owner = {bylard},
  timestamp = {2017-01-28},
  url = {/wp-content/papercite-data/pdf/Zhang.PhD16.pdf}
}
```
R. Zhang, F. Rossi, and M. Pavone, “Model Predictive Control of Autonomous Mobility-on-Demand Systems,” in Proc. IEEE Conf. on Robotics and Automation, Stockholm, Sweden, 2016.
[BibTeX] [Abstract]

Abstract: In this paper we present a model predictive control (MPC) approach to optimize vehicle scheduling and routing in an autonomous mobility-on-demand (AMoD) system. In AMoD systems, robotic, self-driving vehicles transport customers within an urban environment and are coordinated to optimize service throughout the entire network. Specifically, we first propose a novel discrete-time model of an AMoD system and we show that this formulation allows the easy integration of a number of real-world constraints, e.g., electric vehicle charging constraints. Second, leveraging our model, we design a model predictive control algorithm for the optimal coordination of an AMoD system and prove its stability in the sense of Lyapunov. At each optimization step, the vehicle scheduling and routing problem is solved as a mixed integer linear program (MILP) where the decision variables are binary variables representing whether a vehicle will 1) wait at a station, 2) service a customer, or 3) rebalance to another station. Finally, by using real-world data, we show that the MPC algorithm can be run in real-time for moderately-sized systems and outperforms previous control strategies for AMoD systems.
```
@inproceedings{ZhangRossiEtAl2016b,
  author = {Zhang, R. and Rossi, F. and Pavone, M.},
  title = {Model Predictive Control of {Autonomous} {Mobility-on-Demand} Systems},
  booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
  year = {2016},
  address = {Stockholm, Sweden},
  doi = {10.1109/ICRA.2016.7487272},
  month = may,
  url = {http://arxiv.org/pdf/1509.03985.pdf},
  owner = {bylard},
  timestamp = {2017-01-28}
}
```
R. Zhang and M. Pavone, “Control of Robotic Mobility-on-Demand Systems: A Queueing-Theoretical Perspective,” Int. Journal of Robotics Research, vol. 35, no. 1–3, pp. 186–203, 2016.
[BibTeX] [Abstract]

Abstract: In this paper we present and analyze a queueing-theoretical model for autonomous mobility-on-demand (MOD) systems where robotic, self-driving vehicles transport customers within an urban environment and rebalance themselves to ensure acceptable quality of service throughout the entire network. We cast an autonomous MOD system within a closed Jackson network model with passenger loss. It is shown that an optimal rebalancing algorithm minimizing the number of (autonomously) rebalancing vehicles and keeping vehicles availabilities balanced throughout the network can be found by solving a linear program. The theoretical insights are used to design a robust, real-time rebalancing algorithm, which is applied to a case study of New York City. The case study shows that the current taxi demand in Manhattan can be met with about 8,000 robotic vehicles (roughly 60% of the size of the current taxi fleet). Finally, we extend our queueing-theoretical setup to include congestion effects, and we study the impact of autonomously rebalancing vehicles on overall congestion. Collectively, this paper provides a rigorous approach to the problem of system-wide coordination of autonomously driving vehicles, and provides one of the first characterizations of the sustainability benefits of robotic transportation networks.
```
@article{ZhangPavone2016,
  author = {Zhang, R. and Pavone, M.},
  title = {Control of Robotic {Mobility-on-Demand} Systems: A Queueing-Theoretical Perspective},
  journal = {{Int. Journal of Robotics Research}},
  year = {2016},
  volume = {35},
  number = {1--3},
  pages = {186--203},
  doi = {10.1177/0278364915581863},
  url = {/wp-content/papercite-data/pdf/Zhang.Pavone.IJRR15.pdf},
  owner = {bylard},
  timestamp = {2017-01-28}
}
```
R. Iglesias, F. Rossi, R. Zhang, and M. Pavone, “A BCMP Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems,” in Workshop on Algorithmic Foundations of Robotics, San Francisco, California, 2016.
[BibTeX] [Abstract]

Abstract: In this paper, we present a queueing network approach to the problem of routing and rebalancing a fleet of self-driving vehicles providing on-demand mobility within a capacitated road network. We refer to such systems as autonomous mobility-on-demand systems, or AMoD. We first cast an AMoD system into a closed, multi-class BCMP queueing network model. Second, we present analysis tools that allow the characterization of performance metrics for a given routing policy, in terms, e.g., of vehicle availabilities and second-order moments of vehicle throughput. Third, we propose a scalable method for the synthesis of routing policies, with performance guarantees in the limit of large fleet sizes. Finally, we validate our theoretical results on a case study of New York City. Collectively, this paper provides a unifying framework for the analysis and control of AMoD systems, which subsumes earlier Jackson and flow network models, provides a quite large set of modeling options (e.g., the inclusion of road capacities and general travel time distributions), and allows the analysis of second and higher-order moments for the performance metrics.
```
@inproceedings{IglesiasRossiEtAl2016,
  author = {Iglesias, R. and Rossi, F. and Zhang, R. and Pavone, M.},
  title = {A {BCMP} Network Approach to Modeling and Controlling {Autonomous} {Mobility-on-Demand} Systems},
  booktitle = {{Workshop on Algorithmic Foundations of Robotics}},
  year = {2016},
  address = {San Francisco, California},
  url = {/wp-content/papercite-data/pdf/Iglesias.Rossi.Zhang.Pavone.WAFR16.pdf},
  owner = {bylard},
  timestamp = {2017-03-07}
}
```
R. Zhang, K. Spieser, E. Frazzoli, and M. Pavone, “Models, Algorithms and Evaluation for Autonomous Mobility-on-Demand Systems,” in American Control Conference, Chicago, Illinois, 2015.
[BibTeX] [Abstract]

Abstract: This tutorial paper examines the operational and economic aspects of autonomous mobility-on-demand (AMoD) systems, a rapidly emerging mode of personal transportation wherein robotic, self-driving vehicles transport customers in a given environment. We address AMoD systems along three dimensions: (1) modeling - analytical models capable of capturing the salient dynamic and stochastic features of customer demand, (2) control - coordination algorithms for the vehicles aimed at stability and subsequently throughput maximization, and (3) economic - fleet sizing and financial analyses for case studies of New York City and Singapore. Collectively, the models and algorithms presented in this paper enable a rigorous assessment of the value of AMoD systems. In particular, the case study of New York City shows that the current taxi demand in Manhattan can be met with about 8,000 robotic vehicles (roughly 70% of the size of the current taxi fleet), while the case study of Singapore suggests that an AMoD system can meet the personal mobility need of the entire population of Singapore with a number of robotic vehicles that is less than 40% of the current number of passenger vehicles. Directions for future research on AMoD systems are presented and discussed.
```
@inproceedings{ZhangSpieserEtAl2015,
  author = {Zhang, R. and Spieser, K. and Frazzoli, E. and Pavone, M.},
  title = {Models, Algorithms and Evaluation for {Autonomous} {Mobility-on-Demand} Systems},
  booktitle = {{American Control Conference}},
  year = {2015},
  address = {Chicago, Illinois},
  doi = {10.1109/ACC.2015.7171122},
  month = jul,
  owner = {bylard},
  timestamp = {2017-01-28},
  url = {/wp-content/papercite-data/pdf/Pavone.ea.ACC15.pdf}
}
```
R. Zhang and M. Pavone, “A Queueing Network Approach to the Analysis and Control of Mobility-on-Demand Systems,” in American Control Conference, Chicago, Illinois, 2015.
[BibTeX] [Abstract]

Abstract: This paper presents a queueing network approach to the analysis and control of mobility-on-demand (MoD) systems for urban personal transportation. A MoD system consists of a fleet of vehicles providing one-way car sharing service and a team of drivers to rebalance such vehicles. The drivers then rebalance themselves by driving select customers similar to a taxi service. We model the MoD system as two coupled closed Jackson networks with passenger loss. We show that the system can be approximately balanced by solving two decoupled linear programs and exactly balanced through nonlinear optimization. The rebalancing techniques are applied to a system sizing example using taxi data in three neighborhoods of Manhattan, which suggests that the optimal vehicle-to-driver ratio in a MoD system is between 3 and 5. Lastly, we formulate a real-time closed-loop rebalancing policy for drivers and demonstrate its stability (in terms of customer wait times) for typical system loads.
```
@inproceedings{ZhangPavone2015,
  author = {Zhang, R. and Pavone, M.},
  title = {A Queueing Network Approach to the Analysis and Control of {Mobility-on-Demand} Systems},
  booktitle = {{American Control Conference}},
  year = {2015},
  address = {Chicago, Illinois},
  doi = {10.1109/ACC.2015.7172070},
  month = jul,
  owner = {bylard},
  timestamp = {2017-01-28},
  url = {http://arxiv.org/pdf/1409.6775v2.pdf}
}
```
R. Zhang and M. Pavone, “Control of Robotic Mobility-on-Demand Systems: a Queueing-Theoretical Perspective,” in Robotics: Science and Systems, Berkeley, California, 2014.
[BibTeX] [Abstract]

Abstract: In this paper we present and analyze a queueing-theoretical model for autonomous mobility-on-demand (MOD) systems where robotic, self-driving vehicles transport customers within an urban environment and rebalance themselves to ensure acceptable quality of service throughout the entire network. We cast an autonomous MOD system within a closed Jackson network model with passenger loss. It is shown that an optimal rebalancing algorithm minimizing the number of (autonomously) rebalancing vehicles and keeping vehicles availabilities balanced throughout the network can be found by solving a linear program. The theoretical insights are used to design a robust, real-time rebalancing algorithm, which is applied to a case study of New York City. The case study shows that the current taxi demand in Manhattan can be met with about 8,000 robotic vehicles (roughly 70% of the size of the current taxi fleet operating in Manhattan). Finally, we extend our queueing-theoretical setup to include congestion effects, and we study the impact of autonomously rebalancing vehicles on overall congestion. Collectively, this paper provides a rigorous approach to the problem of system-wide coordination of autonomously driving vehicles, and provides one of the first characterizations of the sustainability benefits of robotic transportation networks.
```
@inproceedings{ZhangPavone2014,
  author = {Zhang, R. and Pavone, M.},
  title = {Control of Robotic {Mobility-on-Demand} Systems: a Queueing-Theoretical Perspective},
  booktitle = {{Robotics: Science and Systems}},
  year = {2014},
  note = {Best Paper Award Finalist},
  address = {Berkeley, California},
  doi = {10.15607/rss.2014.x.026},
  month = jul,
  owner = {bylard},
  timestamp = {2017-01-28},
  url = {http://web.stanford.edu/~pavone/papers/Zhang.Pavone.RSS14.pdf}
}
```
K. Spieser, K. Treleaven, R. Zhang, E. Frazzoli, D. Morton, and M. Pavone, “Toward a Systematic Approach to the Design and Evaluation of Autonomous Mobility-on-Demand Systems: A Case Study in Singapore,” in Road Vehicle Automation, Springer, 2014.
[BibTeX] [Abstract]

Abstract: The objective of this work is to provide analytical guidelines and financial justification for the design of shared-vehicle mobility-on-demand systems. Specifically, we consider the fundamental issue of determining the appropriate number of vehicles to field in the fleet, and estimate the financial benefits of several models of car sharing. As a case study, we consider replacing all modes of personal transportation in a city such as Singapore with a fleet of shared automated vehicles, able to drive themselves, e.g., to move to a customer’s location. Using actual transportation data, our analysis suggests a shared-vehicle mobility solution can meet the personal mobility needs of the entire population with a fleet whose size is approximately one third of the total number of passenger vehicles currently in operation.
```
@incollection{SpieserTreleavenEtAl2014,
  author = {Spieser, K. and Treleaven, K. and Zhang, R. and Frazzoli, E. and Morton, D. and Pavone, M.},
  title = {Toward a Systematic Approach to the Design and Evaluation of {Autonomous} {Mobility-on-Demand} Systems: A Case Study in {Singapore}},
  booktitle = {Road Vehicle Automation},
  year = {2014},
  doi = {10.1007/978-3-319-05990-7_20},
  url = {http://dspace.mit.edu/handle/1721.1/82904},
  owner = {bylard},
  publisher = {{Springer}},
  timestamp = {2017-06-15}
}
```