第2期 张嵛，等：多机器人任务分配的研究与进展 ·117· 的缺陷，而组合拍卖的方法相比单物品拍卖更容易 也有越来越多的研究者将群体智能方法应用到多机 产生全局较优解.在组合拍卖算法中，机器人不仅可 器人任务分配中，特别是在动态环境下进行任务分 以对一个目标进行投标，还可以将多个目标看作一 配的情况.比较典型的方法有阈值法和蚁群算法 个标来竞标这种方法不仅能够提高拍卖的效率，而 2.3.1阈值法 且还能降低竞标机器人的风险.典型代表是Trad- 阈值法2)的基本思想是通过感知任务的激励 erbots 或需求调节机器人的选择和此任务的反应阈值.其 2.2.3单层拍卖 中每个任务j都有一个激励值5，当机器人i感知 在单层拍卖中，任务被建模成原子单元，不考虑 到任务j的s,超过它的反应阈值0，时，开始执行该 任务的结构性和复杂性.单层拍卖分为3类：1)目标 任务.当y低于，时，机器人停止执行任务 层拍卖(Goal point-level allocation):2)区域层拍卖2.3.2蚁群算法 (Area-level allocation);3)任务层拍卖(Missiom 根据昆虫学家的观察，蚂蚁通过在走过的路径 level allocation).现存的MRTA算法多为单层拍卖 上释放一种信息素来影响其他蚂蚁的运动，当信息 机制，如First-price auctions!2 Dynamic Role As- 素越强，吸引其他蚂蚁走这一路径的概率就越大，从 signment)、Traderbots!6、M+系统)、MUR- 而增加该路径的信息素浓度，这样就会有更多的蚂 DOCHI8I和DEMiR-CFI等 蚁走这条路径.丁滢颖等设计了一种基于蚁群算法 2.2.4任务树拍卖 的多机器人协作任务分配策略]，成功地解决了多 Zot和Stentz提出一种基于任务树拍卖的分 机器人系统在未知环境工作时自主协作规问题 配方法)，打破了以往的“单层”任务拍卖模式.由于 Dandan Zhang等将阈值法和蚁群算法相结合 任务树具有结构性，因此能够表示复杂的任务.参与 提出一种基于群体智能方法的自适应任务分配策 拍卖的机器人可对树中不同层的节点进行拍卖.这 略2】，通过高层简单的自增强学习模型，对不同类 种方法的优点在于将任务分解和规划有效地融入分 型的任务产生稳定、灵活的劳动分工.底层通过应用 配过程中 蚁群算法使机器人协作完成同种类型的任务 2.2.5逆转拍卖 2.4 基于线性规划的方法 现存的拍卖算法都是机器人投标任务，所谓逆 Gerky和Mataric将MRTA问题看作是0l型 转拍卖是任务发起拍卖并投标机器人具有的服务： 整数线性规划问题241 引入服务智能体(service Agents)和任务智能体2 找到斤个非负整数4，最大化 个软件智能体辅助完成拍卖过程，Lovekesh和Julie 提出的RACHNA2o就是一种基于逆转拍卖的联盟 王，2，U4 满足 形成系统！ 2.3群体智能方法 =1,1≤j≤n 近几年来，一些研究者受到社会性昆虫行为的 启发，通过对社会性昆虫的模拟产生了一系列对于 =1.1≤1≤n 传统问题的新的解决方法，即群智能算法.群体智能 它是针对单机器人单任务(single-robot tasks 指的是“无智能的主体通过合作表现出智能行为的 and single-task robots)而言，即一个机器人只能完 特性” 成一个任务，而一个任务只需一个机器人完成，这是 群体智能在没有集中控制并且不提供全局模型 MRTA中最简单的情况.它不能处理一个任务需要 的前提下，为寻找复杂的分布式问题的解决方案提 多个机器人协作完成的情况(multi-ro bot tasks).早 供了基础.由于群体中相互合作的个体是分布的，没 期解决线性规划问题的方法主要是单纯型法和匈牙 有中心的控制与数据，这样系统更具有鲁棒性，不会 利法，这2种方法本质上都是矩阵的运算，当系统中 由于某一个或者某几个个体的故障而影响整个问题 机器人和任务数增多时，运算量呈指数级增长.一些 的求解，而且个体之间通过非直接通信(stimergy) 基于混合整数线性规划的MRTA方法2s2)虽然能 进行合作，所以当系统中个体增加时系统通信开销 够成功找到最优解，但是通常需要收集所有机器人 增加得十分小，使系统具有更好的可扩充性.因此群 和任务的信息，并通过一个集中管理者来处理这些 体智能方法非常适合于分布式多机器人系统，而且 信息，因此扩展性差效率也低.为了提高系统的可扩 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net的缺陷 ,而组合拍卖的方法相比单物品拍卖更容易 产生全局较优解. 在组合拍卖算法中 ,机器人不仅可 以对一个目标进行投标 ,还可以将多个目标看作一 个标来竞标. 这种方法不仅能够提高拍卖的效率 ,而 且还能降低竞标机器人的风险. 典型代表是 Trad2 erbots [ 16 ] . 2. 2. 3 单层拍卖 在单层拍卖中 ,任务被建模成原子单元 ,不考虑 任务的结构性和复杂性. 单层拍卖分为 3 类 :1) 目标 层拍卖( Goal point2level allocation) ;2) 区域层拍卖 (Area2level allocation) ; 3) 任务层拍卖 ( Mission2 level allocation) . 现存的 MRTA 算法多为单层拍卖 机制 ,如 First2price auctions [12 ] 、Dynamic Role As2 signment [ 13 ] 、Traderbots [16 ] 、M + 系 统[17 ] 、MU R2 DOCH [ 18 ]和 DEMiR2CF [19 ]等. 2. 2. 4 任务树拍卖 Zlot 和 Stentz 提出一种基于任务树拍卖的分 配方法[3 ] ,打破了以往的“单层”任务拍卖模式. 由于 任务树具有结构性 ,因此能够表示复杂的任务. 参与 拍卖的机器人可对树中不同层的节点进行拍卖. 这 种方法的优点在于将任务分解和规划有效地融入分 配过程中. 2. 2. 5 逆转拍卖 现存的拍卖算法都是机器人投标任务 ,所谓逆 转拍卖是任务发起拍卖并投标机器人具有的服务. 引入服务智能体 (service Agents) 和任务智能体 2 个软件智能体辅助完成拍卖过程. Lovekesh 和 J ulie 提出的 RACHNA [20 ]就是一种基于逆转拍卖的联盟 形成系统. 2. 3 群体智能方法 近几年来 ,一些研究者受到社会性昆虫行为的 启发 ,通过对社会性昆虫的模拟产生了一系列对于 传统问题的新的解决方法 ,即群智能算法. 群体智能 指的是“无智能的主体通过合作表现出智能行为的 特性”. 群体智能在没有集中控制并且不提供全局模型 的前提下 ,为寻找复杂的分布式问题的解决方案提 供了基础. 由于群体中相互合作的个体是分布的 ,没 有中心的控制与数据 ,这样系统更具有鲁棒性 ,不会 由于某一个或者某几个个体的故障而影响整个问题 的求解 ,而且个体之间通过非直接通信 (stimergy) 进行合作 ,所以当系统中个体增加时系统通信开销 增加得十分小 ,使系统具有更好的可扩充性. 因此群 体智能方法非常适合于分布式多机器人系统 ,而且 也有越来越多的研究者将群体智能方法应用到多机 器人任务分配中 ,特别是在动态环境下进行任务分 配的情况. 比较典型的方法有阈值法和蚁群算法. 2. 3. 1 阈值法 阈值法[21 ]的基本思想是通过感知任务的激励 或需求调节机器人的选择和此任务的反应阈值. 其 中每个任务 j 都有一个激励值 sj ,当机器人 i 感知 到任务 j 的 sj 超过它的反应阈值θij 时 ,开始执行该 任务. 当 sj 低于θij时 ,机器人停止执行任务. 2. 3. 2 蚁群算法 根据昆虫学家的观察 ,蚂蚁通过在走过的路径 上释放一种信息素来影响其他蚂蚁的运动 ,当信息 素越强 ,吸引其他蚂蚁走这一路径的概率就越大 ,从 而增加该路径的信息素浓度 ,这样就会有更多的蚂 蚁走这条路径. 丁滢颖等设计了一种基于蚁群算法 的多机器人协作任务分配策略[22 ] ,成功地解决了多 机器人系统在未知环境工作时自主协作规划问题. Dandan Zhang 等将阈值法和蚁群算法相结合 提出一种基于群体智能方法的自适应任务分配策 略[23 ] ,通过高层简单的自增强学习模型 ,对不同类 型的任务产生稳定、灵活的劳动分工. 底层通过应用 蚁群算法使机器人协作完成同种类型的任务. 2. 4 基于线性规划的方法 Gerky 和 Mataric 将 MRTA 问题看作是 021 型 整数线性规划问题[ 24 ] : 找到 n 2 个非负整数αij ,最大化 ∑ n i =1 ∑ n j = 1 αij Uijωj , 满足 ∑ n i = 1 αij = 1 ,1 ≤j ≤n , ∑ n j =1 αij = 1 ,1 ≤i ≤n. 它是针对单机器人单任务 (single2robot tasks and single2task robots) 而言 ,即一个机器人只能完 成一个任务 ,而一个任务只需一个机器人完成 ,这是 MRTA 中最简单的情况. 它不能处理一个任务需要 多个机器人协作完成的情况(multi2robot tasks) . 早 期解决线性规划问题的方法主要是单纯型法和匈牙 利法 ,这 2 种方法本质上都是矩阵的运算 ,当系统中 机器人和任务数增多时 ,运算量呈指数级增长. 一些 基于混合整数线性规划的 MRTA 方法[25228 ] 虽然能 够成功找到最优解 ,但是通常需要收集所有机器人 和任务的信息 ,并通过一个集中管理者来处理这些 信息 ,因此扩展性差效率也低. 为了提高系统的可扩 第 2 期 张 嵛 ,等 :多机器人任务分配的研究与进展 ·117 ·