·118· 智能系统学报 第3卷 展性和效率，Atay和Bayazit提出了一种基于混合 扰；同时大量的计算往往无法满足多移动机器人系 整数线性规划的紧急(emergent)任务分配方法2) 统任务实时性较高的要求.因此，许多研究者提出了 2.5基于情感招募的方法 一些更为有效的方法， 情感(emotion)是自控制(self-regulation)中一 祖丽楠等3川针对系统运行过程中，由于机器人 种有效的机制，己被应用于智能体控制中，但是很少 和任务的相对数量、位置分布关系以及机器人状态 将其应用到机器人群体控制中.情感招募法不需要 发生转换等原因，而出现的任务死锁情况，在上级人 机器人对彼此建模，是一个分布式的分配方法.在机 机交互计算机中设计了一个基于黑板结构的监控机 器人学中应用情感的方式主要有3种：1)使用情感 构，负责监控任务的死锁并进行协调」 建模机器人群体的行为；2)使用情感产生单个机器 柳林等2]给出了任务执行中存在的死锁情况， 人的行为；3)作为人一机器人接口.Aaron Gage等 并通过将任务的偏序关系作为任务分配顺序的方法 提出一种基于情感招募的分配方法0)，主要采用的 有效地避免了死锁的发生.丁滢颖等2针对基于蚁 是前2种方式， 群算法求解任务分配的方法给出了机器人的任务死 2.6基于空闲链的方法 锁定义，针对这种情况在算法中引入衰减因子，有效 现存的多机器人任务分配算法通常不考虑机器 防止了任务死锁的发生 人间相互作用的影响，如干扰(interference)等，而 Dandan ZHANG等221给出了任务死锁发生的条 假设任务是独立的.Dahl将系统中机器人间的相互 件，而且引入等待时间和容忍时间，当等待时间大于 作用考虑在内，提出一种基于空闲链(vacancy 容忍时间时通过降低“感知”信息素避免死锁的产生 chains))的分布式MRTA模型TAVC】,通过在一个 4任务分配算法的比较 组织中创建和填充空位模型化空闲链，该模型能够显 式地处理群动态(group dynamics)的影响，引入任务 4.1 影响算法的因素 处理频率决定哪些机器人可无干扰地同时工作」 对于现存的任务分配方法一般从以下4个方面 进行评价) 3任务死锁与解除 1)计算需求：重要操作重复的次数.对于MR 3.1任务死锁 TA,累加效用值和效用值的比较等都为重要操作. 在多机器人系统中，随着机器人数目的增加，受 2)通讯需求：机器人间通过网络发送消息的总 系统中有限资源的制约，机器人间的冲突呈指数级 数，不考虑消息的大小 增长，严重影响系统的整体性能，甚至发生死锁.目 3)任务分配情况(task consideration) 前多机器人领域中的“任务死锁”并未有统一的定 4)解的质量：采用竞争因子(competitive fac- 义，一般根据具体的任务域和任务分配方法给出不 tor)评价，竞争因子给出了一个算法在最坏情况下 同的定义和解除方法， 的解 3.2死锁的解除 4.2算法比较 若机器人间通过协商来解决任务死锁问题，将 假设有n个机器、m个任务，上述各种方法的性 会产生较大的通信量，增加机器人的通信负载，而且 能比较如表12所示 对机器人硬件要求很高，且容易受到外界环境的干 表1迭代任务分配算法 Ta ble I Iterated task allocation algorithm 名称 计算需求/迭代 通讯需求/迭代 任务分配情况 解的质量 ALL IANCEIS1 O(mn O(m) 同时分配，可重分配 至少2-competitive BLEI6] O(mn) O(mn) 同时分配，可重分配 2-competitive M+ O(m刊 O(mn) 司时分配，不可重分配 2-competitive ASyMTRel7 O(mn) O(mn 同时分配，可重分配 至少2 competitive 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net展性和效率 ,Atay 和 Bayazit 提出了一种基于混合 整数线性规划的紧急(emergent) 任务分配方法[29 ] . 2. 5 基于情感招募的方法 情感(emotion) 是自控制 (self2regulation) 中一 种有效的机制 ,已被应用于智能体控制中 ,但是很少 将其应用到机器人群体控制中. 情感招募法不需要 机器人对彼此建模 ,是一个分布式的分配方法. 在机 器人学中应用情感的方式主要有 3 种 :1) 使用情感 建模机器人群体的行为 ;2) 使用情感产生单个机器 人的行为 ;3) 作为人 —机器人接口. Aaron Gage 等 提出一种基于情感招募的分配方法[ 30 ] ,主要采用的 是前 2 种方式. 2. 6 基于空闲链的方法 现存的多机器人任务分配算法通常不考虑机器 人间相互作用的影响 ,如干扰 (interference) 等 ,而 假设任务是独立的. Dahl 将系统中机器人间的相互 作用 考虑在内 , 提出一 种基于空 闲链 ( vacancy chains) 的分布式 MRTA 模型 TAVC [31 ] ,通过在一个 组织中创建和填充空位模型化空闲链 ,该模型能够显 式地处理群动态(group dynamics) 的影响 ,引入任务 处理频率决定哪些机器人可无干扰地同时工作. 3 任务死锁与解除 3. 1 任务死锁 在多机器人系统中 ,随着机器人数目的增加 ,受 系统中有限资源的制约 ,机器人间的冲突呈指数级 增长 ,严重影响系统的整体性能 ,甚至发生死锁. 目 前多机器人领域中的“任务死锁”并未有统一的定 义 ,一般根据具体的任务域和任务分配方法给出不 同的定义和解除方法. 3. 2 死锁的解除 若机器人间通过协商来解决任务死锁问题 ,将 会产生较大的通信量 ,增加机器人的通信负载 ,而且 对机器人硬件要求很高 ,且容易受到外界环境的干 扰 ;同时大量的计算往往无法满足多移动机器人系 统任务实时性较高的要求. 因此 ,许多研究者提出了 一些更为有效的方法. 祖丽楠等[31 ]针对系统运行过程中 ,由于机器人 和任务的相对数量、位置分布关系以及机器人状态 发生转换等原因 ,而出现的任务死锁情况 ,在上级人 机交互计算机中设计了一个基于黑板结构的监控机 构 ,负责监控任务的死锁并进行协调. 柳林等[32 ]给出了任务执行中存在的死锁情况 , 并通过将任务的偏序关系作为任务分配顺序的方法 有效地避免了死锁的发生. 丁滢颖等[21 ] 针对基于蚁 群算法求解任务分配的方法给出了机器人的任务死 锁定义 ,针对这种情况在算法中引入衰减因子 ,有效 防止了任务死锁的发生. Dandan ZHAN G等[22 ]给出了任务死锁发生的条 件 ,而且引入等待时间和容忍时间 ,当等待时间大于 容忍时间时通过降低“感知”信息素避免死锁的产生. 4 任务分配算法的比较 4. 1 影响算法的因素 对于现存的任务分配方法一般从以下 4 个方面 进行评价[2 ] . 1) 计算需求 :重要操作重复的次数. 对于 MR2 TA ,累加效用值和效用值的比较等都为重要操作. 2) 通讯需求 :机器人间通过网络发送消息的总 数 ,不考虑消息的大小. 3) 任务分配情况(task consideration) . 4) 解的质量 :采用竞争因子 ( competitive fac2 tor) 评价 ,竞争因子给出了一个算法在最坏情况下 的解. 4. 2 算法比较 假设有 n 个机器、m 个任务 ,上述各种方法的性 能比较如表 1、2 所示. 表 1 迭代任务分配算法 Table 1 Iterated task allocation algorithm 名称 计算需求/ 迭代 通讯需求/ 迭代 任务分配情况 解的质量 ALL IANCE [5 ] O( mn) O( m) 同时分配 ,可重分配 至少 22competitive BL E [6 ] O( mn) O( mn) 同时分配 ,可重分配 22competitive M + [17 ] O( mn) O( mn) 同时分配 ,不可重分配 22competitive ASyMTRe [7 ] O( mn) O( mn) 同时分配 ,可重分配 至少 22competitive ·118 · 智 能 系 统 学 报 第 3 卷