多机器人系统的任务分配技术

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/11/7,#,多机器人系统的任务分配技术,Task Allocation of Multi-robot System,许守培,13721131,论文结构,一、多机器人系统的概述（引言）,二、多机器人系统任务分配问题的概述（包括分类）,三、多机器人系统任务分配方法,四、多机器人任务分配在机器人足球赛中的应用现状,五、关于多机器人系统任务分配的发展与建议,总结,一、多机器人系统的概述,1.,多机器人系统简介,多机器人系统是指多个机器人组成的系统。面对复杂的环境与任务，与单机器人相比，多机器人系统具有许多优越性：完成任务效率高、完成任务复杂程度高、信息传递速度快、定位信息准确、系统鲁棒性好以及优化解决问题方案。,2.,多机器人系统的结构,1.,从控制角度和信息交互方式上看，多机器人组织结构可分为集中式、分布式和混合式三,种。,.,集中式,集中式控制结构通常由,主机器人和子机器人构成，,如图,1,所示,。,.,分布式,分布式没有主控单元，系统中机器人个体间地位平等，自主选择行为以完成给定任务，这种结构整体分散、局部集中。图,2,所示。,图,1,图,2,.,混合式,混合方式是将集中与分布控制,相结合的控制方式它在一定程度上,结合集中式结构与分散式结构的优,点，可克服分布式结构中个体高度,自治所造成的性能低下和集中式结,构缺乏控制灵活性等问题。具有很好的鲁棒性和适应性，,图,3,2,.,多机器人系统领域的主要研究内容及亟待解决的问题,1,.,任务分配、动作选择、协调及控制结构；,2,.,物体运输、操作及构建；,3,.,通信及感知；,4,.,运动协调；,5,.,学习；,6,.,可重构及可建模机器人；,7,.,协作定位及地图构建。,二、多机器人系统任务分配问题的概述,早期研究集中于对多机器人系统基础能力要求，即能够顺利的完成任务,;,现今研究重心为提高多机器人系统性能，即在保证完成任务的基础上，增强机器人之间的合作，提高系统工作效率。,多机器人任务分配,MRTA,(Multi-Robot task allocation),是多机器人系统应用的基础，能够充分体现系统决策层组织形式与运行机制。一方面，任务分配的好坏直接影响整个系统的探测效率，并且直接关系到系统中各个机器人能否最发挥其自身能力；另一方面，通过机器人之间的协调与协作共同完成复杂任务已经成为众多研究者关注的问题。,按照观察角度选取的不同，多机器人的任务分配可以分成很多类别。,1.,多机器人任务分配的分类,通讯方式,显式通信,隐式通信,任务的动态性,静态任务分配,动态任务分配,任务完成复杂度,简单任务分配,复杂任务分配,机器人功能结构,同构系统任务分配,异构系统任务分配,合作的动机,涌现式任务分配：如自然中蚂蚁、蜜蜂,意图合作式任务分配,2.,多机器人系统中的两种任务和两种机器人,任务：,机器人,多机器人任务,(MRT),多机器人任务,(SRT),单任务机器人,(STR),多任务机器人,(MTR),多机器人,任,任务分配,问,问题是指,各,各机器人,分,分布式,地,地自主执,行,行任务,由于任务,类,类型不同,各机器人,的,的能力不,同,同,当发 现,新,新 的任,务,务时,各机器人,能,能够通过,根,根据当前,态,态势快速,、,、合理地,实,实现任务,的,的动态分,配,配。,3.,任务分配,问,问题的形,式,式化描述,多机器人,系,系统任务,分,分配的目,标,标：,（,1,）效能最,大,大。将,任,任务分配,给,给多机器,人,人系统内,的,的各个机,器,器人，既,满,满足,，,，并,保,保证每个,任,任务只分,配,配给一个,机,机器人，,即,即,，,，,则,则,。,。,如果待分,配,配的任务,数,数量超过,多,多机器人,协,协作能够,执,执行的最,大,大任务数,量,量，则按,照,照能使多,机,机器人协,作,作完成任,务,务后整体,的,的效能,最,最,大,大的原则,对,对任务进,行,行选择，,以,以提高系,统,统的整体,效,效能。,（,2,）使系统,的,的整体执,行,行能力提,高,高，使任,务,务尽可能,均,均匀地分,布,布在各个,机,机器人上,，,，各机器,人,人的任务,负,负载趋于,平,平衡。设,机,机器人,Ri,的任务负,载,载为,，,，系统内,机,机器人的,平,平均任务,负,负载为,则,则,要,要保证,最,最,小,小、其中,，,，任务负,载,载,为,为,Ri,当前的任,务,务数量与,其,其能够执,行,行的任务,数,数量的比,值,值。,2.4,多机器人,任,任务分配,的,的性能指,标,标,1.,鲁棒性,2.,快速性,3.,最优性,4.,学习能力,三、多机,器,器人系统,任,任务分配,方,方法,多机器人,任,任务分配,问,问题,MRTA(Multi-RobotTask Allocation),是多机器,人,人系统研,究,究的一个,基,基础问题,体现了系,统,统高层组,织,织形式与,运,运行机制,是多机器,人,人系统实,现,现目标的,基,基础。随,着,着系统中,机,机器人数,目,目和任务,难,难度的增,加,加,任务分配,问,问题就显,得,得越来越,重,重要。,1.,基于市场机,制,制的任务分,配,配,市场法定义,为,为：,多机器人系,统,统采用全分,布,布式方法，,只,只有目标信,息,息由机器人,共,共享，而机,器,器人间的协,作,作通过投标,来,来体现。机,器,器人根据本,地,地地图计算,得,得到目标点,的,的花费，并,将,将其作为投,标,标价格。,1.1,单任务拍卖,单个任务分,配,配时每次只,能,能对单个任,务,务进行投标,重复对每个,任,任务进行拍,卖,卖,直到所有任,务,务分配完。,该,该方法不保,证,证求得最优,解,解,但其计算量,和,和通信量比,组,组合任务分,配,配小,实现也比较,简,简单,目前应用比,较,较多。,研究表明寻,找,找单任务最,优,优分配为,NP,难题,并提出,PRIMALLOCATION,算法,该算法与传,统,统的单任务,拍,拍卖算法类,似,似,但机器人以,它,它已拥有的,目,目标与当前,投,投标任务之,间,间的最小距,离,离为投标价,格,格。,1.2,组合拍卖,当任务之间,存,存在协同关,系,系时,单任务拍卖,可,可能导致极,不,不理想的分,配,配方案,组合任务拍,卖,卖通过允许,投,投标人对任,务,务组合进行,投,投标,试图改进单,任,任务拍卖,每个机器人,权,权衡接受任,意,意多个任务,子,子集的价格,这有利于找,到,到最优分配,方,方案。,1.3.,合同网任务,分,分配方法,合同网是一,种,种面向谈判,的,的任务分配,和,和协作机制,，,，通过模仿,经,经济行为中,“,“招标,-,投标,-,中标”机制,实,实现任务的,委,委派和迁移,，,，现已广泛,应,应用到编队,协,协同作战、,卫,卫星和多,UCAV,等领域。,基于合同网,的,的多机器人,系,系统任务分,配,配过程的协,商,商算法如下,：,：,Step1,：招标。当,某,某个机器人,发,发现新的任,务,务时，作为,招,招标者，向,其,其他机器人,宣,宣布任务。,Step2,：投标。收,到,到拍卖信息,后,后，机器人,根,根据自己当,前,前的能力和,状,状态计算买,入,入任务后自,身,身效能并决,定,定是否发出,买,买卖合同标,书,书。,Step3,：通知中标,和,和落标。当,收,收到标书后,，,，机器人对,标,标书进行处,理,理，谁投价,高,高，就将任,务,务转交给谁,执,执行。,Step4,：,Ri,收到中标信,息,息后，任务,集,集被更新为,，,，并,执,执行任务。,2.,基于群体智,能,能的任务分,配,配,基于群体智,能,能的方法是,受,受到社会性,昆,昆虫行为的,启,启发,通过对社会,性,性昆虫觅食,任,任务等的模,拟,拟产生的任,务,务分配方法,。,。由于群体,中,中相互合作,的,的个体是分,布,布的,不会由于某,一,一个或者某,几,几个个体的,故,故障而影响,整,整个问题的,求,求解,而且个体之,间,间通过非直,接,接通信进行,合,合作,使系统具有,更,更好的可扩,充,充性。因此,群,群体智能方,法,法非常适合,于,于分布式多,机,机器人系统,而且也有越,来,来越多的研,究,究者将群体,智,智能方法应,用,用到多机器,人,人任务分配,中,中。,主要方法包,括,括阈值法和蚁,群,群方法，系统具有,鲁,鲁棒性实时,性,性及高效性,，,，适用于分,布,布式,MRTA;,在,MRTA,的研究中，,群,群体智能方,法,法是解决,MRTA,的主要发展,方,方向。,2.1,阈值法,基于阈值的,任,任务分配是,一,一种用涌现,式,式任务分配,该方法中每,个,个机器人对,每,每个任务都,有,有一个阈值,用激素反映,任,任务的紧迫,性,性和重要性,机器人不断,感,感知任务发,出,出的激素。,当,当感知的激,素,素值超过对,应,应的阈值,机器人执行,该,该任务,而当感知的,激,激素值降低,到,到低于阈值,时,时,(,如任务完成,),机器人停止,执,执行。,基于行为的,多,多机器人分,布,布式合作结,构,构,ALLICANCE,以及具有相,应,应参数学习,能,能力的系统,L-ALLIANCE,采用基于阈,值,值的任务分,配,配,定义了两个,动,动机模型,:,焦躁和默许,用这两个动,机,机作为开关,激,激活模型选,择,择相应的行,为,为进行任务,的,的动态分配,。,。,A.Gage,提出一种依,据,据情绪的雇,佣,佣方法来解,决,决多机器人,的,的任务分配,问,问题,每个机器人,都,都有一定的,情,情绪值,用来表征其,对,对任务的热,情,情程度。,2.2,蚁群算法,通过研究发,现,现，单个蚂,蚁,蚁在觅食的,过,过程中会分,泌,泌一种启发,性,性的信息素,（,（,Pheromone,）来和其他,蚂,蚂蚁传递信,息,息。蚂蚁通,过,过不同路径,上,上的信息素,浓,浓度来选择,路,路径，浓度,越,越大的路径,被,被选择的几,率,率也就越大,。,。由于信息,素,素会随着时,间,间的推移而,挥,挥发，因而,较,较短的路径,上,上信息素浓,度,度较大，使,得,得这种路径,更,更具有吸引,力,力，从而吸,引,引更多的蚂,蚁,蚁选择该路,径,径，而使这,又,又得该路径,上,上信息素的,浓,浓度更大。,蚁,蚁群的这种,行,行为形成了,一,一种正反馈,机,机制，使得,最,最优的觅食,路,路径被越来,越,越多的蚂蚁,选,选择。,基于行为的,任,任务分配,3.,其他任务分,配,配方法,基于情感情,感,感招募方法,的,的任务分配,LynneE.Parker.ALLIANCE:AnArchitecture for Fault Tolerant Multirobot Cooperation,FangTangand LynneE.Parker.Distributed Multi-RobotCoalitionsthrough ASyMTRe-D,GAGEA,MURP HYR,VAIAVANISKP,etal.Affectivetaskallocationfordistributed multi-robot teams,四、多机器,人,人任务分配,技,技术在足球,机,机器人中的,应,应用,在机器人足,球,球中,任务分配问,题,题实际上就,是,是角色分配,问,问题,:,不同的研究,机,机构采用不,同,同的角色分,配,配策略来解,决,决这个问题,。,。,足球比赛中,往,往往需要根,据,据需要设置,多,多个不同的,角,角色,然后对每个,角,角色安排相,应,应的任务，,通,通过这种方,法,法将复杂问,题,题进行分割,简,简化。大多,数,数机器人足,球,球球队也采,用,用这种思想,来,来进行协调,。,。,五、关于多,机,机器人系统,任,任务分配的,发,发展和建议,任务分解,异构机器人,增强对环境,的,的适应性,通信效率,效用函数的,最,最