1、2023-05-10计算机应用,Journal of Computer Applications2023,43(5):1620-1624ISSN 1001-9081CODEN JYIIDUhttp：/基于共享注意力的多智能体强化学习订单派送黄晓辉，杨凯铭*，凌嘉壕（华东交通大学 信息工程学院，南昌 330013）（通信作者电子邮箱）摘要：网约车因方便、快捷成为现今人们出行热门之选，如何更高效地派送合适的订单将乘客送到目的地是如今研究的热点。许多研究着重于训练单智能体，再由它统一分配订单，车辆本身并不参与决策。针对以上问题，提出一种基于共享注意力的多智能体强化学习（SARL）算法。该算法将订单派
2、送问题建模为一个马尔可夫决策过程，运用多智能体强化学习，通过集中训练、分散执行的方式让每个智能体均成为决策者；同时加入共享注意力机制，让智能体彼此共享信息并合作。最后，在不同尺度地图、不同乘客数以及不同车辆数情形下与完全随机匹配（Random）、贪婪算法（Greedy）、多智能体强化学习算法IDQN和混合Q值网络（QMIX）进行对比。结果显示，在固定和可变的车辆与乘客组合情况下，SARL算法在三个不同尺度地图（100100、1010和500500）的时间效率均达到了最优，验证了算法的泛化性能和稳定性。SARL算法可以优化车辆和乘客的配对，减少乘客等待时间，提升乘客满意度。关键词：机器学习；深度
3、强化学习；注意力机制；多智能体强化学习；车辆订单派送中图分类号：TP18；TP391 文献标志码：AOrder dispatching by multi-agent reinforcement learning based on shared attentionHUANG Xiaohui，YANG Kaiming*，LING Jiahao（School of Information Engineering，East China Jiaotong University，Nanchang Jiangxi 330013，China）Abstract:Ride-hailing has become a
4、 popular choice for people to travel due to its convenience and speed，how to efficiently dispatch the appropriate orders to deliver passengers to the destination is a research hotspot today.Many researches focus on training a single agent，which then uniformly distributies orders，without the vehicle
5、itself being involved in the decision making.To solve the above problem，a multi-agent reinforcement learning algorithm based on shared attention，named SARL（Shared Attention Reinforcement Learning），was proposed.In the algorithm，the order dispatching problem was modeled as a Markov decision process，an
6、d multi-agent reinforcement learning was used to make each agent become a decision-maker through centralized training and decentralized execution.Meanwhile，the shared attention mechanism was added to make the agents share information and cooperate with each other.Comparison experiments with Random m
7、atching（Random），Greedy algorithm（Greedy），Individual Deep-Q-Network（IDQN）and Q-learning MIXing network（QMIX）were conducted under different map scales，different number of passengers and different number of vehicles.Experimental results show that the SARL algorithm achieves optimal time efficiency in t
8、hree different scale maps（100100，1010 and 500500）for fixed and variable vehicle and passenger combinations，which verifies the generalization performance and stable performance of the SARL algorithm.The SARL algorithm can optimize the matching of vehicles and passengers，reduce the waiting time of pas
9、sengers and improve the satisfaction of passengers.Key words:machine learning;deep reinforcement learning;attention mechanism;multi-agent reinforcement learning;vehicle order dispatching0 引言 近年来，随着互联网高速发展，人们的出行方式有了很大改变。“网约车”走入了人们的生活，随时随地约车、方便快捷且舒适等特点使“网约车”迅速成为人们出行的热门之选。随着需求的不断增长，网约车平台也面临着一项难题，即如何高效地
10、将订单派送给合适的司机。高效的订单派送能极大地优化交通资源分配，同时提高司机及平台收入，并提高用户体验及出行效率，对交通拥堵的情况也略有改善1-3。现今，强化学习方法受到了广泛的关注，主要被用于解决序列决策问题，并且在解决极其复杂的决策问题方面取得了巨大的成功4-7。例如 Mnih 等8提出了一种新的智能决策方法，称为深度Q网络（Deep-Q-Network，DQN），它可以储存训练中的经验，直接从历史经验中学习成功的策略。Rashid等9提出了一种新颖的基于价值的强化学习方法，可以端到端进行集中的训练，以分散的方式执行策略，称为混合Q值网络（Q-learning MIXing network
11、，QMIX）。QMIX设计了一个文章编号：1001-9081（2023）05-1620-05DOI：10.11772/j.issn.1001-9081.2022040630收稿日期：2022-05-06；修回日期：2022-07-11；录用日期：2022-07-13。基金项目：国家自然科学基金资助项目（62062033）；江西省自然科学基金资助项目（20212BAB202008）。作者简介：黄晓辉（1984），男，江西上高人，副教授，博士，CCF会员，主要研究方向：深度学习、智慧交通；杨凯铭（1996），男，江西南昌人，硕士研究生，主要研究方向：深度强化学习、智慧交通；凌嘉壕（1999），男，
12、湖南长沙人，硕士研究生，主要研究方向：深度强化学习、智慧交通。第 5 期黄晓辉等：基于共享注意力的多智能体强化学习订单派送神经网络来整合每个智能体的局部值函数得到联合动作值函数，确保整体最优解和个体最优解的一致。基于此，De Lima等10提出将 QMIX 用于订单派送，取得了不错的效果；但是，该算法忽视了车辆与车辆之间的关联，单纯地认为车辆与车辆是完全独立的个体，从而导致车辆基于贪婪的原则选择订单，可能错失整体的更优解。本文提出一种基于共享注意力的多智能体强化学习（Shared Attention Reinforcement Learning，SARL）算法，在不改变先到先服务的原则下，融入
13、共享注意力模块，让车辆与车辆互相关注、合作，以获得整体更优解。本文的主要工作如下：将订单匹配问题建模为以最快送达时间为目标的马尔可夫决策过程，并基于此提出了SARL算法；设计了一个共享注意力模块，将注意力机制与多智能体强化学习相结合用于订单派送；最后在不同规模的数据集上验证了本文算法的优越性以及泛化能力。1 相关工作 目前基于强化学习的订单派送算法主要分为两类：基于价值网络的单智能体强化学习算法和基于多智能体的强化学习算法。1.1基于价值网络的单智能体强化学习算法该方法主要将整体订单信息输入控制中枢，然后由控制中枢经过学习和训练后分配给合适的车辆完成订单。如图1所示，智能体读取环境状态信息，通
14、过价值网络对状态和可行动作进行评估，选择其中一种动作执行；动作改变环境，环境给出新的状态和执行该动作的奖励，以此循环。这种方法的特点就是集中训练、统一分配，控制中枢会根据价值网络进行学习，评估每一个动作将带来的影响价值，然后根据价值选择合适的动作。Pan等11开发了一种新的深度强化学习算法，称为层次强化定价（Hierarchical Reinforcement Pricing，HRP）。HRP解决了由于高维空间和时间依赖而产生的复杂性问题，减少了输入空间和训练损失。与现有算法相比，HRP算法提高了收敛性，取得了更好的性能。Tang 等12提出了小脑价值网络（Cerebellar Value N
15、ETwork，CVNET）模型，该模型将地图分层平铺，然后通过小脑嵌入组合在一起，帮助网络学习比经纬度更抽象的概念比如街道、小区、城市等；其次针对不同区域比如市中心或者郊区网络能自适应学习并结合不同地图精度来获得更准确的状态表达。Wang等13提出了基于行动搜索的深度 Q 网络学习方法，为了提高模型的适应性和效率，还提出了一种相关特征渐进迁移的方法，并证明了先从源城市学习到分配策略，然后再将它迁移到目标城市或者同一个城市的不同时间的方法，比没有迁移的学习效果更好。van Hasselt 等14提出了一种新的时差学习算法多 Q 学习（Multi Q-Learning，MQL）。MQL 算法试图通
16、过使用多动作值函数近似来提高值估计的稳定性。Chilukuri等15提出了时间约束网络中联合路由和调度的深度强化学习（deep REinforcement learning method for joint routing and sCheduling in time-ConstrainEd network，RECCE）算法，用于集中控制时间受限网络中的联合路由与调度，不同于其他启发式算法在每个时间间隙中考虑相同的调度标准（如松弛性、相对截止日期），RECCE利用深度强化学习应用不同的标准在每个时隙中转发数据包，结果表明RECCE效果显著。1.2基于多智能体的强化学习算法多智能体强化学习主要是让每一个智能体做自己的决策，一般执行三种任务，完全合作任务（订单派送一般被认为是完全合作任务）、完全对抗任务和混合任务。每个智能体会根据相应值网络学习出一个价值，再通过特定网络将价值组合得到联合动作-状态的总奖励值。Rashid 等9提出的QMIX网络将联合作用值估计为每个智能体值的复杂非线性组合，这些值只以局部观察为条件，在结构上强制每个智能体的联合动作值是单调的，这使非策略学习中的联合动作值更
