Real-time Control of Electric Autonomous Mobility-on-Demand Systems via Graph Reinforcement Learning

📄 arXiv: 2311.05780v2 📥 PDF

作者: Aaryan Singhal, Daniele Gammelli, Justin Luke, Karthik Gopalakrishnan, Dominik Helmreich, Marco Pavone

分类: eess.SY, cs.LG, cs.RO

发布日期: 2023-11-09 (更新: 2024-04-04)

备注: 9 pages, revised SF travel data, includes additional experimental results, content and clarification revisions per reviewer feedback, and typo fixes

期刊: 2024 European Control Conference (ECC), pp. 1407-1414, 2024

DOI: 10.23919/ECC64448.2024.10591098

💡 一句话要点

通过图强化学习提出实时控制电动自主按需出行系统

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 电动出行 强化学习 图网络 实时决策 城市交通 优化算法 自主系统

📋 核心要点

  1. 现有的E-AMoD系统在实时决策方面面临挑战，传统线性规划方法无法满足实时性要求。
  2. 本文提出了一种基于图网络的强化学习框架，通过双层形式优化E-AMoD控制问题，提升了可扩展性和性能。
  3. 实验结果显示，该方法在计算速度上提升超过100倍，并在利润上达到理论最优解的89%，显示出显著的效果提升。

📝 摘要（中文）

电动自主按需出行（E-AMoD）车队的运营者需要实时做出多项决策，如将可用车辆匹配到乘车请求、将闲置车辆重新平衡到高需求区域以及为车辆充电以确保足够的续航。虽然可以将此问题建模为优化流的线性规划，但其规模使得在实际环境中难以实时实现。本文通过强化学习的视角提出E-AMoD控制问题，并提出基于图网络的框架，以显著提高可扩展性和性能。具体而言，我们采用双层形式，利用图网络强化学习代理指定空间-充电图中的期望下一状态，并求解更易处理的线性规划以实现该期望状态。实验表明，该方法在旧金山和纽约市的真实数据上实现了理论最优解利润的89%，并在计算时间上实现了超过100倍的加速。我们还展示了学习策略在跨城市泛化和服务区域扩展等任务上的零-shot迁移能力，显示了框架的实用性、可扩展性和灵活性。最后，该方法在与最佳领域特定启发式方法的比较中，利润提高了最多3.2倍，且运行时间相当。

🔬 方法详解

问题定义：本文旨在解决电动自主按需出行系统中的实时决策问题，现有的线性规划方法由于规模庞大，无法在实际环境中实现实时控制。

核心思路：论文提出通过强化学习，特别是图网络，来优化E-AMoD控制问题。通过指定期望状态并求解更易处理的线性规划，来实现实时决策。

技术框架：整体框架包括两个主要模块：第一，图网络强化学习代理用于指定期望的下一状态；第二，求解线性规划以实现该状态，确保可行性。

关键创新：最重要的创新在于将图网络与强化学习结合，显著提高了系统的可扩展性和实时性能，区别于传统的线性规划方法。

关键设计：在设计中，采用了双层优化结构，关键参数设置和损失函数设计确保了学习过程的稳定性和有效性，网络结构则基于图神经网络，适应性强。

📊 实验亮点

实验结果显示，所提出的方法在计算时间上实现了超过100倍的加速，并在利润上达到了理论最优解的89%。此外，该方法在与最佳领域特定启发式方法的比较中，利润提高了最多3.2倍，且运行时间相当，展示了其优越性。

🎯 应用场景

该研究的潜在应用领域包括城市交通管理、共享出行服务和智能交通系统等。通过优化电动自主出行系统的实时决策能力，能够提高运营效率，减少交通拥堵，并为未来的智能城市发展提供支持。

📄 摘要（原文）

Operators of Electric Autonomous Mobility-on-Demand (E-AMoD) fleets need to make several real-time decisions such as matching available vehicles to ride requests, rebalancing idle vehicles to areas of high demand, and charging vehicles to ensure sufficient range. While this problem can be posed as a linear program that optimizes flows over a space-charge-time graph, the size of the resulting optimization problem does not allow for real-time implementation in realistic settings. In this work, we present the E-AMoD control problem through the lens of reinforcement learning and propose a graph network-based framework to achieve drastically improved scalability and superior performance over heuristics. Specifically, we adopt a bi-level formulation where we (1) leverage a graph network-based RL agent to specify a desired next state in the space-charge graph, and (2) solve more tractable linear programs to best achieve the desired state while ensuring feasibility. Experiments using real-world data from San Francisco and New York City show that our approach achieves up to 89% of the profits of the theoretically-optimal solution while achieving more than a 100x speedup in computational time. We further highlight promising zero-shot transfer capabilities of our learned policy on tasks such as inter-city generalization and service area expansion, thus showing the utility, scalability, and flexibility of our framework. Finally, our approach outperforms the best domain-specific heuristics with comparable runtimes, with an increase in profits by up to 3.2x.