Federico Rossi
Federico Rossi is a Ph.D. candidate in Aeronautics and Astronautics. He received a B.Sc. in Aerospace Engineering from Politecnico di Milano and a M.Sc. in Space Engineering from Politecnico di Milano and Politecnico di Torino. He is an alumn of the Alta Scuola Politecnica.
Federico’s research focuses on autonomous mobility-on-demand, and in particular on congestion-aware routing and pricing of networks of self-driving vehicles. Federico is also interested in multi-agent decision making, with applications to patrolling and connected cars. Past projects included a collaboration with Universidad san Francisco de Quito and the Galapagos Marine Reserve on multi-UAV patrolling to protect Galapagos sharks from poachers.
In his free time, Federico enjoys astronomy and photography.
For more information, see federico.io.
Currently at NASA Jet Propulsion Laboratory
ASL Publications
-
K. Solovey, S. Bandyopadhyay, F. Rossi, M. T. Wolf, and M. Pavone, “Fast Near-Optimal Heterogeneous Task Allocation via Flow Decomposition,” in Proc. IEEE Conf. on Robotics and Automation, Xi’an, China, 2021.
Abstract: Multi-robot systems are uniquely well-suited to performing complex tasks such as patrolling and tracking, information gathering, and pick-up and delivery problems, offering significantly higher performance than single-robot systems. A fundamental building block in most multi-robot systems is task allocation: assigning robots to tasks (e.g., patrolling an area, or servicing a transportation request) as they appear based on the robots’ states to maximize reward. In many practical situations, the allocation must account for heterogeneous capabilities (e.g., availability of appropriate sensors or actuators) to ensure the feasibility of execution, and to promote a higher reward, over a long time horizon. To this end, we present the FlowDec algorithm for efficient heterogeneous task-allocation achieving an approximation factor of at least 1/2 of the optimal reward. Our approach decomposes the heterogeneous problem into several homogeneous subproblems that can be solved efficiently using min-cost flow. Through simulation experiments, we show that our algorithm is faster by several orders of magnitude than a MILP approach.
@inproceedings{SoloveyBandyopadhyayEtAl2021, author = {Solovey, K. and Bandyopadhyay, S. and Rossi, F. and Wolf, M. T. and Pavone, M.}, title = {Fast Near-Optimal Heterogeneous Task Allocation via Flow Decomposition}, booktitle = {{Proc. IEEE Conf. on Robotics and Automation}}, year = {2021}, address = {Xi'an, China}, month = may, url = {https://arxiv.org/abs/2011.03603}, owner = {kirilsol}, timestamp = {2020-12-07} } -
A. Estandia, M. Schiffer, F. Rossi, J. Luke, E. C. Kara, R. Rajagopal, and M. Pavone, “On the Interaction between Autonomous Mobility on Demand Systems and Power Distribution Networks – An Optimal Power Flow Approach,” IEEE Transactions on Control of Network Systems, vol. 8, no. 3, pp. 1163–1176, 2021.
Abstract: In future transportation systems, the charging behavior of electric Autonomous Mobility on Demand (AMoD) fleets, i.e., fleets of electric self-driving cars that service on-demand trip requests, will likely challenge power distribution networks (PDNs), causing overloads or voltage drops. In this paper, we show that these challenges can be significantly attenuated if the PDNs’ operational constraints and exogenous loads (e.g., from homes or businesses) are accounted for when operating an electric AMoD fleet. We focus on a system-level perspective, assuming full coordination between the AMoD and the PDN operators. From this single entity perspective, we assess potential coordination benefits. Specifically, we extend previous results on an optimization-based modeling approach for electric AMoD systems to jointly control an electric AMoD fleet and a series of PDNs, and analyze the benefit of coordination under load balancing constraints. For a case study of Orange County, CA, we show that the coordination between the electric AMoD fleet and the PDNs eliminates 99% of the overloads and 50% of the voltage drops that the electric AMoD fleet would cause in an uncoordinated setting. Our results show that coordinating electric AMoD and PDNs can help maintain the reliability of PDNs under added electric AMoD charging load, thus significantly mitigating or deferring the need for PDN capacity upgrades.
@article{EstandiaSchifferEtAl2019, author = {Estandia, A. and Schiffer, M. and Rossi, F. and Luke, J. and Kara, E. C. and Rajagopal, R. and Pavone, M.}, title = {On the Interaction between Autonomous Mobility on Demand Systems and Power Distribution Networks -- An Optimal Power Flow Approach}, journal = {{IEEE Transactions on Control of Network Systems}}, year = {2021}, volume = {8}, number = {3}, pages = {1163--1176}, doi = {10.1109/TCNS.2021.3059225}, owner = {jthluke}, timestamp = {2021-02-21}, url = {https://arxiv.org/abs/1905.00200} } -
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} } -
R. A. Brown, F. Rossi, K. Solovey, M. T. Wolf, and M. Pavone, “Exploiting Locality and Structure for Distributed Optimization in Multi-Agent Systems,” in European Control Conference, St. Petersburg, Russia, 2020.
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. Nevertheless, existing algorithms for distributed optimization generally do not exploit the locality structure of the problem, requiring all agents to compute or exchange the full set of decision variables. In this paper, we develop a rigorous notion of "locality" that relates the structural properties of a linearly-constrained convex optimization problem (in particular, the sparsity structure of the constraint matrix and the objective function) to the amount of information that agents should exchange to compute an arbitrarily high-quality approximation to the problem from a cold-start. We leverage the notion of locality to develop a locality-aware distributed optimization algorithm, and we show that, for problems where individual agents only require to know a small portion of the optimal solution, the algorithm requires very limited inter-agent communication. Numerical results show that the convergence rate of our algorithm is directly explained by the locality parameter proposed, and that the proposed theoretical bounds are remarkably tight.
@inproceedings{BrownRossiEtAl20, author = {Brown, R. A. and Rossi, F. and Solovey, K. and Wolf, M. T. and Pavone, M.}, title = {Exploiting Locality and Structure for Distributed Optimization in Multi-Agent Systems}, booktitle = {{European Control Conference}}, year = {2020}, address = {St. Petersburg, Russia}, month = may, url = {/wp-content/papercite-data/pdf/Brown.Rossi.ea.ECC20.pdf}, owner = {rabrown1}, timestamp = {2020-02-25} } -
M. Salazar, N. Lanzetti, F. Rossi, M. Schiffer, and M. Pavone, “Intermodal Autonomous Mobility-on-Demand,” IEEE Transactions on Intelligent Transportation Systems, vol. 21, no. 9, pp. 3946–3960, 2020.
Abstract:
@article{SalazarLanzettiEtAl2019, author = {Salazar, M. and Lanzetti, N. and Rossi, F. and Schiffer, M. and Pavone, M.}, title = {Intermodal Autonomous Mobility-on-Demand}, journal = {{IEEE Transactions on Intelligent Transportation Systems}}, volume = {21}, number = {9}, pages = {3946--3960}, year = {2020}, url = {https://ieeexplore.ieee.org/document/8894439}, owner = {samauro}, timestamp = {2019-11-11} } -
F. Rossi, R. Iglesias, M. Alizadeh, and M. Pavone, “On the Interaction Between Autonomous Mobility-on-Demand Systems and the Power Network: Models and Coordination Algorithms,” IEEE Transactions on Control of Network Systems, vol. 7, no. 1, pp. 384–397, 2020.
Abstract: We study the interaction between a fleet of electric self-driving vehicles servicing on-demand transportation requests (referred to as autonomous mobility-on-demand, or AMoD, systems) and the electric power network. We propose a joint model that captures the coupling between the two systems stemming from the vehicles’ charging requirements, capturing time-varying customer demand, battery depreciation, and power transmission constraints. First, we show that the model is amenable to efficient optimization. Then, we prove that the socially optimal solution to the joint problem is a general equilibrium if locational marginal pricing is used for electricity. Finally, we show that the equilibrium can be computed by selfish transportation and generator operators (aided by a nonprofit independent system operator) without sharing private information. We assess the performance of the approach and its robustness to stochastic fluctuations in demand through case studies and agent-based simulations. Collectively, these results provide a first-of-a-kind characterization of the interaction between AMoD systems and the power network, and shed additional light on the economic and societal value of AMoD.
@article{RossiIglesiasEtAl2018b, author = {Rossi, F. and Iglesias, R. and Alizadeh, M. and Pavone, M.}, title = {On the Interaction Between {Autonomous Mobility-on-Demand} Systems and the Power Network: Models and Coordination Algorithms}, journal = {{IEEE Transactions on Control of Network Systems}}, year = {2020}, volume = {7}, number = {1}, pages = {384--397}, doi = {10.1109/TCNS.2019.2923384}, owner = {jthluke}, timestamp = {2024-10-28}, url = {https://arxiv.org/abs/1709.04906} } -
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.
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.
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} } -
M. Salazar, F. Rossi, M. Schiffer, C. H. Onder, and M. Pavone, “On the Interaction between Autonomous Mobility-on-Demand and the Public Transportation Systems,” in Proc. IEEE Int. Conf. on Intelligent Transportation Systems, Maui, Hawaii, 2018.
Abstract: In this paper we study models and coordination policies for intermodal Autonomous Mobility-on-Demand (AMoD), wherein a fleet of self-driving vehicles provides on-demand mobility jointly with public transit. Specifically, we first present a network flow model for intermodal AMoD, where we capture the coupling between AMoD and public transit and the goal is to maximize social welfare. Second, leveraging such a model, we design a pricing and tolling scheme that allows to achieve the social optimum under the assumption of a perfect market with selfish agents. Finally, we present a real-world case study for New York City. Our results show that the coordination between AMoD fleets and public transit can yield significant benefits compared to an AMoD system operating in isolation.
@inproceedings{SalazarRossiEtAl2018, author = {Salazar, M. and Rossi, F. and Schiffer, M. and Onder, C. H. and Pavone, M.}, title = {On the Interaction between Autonomous Mobility-on-Demand and the Public Transportation Systems}, booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}}, year = {2018}, note = {{Extended version available} at \url{https://arxiv.org/abs/1804.11278}}, address = {Maui, Hawaii}, month = nov, url = {https://arxiv.org/pdf/1804.11278.pdf}, owner = {frossi2}, timestamp = {2019-07-02} } -
F. Rossi, R. Iglesias, M. Alizadeh, and M. Pavone, “On the Interaction Between Autonomous Mobility-on-Demand Systems and the Power Network: Models and Coordination Algorithms,” in Robotics: Science and Systems, Pittsburgh, Pennsylvania, 2018.
Abstract: We study the interaction between a fleet of electric, self-driving vehicles servicing on-demand transportation requests (referred to as Autonomous Mobility-on-Demand, or AMoD, system) and the electric power network. We propose a joint linear model that captures the coupling between the two systems stemming from the vehicles’ charging requirements. The model subsumes existing network flow models for AMoD systems and linear models for the power network, and it captures time-varying customer demand and power generation costs, road congestion, and power transmission and distribution constraints. We then leverage the linear model to jointly optimize the operation of both systems. We propose an algorithmic procedure to losslessly reduce the problem size by bundling customer requests, allowing it to be efficiently solved by state-of-the-art linear programming solvers. Finally, we study the implementation of a hypothetical electric-powered AMoD system in Dallas-Fort Worth, and its impact on the Texas power network. We show that coordination between the AMoD system and the power network can reduce the overall energy expenditure compared to the case where no cars are present (despite the increased demand for electricity) and yield savings of $ 78M per year compared to an uncoordinated scenario. Collectively, the results of this paper provide a first-of-a-kind characterization of the interaction between electric-powered AMoD systems and the electric power network, and shed additional light on the economic and societal value of AMoD.
@inproceedings{RossiIglesiasEtAl2018, author = {Rossi, F. and Iglesias, R. and Alizadeh, M. and Pavone, M.}, title = {On the Interaction Between {Autonomous Mobility-on-Demand} Systems and the Power Network: Models and Coordination Algorithms}, booktitle = {{Robotics: Science and Systems}}, year = {2018}, address = {Pittsburgh, Pennsylvania}, month = jun, note = {{Extended version available at }\url{https://arxiv.org/abs/1709.04906}}, owner = {frossi2}, timestamp = {2018-06-30}, url = {/wp-content/papercite-data/pdf/Rossi.Iglesias.Alizadeh.Pavone.RSS18.pdf} } -
F. Rossi, S. Bandyopadhyay, M. Wolf, and M. Pavone, “Review of Multi-Agent Algorithms for Collective Behavior: a Structural Taxonomy,” in IFAC Workshop on Networked & Autonomous Air & Space Systems, Santa Fe, New Mexico, 2018.
Abstract: In this paper, we review multi-agent collective behavior algorithms in the literature and classify them according to their underlying mathematical structure. For each mathematical technique, we identify the multi-agent coordination tasks it can be applied to, and we analyze its scalability, bandwidth use, and demonstrated maturity. We highlight how versatile techniques such as artificial potential functions can be used for applications ranging from low-level position control to high-level coordination and task allocation, we discuss possible reasons for the slow adoption of complex distributed coordination algorithms in the field, and we highlight areas for further research and development.
@inproceedings{RossiBandyopadhyayEtAl2018, author = {Rossi, F. and Bandyopadhyay, S. and Wolf, M. and Pavone, M.}, title = {Review of Multi-Agent Algorithms for Collective Behavior: a Structural Taxonomy}, booktitle = {{IFAC Workshop on Networked \& Autonomous Air \& Space Systems}}, year = {2018}, address = {Santa Fe, New Mexico}, month = jun, url = {https://arxiv.org/abs/1803.05464}, owner = {frossi2}, timestamp = {2018-02-01} } -
R. Iglesias, F. Rossi, K. Wang, D. Hallac, J. Leskovec, and M. Pavone, “Data-Driven Model Predictive Control of Autonomous Mobility-on-Demand Systems,” in Proc. IEEE Conf. on Robotics and Automation, Brisbane, Australia, 2018.
Abstract: The goal of this paper is to present an end-to-end, data-driven framework to control Autonomous Mobility-on-Demand systems (AMoD, i.e. fleets of self-driving vehicles). We first model the AMoD system using a time-expanded network, and present a formulation that computes the optimal rebalancing strategy (i.e., preemptive repositioning) and the minimum feasible fleet size for a given travel demand. Then, we adapt this formulation to devise a Model Predictive Control (MPC) algorithm that leverages short-term demand forecasts based on historical data to compute rebalancing strategies. We test the end-to-end performance of this controller with a state-of-the-art LSTM neural network to predict customer demand and real customer data from DiDi Chuxing: we show that this approach scales very well for large systems (indeed, the computational complexity of the MPC algorithm does not depend on the number of customers and of vehicles in the system) and outperforms state-of-the-art rebalancing strategies by reducing the mean customer wait time by up to to 89.6%.
@inproceedings{IglesiasRossiEtAl2018, author = {Iglesias, R. and Rossi, F. and Wang, K. and Hallac, D. and Leskovec, J. and Pavone, M.}, title = {Data-Driven Model Predictive Control of Autonomous Mobility-on-Demand Systems}, booktitle = {{Proc. IEEE Conf. on Robotics and Automation}}, year = {2018}, address = {Brisbane, Australia}, month = may, owner = {frossi2}, timestamp = {2018-01-14}, url = {/wp-content/papercite-data/pdf/Iglesias.Rossi.Wang.ea.ICRA18.pdf} } -
F. Rossi, “On the Interaction between Autonomous Mobility-on-Demand Systems and the Built Environment: Models and Large Scale Coordination Algorithms,” PhD thesis, Stanford University, Dept. of Aeronautics and Astronautics, Stanford, California, 2018.
Abstract: Autonomous Mobility-on-Demand systems (that is, fleets of self-driving cars offering on-demand transportation) hold promise to reshape urban transportation by offering high quality of service at lower cost compared to private vehicles. However, the impact of such systems on the infrastructure of our cities (and in particular on traffic congestion and the electric power network) is an active area of research. In particular, Autonomous Mobility-on-Demand (AMoD) systems could greatly increase traffic congestion due to additional "rebalancing" trips required to re-align the distribution of available vehicles with customer demand; furthermore, charging of large fleets of electric vehicles can induce significantly stress in the electric power network, leading to high electricity prices and potential network instability. In this thesis, we build analytical tools and algorithms to model and control the interaction between AMoD systems and our cities. We open our work by exploring the interaction between AMoD systems and urban congestion. Leveraging the theory of network flows, we devise models for AMoD systems that capture endogenous traffic congestion and are amenable to efficient optimization. These models allow us to show the key theoretical result that, under mild assumptions that are substantially verified for U.S. cities, AMoD systems do not increase congestion compared to privately-owned vehicles for a given level of customer demand if empty-traveling vehicles are properly routed. We leverage this insight to design a real-time congestion-aware routing algorithm for empty vehicles; microscopic agent-based simulations with New York City taxi data show that the algorithm significantly reduces congestion compared to a state-of-the-art congestion-agnostic rebalancing algorithm, resulting in 22% lower wait times for AMoD customers. We then devise a randomized congestion-aware routing algorithm for customer-carrying vehicles and prove rigorous analytical bounds on its performance. Preliminary results based on New York City taxi data show that the algorithm could yield a further reduction in congestion and, as a result, 5% lower service times for AMoD customers. We then turn our attention to the interaction between AMoD fleets with electric vehicles and the power network. We extend the network flow model developed in the first part of the thesis to capture the vehicles’ state-of-charge and their interaction with the power network (including charging and the ability to inject power in the network in exchange for a payment, denoted as "vehicle-to-grid"). We devise an algorithmic procedure to losslessly reduce the size of the resulting model, making it amenable to efficient optimization, and test our models and optimization algorithms on a hypothetical deployment of an AMoD system in Dallas-Fort Worth, TX with the goal of maximizing social welfare. Simulation results show that coordination between the AMoD system and the power network can reduce electricity prices by over 180M/year, with savings of 120M/year for local power network customers and $ 35M/year for the AMoD operator. In order to realize such benefits, the transportation operator must cooperate with the power network: we prove that a pricing scheme can be used to enforce the socially optimal solution as a general equilibrium, aligning the interests of a self-interested transportation operator and self-interested power generators with the goal of maximizing social welfare. We then design privacy-preserving algorithms to compute such coordination-promoting prices in a distributed fashion. Finally, we propose a receding-horizon implementation that trades off optimality for speed and demonstrate that it can be deployed in real-time with microscopic simulations in Dallas-Fort Worth. Collectively, these results lay the foundations for congestion-aware and power-aware control of AMoD systems; in particular, the models and algorithms in this thesis provide tools that will enable transportation network operators and urban planners to foster the positive externalities of AMoD and avoid the negative ones, thus fully realizing the benefits of AMoD systems in our cities.
@phdthesis{Rossi2018, author = {Rossi, F.}, title = {On the Interaction between {Autonomous Mobility-on-Demand} Systems and the Built Environment: Models and Large Scale Coordination Algorithms}, school = {{Stanford University, Dept. of Aeronautics and Astronautics}}, year = {2018}, address = {Stanford, California}, month = mar, owner = {frossi2}, timestamp = {2018-03-19}, url = {/wp-content/papercite-data/pdf/Rossi.PhD18.pdf} } -
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.
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} } -
Y. Hindy and F. Rossi, “StanfordASL/matsim-AMoD.” 2017.
Abstract:
@online{HindyRossi2017, author = {Hindy, Y. and Rossi, F.}, title = {{StanfordASL/matsim-AMoD}}, doi = {10.5281/zenodo.1048414}, owner = {frossi2}, timestamp = {2017-11-13}, year = {2017} } -
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.
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, 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.
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. 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.
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} } -
F. Rossi and M. Pavone, “On the Fundamental Limitations of Performance for Distributed Decision-Making in Robotic Networks,” in Proc. IEEE Conf. on Decision and Control, Los Angeles, California, 2014.
Abstract: This paper studies fundamental limitations of performance for distributed decision-making in robotic networks. The class of decision-making problems we consider encompasses a number of prototypical problems such as average-based consensus as well as distributed optimization, leader election, majority voting, MAX, MIN, and logical formulas. We first propose a formal model for distributed computation on robotic networks that is based on the concept of I/O automata and is inspired by the Computer Science literature on distributed computing clusters. Then, we present a number of bounds on time, message, and byte complexity, which we use to discuss the relative performance of a number of approaches for distributed decision-making. From a methodological standpoint, our work sheds light on the relation between the tools developed by the Computer Science and Controls communities on the topic of distributed algorithms.
@inproceedings{RossiPavone2014, author = {Rossi, F. and Pavone, M.}, title = {On the Fundamental Limitations of Performance for Distributed Decision-Making in Robotic Networks}, booktitle = {{Proc. IEEE Conf. on Decision and Control}}, year = {2014}, address = {Los Angeles, California}, doi = {10.1109/CDC.2014.7039760}, month = dec, url = {http://arxiv.org/pdf/1409.4863.pdf}, owner = {bylard}, timestamp = {2017-02-20} } -
F. Rossi and M. Pavone, “Distributed Consensus with Mixed Time/Communication Bandwidth Performance Metrics,” in Allerton Conf. on Communications, Control and Computing, Champaign, Illinois, 2014.
Abstract: In this paper we study the inherent trade-off between time and communication complexity for the distributed consensus problem. In our model, communication complexity is measured as the maximum data throughput (in bits per second) sent through the network at a given instant. Such a notion of communication complexity, referred to as bandwidth complexity, is related to the frequency bandwidth a designer should collectively allocate to the agents if they were to communicate via a wireless channel, which represents an important constraint for dense robotic networks. We prove a lower bound on the bandwidth complexity of the consensus problem and provide a consensus algorithm that is bandwidth-optimal for a wide class of consensus functions. We then propose a distributed algorithm that can trade communication complexity versus time complexity as a function of a tunable parameter, which can be adjusted by a system designer as a function of the properties of the wireless communication channel. We rigorously characterize the tunable algorithm’s worst-case bandwidth complexity and show that it compares favorably with the bandwidth complexity of well-known consensus algorithm.
@inproceedings{RossiPavone2014b, author = {Rossi, F. and Pavone, M.}, title = {Distributed Consensus with Mixed Time/Communication Bandwidth Performance Metrics}, booktitle = {{Allerton Conf. on Communications, Control and Computing}}, year = {2014}, address = {Champaign, Illinois}, doi = {10.1109/ALLERTON.2014.7028468}, url = {http://arxiv.org/pdf/1410.0956.pdf}, owner = {bylard}, timestamp = {2017-01-28} } -
F. Rossi and M. Pavone, “Decentralized Decision-Making on Robotic Networks with Hybrid Performance Metrics,” in Allerton Conf. on Communications, Control and Computing, Champaign, Illinois, 2013.
Abstract: The past decade has witnessed a rapidly growing interest in decentralized algorithms for collective decision-making in cyber-physical networks. For a large variety of settings, control strategies are now known that either minimize time complexity (i.e., convergence time) or optimize communication complexity (i.e., number and size of exchanged messages). Yet, little attention has beed paid to the problem of studying the inherent trade-off between time and communication complexity. Generally speaking, time-optimal algorithms are fast and robust, but require a large (and sometimes impractical) number of exchanged messages; in contrast, communication optimal algorithms minimize the amount of information routed through the network, but are slow and sensitive to link failures. In this paper we address this gap by focusing on a generalized version of the decentralized consensus problem (that includes voting and mediation) on undirected network topologies and in the presence of "infrequent" link failures. We present and rigorously analyze a tunable, semi-hierarchical algorithm, where the tuning parameter allows a graceful transition from time-optimal to communication-optimal performance (hence, allowing hybrid performance metrics), and determines the algorithm’s robustness, measured as the time required to recover from a failure. An interesting feature of our algorithm is that it leads the decision-making agents to self-organize into a semi-hierarchical structure with variable-size clusters, among which information is flooded. Our results make use of a novel connection between the consensus problem and the theory of gamma synchronizers. Simulation experiments are presented and discussed.
@inproceedings{RossiPavone2013, author = {Rossi, F. and Pavone, M.}, title = {Decentralized Decision-Making on Robotic Networks with Hybrid Performance Metrics}, booktitle = {{Allerton Conf. on Communications, Control and Computing}}, year = {2013}, address = {Champaign, Illinois}, doi = {10.1109/Allerton.2013.6736546}, month = oct, url = {/wp-content/papercite-data/pdf/Rossi.Pavone.Allerton13.pdf}, owner = {bylard}, timestamp = {2017-02-20} }