基于共享注意力的多智能体强化学习订单派送_黄晓辉.pdf
《基于共享注意力的多智能体强化学习订单派送_黄晓辉.pdf》由会员分享,可在线阅读,更多相关《基于共享注意力的多智能体强化学习订单派送_黄晓辉.pdf(5页珍藏版)》请在咨信网上搜索。
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基于多智能体的强化学习算法多智能体强化学习主要是
17、让每一个智能体做自己的决策,一般执行三种任务,完全合作任务(订单派送一般被认为是完全合作任务)、完全对抗任务和混合任务。每个智能体会根据相应值网络学习出一个价值,再通过特定网络将价值组合得到联合动作-状态的总奖励值。Rashid 等9提出的QMIX网络将联合作用值估计为每个智能体值的复杂非线性组合,这些值只以局部观察为条件,在结构上强制每个智能体的联合动作值是单调的,这使非策略学习中的联合动作值更易最大化,并保证了集中式和分散式策略之间的一致性。针对 QMIX 的局限性,Son等16提出了分解变换协作多智能体强化学习(Q-learning to factorize with TRANsform
18、ation for cooperative multi-agent reinforcement learning,QTRAN)。QTRAN 摆脱了结构约束,采用了一种新的方法将原来的联合作用值函数转换为易于分解的联合作用值函数,并且具有相同的最优作用。QTRAN保证了比 QMIX更通用的因子分解,因此比以前的方法覆盖了更广泛的多智能体强化学习任务类别。Cui 等17提出了一种基于协调度的合作多智能体强 化 学 习 方 法(Cooperative Multi-Agent Reinforcement Learning method based on Coordination Degree,CMAR
19、L-CD),并对其在更一般情况下的动态特性进行了分析,结果表明CMARL-CD在不需要估计全局价值函数的情况下实现了智能体之间的协调。每个智能体估计自身行动的协调度,这代表了成为最优行动的潜力。Liu 等18提出了 COPA,一个教练-选手框架,假设教练对环境有全局观,并通过分配个人策略来协调只有部分观点的球员。具体来说,采用教练和球员的注意力机制;提出一个变分目标来规范学习;设计一种自适应的沟通方式,让教练决定何时与选手沟通。Luo等19提出了一种新的基于动作级联的策略优化方法,将电动汽车重新定位的动作分解为两个后续的、有条件依赖的子动作,并使用两个连通网络来求解制定的多智能强化学习任务。Z
20、hou等20提出了一种基于多智能体强化学习的分散执行订单调度方法,以解决大规模订单调度问题。与以前的协作多智能体强化学习算法不同,所有智能体在联合策略评估的指导下独立工作,因为智能体之间不需要通信或显式合作。2 问题及符号定义 本文是一个在线学习问题,首先将问题建模为马尔可夫决策过程G=(N,S,A,R,P,),其中N、S、A、R、P、分别为智能体的数量、状态集、动作空间、奖励函数、转移概率函数、折扣因子。它们的定义如下:智能体数量 N:将每辆空闲车辆视为一个智能体,每个智能体有自己独立的决策,它的目标是将发送订单的乘客送图1深度强化学习流程Fig.1Flow of deep reinforc
21、ement learning1621第 43 卷计算机应用到目的地;智能体之间彼此独立,只负责自己的决策。状态集S:S()s1c,s2c,sic|s1p,s2p,sip,其中sic表示 t 时刻第i辆车的状态信息,sip表示t时刻第i个乘客的状态信息,它们分别包含车辆位置与状态、乘客上车点及目的地坐标。当idle=0时 表 示 车 辆 空 闲,即sic=(cix,ciy,idle),sip=(pix,piy,dix,diy)。动作ait A:ait表示t时刻第i个智能体的动作行为,动作为司机到指定位置接乘客并送达目的地或保持空闲。如a21=5表示在第 1个时间片编号为 2的车辆被指派去完成 5
22、号乘客发出的订单。奖励函数Rt:在同一个时间片的智能体享受共同的奖励函数,为一轮实验总计时长的负数。每个智能体都试图最大化自己的预期回报,本文设置=0.99:E|k=0kRt+k。状态转移概率函数P()st+1|st,at:S A 0,1,它表示当前状态采取联合行动时转移到下一个状态时的概率。在强化学习过程中,需要度量每一个动作以及车辆联合动作的价值:个体价值Qit:Qit(sit,ait)表示在t时刻第i个智能体在状态sit的情况下选择动作ait获得的价值。联合总价值Qtot:表示总体价值,即所有智能体执行动作后产生的共同价值,它的大小表示整体行为的好坏。3 基于共享注意力的多智能体强化学习
23、算法 SARL算法的整体框架主要分为两层:第一层为计算个体价值的智能体网络;第二层为计算联合价值的共享注意力模块。3.1计算Qi的智能体网络SARL的框架如图 2所示:第一层网络采用 DQN估计个体价值,采用 DQN 的优势是可以更准确地估算个体价值。如果乘客或者车辆不在地图上,所有坐标信息都会被设置为0,每位乘客都会与一辆汽车配对,作为整体行动的一部分。网络将为每个乘客匹配车辆并估算个体价值,并输出具有最大个体价值的动作。整体损失函数为:L()=1Bi=1BG(Rt-Qit(s,ait,)(1)其中:B是batch size;Rt是t时刻智能体获得的奖励;Qit是t时刻第i个智能体选择动作a
24、it之后得到的价值。G为Huber损失函数,定义如下:G(x)=|12x2,|x 1|x-12,其他(2)Huber损失函数的优势在于当对动作价值的估计有噪声时,例如出现经验回访池中没有的状态-动作对,它对噪声是鲁棒的,在这种情况下可以防止梯度爆炸。Huber损失结合了平均绝对误差和均方误差的优点,对异常点更加鲁棒。3.2共享注意力模块共享注意力模块是对多头注意力机制的改进,框架如图3所示。Qtot的计算公式如下:Qtot=C(s)+h=1H i=1Ni,h(s)Qi(3)这个框架通过选择性地关注来自其他智能体的信息来学习每个智能体的自我注意力。每对智能体之间的自我注意力不执行,而是使用自我注
25、意力来帮助整个系统在每个智能体上建模每个个体的影响。具体来说,将全局状态的嵌入向量es(st)和合作特征的嵌入向量ei(uit)之间的相似性传递到Softmax中得到多头注意力的头系数i,h,这个过程将进行H次,例如2,2表示第二个智能体的第二阶头系数:i,h exp(eTiWTk,hWq,hes)(4)其中:Wk,h和Wq,h为共享注意力模块的输入,分别为全局状态和共享特征向量;es(st)和ei(uit)可以通过对全局状态和共享特征向量进行一层或两层嵌入变换获得。之后,i,h再与每个智能体个体价值Qi进行点积得到联合价值Qh:Qh=i=1Ni,hQi(5)接下来,对N个智能体的联合价值Qh
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 共享 注意力 智能 强化 学习 订单 派送 黄晓辉
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。