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