·116· 智能系统学报 第3卷 机器人，不带有对将来分配的规划.而TE是有更多 2.2市场机制方法 可用的信息，如要分配的所有任务的集合或如何获 它是一种基于协商主义的任务分配方法，多机 得任务的模型等 器人系统在某种协议基础上通过机器人之间的相互 基于以上3点将MRTA问题分为8类：1)ST- 协商、谈判来完成任务分配.这种方法适合于在任务 SR-IA;2)ST-SR-TE;3)ST-MR-IA;4)ST-MR-TE; 和机器人状态可知的中小规模异构机器人中进行分 5)MT-SR-IA;6)MT-SR-TE;7)MT-MR-IA; 布式问题的协作求解，能够实现全局最优任务分配， 8)MT-MR-TE.其中ST-SR-IA是最简单的一种情 缺点是机器人必须通过显式的通信有意图的协作」 况，可看作是OAP的实例，也是目前研究最多的一 资源消耗较多，一旦通讯中断性能将明显下降].其 类MRTA问题.通常将任务看作是不可分割的原 典型代表是R.Smith提出的合同网).合同网模型 子单元，忽略任务的内部结构，即给定一组任务T、(CNP)由多个可以互相传递信息的结点组成，基本 一组机器人R和每个机器人执行任务的代价函数 思想是按照市场中的招标投标中标机制来完成 cr,找到一个任务分配方案使全局代价函数值最 各结点间的协商过程 小 传统合同网模型存在许多缺点，而且对于什么 然而，只有少数MRTA问题采用纯粹的ST 时候发布任务，如何评价“标的”值从而得到全局最 SRIA一次性分配结构，大多数都采用它的2个变 优解哪些已分配的任务应该再进行拍卖来保持解 形结构：迭代分配(iterated assignment)和在线分配 的质量，什么时候进行再分配和由谁决定再分配，这 (online assignment).在迭代分配结构下每次迭代 些任务分配中不可避免的问题CNP并未解决 中所有任务是同时分配的，其典型代表有ALLF 近年来各种基于合同网的改进方法被广泛应用 ANCE BLE和M+等.而在线分配是串行分配任 到多机器人任务分配中，目前研究最多的是拍卖算 务的，典型的代表有MURDOCH、First-price auc- 法.拍卖算法因其具有可扩展性而特别适合于分布 tions和Dynamic Role Assignment等 式机器人领域，而且理论上能够保证得到任务的最 优分配.但通讯开销大，多次循环方可收敛到平衡 2 任务分配方法 早期的拍卖算法是集中式的，系统中由一个集中的 目前，多机器人任务分配方法主要有基于行为 管理者进行任务拍卖和任务分配，如Caloud等设计 的分配方法、市场机制方法、群体智能方法、基于线 的GOPHER11.目前多采用分布式拍卖算法，系统 性规划的方法、基于情感招募的方法、基于空闲链的 中每个机器人作为自利的agent参与虚拟市场，通 方法等 过拍卖和投标任务进行任务分配.基于拍卖的任务 2.1基于行为的分配方法 分配问题一般分为3步山 基于行为的任务分配算法一般分为3步： 1)每个机器人根据自身执行指定任务的适合度 1)找到一个具有最大效用的机器人任务对 对任务进行投标； (i,) 2)拍卖机制决定将任务分配给哪个机器人： 2)将任务j分配给机器人i,并不再考虑它们： 3)投标获胜的机器人控制器通过执行一个或多 3)回到第1)步 个动作来完成任务 其典型代表有ALL IANCES]和Broadcast of 2.2.1单物品拍卖 Local Eligibility(BLE)II这2种方法都是通过行为 所谓单物品拍卖算法就是对于一个目标点，向 抑制来实现任务分配的，每个机器人对每个任务有 所有的机器人进行拍卖，参与拍卖的机器人根据它 一定的期望度，并且在行为层直接抑制其他机器人 目前所在的位置和目标点之间的距离出价，距离最 的活动.在2005年Parker又提出一个基于行为的 短的机器人将获得任务，并开始执行，其他机器人继 任务分配机制ASyMTRe!),将环境和感知信息映 续参加剩下目标点的拍卖.如First-price auc- 射到行为模式获得所需的信息流，自动地在机器人 tions ,Dynamic role assignment GAO Ping 间重构各种模式间的连接，综合得到完成任务的行 an4等 为 2.2.2组合拍卖 该方法的特点是实时性、容错性和鲁棒性好，但 Behauh提出了组合拍卖的方法s1,采用一个 只能求得局部最优解 简单的例子证明单物品竞拍有得不到全局最优路径 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net机器人 ,不带有对将来分配的规划. 而 TE 是有更多 可用的信息 ,如要分配的所有任务的集合或如何获 得任务的模型等. 基于以上 3 点将 MRTA 问题分为 8 类 :1) ST2 SR2IA ;2) ST2SR2TE ;3) ST2MR2IA ;4) ST2MR2TE ; 5 ) M T2SR2IA ; 6 ) M T2SR2TE ; 7 ) M T2MR2IA ; 8) M T2MR2TE. 其中 ST2SR2IA 是最简单的一种情 况 ,可看作是 OAP 的实例 ,也是目前研究最多的一 类 MRTA 问题. 通常将任务看作是不可分割的原 子单元 ,忽略任务的内部结构 ,即给定一组任务 T、 一组机器人 R 和每个机器人执行任务的代价函数 cr ,找到一个任务分配方案使全局代价函数值最 小[3 ] . 然而 ,只有少数 MRTA 问题采用纯粹的 ST2 SR2IA 一次性分配结构 ,大多数都采用它的 2 个变 形结构 :迭代分配(iterated assignment) 和在线分配 (online assignment) . 在迭代分配结构下每次迭代 中所有任务是同时分配的 ,其典型代表有 ALL I2 ANCE、BL E 和 M + 等. 而在线分配是串行分配任 务的 ,典型的代表有 MURDOCH 、First2price auc2 tions 和 Dynamic Role Assignment 等. 2 任务分配方法 目前 ,多机器人任务分配方法主要有基于行为 的分配方法、市场机制方法、群体智能方法、基于线 性规划的方法、基于情感招募的方法、基于空闲链的 方法等. 2. 1 基于行为的分配方法 基于行为的任务分配算法一般分为 3 步[4 ] : 1) 找到一个具有最大效用的机器人 ———任务对 (i , j) ; 2) 将任务 j 分配给机器人 i ,并不再考虑它们 ; 3) 回到第 1) 步. 其典型代表有 ALL IANCE [5 ] 和 Broadcast of Local Eligibility (BL E) [6 ]这 2 种方法都是通过行为 抑制来实现任务分配的 ,每个机器人对每个任务有 一定的期望度 ,并且在行为层直接抑制其他机器人 的活动. 在 2005 年 Parker 又提出一个基于行为的 任务分配机制 ASyM TRe [7 ] ,将环境和感知信息映 射到行为模式获得所需的信息流 ,自动地在机器人 间重构各种模式间的连接 ,综合得到完成任务的行 为. 该方法的特点是实时性、容错性和鲁棒性好 ,但 只能求得局部最优解. 2. 2 市场机制方法 它是一种基于协商主义的任务分配方法 ,多机 器人系统在某种协议基础上通过机器人之间的相互 协商、谈判来完成任务分配. 这种方法适合于在任务 和机器人状态可知的中小规模异构机器人中进行分 布式问题的协作求解 ,能够实现全局最优任务分配 , 缺点是机器人必须通过显式的通信有意图的协作 , 资源消耗较多 ,一旦通讯中断性能将明显下降[8 ] . 其 典型代表是 R. Smit h 提出的合同网[9 ] . 合同网模型 (CN P) 由多个可以互相传递信息的结点组成 ,基本 思想是按照市场中的招标 —投标 —中标机制来完成 各结点间的协商过程. 传统合同网模型存在许多缺点 ,而且对于什么 时候发布任务 ,如何评价“标的”值从而得到全局最 优解 ,哪些已分配的任务应该再进行拍卖来保持解 的质量 ,什么时候进行再分配和由谁决定再分配 ,这 些任务分配中不可避免的问题 CN P 并未解决. 近年来各种基于合同网的改进方法被广泛应用 到多机器人任务分配中 ,目前研究最多的是拍卖算 法. 拍卖算法因其具有可扩展性而特别适合于分布 式机器人领域 ,而且理论上能够保证得到任务的最 优分配. 但通讯开销大 ,多次循环方可收敛到平衡. 早期的拍卖算法是集中式的 ,系统中由一个集中的 管理者进行任务拍卖和任务分配 ,如 Caloud 等设计 的 GOPHER [10 ] . 目前多采用分布式拍卖算法 ,系统 中每个机器人作为自利的 agent 参与虚拟市场 ,通 过拍卖和投标任务进行任务分配. 基于拍卖的任务 分配问题一般分为 3 步[11 ] : 1) 每个机器人根据自身执行指定任务的适合度 对任务进行投标 ; 2) 拍卖机制决定将任务分配给哪个机器人 ; 3) 投标获胜的机器人控制器通过执行一个或多 个动作来完成任务. 2. 2. 1 单物品拍卖 所谓单物品拍卖算法就是对于一个目标点 ,向 所有的机器人进行拍卖 ,参与拍卖的机器人根据它 目前所在的位置和目标点之间的距离出价 ,距离最 短的机器人将获得任务 ,并开始执行 ,其他机器人继 续参 加 剩 下 目 标 点 的 拍 卖. 如 First2price auc2 tions [ 12 ] ,Dynamic role assignment [13 ]和 GAO Ping2 an [14 ]等. 2. 2. 2 组合拍卖 Behauh 提出了组合拍卖的方法[15 ] ,采用一个 简单的例子证明单物品竞拍有得不到全局最优路径 ·116 · 智 能 系 统 学 报 第 3 卷