提出主动路由框架，让多容量机器人实时响应配送请求并保持系统稳定。
Pro-Routing: Proactive Routing of Autonomous Multi-Capacity Robots for Pickup-and-Delivery Tasks
- 基于前瞻滚动优化，动态适应实时需求变化。
- 理论证明可保证系统稳定，小规模部署下服务率提升6%，等待时间减少33%。
- 适合需高可靠性的城市配送、校园接驳等实时调度场景。
我们研究多机器人系统中，由具备多容量的自主机器人组成的车队，需在空间分布的取送请求下，在固定最大等待时间内完成任务。请求可提前安排或实时到达。路由策略的稳定性定义为策略成本随时间保持有界。以往工作要么离线求解以保证理论稳定性，要么处理实时请求但放弃稳定性保障。本文提出一种新型主动滚动式路由框架，既能适应实时需求，又能理论上保证学习到的路由策略稳定。通过设计一个车队规模算法，确保足够大的车队规模以构建性地实现稳定性。为验证理论结果，我们以哈佛大学晚间校车系统的真实乘车请求为例进行案例研究，并在当前部署的小规模车队上评估性能。相比现有部署算法、贪心启发式及基于蒙特卡洛树搜索的算法，当采用理论推导出的充足车队规模时，本方法保持系统稳定；在较小车队规模下，本方法服务请求量比最接近基线高出6%，中位乘客等待时间降低33%。
原文摘要 · Abstract (English)
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%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。