基于多机器人竞争行为的分布式k-WTA算法.pdf
《基于多机器人竞争行为的分布式k-WTA算法.pdf》由会员分享,可在线阅读,更多相关《基于多机器人竞争行为的分布式k-WTA算法.pdf(9页珍藏版)》请在咨信网上搜索。
1、浙江科技学院学报,第 卷第期,年月J o u r n a l o fZ h e j i a n gU n i v e r s i t yo fS c i e n c ea n dT e c h n o l o g yV o l N o ,F e b d o i:/j i s s n 收稿日期:基金项目:浙江省自然科学基金项目(L Z Y E )通信作者:孔颖(),女,浙江省杭州人,教授,博士,主要从事神经网络与机械臂轨迹规划研究.E m a i l:k o n g y i n g c o m.基于多机器人竞争行为的分布式k WT A算法周俊文,孔颖,P e r s e v e a r a n
2、c eM a r e c h a(浙江科技大学 信息与电子工程学院,杭州 )摘要:【目的】为解决通信受限的智能体网络中的任务分配问题,提出了一种基于二次规划的通用分布式k WT A(k w i n n e r s t a k e a l l,k 赢者通吃)算法,本算法不需要中心命令来识别k个赢家.【方法】首先,结合高通一致性滤波器在现有集中式模型的基础上构造出一种新的分布式k WT A模型;然后,利用拉塞尔不变性原理(L a s a l l e s i n v a r i a n c ep r i n c i p l e)计算出本模型在不变集上等价于现有集中式模型,在理论上证明了其全局渐进收敛
3、到k WTA问题的解;最后进行仿真试验以验证其有效性.【结果】本模型具有全局渐进收敛和智能等优势.此外,通过静态输入和动态输入的两个数值算例验证了本模型在分布式网络中搜索赢家的有效性.【结论】本研究提出的k WT A模型能有效地解决通信受限的智能体网络中的竞争问题,可以为多机器人分布式任务分配工程应用提供参考.关键词:k赢者通吃;竞争方式;最优化;收敛;多智能体系统中图分类号:T P 文献标志码:A文章编号:()O nd i s t r i b u t e dk WT Aa l g o r i t h mf o r c o m p e t i t i v eb e h a v i o r so
4、 fm u l t i r o b o t sZ HOUJ u n w e n,KONGY i n g,P e r s e v e a r a n c eM a r e c h a(S c h o o l o f I n f o r m a t i o na n dE l e c t r o n i cE n g i n e e r i n g,Z h e j i a n gU n i v e r s i t yo fS c i e n c ea n dT e c h n o l o g y,H a n g z h o u ,Z h e j i a n g,C h i n a)A b s t
5、r a c t:O b j e c t i v eT os o l v e t h ep r o b l e mo f t a s ka l l o c a t i o n i nt h ea g e n tn e t w o r kw i t h l i m i t e dc o mm u n i c a t i o n,ag e n e r a ld i s t r i b u t e dk w i n n e r s t a k e a l l(k WT A)a l g o r i t h m w a sp r o p o s e do nt h eb a s i so fq u a d
6、 r a t i cp r o g r a mm i n g,f o rw h i c hn oc e n t e r c o mm a n dw a sn e e d e dt o i d e n t i f yt h ekw i n n e r s M e t h o dF i r s t,an e w d i s t r i b u t e dk WT A m o d e lw a sc o n s t r u c t e d b a s e do nt h ee x i s t i n gc e n t r a l i z e d m o d e lb y c o m b i n i
7、n g t h e h i g h p a s sc o n s i s t e n c yf i l t e r;s e c o n d,u s i n gL a s a l l e s i n v a r i a n c ep r i n c i p l e,i tw a sc a l c u l a t e dt h a tt h em o d e lw a se q u i v a l e n tt ot h ee x i s t i n gc e n t r a l i z e dm o d e l i nt h e i n v a r i a n t s e t,a n dt h
8、eg l o b a l a s y m p t o t i cc o n v e r g e n c e t ot h es o l u t i o no fk WT Ap r o b l e mw a sp r o v e dt h e o r e t i c a l l y;f i n a l l y,s i m u l a t i o ne x p e r i m e n t sw e r ec a r r i e do u t t ov e r i f y i t s e f f e c t i v e n e s s R e s u l tT h em o d e l h a s
9、t h e a d v a n t a g e so f g l o b a l a s y m p t o t i c c o n v e r g e n c ea n di n t e l l i g e n c e I na d d i t i o n,t w o n u m e r i c a le x a m p l e so fs t a t i ci n p u ta n d d y n a m i ci n p u td e m o n s t r a t et h ee f f e c t i v e n e s so ft h e m o d e li ns e a r c
10、 h i n g w i n n e r si n d i s t r i b u t e d n e t w o r k s C o n c l u s i o nT h ek WT A m o d e lp r o p o s e di nt h i ss t u d yc a ne f f e c t i v e l ys o l v et h ec o m p e t i t i o np r o b l e mi nt h ea g e n tn e t w o r kw i t hl i m i t e dc o mm u n i c a t i o n,w h i c hc a
11、np r o v i d ear e f e r e n c ef o re n g i n e e r i n ga p p l i c a t i o no fd i s t r i b u t e dt a s ka l l o c a t i o nf o rm u l t i r o b o t s K e y w o r d s:k w i n n e r t a k e a l l;c o m p e t i t i v em a n n e r;o p t i m i z a t i o n;c o n v e r g e n c e;m u l t i a g e n t s
12、 y s t e mk WT A(k w i n n e r s t a k e a l l,k赢者通吃)网络是一种能从一组输入数据中选择前k个最大值的竞争型神经网络.赢者通吃(w i n n e r t a k e a l l,WT A)网络作为k WT A网络的一种特例,在图像分类、模式识别、神经网络电路等领域得到了广泛的应用.在智能计算领域中,这类从输入数据中取最大值的操作是极其重要的.因此,国内外研究者对k WT A网络开展了一系列研究,如M a j a n i等首次提出并研究了WT A网络的泛化形式k WT A网络,保证了模型的局部稳定性.C a l v e r t等提出了模拟浩斯菲
13、尔德神经网络,并通过完整的数学分析证明了它可以有效地识别实数列表中的前k个最大分量.为了优化模型结构,L i u等首次将k WT A问题转换为一个等价的二次规划问题.进而动态神经网络、对偶神经网络、投影神经网络等陆续被开发应用,同时在引入激活函数、收敛速度 等方面进行了改进.这些模型在处理常数输入的k WT A运算时能实现有限时间收敛,但在处理时变输入信息时存在滞后误差,需通过设置足够大的参数来改善.P e n g等 设计了具有非硬限制激活函数的k WT A神经网络,极大地简化了模型结构,降低了计算成本.Q i等 设计并研究了利用饱和允许激活函数执行k WT A操作的k WT A神经网络,该网
14、络具有较强的扰动鲁棒性.L i u等 设计并分析了具有较高精度和较强鲁棒性的k WT A网络,并给出了多机器人系统中执行跟踪任务的应用,验证了该网络的有效性.近年来,机器人技术在工程领域得到了迅速的发展,受到了广泛的关注,并取得了丰硕的成果.单个机器人虽然在很多方面满足了一些行业的需求,但在一些复杂或大规模作业中经济效益不高.针对这一不足,出现了多机器人系统,其明显的优点是能够通过机器人的协同,高效、灵活地完成任务.现有的多机器人系统大多采用集中式控制方法,依赖一个控制中心,除了存在潜在的不稳定因素外,还存在计算量大、通信负荷高的问题.与集中式方法相比,分布式方法只需要邻居对邻居的通信,大幅减
15、轻了整体通信负荷,即使某些机器人失效,分布式方法仍能正常工作.到目前为止,对k WT A的研究大多使用集中式控制方法,即没有加入任何拓扑约束,不能被直接用于具有任意拓扑结构的多智能体网络.L i等 首次考虑了多智能体网络的拓扑结构,提出了一种分布式WT A模型来解决网络中的动态竞争问题.J i n等 研究了基于k WT A的多机器人分布式竞争协同,并采用了低通一致性滤波器来估计k WT A模型中的动态项,使得单个机器人能够仅依靠其邻居信息计算出对整个系统输出信息的均值估计.这些成果指出了研究分布式k WT A网络的必要性,为后续基于k WT A思路的广泛应用奠定了基础.但据现有文献,关于分布式
16、k WT A模型的研究还很少.针对分布式k WT A问题,本研究首先提出了一种使用高通一致性滤波器的分布式k WT A模型.然后利用拉塞尔不变性原理(L a s a l l e s i n v a r i a n c ep r i n c i p l e)计算出本模型有一个不变集,在不变集中本模型退化为现有的具有全局渐进收敛性的集中式k WT A模型,证明了本模型全局渐进收敛于k WT A问题的解.最后通过两个算例,验证了所提出的分布式k WT A模型的性能.k WT A问题 集中式k WT A模型一般而言,k WT A问题可以被表述为下列函数:ri(xi),xix中的前k个最大元素;,xix
17、中的前k个最大元素.()第期周俊文,等:基于多机器人竞争行为的分布式k WT A算法式()中:xRRs为输入向量;rRRs为输出向量;s为输入量和输出量的元素数.当ri时,第i个元素成为赢 家;否 则,第i个 元 素 就 成 了 输 家.上 面 的k WT A问 题 也 可 以 表 示 为 如 下 的 二 次 规 划问题:m i nrRRssirisixiris t sirik.()式()中:为设计参数;ri,i,s;k为设定的赢家数量.当xkxk时,上述二次规划问题的解完全等价于式()中描述的k WT A问题,其中xk表示x中的第k个最大元素.为解决上述二次规划问题,一种单状态变量k WT
18、A网络模型被定义为(sirik);rigi(xi).()式()中:为辅助变量;为设计参数;gi()为激活函数g()的第i个元素,其可被描述为gi(xi),xi;,xi;xi,xi.在式()中可以发现,无论问题规模大小,模型只有一个状态变量.由于总是需要输入向量x中所有元素的信息,所以k WT A模型式()是集中式的.上述属性也出现在许多模型中,如简化对偶神经网络模型 ,改进对偶神经网络模型 ,具有阶跃激活函数的k WT A网络模型 和单神经元的递归神经网络模型 .在下一章提出的分布式模型将基于k WT A模型式(),因为它是现有模型中最简单的.分布式k WT A问题受限通信拓扑可被定义为一个具
19、有s个智能体的无向连接网络G(W,E,A),其中W表示点集,E表示边集,A表示邻接矩阵.设N(i)表示第i个智能体的邻居集,那么第i个智能体只能与邻居集N(i)中的对象交换信息.在这种情况下,k WT A问题变成了如何借助智能体与邻居的竞争来在所有智能体中找到k个赢家.本研究的目的是寻找一种能够在受限通信条件下解决k WT A问题的分布式模型.分布式k WT A模型 模型描述在式()中,求和项siri需要所有的智能体信息,是一个集中项.Z h a n g等 利用高通滤波器,将代数连通性估计模型中的集中求和项用局部信息计算出的估计值代替,得到相应的分布式模型.类似地,在式()的基础上,增加辅助状
20、态向量p和q,利用高通一致性滤波器将求和项siri用估计值代替.结合受限网络的定义,构建如下分布式k WT A模型:pi(qirijN(i)ai j(pipj)ks);qi(jN(i)ai j(qiqj)jN(i)ai j(rirj);rigi(pixi).()浙江科技学院学报第 卷式()中:、均为大于零的设计参数,其中xkxk;ai j为邻接矩阵A中第i行第j列的元素.结合所有智能体的控制输入,分布式k WT A模型式()可以写成如下形式:p(qrpk es);q L(qr);rg(px).()式()中:e为一个s维向量,所有元素都是;L为通信图G的拉普拉斯矩阵,满足 m i n(L),m
21、i n(L)为L的第二个最小特征值.理论分析定理假设q(),通信受限情况下的分布式k WT A模型式()的输出值全局渐进收敛于k WT A问题式()的解.证明:定义函数h(p)h(p),h(p),hs(ps)T,其元素hi(pi)定义如下:hi(pi)gi(pi)pi,pi或pi;,pi;,pi或pi.定义如下辅助变量:d i a g(h(p)g(p)p;qre eTrs;eTrsks;L p.由式()我们可以得到:p e .()根据式()和式(),的导数如下:eTrs s(hT(p)h(p)hT(p).()式()中:为范数.同时得到的导数如下:L(pre eTrse eTs)(Ie eTs)
22、d i a g(h(p)p.()式()中:I为一个s维单位矩阵.对于一个无向连通图,拉普拉斯矩阵满足L eeTL.利用拉普拉斯矩阵的性质,我们可以得到:L(Ie eTs)d i a g(h(p)p;eTeT(qre eTrs)eTq;eTq eTL(qr).()所以假设q(),我们可得eT.根据以上性质,eT可以做出如下变化:eT(Le eT)C.()式()中:CLe eT;m i n(L)/s;矩阵C满足m i n(C)m i n(L),其中m i n()表示最小的特征值.因此,式()可以进一步写成:C(Ie eTs)d i a g(h(p)p.()定义一个如下的李雅普诺夫函数:VVs VV
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 机器人 竞争 行为 分布式 WTA 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。