Kiril Solovey

ASL Publications

D. Jalota, K. Solovey, K. Gopalakrishnan, S. Zoepf, H. Balakrishnan, and M. Pavone, “When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes,” in IEEE Transactions on Control of Network Systems, 2023. (In Press)
[BibTeX] [Abstract]

Abstract: Congestion pricing has long been hailed as a means to mitigate traffic congestion; however, its practical adoption has been limited due to the resulting social inequity issue, e.g., low-income users are priced out off certain roads. This issue has spurred interest in the design of equitable mechanisms that aim to refund the collected toll revenues as lump-sum transfers to users. Although revenue refunding has been extensively studied for over three decades, there has been no thorough characterization of how such schemes can be designed to simultaneously achieve system efficiency and equity objectives. In this work, we bridge this gap through the study of congestion pricing and revenue refunding (CPRR) schemes in non-atomic congestion games. We first develop CPRR schemes, which in comparison to the untolled case, simultaneously (i) increase system efficiency and (ii) decrease wealth inequality, while being (iii) user-favorable: irrespective of their initial wealth or values-of-time (which may differ across users) users would experience a lower travel cost after the implementation of the proposed scheme. We then characterize the set of optimal user-favorable CPRR schemes that simultaneously maximize system efficiency and minimize wealth inequality. These results assume a well-studied behavior model of users minimizing a linear function of their travel times and tolls, without considering refunds. We also study a more complex behavior model wherein users are influenced by and react to the amount of refund that they receive. Although, in general, the two models can result in different outcomes in terms of system efficiency and wealth inequality, we establish that those outcomes coincide when the aforementioned optimal CPRR scheme is implemented. Overall, our work demonstrates that through appropriate refunding policies we can achieve system efficiency while reducing wealth inequality.
```
@inproceedings{JalotaSoloveyGopalakrishnanEtAl2023,
  author = {Jalota, D. and Solovey, K. and Gopalakrishnan, K. and Zoepf, S. and Balakrishnan, H. and Pavone, M.},
  title = {When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes},
  booktitle = {{IEEE Transactions on Control of Network Systems}},
  note = {In press},
  year = {2023},
  month = oct,
  keywords = {press},
  owner = {devanshjalota},
  timestamp = {2021-06-22},
  url = {https://ieeexplore.ieee.org/document/10319707}
}
```
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.
[BibTeX] [Abstract]

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}
}
```
D. Dayan, K. Solovey, M. Pavone, and D. Halperin, “Near-Optimal Multi-Robot Motion Planning with Finite Sampling,” IEEE Transactions on Robotics, vol. 39, no. 5, pp. 3422–3436, 2023.
[BibTeX] [Abstract]

Abstract: An underlying structure in several sampling-based methods for continuous multi-robot motion planning (MRMP) is the tensor roadmap (TR), which emerges from combining multiple PRM graphs constructed for the individual robots via a tensor product. We study the conditions under which the TR encodes a near-optimal solution for MRMP—satisfying these conditions implies near optimality for a variety of popular planners, including dRRT*, and the discrete methods M* and CBS when applied to the continuous domain. We develop the first finite-sample analysis of this kind, which specifies the number of samples, their deterministic distribution, and magnitude of the connection radii that should be used by each individual PRM graph, to guarantee near-optimality using the TR. This significantly improves upon a previous asymptotic analysis, wherein the number of samples tends to infinity, and supports guaranteed high-quality solutions in practice, within bounded running time. To achieve our new result, we first develop a sampling scheme, which we call the staggered grid, for finite-sample motion planning for individual robots, which requires significantly less samples than previous work. We then extend it to the much more involved MRMP setting which requires to account for interactions among multiple robots. Finally, we report on a few experiments that serve as a verification of our theoretical findings and raise interesting questions for further investigation.
```
@article{DayanSoloveyEtAl2021,
  author = {Dayan, D. and Solovey, K. and Pavone, M. and Halperin, D.},
  title = {Near-Optimal Multi-Robot Motion Planning with Finite Sampling},
  journal = {{IEEE Transactions on Robotics}},
  volume = {39},
  number = {5},
  pages = {3422--3436},
  year = {2023},
  url = {https://arxiv.org/abs/2011.08944},
  owner = {kirilsol},
  timestamp = {2024-02-29}
}
```
A. Wu, T. Lew, K. Solovey, E. Schmerling, and M. Pavone, “Robust-RRT: Probabilistically-Complete Motion Planning for Uncertain Nonlinear Systems,” in Int. Symp. on Robotics Research, 2022.
[BibTeX] [Abstract]

Abstract: Robust motion planning entails computing a global motion plan that is safe under all possible uncertainty realizations, be it in the system dynamics, the robot’s initial position, or with respect to external disturbances. Current approaches for robust motion planning either lack theoretical guarantees, or make restrictive assumptions on the system dynamics and uncertainty distributions. In this paper, we address these limitations by proposing the robust rapidly-exploring random-tree (Robust-RRT) algorithm, which integrates forward reachability analysis directly into sampling-based control trajectory synthesis. We prove that Robust-RRT is probabilistically complete (PC) for nonlinear Lipschitz continuous dynamical systems with bounded uncertainty. In other words, Robust-RRT eventually finds a robust motion plan that is feasible under all possible uncertainty realizations assuming such a plan exists. Our analysis applies even to unstable systems that admit only short-horizon feasible plans; this is because we explicitly consider the time evolution of reachable sets along control trajectories. Thanks to the explicit consideration of time dependency in our analysis, PC applies to unstabilizable systems. To the best of our knowledge, this is the most general PC proof for robust sampling-based motion planning, in terms of the types of uncertainties and dynamical systems it can handle. Considering that an exact computation of reachable sets can be computationally expensive for some dynamical systems, we incorporate sampling-based reachability analysis into Robust-RRT and demonstrate our robust planner on nonlinear, underactuated, and hybrid systems.
```
@inproceedings{WuLewEtAl2022,
  author = {Wu, A. and Lew, T. and Solovey, K. and Schmerling, E. and Pavone, M.},
  booktitle = {{Int. Symp. on Robotics Research}},
  title = {{Robust-RRT}: Probabilistically-Complete Motion Planning for Uncertain Nonlinear Systems},
  year = {2022},
  month = may,
  keywords = {pub},
  owner = {lew},
  timestamp = {2022-05-22},
  url = {https://arxiv.org/abs/2205.07728}
}
```
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.
[BibTeX] [Abstract]

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}
}
```
S. Choudhury, K. Solovey, and M. P. Kochenderfer, “Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks,” in Proc. Int. Conf. on Autonomous Agents and Multiagent Systems, 2022.
[BibTeX] [Abstract]

Abstract: We address the problem of routing a team of drones and trucks over large-scale urban road networks. To conserve their limited flight energy, drones can use trucks as temporary modes of transit en route to their own destinations. Such coordination can yield significant savings in total vehicle distance traveled, i.e., truck travel distance and drone flight distance, compared to operating drones and trucks independently. But it comes at the potentially prohibitive computational cost of deciding which trucks and drones should coordinate and when and where it is most beneficial to do so. We tackle this fundamental trade-off by decoupling our overall intractable problem into tractable sub-problems that we solve stage-wise. The first stage solves only for trucks, by computing paths that make them more likely to be useful transit options for drones. The second stage solves only for drones, by routing them over a composite of the road network and the transit network defined by truck paths from the first stage. We design a comprehensive algorithmic framework that frames each stage as a multi-agent path finding problem and implement two distinct methods for solving them. We evaluate our approach on extensive simulations with up to 100 agents on the real-world Manhattan road network containing nearly 4500 vertices and 10000 edges. Our framework saves on more than 50% of vehicle distance traveled compared to independently solving for trucks and drones, and computes solutions for all settings within 5 minutes on commodity hardware.
```
@inproceedings{ChoudhurySoloveyEtAl2022,
  author = {Choudhury, S. and Solovey, K. and Kochenderfer, M. Pavone},
  title = {Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks},
  booktitle = {{Proc. Int. Conf. on Autonomous Agents and Multiagent Systems}},
  year = {2022},
  keywords = {pub},
  owner = {kirilsol},
  timestamp = {2021-10-17}
}
```
D. Jalota, K. Solovey, K. Gopalakrishnan, S. Zoepf, H. Balakrishnan, and M. Pavone, “When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes,” in ACM Conf. on Equity and Access in Algorithms, Mechanisms, and Optimization, Online, 2021.
[BibTeX] [Abstract]

Abstract: Congestion pricing has long been hailed as a means to mitigate traffic congestion; however, its practical adoption has been limited due to the resulting social inequity issue, e.g., low-income users are priced out off certain roads. This issue has spurred interest in the design of equitable mechanisms that aim to refund the collected toll revenues as lump-sum transfers to users. Although revenue refunding has been extensively studied for over three decades, there has been no thorough characterization of how such schemes can be designed to simultaneously achieve system efficiency and equity objectives. In this work, we bridge this gap through the study of congestion pricing and revenue refunding (CPRR) schemes in non-atomic congestion games. We first develop CPRR schemes, which in comparison to the untolled case, simultaneously (i) increase system efficiency and (ii) decrease wealth inequality, while being (iii) user-favorable: irrespective of their initial wealth or values-of-time (which may differ across users) users would experience a lower travel cost after the implementation of the proposed scheme. We then characterize the set of optimal user-favorable CPRR schemes that simultaneously maximize system efficiency and minimize wealth inequality. These results assume a well-studied behavior model of users minimizing a linear function of their travel times and tolls, without considering refunds. We also study a more complex behavior model wherein users are influenced by and react to the amount of refund that they receive. Although, in general, the two models can result in different outcomes in terms of system efficiency and wealth inequality, we establish that those outcomes coincide when the aforementioned optimal CPRR scheme is implemented. Overall, our work demonstrates that through appropriate refunding policies we can achieve system efficiency while reducing wealth inequality.
```
@inproceedings{JalotaEtAl2021,
  author = {Jalota, D. and Solovey, K. and Gopalakrishnan, K. and Zoepf, S. and Balakrishnan, H. and Pavone, M.},
  title = {When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes},
  booktitle = {{ACM Conf. on Equity and Access in Algorithms, Mechanisms, and Optimization}},
  year = {2021},
  address = {Online},
  month = oct,
  owner = {devanshjalota},
  timestamp = {2021-06-22},
  url = {https://dl.acm.org/doi/10.1145/3465416.3483296}
}
```
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.
[BibTeX] [Abstract]

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}
}
```
S. Choudhury, K. Solovey, and M. Kochenderfer M. Pavone, “Efficient Large-Scale Multi-Drone Delivery Using Transit Networks,” Journal of Artificial Intelligence Research, vol. 70, pp. 757–788, Mar. 2021.
[BibTeX] [Abstract]

Abstract: We consider the problem of controlling a large fleet of drones to deliver packages simultaneously across broad urban areas. To conserve their limited flight range, drones can seamlessly hop between and ride on top of public transit vehicles (e.g., buses and trams). We design a novel comprehensive algorithmic framework that strives to minimize the maximum time to complete any delivery. We address the multifaceted complexity of the problem through a two-layer approach. First, the upper layer assigns drones to package delivery sequences with a provably near-optimal polynomial-time task allocation algorithm. Then, the lower layer executes the allocation by periodically routing the fleet over the transit network while employing efficient bounded-suboptimal multi-agent pathfinding techniques tailored to our setting. We present extensive experiments supporting the efficiency of our approach on settings with up to 200 drones, 5000 packages, and large transit networks of up to 8000 stops in San Francisco and the Washington DC area. Our results show that the framework can compute solutions within a few seconds (up to 2 minutes for the largest settings) on commodity hardware, and that drones travel up to 450% of their flight range by using public transit.
```
@article{ChoudhurySoloveyETAL2020j,
  author = {Choudhury, S. and Solovey, K. and Kochenderfer, M. Pavone, M.},
  title = {Efficient Large-Scale Multi-Drone Delivery Using Transit Networks},
  journal = {{Journal of Artificial Intelligence Research}},
  year = {2021},
  volume = {70},
  pages = {757--788},
  month = mar,
  owner = {kirilsol},
  timestamp = {2021-03-23},
  url = {https://doi.org/10.1613/jair.1.12450}
}
```
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.
[BibTeX] [Abstract]

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. 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.
[BibTeX] [Abstract]

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}
}
```
K. Solovey, L. Janson, E. Schmerling, E. Frazzoli, and M. Pavone, “Revisiting the Asymptotic Optimality of RRT*,” in Proc. IEEE Conf. on Robotics and Automation, Paris, France, 2020.
[BibTeX] [Abstract]

Abstract: RRT* is one of the most widely used sampling-based algorithms for asymptotically-optimal motion planning. This algorithm laid the foundations for optimality in motion planning as a whole, and inspired the development of numerous new algorithms in the field, many of which build upon RRT* itself. In this paper, we first identify a logical gap in the optimality proof of RRT*, which was developed in Karaman and Frazzoli (2011). Then, we present an alternative and mathematically-rigorous proof for asymptotic optimality. Our proof suggests that the connection radius used by RRT* should be increased from γ(\frac\log nn)^1/d to γ’ (\frac\log nn)^1/(d+1) in order to account for the additional dimension of time that dictates the samples’ ordering. Here gamma, γ’ are constants, and n, d are the number of samples and the dimension of the problem, respectively.
```
@inproceedings{SoloveyJansonETAL2020,
  author = {Solovey, K. and Janson, L. and Schmerling, E. and Frazzoli, E. and Pavone, M.},
  title = {Revisiting the Asymptotic Optimality of RRT*},
  booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
  year = {2020},
  address = {Paris, France},
  month = may,
  url = {https://ieeexplore.ieee.org/document/9196553},
  timestamp = {2020-02-25}
}
```
S. Choudhury, K. Solovey, and M. Kochenderfer M. Pavone, “Efficient Large-Scale Multi-Drone Delivery Using Transit Networks,” in Proc. IEEE Conf. on Robotics and Automation, Paris, France, 2020.
[BibTeX] [Abstract]

Abstract: We consider the problem of controlling a large fleet of drones to deliver packages simultaneously across broad urban areas. To conserve their limited flight range, drones can seamlessly hop between and ride on top of public transit vehicles (e.g., buses and trams). We design a novel comprehensive algorithmic framework that strives to minimize the maximum time to complete any delivery. We address the multifaceted complexity of the problem through a two-layer approach. First, the upper layer assigns drones to package delivery sequences with a provably near-optimal polynomial-time task allocation algorithm. Then, the lower layer executes the allocation by periodically routing the fleet over the transit network while employing efficient bounded-suboptimal multi-agent pathfinding techniques tailored to our setting. We present extensive experiments supporting the efficiency of our approach on settings with up to 200 drones, 5000 packages, and large transit networks of up to 8000 stops in San Francisco and the Washington DC area. Our results show that the framework can compute solutions within a few seconds (up to 2 minutes for the largest settings) on commodity hardware, and that drones travel up to 450% of their flight range by using public transit.
```
@inproceedings{ChoudhurySoloveyETAL2020,
  author = {Choudhury, S. and Solovey, K. and Kochenderfer, M. Pavone, M.},
  title = {Efficient Large-Scale Multi-Drone Delivery Using Transit Networks},
  booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
  year = {2020},
  address = {Paris, France},
  month = may,
  owner = {kirilsol},
  timestamp = {2020-09-22},
  url = {https://ieeexplore.ieee.org/document/9197313}
}
```
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.
[BibTeX] [Abstract]

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}
}
```
K. Solovey, M. Salazar, and M. Pavone, “Scalable and Congestion-aware Routing for Autonomous Mobility-on-Demand via Frank-Wolfe Optimization,” in Robotics: Science and Systems, Freiburg im Breisgau, Germany, 2019.
[BibTeX] [Abstract]

Abstract: We consider the problem of vehicle routing for Autonomous Mobility-on-Demand (AMoD) systems, wherein a fleet of self-driving vehicles provides on-demand mobility in a given environment. Specifically, the task it to compute routes for the vehicles (both customer-carrying and empty travelling) so that travel demand is fulfilled and operational cost is minimized. The routing process must account for congestion effects affecting travel times, as modeled via a volume-delay function (VDF). Route planning with VDF constraints is notoriously challenging, as such constraints compound the combinatorial complexity of the routing optimization process. Thus, current solutions for AMoD routing resort to relaxations of the congestion constraints, thereby trading optimality with computational efficiency. In this paper, we present the first computationally-efficient approach for AMoD routing where VDF constraints are explicitly accounted for. We demonstrate that our approach is faster by at least one order of magnitude with respect to the state of the art, while providing higher quality solutions. From a methodological standpoint, the key technical insight is to establish a mathematical reduction of the AMoD routing problem to the classical traffic assignment problem (a related vehicle-routing problem where empty traveling vehicles are not present). Such a reduction allows us to extend powerful algorithmic tools for traffic assignment, which combine the classic Frank-Wolfe algorithm with modern techniques for pathfinding, to the AMoD routing problem. We provide strong theoretical guarantees for our approach in terms of near-optimality of the returned solution.
```
@inproceedings{SoloveySalazarEtAl2019,
  author = {Solovey, K. and Salazar, M. and Pavone, M.},
  title = {Scalable and Congestion-aware Routing for Autonomous Mobility-on-Demand via Frank-Wolfe Optimization},
  booktitle = {{Robotics: Science and Systems}},
  year = {2019},
  address = {Freiburg im Breisgau, Germany},
  month = jun,
  url = {/wp-content/papercite-data/pdf/Solovey.Salazar.Pavone.RSS19.pdf},
  owner = {samauro},
  timestamp = {2019-02-02}
}
```

Contacts:

Kiril Solovey

Awards:

ASL Publications