# Pro-Routing: Proactive Routing of Autonomous Multi-Capacity Robots for Pickup-and-Delivery Tasks

arXiv: https://arxiv.org/abs/2503.24325 · HTML: https://mlsanity.com/paper/2503.24325/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 79 references that are in the map.
- First posted on arXiv 31 Mar 2025.

## Builds on (most cited first, 19 of 19)

- [Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting](https://mlsanity.com/paper/2012.07436/) (2020)
- [A Time Series is Worth 64 Words: Long-term Forecasting with Transformers](https://mlsanity.com/paper/2211.14730/) (2022)
- [iTransformer: Inverted Transformers Are Effective for Time Series Forecasting](https://mlsanity.com/paper/2310.06625/) (2023)
- [TimeMixer: Decomposable Multiscale Mixing for Time Series Forecasting](https://mlsanity.com/paper/2405.14616/) (2024)
- [Deep Time Series Models: A Comprehensive Survey and Benchmark](https://mlsanity.com/paper/2407.13278/) (2024)
- [Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control](https://mlsanity.com/paper/2108.10315/) (2021)
- [Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems](https://mlsanity.com/paper/2011.04222/) (2020)
- [An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services](https://mlsanity.com/paper/2203.15127/) (2022)
- [A Distributed Version of the Hungarian Method for Multi-Robot Assignment](https://mlsanity.com/paper/1805.08712/) (2018)
- [Robust Task Scheduling for Heterogeneous Robot Teams under Capability Uncertainty](https://mlsanity.com/paper/2106.12111/) (2021)
- [Analysis and Control of Autonomous Mobility-on-Demand Systems](https://mlsanity.com/paper/2106.14827/) (2021)
- [Multiagent Reinforcement Learning for Autonomous Routing and Pickup Problem with Adaptation to Variable Demand](https://mlsanity.com/paper/2211.14983/) (2022)
- [Speeding up Routing Schedules on Aisle-Graphs with Single Access](https://mlsanity.com/paper/2102.05733/) (2021)
- [Multi-Robot Pickup and Delivery via Distributed Resource Allocation](https://mlsanity.com/paper/2104.02415/) (2021)
- [Autonomous Delivery of Multiple Packages Using Single Drone in Urban Airspace](https://mlsanity.com/paper/2209.01580/) (2022)
- [Generalized Assignment for Multi-Robot Systems via Distributed Branch-And-Price](https://mlsanity.com/paper/2004.11857/) (2020)
- [Optimizing UAV Recharge Scheduling for Heterogeneous and Persistent Aerial Service](https://mlsanity.com/paper/2205.12656/) (2022)
- [Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare](https://mlsanity.com/paper/2307.02637/) (2023)
- [Approximate Multiagent Reinforcement Learning for On-Demand Urban Mobility Problem on a Large Map (extended version)](https://mlsanity.com/paper/2311.01534/) (2023)

## Abstract (arXiv)

We consider a multi-robot setting, where we have a fleet of multi-capacity autonomous robots that must service spatially distributed pickup-and-delivery requests with fixed maximum wait times. Requests can be either scheduled ahead of time or they can enter the system in real-time. In this setting, stability for a routing policy is defined as the cost of the policy being uniformly bounded over time. Most previous work either solve the problem offline to theoretically maintain stability or they consider dynamically arriving requests at the expense of the theoretical guarantees on stability. In this paper, we aim to bridge this gap by proposing a novel proactive rollout-based routing framework that adapts to real-time demand while still provably maintaining the stability of the learned routing policy. We derive provable stability guarantees for our method by proposing a fleet sizing algorithm that obtains a sufficiently large fleet that ensures stability by construction. To validate our theoretical results, we consider a case study on real ride requests for Harvard's evening Van System. We also evaluate the performance of our framework using the currently deployed smaller fleet size. In this smaller setup, we compare against the currently deployed routing algorithm, greedy heuristics, and Monte-Carlo-Tree-Search-based algorithms. Our empirical results show that our framework maintains stability when we use the sufficiently large fleet size found in our theoretical results. For the smaller currently deployed fleet size, our method services 6% more requests than the closest baseline while reducing median passenger wait times by 33%.