基于多种群协同进化的多逃逸者围捕任务分配.pdf
《基于多种群协同进化的多逃逸者围捕任务分配.pdf》由会员分享,可在线阅读,更多相关《基于多种群协同进化的多逃逸者围捕任务分配.pdf(8页珍藏版)》请在咨信网上搜索。
1、收稿日期:2023-02-23摇 摇 摇 摇 摇 摇 修回日期:2023-06-27基金项目:安徽省重点研究与开发计划(202004d07020011,202104d07020001);中央高校基本科研业务费专项资金项目(PA2020GDKC0015,PA2021GDSK0073,PA2021GDSK0074)作者简介:高子璇(1998-),女,硕士研究生,研究方向为多智能体协作、多机器人系统等;通信作者:张国富(1979-),男,教授,研究方向为多智能体系统、联盟博弈、演化计算等。基于多种群协同进化的多逃逸者围捕任务分配高子璇1,张国富1,2,3,4,苏兆品1,2,3,4,李摇 磊1(1.合
2、肥工业大学 计算机与信息学院,安徽 合肥 230601;2.大数据知识工程教育部重点实验室(合肥工业大学),安徽 合肥 230601;3.智能互联系统安徽省实验室(合肥工业大学),安徽 合肥 230009;4.工业安全应急技术安徽省重点实验室(合肥工业大学),安徽 合肥 230601)摘摇 要:群机器人逃逸围捕一直是人工智能和机器人领域的研究热点之一。在面向多逃逸者时,如何为每个逃逸者高效地分配合适的机器人以完成协同围捕是一个难点问题。已有研究大都采用距离优先分配的策略,为每个逃逸者选择离它最近的一组机器人进行围捕,在逃逸者数量较多的情况下,难以实现围捕任务的均衡分配,降低了系统围捕的效率。为
3、此,提出了一种基于多种群协同进化的多逃逸者围捕任务分配算法。首先,构建了一种全方向的群机器人逃逸围捕任务分配数学模型;然后,基于遗传算法和多种群协同进化提出了一种多逃逸者围捕任务分配算法,设计了相应的编码方式、交叉和变异策略;最后,在开发的群机器人逃逸围捕仿真平台上测试了算法的有效性。对比实验结果表明,所提算法在完成围捕任务所耗费的步数上最多降低了 20%,围捕效率最大提高了 25%。关键词:群机器人逃逸围捕;多逃逸者任务分配;遗传算法;多种群协同进化;静态障碍物避障中图分类号:TP18摇 摇 摇 摇 摇 摇 摇 文献标识码:A摇 摇 摇 摇 摇 摇 文章编号:1673-629X(2023)1
4、2-0185-08doi:10.3969/j.issn.1673-629X.2023.12.026Task Allocation of Multi-escapee Roundup Based on Multi-populationCoevolutionGAO Zi-xuan1,ZHANG Guo-fu1,2,3,4,SU Zhao-pin1,2,3,4,LI Lei1(1.School of Computer Science and Information Engineering,Hefei University of Technology,Hefei 230601,China;2.Key L
5、aboratory of Knowledge Engineering with Big Data(Hefei University of Technology),Ministry of Education,Hefei 230601,China;3.Intelligent Interconnected Systems Laboratory of Anhui Province(Hefei University of Technology),Hefei 230009,China;4.Anhui Province Key Laboratory of Industry Safety and Emerge
6、ncy Technology(Hefei University of Technology),Hefei 230601,China)Abstract:Swarm robot escape roundup has been one of the research hotspots in the field of artificial intelligence and robotics.Whenfacing multiple escapees,it is a difficult problem to efficiently assign the appropriate robots to each
7、 escapee to complete collaborativeroundup.Most of the researches have adopted the distance-first allocation strategy to select the nearest group of robots for each escapee,which makes it difficult to achieve a balanced distribution of the fencing task when the number of escapee is large and reduces
8、theefficiency of system fencing.To this end,a multi-escapee roundup task allocation algorithm based on the co-evolution of multipleswarms is proposed.Firstly,an all-directional swarm robot escape roundup task assignment mathematical model is constructed,and thena multi-escapee roundup task assignmen
9、t algorithm is proposed based on genetic algorithm and multiple swarm co-evolution,and the cor鄄responding coding methods,crossover and variation strategies are designed.Finally,the effectiveness of the proposed algorithm is testedon the developed swarm robot escape roundup simulation platform.Compar
10、ative experimental results show that the proposed algorithmreduces the number of steps consumed in completing the roundup task by up to 20%and improves the roundup efficiency by up to 25%.第 33 卷摇 第 12 期2023 年 12 月摇 摇 摇 摇 摇 摇 摇 摇 摇 摇计 算 机 技 术 与 发 展COMPUTER TECHNOLOGY AND DEVELOPMENT摇 摇 摇 摇 摇 摇 摇 摇 摇
11、摇Vol.33摇 No.12Dec.摇 2023Key words:swarm robot escape roundup;multi-escapee task allocation;genetic algorithm;multi-population coevolution;staticobstacle avoidance0摇 引摇 言随着机器人在军事、工业领域中的应用,机器人追逃问题1-2已成为人工智能和机器人领域中的研究热点之一,其研究类型主要分为对单逃逸者的追逃问题和对多逃逸者的追逃问题。自 Isaacs3为两个参与者制定追逃策略以来,对单追捕-单逃逸者之间的博弈进行了详细的研究。单追捕
12、-单逃逸者的情况是一个零和博弈,可以用著名的贝尔曼方程4的扩展来解决。Jia 等5提出用连续时间马尔可夫决策过程(CTMDP)来解决一个追击者和一个逃逸者的追逃问题中的不确定性。Pan 等6提出了一种基于区域的中继追击方案,在追捕的过程中可以更换主动追击者,来使追击时间缩短。Kokolakis 等7提出了一种基于关键强化学习(RL)的算法用于在线学习,并在有限时间内学习追击策略,从而实现对逃逸者的有限时间捕获。在多追捕-单逃逸者的追逃问题中,Lin 等8研究了一类线性二次多追捕-单逃逸者微分对策,逃逸者实施传统的反馈纳什策略,而追捕者基于最佳可实现性能指标的新概念实施纳什策略。Kumkov 等
13、9为对象组的冲突互动制定了特殊的公式和方法来解决对象太多时相位向量的维数很高时带来的困难。近年来,现代交互多智能体系统推动了对多追捕-多逃逸者追逃问题的研究,该研究涉及到围捕任务的分配,主要解决如何分配若干个机器人进行协同围捕逃逸者的问题。围捕机器人在障碍物环境下的实时移动大多采用人工势场法10等来确定。在多追捕-多逃逸者的追逃问题的研究中,Stipanovic 等11通过将水平集函数定义为玩家的目标来确定确保捕获或规避的条件,提供了一种在具有多个参与者的追逃游戏中设计保证捕获或保证规避策略的方法。胡俊和朱庆保12为围捕任务的分配设计了一种“协商分配法冶,李瑞珍13沿用了“协商分配法冶并应用于
14、全方位的围捕系统中,但并没有在逃逸机器人数量较多的情境下进行更深入的实验与研究。徐望宝等14-15提出了一种基于人工力矩的自组织围捕方法,并设计了一种围捕机器人吸引点基于局部信息的确定与调整方法;文献16提出了一种链阵方法,计算复杂度高,围捕团队数目可以不相同并且可以随时加入或退出,在围捕者改变围捕目标后,围捕效率不够理想。高晓阳17提出了一种分配原则,使围捕机器人依次选择离自己最近的围捕点,丧失了对所有机器人一视同仁的公平性。张红强等18提出了一种基于围捕者面对多目标中心方向 180 度范围内的两最近邻进行任务分配的分配方法,减少运动距离和能量消耗。Lopez 等19设计了一种规则,围捕者先
15、选择距离自己最近的围捕点,如果两个围捕者有相同的最接近的逃逸者,将距离最短的围捕者的目标更改为其第二个最近的逃逸者,可以解决任务分配冲突的问题。陈铭治和朱大奇20将每个围捕者到逃逸者的预估时间编为矩阵,根据围捕一个逃逸者所需围捕者的数目计算该逃逸者被围捕所需的最短总时间,围捕者优先围捕具有最小预估时间的逃逸者。需要指出的是,上述已有研究大都采用距离优先分配的策略,在逃逸者数量较多的情况下,难以实现围捕任务的均衡分配,降低了系统围捕的效率。为此,该文在总结和分析前人工作的基础上,构建了一种全方向的群机器人逃逸围捕任务分配数学模型,然后基于遗传算法和多种群协同进化提出了一种多逃逸者围捕任务分配算法
16、,设计了相应的编码方式、交叉和变异策略。最后,在开发的群机器人逃逸围捕仿真平台上测试了算法的有效性。1摇 问题描述群机器人多逃逸者围捕问题设定在二维受限环境,有 m 个围捕机器人,用 Q=q1,q2,qm 表示;有n 个逃逸机器人,用 P=p1,p2,pn 表示。对每个逃逸机器人 pi(i=1,2,n),存在一个以逃逸者当前位置为中心,感知距离 r 为半径建立的安全域,如图 1所示。在安全域边界上设定 e 个均匀分布的围捕点,每个围捕点由一个围捕机器人完成,当该逃逸机器人周围的所有围捕点均被围捕机器人占领时,认为该逃逸机器人被围捕成功,所有逃逸机器人均被围捕成功时,停止追逃行为,判定群机器人围
17、捕系统围捕成功。图 1摇 安全域及 Fk示意图将每一个逃逸机器人看作一个围捕任务,则共有n 个任务,设任务集为 S=S1,S2,Sn,由图 1 可知,每个任务由 e 个围捕者共同完成。则围捕点的集合为 Si1,Si2,Sie,即任务 Si对应围捕点集合681摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 计算机技术与发展摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 第 33 卷Si1,Si2,Sie。假设围捕机器人 qk(k=1,2,m)所对应的围捕点为 Sij(i=1,2,n;j=1,2,e),qk到 Sij的距离Fk如图 1 所
18、示,并表示为公式 1。Fk=(xk-xij)2+(yk-yij)2(1)其中,(xk,yk),(xij,yij)分别为围捕机器人 qk和对应围捕点 Sij在地图中对应的坐标。2摇 基于多种群协同进化的多逃逸者围捕任务分配策略求解该文设计了一种基于多种群协同进化遗传算法来求解群机器人多逃逸者围捕任务的分配问题。为了保持种群的多样性,先初始化生成 D 个不同的编码组合,在每个组合里再将任务集合 S 进行合适的分组,一组代表一个种群,通过多种群协同进化的方式得到最终的分配方案,算法流程如图 2 所示。多种群协同进化遗传算法的过程如下:(1)随机生成 D 个不同的编码组合,在这些组合里,任务集顺序保持
19、一致,围捕者集合的顺序随机生成。(2)将每一个组合中的编码按同样的分组方式对编码进行划分分组,来保持合适的编码长度。(3)分组后的每一组为一个独立的种群,每个种群同时进行各自的初始化和交叉、变异、选择等操作。(4)将每个种群选择的最优解按分组顺序进行组合,得到最终解。(5)每个组合均可得到一个最终解,再选择 D 个组合中的最优解作为文中算法所得到的分配方案。该分配方案的适应度函数值的大小即为本次算法最终得到的目标函数值。1L11LD图 2摇 基于多种群协同进化的任务分配算法流程2.1摇 个体编码在任务数量多的情况下,若不进行分组直接使用遗传算法,则会导致基因位长度过长,产生的效果很差。首先将任
20、务集合 S=S1,S2,Sn 进行分组,假设每一组最多有 w 个任务,则任务组数 L=腋nw骎,任务数量少的情况下不用进行分组,直接将这些任务设为一组,建立一个种群就足够,即可表示为:若任务数目 n w,且不是 w 的整数倍,则 n 对 w 取余,余数自为一组。第 h(h=1,2,L)组的个体编码如图3 所示,每一个编码表示种群中的一个个体。第一行表示任务Sha(a=1,2,w),第二行表示围捕者 qhb(b=1,2,ew)。1hq2hq3hq4hqheq()h ewq.1hShwS图 3摇 第 h 组个体编码示意图Sha(a=1,2,w)为任务集 S 中按顺序排序分配到各组中的任务,qhb(
21、b=1,2,ew)为围捕者集合 Q中随机选取的不重复围捕者。所有组的任务组合起来为一个完整的任务集 S,所有组的围捕者组合起来为781摇 第 12 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 高子璇等:基于多种群协同进化的多逃逸者围捕任务分配一个完整的围捕者集合 Q,如公式 2 所示。胰h=1,2,LSh1,Sh2,Shw=S胰h=1,2,Lqh1,qh2,qhew=Q(2)每一组的任务和围捕者均不会重复,即对 L 组中任意的两组 h1和 h2,都有如下约束条件:坌h1,h2沂1,2,LSh11,Sh12,Sh1w 疑 Sh21,Sh22,Sh2w=堙坌h1,h2沂1,2,Lqh11,qh1
22、2,qh1ew 疑 qh21,qh22,qh2ew=堙(3)L 个种群相互独立,各自进行交叉变异选择的过程,互不干扰。2.2摇 种群初始化为了保持种群个体多样性,首先生成 D 个不同的组合,其中第一行编码为任务集 S 的顺序排列,第二行编码为围捕者集合 Q 的随机乱序排列。将生成的长序列划分为 L 个任务组,一组代表一个种群,每个种群由第二行编码的染色体信息形成 Z 个不同的个体,表示围捕任务的第一行编码初始化后保持不变。2.3摇 适应度函数围捕机器人完成全部围捕任务所耗费的步长往往由距离围捕点最远的围捕机器人所决定,对于群机器人多逃逸者围捕的任务而言,任务分配的目标是使该距离越小越好,因此设
23、定适应度函数 Fit 为该编码个体中 Fk的最大值。Fit=max(Fk),摇 k=1,2,ew(4)适应度函数越小,围捕效果越好,在选择过程中选择适应度函数值更小的个体来进行下一次的交叉和变异。2.4摇 交叉算子如图 4 所示,对每一个种群中所有个体各进行下述操作:相邻两个父代个体两两为一组进行交叉,每个父代个体均选择头部作为交叉点;设定 Cr沂0,1 为交叉概率,c饮rand(0,1),若满足 c 臆 Cr,则在其中的一个父代个体中随机选中一段基因位,然后插入到另一个父代个体的头部,另一个父代个体也选择相同位置的相同长度的基因段进行相同的操作;按照所需的基因位长度 ew 从前到后对重复或多
24、余的基因进行剔除。在文中的编码方式下,每个个体的基因位都是唯一且不可随意缺失的,只可移动位置。仅用普通的交叉算法使两个父代个体相互交换产生新个体,会导致个体中基因位的缺失或重复,因此采用上述交叉模式既可以保证这一编码特性,又可为种群提供不同的基因位置组合。1q6q2q3q7q8q12q14q17q24q4q20q24q4q20q1q14q8q1q14q8q1q6q2q3q7q8q12q14q17q24q4q20q24q4q20q1q6q2q3q7q8q12q14q17q24q4q20q1q14q8q1q6q2q3q7q8q12q14q17q24q4q20q1q14q8q1q2q8q14q17q
- 配套讲稿:
如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。