Coalitional Bargaining via Reinforcement Learning: An Application to Collaborative Vehicle Routing
作者: Stephen Mak, Liming Xu, Tim Pearce, Michael Ostroumov, Alexandra Brintrup
分类: cs.LG
发布日期: 2023-10-26
备注: Accepted to NeurIPS 2021 Workshop on Cooperative AI
💡 一句话要点
通过强化学习提出合作博弈解决协作车辆调度问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 协作车辆调度 强化学习 合作博弈 自利代理 最优联盟识别 计算复杂性 物流优化
📋 核心要点
- 传统博弈论方法在协作车辆调度中难以处理特征函数的复杂性，计算成本高。
- 本文提出通过强化学习建模合作博弈，代理隐式推理特征函数，显著降低计算复杂度。
- 实验结果显示，代理在79%情况下识别最优联盟，平均最优性差距为4.2%，运行时间减少62%。
📝 摘要（中文）
协作车辆调度是指配送公司通过共享配送信息来合作执行配送请求，从而实现规模经济，降低成本、温室气体排放和道路拥堵。然而，传统的博弈论解决方案如Shapley值或核值在实际应用中难以计算。本文提出将该问题建模为一个合作博弈游戏，代理不直接访问特征函数，而是隐式推理，从而避免了多次评估车辆调度问题的复杂性。我们的方法具有可扩展性，并考虑了公司的自利特性。实验结果表明，代理在79%的情况下正确识别最优联盟，平均最优性差距为4.2%，运行时间减少62%。
🔬 方法详解
问题定义：本文旨在解决协作车辆调度中的合作博弈问题，传统方法在计算特征函数时面临指数级复杂性，导致难以应用于实际场景。
核心思路：我们提出一种新的建模方式，将问题视为合作博弈，代理通过隐式推理特征函数，避免了多次评估车辆调度问题的需求，从而提高了计算效率。
技术框架：整体框架包括代理的独立近端策略优化（IPPO），代理通过学习自我调整策略，形成有效的合作联盟。主要模块包括状态表示、策略学习和奖励机制。
关键创新：本研究的创新在于引入了隐式特征函数推理，显著降低了计算复杂度，使得在实际应用中更具可行性。与传统方法相比，我们的方法在处理复杂博弈时更加高效。
关键设计：在设计中，我们采用了修改后的独立近端策略优化算法，设置了适当的奖励函数以引导代理学习最优策略，确保了学习过程的稳定性和收敛性。具体的网络结构和参数设置在实验中进行了优化。
🖼️ 关键图片
📊 实验亮点
实验结果显示，代理在79%的情况下能够正确识别最优联盟，平均最优性差距仅为4.2%。此外，运行时间相比于传统方法减少了62%，显示出显著的效率提升，验证了所提方法的有效性。
🎯 应用场景
该研究在配送行业具有广泛的应用潜力，能够帮助配送公司通过合作降低运营成本和环境影响。未来，该方法还可扩展至其他需要合作博弈的领域，如物流、供应链管理和智能交通系统等，推动行业的可持续发展。
📄 摘要（原文）
Collaborative Vehicle Routing is where delivery companies cooperate by sharing their delivery information and performing delivery requests on behalf of each other. This achieves economies of scale and thus reduces cost, greenhouse gas emissions, and road congestion. But which company should partner with whom, and how much should each company be compensated? Traditional game theoretic solution concepts, such as the Shapley value or nucleolus, are difficult to calculate for the real-world problem of Collaborative Vehicle Routing due to the characteristic function scaling exponentially with the number of agents. This would require solving the Vehicle Routing Problem (an NP-Hard problem) an exponential number of times. We therefore propose to model this problem as a coalitional bargaining game where - crucially - agents are not given access to the characteristic function. Instead, we implicitly reason about the characteristic function, and thus eliminate the need to evaluate the VRP an exponential number of times - we only need to evaluate it once. Our contribution is that our decentralised approach is both scalable and considers the self-interested nature of companies. The agents learn using a modified Independent Proximal Policy Optimisation. Our RL agents outperform a strong heuristic bot. The agents correctly identify the optimal coalitions 79% of the time with an average optimality gap of 4.2% and reduction in run-time of 62%.