第6期 曹鹏飞，等：面向多机器人动态任务分配的事件驱动免疫网络算法 ·953· 都适用于静态或任务信息事先已知的场景中，对 能力值和速度值"，每项清理任务具有能力值 于随着时间动态产生，且事先只能感知任务位 和服务时间要求，监测节点可以实时监测系统中 置，无法具体判断任务量，需要机器人在任务执 动态产生任务的位置，但无法获得任务的具体信 行时自主协作的场景中存在较大的局限。 息，任务是否需要多机器人协作，需要在任务执 生物免疫系统维持着生物系统的动态平衡， 行过程中动态判别，通过多机器人协作完成区域 具有较强的学习性、记忆性和自适应性⑧。受此 内的清理搜集任务，可根据机器人和任务属性定 启发，本文借鉴独特型免疫网络，将多机器人系 义模型。 统和免疫系统进行类比，构建任务分配与协作模 表1机器人系统与生物免疫网络的映射关系 型，并利用事件驱动机制实现了多机器人动态的 Table 1 Mapping relationship between robot system and 任务分配与协作，并引入焦躁模型来解决任务死 biological immune network 锁问题，使多机器人系统能够在动态任务、且任 生物免疫系统 多机器人系统 务量无法事先确定的复杂场景中实现任务自适应 抗原 任务 分配与自主协作，构建一个智能协同的机器人网 抗体 机器人 络。将本文算法应用于需要协作的清理搜集任 B细胞 控制节点 务中，仿真和实验表明本文算法能够有效解决此 类动态任务分配问题。 T细胞 监测节点 免疫网络 机器人通信网络 1 多机器人任务分配与协作的免疫 抗原激励 机器人和任务之间的激励 网络模型 抗体间激励 机器人与机器人之间的激励 1.1生物免疫网络 1)抗体与抗原激励 生物免疫系统维持着整个生物系统的动态平 在初始时刻，机器人间的任务分配，主要是根 衡，非常适合于动态和鲁棒性系统研究，将其应 据任务对机器人的激励进行选择，某个任务对某 用到实际工程，可以增强系统的稳定性。 个机器人的激励较高，则其获得该任务的概率就 1974年Jerne提出的独特型网络假说认为， 较大。设第i个机器人R和第j个任务工之间的 生物系统可以维持本身的均衡，通过细胞间的相 激励为g,将其定义为 互作用，利用浓度最大的抗体消灭抗原。 Aifivi+Apj 在此基础上，Farmer等提出了相应的动态 8i= (3) Aadii 方程，并将免疫系统应用于工程应用。 式中：1、2、3相应部分调整系数，和y,为相应 A(t)=A:(t-1)+ N2(t-1)- 机器人R的能力值和速度大小，d,为机器人R,和 (1) 任务T之间的距离大小，P为任务T的优先等级。 2a-廊- 2)抗体与抗体激励 a:(t-1) 根据独特型免疫网络，抗体之间也存在激 a:(t)=1/(1+exp(0.5-A:(t)) (2) 励。在机器人到达相应任务点后，若机器人R需 式中：A()和a()为分别为t时刻抗体i的激励水 要得到帮助，则其需要激励另外机器人，以使其 平和浓度；a、B为作用系数；k表示抗体的消亡； 尽快得到协作。若机器人R可以单独的执行被 N为抗体数目；m:和m分别表示抗体间的激励 分配的任务，则其将会对其他机器人产生抑制作 和抑制；g,表示抗体和抗原间激励。 用，便不会产生激励作用。设机器人R对机器人 受此启发，为了实现的任务动态环境中的多 R产生的激励为m,将其定义为 机器人任务分配，参照生物免疫网络机理，将免 疫网络与实际的多机器人系统进行类比，映射关 my=Afv,+Asv (4) Asdii 系如表1，提出一种多机器人任务分配与协作模型。 式中：4、5、6为相应部分的调整系数，和y:为 1.2任务分配与协作模型 相应机器人R,的能力值和速度值，d,为两机器人 针对一定区域内的松散型清理搜集任务，需 间的欧氏距离，当等待在某个任务处的机器人对 要通过多个同构或异构机器人独立或协作完成。 空闲机器人激励越大，其前往协作的概率越大。 设环境中存在m个机器人R,(i∈{L,2,…,m)和 3)综合激励 n个任务T(j∈(1,2，…，)，机器人R具有相应的 当机器要再次进行任务选择的时候，其需要都适用于静态或任务信息事先已知的场景中，对 于随着时间动态产生，且事先只能感知任务位 置，无法具体判断任务量，需要机器人在任务执 行时自主协作的场景中存在较大的局限。 生物免疫系统维持着生物系统的动态平衡， 具有较强的学习性、记忆性和自适应性[8-9]。受此 启发，本文借鉴独特型免疫网络，将多机器人系 统和免疫系统进行类比，构建任务分配与协作模 型，并利用事件驱动机制实现了多机器人动态的 任务分配与协作，并引入焦躁模型来解决任务死 锁问题，使多机器人系统能够在动态任务、且任 务量无法事先确定的复杂场景中实现任务自适应 分配与自主协作，构建一个智能协同的机器人网 络 [10]。将本文算法应用于需要协作的清理搜集任 务中，仿真和实验表明本文算法能够有效解决此 类动态任务分配问题。 1 多机器人任务分配与协作的免疫 网络模型 1.1 生物免疫网络 生物免疫系统维持着整个生物系统的动态平 衡，非常适合于动态和鲁棒性系统研究，将其应 用到实际工程，可以增强系统的稳定性。 1974 年 Jerne 提出的独特型网络假说认为， 生物系统可以维持本身的均衡，通过细胞间的相 互作用，利用浓度最大的抗体消灭抗原[11]。 在此基础上，Farmer 等 [12] 提出了相应的动态 方程，并将免疫系统应用于工程应用。 Ai(t) = Ai(t−1)+   α N ∑N j=1 mjiaj(t−1)− α N ∑N k=1 mikak (t−1)+βgi −ki   ai(t−1) (1) ai(t) = 1/ ( 1+exp(0.5− Ai(t))) (2) 式中：Ai (t) 和 ai (t) 为分别为 t 时刻抗体 i 的激励水 平和浓度；α、β 为作用系数；ki 表示抗体的消亡； N 为抗体数目；mji 和 mik 分别表示抗体间的激励 和抑制；gi 表示抗体和抗原间激励。 受此启发，为了实现的任务动态环境中的多 机器人任务分配，参照生物免疫网络机理，将免 疫网络与实际的多机器人系统进行类比，映射关 系如表 1，提出一种多机器人任务分配与协作模型。 1.2 任务分配与协作模型 i ∈ {1,2,··· ,m} j ∈ {1,2,··· ,n} 针对一定区域内的松散型清理搜集任务，需 要通过多个同构或异构机器人独立或协作完成。 设环境中存在 m 个机器人 Ri ( ) 和 n 个任务 Tj ( )，机器人 Ri 具有相应的 能力值 fi 和速度值 vi，每项清理任务具有能力值 和服务时间要求，监测节点可以实时监测系统中 动态产生任务的位置，但无法获得任务的具体信 息，任务是否需要多机器人协作，需要在任务执 行过程中动态判别，通过多机器人协作完成区域 内的清理搜集任务，可根据机器人和任务属性定 义模型[5]。 表 1 机器人系统与生物免疫网络的映射关系 Table 1 Mapping relationship between robot system and biological immune network 生物免疫系统 多机器人系统 抗原 任务 抗体 机器人 B细胞 控制节点 T细胞 监测节点 免疫网络 机器人通信网络 抗原激励 机器人和任务之间的激励 抗体间激励 机器人与机器人之间的激励 1) 抗体与抗原激励 在初始时刻，机器人间的任务分配，主要是根 据任务对机器人的激励进行选择，某个任务对某 个机器人的激励较高，则其获得该任务的概率就 较大。设第 i 个机器人 Ri 和第 j 个任务 Tj 之间的 激励为 gij，将其定义为 gi j = λ1 fivi +λ2 pj λ3di j (3) 式中：λ1、λ2、λ3 相应部分调整系数，fi 和 vi 为相应 机器人 Ri 的能力值和速度大小，dij 为机器人 Ri 和 任务 Tj 之间的距离大小，pj 为任务 Tj 的优先等级。 2) 抗体与抗体激励 根据独特型免疫网络，抗体之间也存在激 励。在机器人到达相应任务点后，若机器人 Ri 需 要得到帮助，则其需要激励另外机器人，以使其 尽快得到协作。若机器人 Ri 可以单独的执行被 分配的任务，则其将会对其他机器人产生抑制作 用，便不会产生激励作用。设机器人 Ri 对机器人 Rj 产生的激励为 mij，将其定义为 mi j = λ4 fivi +λ5vj λ6di j (4) 式中：λ4、λ5、λ6 为相应部分的调整系数，fi 和 vi 为 相应机器人 Ri 的能力值和速度值，dij 为两机器人 间的欧氏距离，当等待在某个任务处的机器人对 空闲机器人激励越大，其前往协作的概率越大。 3) 综合激励 当机器要再次进行任务选择的时候，其需要 第 6 期 曹鹏飞，等：面向多机器人动态任务分配的事件驱动免疫网络算法 ·953·