第9卷第1期 智能系统学报 Vol.9 No.1 2014年2月 CAAI Transactions on Intelligent Systems Feb.2014 D0:10.3969/j.issn.1673-4785.201303006 网络出版地址:http:/www.cnki.net/kcms/doi/10.3969/j.issn.1673-4785.201303006.html 干扰素调节的多机器人协作搬运免疫网络算法 袁明新,叶兆莉,程帅,申燚 (江苏科技大学机电与汽车工程学院,江苏张家港215600) 摘要:为了进一步发挥多机器人系统在协作搬运过程中的执行效率,提出了一种新的基于干扰素调节的免疫网络 分配算法。将箱子和机器人分别看作抗原和抗体,首先定义了抗原和抗体之间以及抗体和抗体之间的亲和度:然后 根据干扰素作用机制定义了干扰素调节因子:最后借鉴Jee的独特型免疫网络假设,建立了多机器人协作搬运的 新免疫分配模型。多环境测试结果表明:与其他免疫分配算法相比,新算法不仅能显著缩短搬运路径、降低机器人 的能量损耗,还能减少参与协作的机器人数目,提高了系统的执行效率,充分体现了多机器人系统协作中任务分配 的合理性,显示出较强的任务规划能力。 关键词:协作搬运:多机器人系统:免疫网络算法;干扰素;亲和度 中图分类号:TP242文献标志码:A文章编号:1673-4785(2014)01-0076-07 中文引用格式:袁明新,叶兆莉,程帅,等.干扰素调节的多机器人协作搬运免疫网络算法[J].智能系统学报,2014,9(1):76-82. 英文引用格式:YUAN Mingxin,YE Zhaoli,,CHENG Shuai,etal.MIulti-robot cooperative handling based on immune network al- gorithm regulated by interferon[J].CAAI Transactions on Intelligent Systems,2014,9(1):76-82. Multi-robot cooperative handling based on immune network algorithm regulated by interferon YUAN Mingxin,YE Zhaoli,CHENG Shuai,SHEN Yi (School of Mechatronics and Automotive Engineering,Jiangsu University of Science and Technology,Zhangjiagang 215600,China) Abstract:In order to further improve the executing efficiency of multi-robot systems during cooperative handling,a new interferon regulation-based immune network algorithm is put forward.The affinities between the antibody and antigen as well as the antibodies are defined firstly by taking the boxes and robots as the antigen and antibody,re- spectively;secondly,the interferon adjustment factor according to the interferon mechanism is defined;thirdly,the new multi-robot task allocation model is established based on Jerne's idiotypic network hypothesis.Compared with the correlative immune allocation algorithms,the test results from multiple environments indicate that the proposed algorithm not only markedly shortens the handling path and reduces energy loss,but also reduces the amount of ro- bots in cooperation,which shows the rationality of the tasking allocation and the stronger planning ability of the pro- posed allocation model. Keywords:cooperative handling;multi-robot systems;immune network algorithm;interferon;affinity 多机器人系统能克服单机器人在信息获取、处同网法、空闲链法和阈值法等。Dhl等[2]在空闲 理和控制等方面的局限性,提高了任务执行效率和 链的基础上建立了奖赏函数,有效调节了平均奖赏 系统灵活性。任务分配是多机器人协作搬运的首要 值,较好地实现了任务分配,但存在着计算量大、效 解决问题,分配的合理性将直接关系到系统的运行 率低的不足。Bradford等[)重新构建了拍卖的投标 效率。目前多机器人任务分配主要通过基于行为、 矩阵,并将任务分组与协同效应相结合,显现出计算 市场机制和线性规划等方法来设计,典型代表有合 量小、用时少的优点,但系统能耗大、效率低等问题 有待解决。为了进一步提高多机器人系统的协作效 收稿日期:2013-03-03.网络出版日期:2014-02-20 基金项目:国家自然科学基金资助项目(61105071):江苏省高校青蓝 率,近年来群体智能分配方法得到了重视。Eips 工程优秀青年骨千教师资助项目(苏教师[2012]39号): 江苏科技大学人才引进项目(35271004). 等[4]利用粒子群算法解决了机器人运动分配问题, 通信作者:袁明新.E-mail:mxyuan78@gmail.com 但是在解空间中不易搜索到最优粒子。Zhang等)
第 9 卷第 1 期 智 能 系 统 学 报 Vol.9 №.1 2014 年 2 月 CAAI Transactions on Intelligent Systems Feb. 2014 DOI:10.3969 / j.issn.1673⁃4785.201303006 网络出版地址:http: / / www.cnki.net / kcms/ doi / 10.3969 / j.issn.1673⁃4785.201303006.html 干扰素调节的多机器人协作搬运免疫网络算法 袁明新,叶兆莉,程帅,申燚 (江苏科技大学 机电与汽车工程学院,江苏 张家港 215600) 摘 要:为了进一步发挥多机器人系统在协作搬运过程中的执行效率,提出了一种新的基于干扰素调节的免疫网络 分配算法。 将箱子和机器人分别看作抗原和抗体,首先定义了抗原和抗体之间以及抗体和抗体之间的亲和度;然后 根据干扰素作用机制定义了干扰素调节因子;最后借鉴 Jerne 的独特型免疫网络假设,建立了多机器人协作搬运的 新免疫分配模型。 多环境测试结果表明:与其他免疫分配算法相比,新算法不仅能显著缩短搬运路径、降低机器人 的能量损耗,还能减少参与协作的机器人数目,提高了系统的执行效率,充分体现了多机器人系统协作中任务分配 的合理性,显示出较强的任务规划能力。 关键词:协作搬运;多机器人系统;免疫网络算法;干扰素;亲和度 中图分类号: TP242 文献标志码:A 文章编号:1673⁃4785(2014)01⁃0076⁃07 中文引用格式:袁明新,叶兆莉,程帅,等.干扰素调节的多机器人协作搬运免疫网络算法[J]. 智能系统学报, 2014, 9(1): 76⁃82. 英文引用格式:YUAN Mingxin, YE Zhaoli, CHENG Shuai, et al. Multi⁃robot cooperative handling based on immune network al⁃ gorithm regulated by interferon[J]. CAAI Transactions on Intelligent Systems, 2014, 9(1): 76⁃82. Multi⁃robot cooperative handling based on immune network algorithm regulated by interferon YUAN Mingxin, YE Zhaoli, CHENG Shuai, SHEN Yi (School of Mechatronics and Automotive Engineering, Jiangsu University of Science and Technology, Zhangjiagang 215600, China) Abstract:In order to further improve the executing efficiency of multi⁃robot systems during cooperative handling, a new interferon regulation⁃based immune network algorithm is put forward. The affinities between the antibody and antigen as well as the antibodies are defined firstly by taking the boxes and robots as the antigen and antibody, re⁃ spectively; secondly, the interferon adjustment factor according to the interferon mechanism is defined; thirdly, the new multi⁃robot task allocation model is established based on Jernes idiotypic network hypothesis. Compared with the correlative immune allocation algorithms, the test results from multiple environments indicate that the proposed algorithm not only markedly shortens the handling path and reduces energy loss, but also reduces the amount of ro⁃ bots in cooperation, which shows the rationality of the tasking allocation and the stronger planning ability of the pro⁃ posed allocation model. Keywords:cooperative handling; multi⁃robot systems; immune network algorithm; interferon; affinity 收稿日期:2013⁃03⁃03. 网络出版日期:2014⁃02⁃20. 基金项目:国家自然科学基金资助项目(61105071);江苏省高校青蓝 工程优秀青年骨干教师资助项目(苏教师[ 2012] 39 号); 江苏科技大学人才引进项目(35271004). 通信作者:袁明新. E⁃mail:mxyuan78@ gmail.com. 多机器人系统能克服单机器人在信息获取、处 理和控制等方面的局限性,提高了任务执行效率和 系统灵活性。 任务分配是多机器人协作搬运的首要 解决问题,分配的合理性将直接关系到系统的运行 效率。 目前多机器人任务分配主要通过基于行为、 市场机制和线性规划等方法来设计,典型代表有合 同网法、空闲链法和阈值法等[1] 。 Dahl 等[2] 在空闲 链的基础上建立了奖赏函数,有效调节了平均奖赏 值,较好地实现了任务分配,但存在着计算量大、效 率低的不足。 Bradford 等[3] 重新构建了拍卖的投标 矩阵,并将任务分组与协同效应相结合,显现出计算 量小、用时少的优点,但系统能耗大、效率低等问题 有待解决。 为了进一步提高多机器人系统的协作效 率,近年来群体智能分配方法得到了重视。 Ellips 等[4]利用粒子群算法解决了机器人运动分配问题, 但是在解空间中不易搜索到最优粒子。 Zhang 等[5]
第1期 袁明新,等:干扰素调节的多机器人协作搬运免疫网络算法 .77. 提出基于群集智能的自适应任务分配方法,通过自 a:(t)= 强化学习和蚁群算法完成觅食任务合作,但是计算 1+exp(0.5-A:(t)) 量大、效率低。生物免疫的自组织、自适应性为解决 式中:A,(t)为t时刻抗体i的激励水平:N为抗体 工程问题,尤其是机器人系统提供了新思路。基于 数:等号右边括号中第1项为抗体i之间的吸引 Farmer的免疫动力学模型,高云园等[6]实现了箱 力,m:为两者刺激系数;第2项为抗体i、k之间的排 子搬运的任务分配,但执行效率还有待进一步提高。 斥力,m为两者抑制系数;第3项g:为抗原对抗体i 吴皓等[]通过在模型中增加T细胞来控制抗体浓 的激励:第4项k:模拟抗体的自然消亡:α、B分别为 度,解决了未知环境的探测问题,但如何将局部探测 抗体i对其他抗体和抗原的作用系数;a.(t)、a,(t)、 转为全局探测还有待研究。为了解决全局环境中的 a4(t)分别为t时刻抗体ij、k的浓度,采用扁平S形 任务分配,并进一步提高协作搬运效率,文中在 函数来表示,目的是确保各抗体浓度值的稳定。 Jeme独特型免疫网络基础上,通过定义干扰素调节 基于Farmer的免疫动力学模型,Ishiguro提出 因子等,实现分配网络的调节和优化,通过仿真来验 了行为仲裁系统,并在垃圾回收上得到了应用:Me 证分配模型的有效性和优越性。 shref等[]解决了分布式自主机器人系统中的狗羊 放牧问题。两者都较好地体现了人工免疫网络的柔 1多机器人任务分配免疫网络模型 韧性和鲁棒性。为了解决多机器人协作搬运问题, 1.1免疫网络模型 文中以搬箱问题为研究对象,在Jerne的独特型免 生物免疫系统是一种高度进化的自适应信息处 疫网络假设基础上,借鉴Farmer的动力学模型提出 理系统。免疫学说理论之一的Jeme独特型免疫网 了一种新的任务分配模型。在该人工免疫模型中, 络假设认为:抗原入侵会打破系统原先的平衡性,不 将机器人和箱子作为抗体和抗原,机器人搬运箱子 同种类的抗体和淋巴细胞之间通过相互通讯进行相 的过程看作抗体消灭抗原过程,从而实现了多机器 互激励或抑制,从而克服抗原,最终维持系统稳 人的任务分配。 定。图1为独特型免疫网络假设示意图。 1.2免疫分配模型的基本定义 抗原 为了便于描述分配模型中的定义,给出如图2 所示的机器人分配环境,环境中分布着若干机器人 R,(i∈{1,2,…,m})和若干箱子B,(l∈{1,2,…, 3-cell2 }),任务分配的目的是机器人通过合作方式,以最 Id? 大性能和效率将箱子推到目标点G。 B-celll 10 Ab2 B Idl P2 ● B-cell3 8 Abl Id3 R 抗体 6 ,激 Ab3 G P3 一抑制 图1独特型免疫网络 ■ 2 R B。 Fig.1 Idiotypic immune network 根据该免疫网络假设,Farmer等[o1]首次提出 10 x/m 了计算抗体激励水平及浓度的动态方程,其表达式 如下: 图2多机器人任务分配环境 t)=A,(t-1)+(NΣm4(1-1 Fig.2 Task allocation environment of multi-robot 1.2.1抗体与抗原间亲合度 g言ma1-1)+g,-k)a,(-1) 箱子在初始时刻及搬运过程中的机器人分配
提出基于群集智能的自适应任务分配方法,通过自 强化学习和蚁群算法完成觅食任务合作,但是计算 量大、效率低。 生物免疫的自组织、自适应性为解决 工程问题,尤其是机器人系统提供了新思路。 基于 Farmer 的免疫动力学模型,高云园等[6⁃7] 实现了箱 子搬运的任务分配,但执行效率还有待进一步提高。 吴皓等[8]通过在模型中增加 T 细胞来控制抗体浓 度,解决了未知环境的探测问题,但如何将局部探测 转为全局探测还有待研究。 为了解决全局环境中的 任务分配, 并进一步提高协作搬运效率, 文中在 Jerne 独特型免疫网络基础上,通过定义干扰素调节 因子等,实现分配网络的调节和优化,通过仿真来验 证分配模型的有效性和优越性。 1 多机器人任务分配免疫网络模型 1.1 免疫网络模型 生物免疫系统是一种高度进化的自适应信息处 理系统。 免疫学说理论之一的 Jerne 独特型免疫网 络假设认为:抗原入侵会打破系统原先的平衡性,不 同种类的抗体和淋巴细胞之间通过相互通讯进行相 互激励或抑制, 从而克服抗原, 最终维持系统稳 定[9] 。 图 1 为独特型免疫网络假设示意图。 图 1 独特型免疫网络 Fig.1 Idiotypic immune network 根据该免疫网络假设,Farmer 等[10⁃11] 首次提出 了计算抗体激励水平及浓度的动态方程,其表达式 如下: Ai(t) = Ai(t - 1) + ( α N∑ N j = 1 mjiaj(t - 1) - α N∑ N l = 1 milal(t - 1) + βgi - ki)ai(t - 1) ai(t) = 1 1 + exp(0.5 - Ai(t)) 式中:Ai( t) 为 t 时刻抗体 i 的激励水平;N 为抗体 数;等号右边括号中第 1 项为抗体 i、j 之间的吸引 力,mji为两者刺激系数;第 2 项为抗体 i、k 之间的排 斥力,mik为两者抑制系数;第 3 项 gi为抗原对抗体 i 的激励;第 4 项 ki模拟抗体的自然消亡;α、β 分别为 抗体 i 对其他抗体和抗原的作用系数;ai(t)、aj( t)、 ak(t)分别为 t 时刻抗体 i、j、k 的浓度,采用扁平 S 形 函数来表示,目的是确保各抗体浓度值的稳定。 基于 Farmer 的免疫动力学模型,Ishiguro 提出 了行为仲裁系统,并在垃圾回收上得到了应用;Me⁃ shref 等[12]解决了分布式自主机器人系统中的狗羊 放牧问题。 两者都较好地体现了人工免疫网络的柔 韧性和鲁棒性。 为了解决多机器人协作搬运问题, 文中以搬箱问题为研究对象,在 Jerne 的独特型免 疫网络假设基础上,借鉴 Farmer 的动力学模型提出 了一种新的任务分配模型。 在该人工免疫模型中, 将机器人和箱子作为抗体和抗原,机器人搬运箱子 的过程看作抗体消灭抗原过程,从而实现了多机器 人的任务分配。 1.2 免疫分配模型的基本定义 为了便于描述分配模型中的定义,给出如图 2 所示的机器人分配环境,环境中分布着若干机器人 Ri(i∈{1,2,…,m}) 和若干箱子 Bl( l∈{1,2,…, n}),任务分配的目的是机器人通过合作方式,以最 大性能和效率将箱子推到目标点 G。 图 2 多机器人任务分配环境 Fig.2 Task allocation environment of multi⁃robot 1.2.1 抗体与抗原间亲合度 箱子在初始时刻及搬运过程中的机器人分配, 第 1 期 袁明新,等:干扰素调节的多机器人协作搬运免疫网络算法 ·77·
·78. 智能系统学报 第9卷 主要是根据两者之间的亲和度进行。设第i个机器 Jeme的独特型网络模型假设,在Farmer的动力学 人R与第l个箱子B之间激励为g:,则将g:定义为 模型基础上,利用文中所定义的抗体与抗原间亲合 fi×u 度、抗体间亲合度以及干扰素调节因子构建了多机 8:=7 (1) 入,da+入2dg) 器人新任务分配模型: (1+y,机器人与目标点在箱子异侧 A:(t)=A:(t-1)+ (2) (1-y,机器人与目标点在箱子同侧 式中:f为机器人R,的推力,d,是机器人R和箱子B, (只m(:-1)+g:+d-k)a,u-) 之间距离,d是箱子B,和目标点之间距离,入,和入2 (4) 为调整系数,山为激励或抑制因子,r为调整系数。 在多机器人任务分配过程中,若机器人需等待 当机器人位于箱子左边时,f越大,d和d,越小,8: 协作,则式(4)作为寻找协作机器人的依据。 越大。另外,按照实验模型,机器人在箱子左侧时g: 1.4多机器人协作搬运算法 得到正激励,反之为负激励。 考虑到多机器人系统的分布式体系结构和通讯 1.2.2抗体间亲合度 的灵活性要求,文中系统采用了黑板模式的通讯方 根据独特型免疫网络假设,抗体间作用包括刺 式。系统中的每个机器人将其感知到的任务和自身 激和抑制。若机器人R无法独自搬运箱子B,则R 信息写在“黑板”的共享区域内,同时从“黑板”上读 产生抗体刺激其他机器人来协作搬运箱子:若机器 取相关信息。黑板上的共享信息包括机器人信息、 人R可独自搬运箱子B,则R产生的抗体对其他机 已搬运箱子信息和目标点信息。机器人之间通过相 器人起到免疫抑制作用。为体现多机器人搬运中的 互通讯和激励值来完成任务分配和搬运。算法具体 刺激和抑制,定义如下亲合度系数m: 过程描述如下: f后×万×u m = 1)初始化抗原和抗体信息,根据式(1)和(2)计 (入1d+入2d) 算机器人和箱子之间的激励; 式中:ff分别为R和R的推力大小,d,为机器人R 2)根据激励值选择合适的机器人去搬运箱子, 和R之间的距离,d为机器人R,和目标点之间的距 被选择机器人向相应箱子移动; 离,u、入,入,的取值同上。 3)判断该机器人能否推动箱子,若能则转步骤 1.2.3千扰素调节因子 5),同时抑制其他空闲机器人来协作:否则转步骤 干扰素是人和动物细胞受到适宜刺激时产生的 一种微量的且具有高度生物学活性的糖蛋白,由Is 4)去寻找其他协作机器人; sacs等于1957年利用鸡胚绒毛尿囊膜研究流感病 4)根据式(4)计算等待搬运的箱子与空闲机器 毒干扰现象时发现。干扰素对体液免疫、细胞免疫 人的激励值,选择合适的机器人前来协作搬运,并转 均有免疫调节作用,对巨噬细胞和自然杀伤细胞也 步骤3); 有一定的免疫增强作用1]。临床医学表明:干扰素 5)通过机器人或者多机器人协作将箱子搬运 对免疫的调控作用有助于抑制乙肝、丙肝病毒的复 至目标点; 制。为了进一步提高基于免疫网络的任务分配效 6)更新机器人和箱子的坐标等信息,重新计算 果,将其引入并实现了免疫网络分配模型的调节。 未搬运箱子和机器人两两间的激励值,重复步骤 千扰素调节因子d:定义为 2)~5),直至所有箱子被搬运至目标点。 4s5x6 在步骤4)中,当机器人都处于等待状态时,称 N (3) 为“任务死锁”。对此,文中采用Parker提出的“焦 式中:d为机器人R需注射的干扰素剂量,N'为目前 躁模型”[4),即当机器人等待队友协作过久,则选择 待搬运箱子的数目,8=103为调整系数。由式(3) 不再等待,并通过减小其激励值来降低其再次被此 可以看出,当待搬运箱子数目减少时,干扰素注射量 任务选择的概率。 逐步增加,从而能自动调节机体的免疫水平。 为了进一步清晰看出机器人的任务分配过程, 1.3任务分配的抗体选择模型 上述免疫网络分配算法可以用图3所示的流程图来 根据多机器人协作搬运中的任务分配要求及 描述
主要是根据两者之间的亲和度进行。 设第 i 个机器 人 Ri与第 l 个箱子 Bl之间激励为 gi,则将 gi定义为 gi = f i × μ (λ1 dil + λ2 dlg ) (1) μ = 1 + γ, 1 - γ, { 机器人与目标点在箱子异侧 机器人与目标点在箱子同侧 (2) 式中:f i为机器人 Ri的推力,dil是机器人 Ri和箱子 Bl 之间距离,dlg是箱子 Bl和目标点之间距离,λ1和 λ2 为调整系数,u 为激励或抑制因子,r 为调整系数。 当机器人位于箱子左边时,f i越大,dil和 dlg越小,gi 越大。 另外,按照实验模型,机器人在箱子左侧时 gi 得到正激励,反之为负激励。 1.2.2 抗体间亲合度 根据独特型免疫网络假设,抗体间作用包括刺 激和抑制。 若机器人 Ri无法独自搬运箱子 Bl,则 Ri 产生抗体刺激其他机器人来协作搬运箱子;若机器 人 Ri可独自搬运箱子 Bl,则 Ri产生的抗体对其他机 器人起到免疫抑制作用。 为体现多机器人搬运中的 刺激和抑制,定义如下亲合度系数 m: m = f i × f j × μ (λ1 dij + λ2 djg ) 式中:f i、f j分别为 Ri和 Rj的推力大小,dij为机器人 Ri 和 Rj之间的距离,djg为机器人 Rj和目标点之间的距 离,u、λ1 、λ2的取值同上。 1.2.3 干扰素调节因子 干扰素是人和动物细胞受到适宜刺激时产生的 一种微量的且具有高度生物学活性的糖蛋白,由 Is⁃ sacs 等于 1957 年利用鸡胚绒毛尿囊膜研究流感病 毒干扰现象时发现。 干扰素对体液免疫、细胞免疫 均有免疫调节作用,对巨噬细胞和自然杀伤细胞也 有一定的免疫增强作用[13] 。 临床医学表明:干扰素 对免疫的调控作用有助于抑制乙肝、丙肝病毒的复 制。 为了进一步提高基于免疫网络的任务分配效 果,将其引入并实现了免疫网络分配模型的调节。 干扰素调节因子 di定义为 di = f i × δ N′ (3) 式中:di为机器人 Ri需注射的干扰素剂量,N′为目前 待搬运箱子的数目,δ = 10 -3为调整系数。 由式(3) 可以看出,当待搬运箱子数目减少时,干扰素注射量 逐步增加,从而能自动调节机体的免疫水平。 1.3 任务分配的抗体选择模型 根据多机器人协作搬运中的任务分配要求及 Jerne 的独特型网络模型假设,在 Farmer 的动力学 模型基础上,利用文中所定义的抗体与抗原间亲合 度、抗体间亲合度以及干扰素调节因子构建了多机 器人新任务分配模型: Ai(t) = Ai(t - 1) + ( α N∑ N j = 1 maj(t - 1) + βgi + di - ki)ai(t - 1) (4) 在多机器人任务分配过程中,若机器人需等待 协作,则式(4)作为寻找协作机器人的依据。 1.4 多机器人协作搬运算法 考虑到多机器人系统的分布式体系结构和通讯 的灵活性要求,文中系统采用了黑板模式的通讯方 式。 系统中的每个机器人将其感知到的任务和自身 信息写在“黑板”的共享区域内,同时从“黑板”上读 取相关信息。 黑板上的共享信息包括机器人信息、 已搬运箱子信息和目标点信息。 机器人之间通过相 互通讯和激励值来完成任务分配和搬运。 算法具体 过程描述如下: 1)初始化抗原和抗体信息,根据式(1)和(2)计 算机器人和箱子之间的激励; 2)根据激励值选择合适的机器人去搬运箱子, 被选择机器人向相应箱子移动; 3)判断该机器人能否推动箱子,若能则转步骤 5),同时抑制其他空闲机器人来协作;否则转步骤 4)去寻找其他协作机器人; 4)根据式(4)计算等待搬运的箱子与空闲机器 人的激励值,选择合适的机器人前来协作搬运,并转 步骤 3); 5)通过机器人或者多机器人协作将箱子搬运 至目标点; 6)更新机器人和箱子的坐标等信息,重新计算 未搬运箱子和机器人两两间的激励值,重复步骤 2) ~5),直至所有箱子被搬运至目标点。 在步骤 4)中,当机器人都处于等待状态时,称 为“任务死锁”。 对此,文中采用 Parker 提出的“焦 躁模型” [14] ,即当机器人等待队友协作过久,则选择 不再等待,并通过减小其激励值来降低其再次被此 任务选择的概率。 为了进一步清晰看出机器人的任务分配过程, 上述免疫网络分配算法可以用图 3 所示的流程图来 描述。 ·78· 智 能 系 统 学 报 第 9 卷
第1期 袁明新,等:干扰素调节的多机器人协作搬运免疫网络算法 .79. 表中,N为箱子数目,M为箱子重量,N为机器 算法和环境初始化 人数目,F为机器人推力值。文中算法参数为α=0.5, 根据抗原抗体亲和度 B=0.1,k=0.002,4,(0)=a,(0)=0.5,入1=0.8,入2=0.2。 初始分配机器人 2.2分配结果及分析 判断机器人是 根据抗体激励值 表2为3种免疫算法在6种环境中的不同分配 否能推动箱子 刺激其他空闲机 器人前来协作 效果。由表2不难看出,文中算法在6种环境中的 分配是最优的。首先在机器人行驶总步数上,由于 判断是否所有 文中免疫网络加入了干扰素调节因子,使得其规划 箱子完成分配 路径短于其他算法;其次在能量损耗上,新方法通过 Y 降低能力强的机器人重复参与搬运的可能性,减少 结束 了损耗值:最后协作机器人数量也得到了控制。因 图3多机器人任务分配流程 此基于干扰素调节机制的免疫网络模型,不仅能兼 Fig.3 Flow of multi-robot task allocation 顾机器人行驶总路程和机器人推力损耗,还能提高 2 实验结果与分析 多机器人系统的执行效率,实现了分配方案的优化。 2.1实验描述 为了看出基于免疫网络模型的多机器人协作搬 为了验证文中新免疫网络分配模型在多机器人 运情况,以相对较复杂的环境6为例来进行说明,结 协作搬运任务中的有效性,利用MATLAB7.1,在CPU 果如图4所示。图中,“●”、“■”分别表示机器人和 1.20GHz、内存为2GB的计算机上进行了多环境任务 分配测试,并将测试结果与文献[6,8]中免疫算法进 箱子的初始位置:“口”为箱子的搬运轨迹:“”为目 行了比较。环境共6种,参数设置如表1所示。 标点:R1/2表示1号机器人,且推力值为2kg:B1/2 表1多机器人任务分配环境参数设置 表示1号箱子,且重量为2kg:1号箱子左侧的⑥表 Table 1 Setting of environmental parameter for multi-ro- 示1号箱子由6号机器人搬运。由图4可以清晰地 bot task allocation 环境Ng Mg/kg Ng Fx/kg 看出不同算法对应的机器人和箱子的分配情况。以 环境1 3 2、5、7 3 234 图4(c)为例,箱子1和2分别由1号和6号机器人 环境2 3 25、7 4 2、34、5 单独搬完,箱子3由4号和5号机器人协作搬完,箱 环境3 4 2、5、7、8 3 235 环境44 2、5、7、8 2、3、4、5 子4由3号和6号机器人协作搬完,箱子5由2号 环境5 2、5、7、8、9 2、34、5 和5号机器人协作搬完。 环境6 5 2、5、7、89 6 2、3、4、5、6、7 表23种免疫算法在6种环境中的任务分配比较 Table 2 Comparisons of task allocation in six environments among three immune algorithms 机器人行驶的总步数 机器人推力的损耗值kg 参与协作的机器人总数目 环境 文献[6] 文献[8] 文献[6] 文献[8] 文献[6] 文献[8] 文中算法 文中算法 文中算法 算法 算法 算法 算法 算法 算法 环境1 136 132 132 2 2 5 5 5 环境2 162 148 144 5 4 5 5 环境3 235 255 224 6 8 6 > 8 > 环境4 243 233 208 6 6 6 7 7 环境5 298 285 258 6 6 10 9 9 环境6 272 264 234 12 17 9 8
图 3 多机器人任务分配流程 Fig.3 Flow of multi⁃robot task allocation 2 实验结果与分析 2.1 实验描述 为了验证文中新免疫网络分配模型在多机器人 协作搬运任务中的有效性,利用 MATLAB7.1,在 CPU 1.20 GHz、内存为 2GB 的计算机上进行了多环境任务 分配测试,并将测试结果与文献[6,8]中免疫算法进 行了比较。 环境共 6 种,参数设置如表 1 所示。 表 1 多机器人任务分配环境参数设置 Table 1 Setting of environmental parameter for multi⁃ro⁃ bot task allocation 环境 NB MB / kg NR FR / kg 环境 1 3 2、5、7 3 2、3、4 环境 2 3 2、5、7 4 2、3、4、5 环境 3 4 2、5、7、8 3 2、3、5 环境 4 4 2、5、7、8 4 2、3、4、5 环境 5 5 2、5、7、8、9 4 2、3、4、5 环境 6 5 2、5、7、8、9 6 2、3、4、5、6、7 表中,NB为箱子数目,MB为箱子重量,NR为机器 人数目,FR为机器人推力值。 文中算法参数为 α= 0.5, β=0.1,k=0.002,Ai(0)= ai(0)= 0.5,λ1 =0.8,λ2 =0.2。 2.2 分配结果及分析 表 2 为 3 种免疫算法在 6 种环境中的不同分配 效果。 由表 2 不难看出,文中算法在 6 种环境中的 分配是最优的。 首先在机器人行驶总步数上,由于 文中免疫网络加入了干扰素调节因子,使得其规划 路径短于其他算法;其次在能量损耗上,新方法通过 降低能力强的机器人重复参与搬运的可能性,减少 了损耗值;最后协作机器人数量也得到了控制。 因 此基于干扰素调节机制的免疫网络模型,不仅能兼 顾机器人行驶总路程和机器人推力损耗,还能提高 多机器人系统的执行效率,实现了分配方案的优化。 为了看出基于免疫网络模型的多机器人协作搬 运情况,以相对较复杂的环境 6 为例来进行说明,结 果如图 4 所示。 图中,“ ”、“ ”分别表示机器人和 箱子的初始位置;“ ”为箱子的搬运轨迹;“ ”为目 标点;R1 / 2 表示 1 号机器人,且推力值为 2 kg;B1 / 2 表示 1 号箱子,且重量为 2 kg;1 号箱子左侧的⑥表 示 1 号箱子由 6 号机器人搬运。 由图 4 可以清晰地 看出不同算法对应的机器人和箱子的分配情况。 以 图 4(c)为例,箱子 1 和 2 分别由 1 号和 6 号机器人 单独搬完,箱子 3 由 4 号和 5 号机器人协作搬完,箱 子 4 由 3 号和 6 号机器人协作搬完,箱子 5 由 2 号 和 5 号机器人协作搬完。 表 2 3 种免疫算法在 6 种环境中的任务分配比较 Table 2 Comparisons of task allocation in six environments among three immune algorithms 环境 机器人行驶的总步数 机器人推力的损耗值 / kg 参与协作的机器人总数目 文献[6] 算法 文献[8] 算法 文中算法 文献[6] 算法 文献[8] 算法 文中算法 文献[6] 算法 文献[8] 算法 文中算法 环境 1 136 132 132 2 2 2 5 5 5 环境 2 162 148 144 7 5 4 5 5 4 环境 3 235 255 224 6 8 6 7 8 7 环境 4 243 233 208 6 6 6 7 7 7 环境 5 298 285 258 6 6 5 10 10 9 环境 6 272 264 234 12 17 9 9 8 8 第 1 期 袁明新,等:干扰素调节的多机器人协作搬运免疫网络算法 ·79·
·80· 智能系统学报 第9卷 R4/5 11f R4/5 ● B5/9 R5/6 ②■ R4/5 ● B5/9 R5/6 B5/9 9 R2/ 9 R5/6 5■ 9 ②■ ● ● ,器B37R22。 ④■ R23●6 R23●⑤ 7 ④B3/7 7 R3/4 B3/7 ⑤B37 .R12 入 5 ④口go000g口o0gg R3/4 RI2 5 ●B1/2 R3/4B12 0,oo9日 R6/7 3春中(10.5) ●R67 回■口“月 R67 ③B4/8 B2/5 6 B2/5 5 B48 B2/3 6B4/8 1 3 57 9 11 3 579 3 57 9 11 x/m x/m x/m (a)文献6算法 (b)文献8算法 (©)文中算法 图43种算法在环境6中的多机器人协作搬运比较 Fig.4 Comparisons of multi-robot cooperation handling of three algorithms in environment 6 图5给出了文中算法在环境6中的机器人搬运 已经等候在Box5处的Robot2协作将箱子搬运至目 路径,由该路径可以进一步清晰看出机器人的协作 标处:完成任务后,Robot:5又被Box3选择,同时与守 过程。以图5(e)为例,Robot5先被Box5选择,并与 候在此处的Robot-4协作将Box3搬运至目标处。 11 11 11 B5/9 9 9 2 9 B5/9 B5/9 7 R2/3●⑤ 函n 7 B3/7 B37 三5 R12 三5 三5 R3/4 (10,5) (10.5) B12 (10.5) ① ■ 3 B1/2 3 BI2 3 3 B4/8 b25 48 B2/5 1 ⑥B4/8 B2/5 3 57 911 35791川 -11357911 x/m x/m x/m (a)Robotl (b)Robot2 (c)Robot3 11 R4/5 11 11r 9 ■ 9 R5/6 +②B5/9 9 ◆ B5/9 5/9 ④= 7 ⑤B37 ◆ 5B3/7 3/7 (10.5) 三5 (10.5) 三5 三5 (10.5) B1/2 ■ B1/2 3 Bi2 3 R67 45 B25 B48 b25 1 ③ B4/8 6 B2/5 357911 357911 357911 x/m x/m x/m (d)Robot4 (e)Robot5 (Robot6 图5文中算法在环境6中的机器人搬运路径 Fig.5 Robot handling path of proposed algorithm in environment 6 图6给出了文中算法在环境6中的机器人浓度 示,分配系统根据浓度来实现箱子的机器人分配。 选择,1~6号机器人浓度通过不同纹理的柱高来表 对应某个箱子,若某机器人的柱高为0,则表示该机
图 4 3 种算法在环境 6 中的多机器人协作搬运比较 Fig.4 Comparisons of multi⁃robot cooperation handling of three algorithms in environment 6 图 5 给出了文中算法在环境 6 中的机器人搬运 路径,由该路径可以进一步清晰看出机器人的协作 过程。 以图 5(e)为例,Robot5 先被 Box5 选择,并与 已经等候在 Box5 处的 Robot2 协作将箱子搬运至目 标处;完成任务后,Robot5 又被 Box3 选择,同时与守 候在此处的 Robot4 协作将 Box3 搬运至目标处。 图 5 文中算法在环境 6 中的机器人搬运路径 Fig.5 Robot handling path of proposed algorithm in environment 6 图 6 给出了文中算法在环境 6 中的机器人浓度 选择,1~6 号机器人浓度通过不同纹理的柱高来表 示,分配系统根据浓度来实现箱子的机器人分配。 对应某个箱子,若某机器人的柱高为 0,则表示该机 ·80· 智 能 系 统 学 报 第 9 卷
第1期 袁明新,等:干扰素调节的多机器人协作搬运免疫网络算法 ·81- 器人已被选择执行其他任务:若某次选择时,所有机 3 结束语 器人柱高均为0,则表示该箱子已被搬运至目标处, 任务已完成。以图6(c)来说明:对应箱子Box3,系 为了解决多机器人系统协作问题,文中基于 统第1次选择Robota4去搬运,Robot44不能独自搬运 Jeme的独特型免疫网络假设和Farmer的动力学模 Box3,需等待协作;系统第2次选择时,Robot3.、Ro 型,根据干扰素作用机制,设计了一种新的基于干扰 bot4、Robott6号机器人柱高为0,则表示在第1次分 素调节的免疫网络分配模型。6种环境测试结果表 配时它们已经被成功分配任务,从而在空闲的R0- 明,利用干扰素调节可以显著减少机器人搬运路程: botl、Robot.2、Robot.5三者中选择浓度最大的Ro- 通过降低能力强的机器人重复参与次数,可以同时 减少能量损耗和协作等待机器人数目。与已有的2 bot5,于是Robots4和Robots5协作来搬运Box3:第3 种免疫网络分配算法相比,文中算法在多机器人的 次选择时可以看出所有机器人柱高为0,表明搬运 协作效率和完成质量方面都有明显提高,显示出该 Box3的任务已经完成。图6更为清晰地给出了文 算法的有效性。与单机器人相比,多机器人系统的 中算法在进行多机器人任务分配时,免疫系统模型 内在并行性和叠加性,使得其具有更高的任务执行 中的浓度变化情况。浓度的变化体现出抗原抗体之 效率和功能,而文中免疫分配模型将有助于进一步 间的激励和抑制结果,而分配结果表明了文中免疫 发挥多机器人系统的功效,因此该成果具有理论和 网络模型的有效性和优越性。 实用价值。课题下一步将把重点放在如何根据机器 0.5 人和任务信息,进一步提高机器人之间的协作以及 免疫分配模型的实际应用上,在完善免疫网络分配 算法的同时,发挥算法的实际应用价值。 次数 参考文献: (a)Boxl [1]董场斌,蒋静坪,何衍.基于适应度的多机器人任务分配 0.5d 策略[J]浙江大学学报:工学版,2007,41(2):272-277. 赵 DONG Yangbin,JIANG Jingping,HE Yan.Fitness-based task allocation strategy for multi robot system[J].Journal of 次数 Zhejiang University:Engineering Science,2007,41(2): (b)Box2 272-277. 0.5c [2]DAHL T S,MATARIC M,SUKHATME G S.Multi-robot 是 task allocation through vacancy chain scheduling[J].Robot- 0 ics and Autonomous Systems,2009,57(6):674-687. 3 次数 [3]BRADFORD H,MAURICE P.Sequential single-cluster (c)Box3 auctions for robot task allocation[J].Advances in Artificial 0.5 Intelligence,2011,7106:412-421. D [4]ELLIPS M,DAVOUD S.Multi-objective robot motion plan- 田人x翻 ning using a particle swarm optimization model[J].Journal 3 of Zhejiang University:Science,2010,11(8):607-619. 次数 [5]ZHANG D,XIE G,YU J,et al.Adaptive task assignment (d)Box4 for multiple mobile robots via swarm intelligence approach 0.5r [J].Robotics and Autonomous Systems,2007,55(7): 572-588. [6]高云园,韦巍.未知环境中基于免疫网络的多机器人自主 0 田太 1 协作[J]浙江大学学报:工学版,2006,40(5):733-737. ▣Robotl☑Robot2 ☒Robot3 GAO Yunyuan,WEI Wei.Multi-robot self-determination co- 图Robot4目Robot5 ☒Robot6 operation based on immune network in an unknown environ- ment[J].Journal of Zhejiang University Engineering Sci- 图6文中算法在环境6中的机器人浓度选择 ence,2006,40(5):733-737. Fig.6 Concentration selection of proposed algorithm in [7]GAO Yunyuan,WEI Wei.Multi-robot autonomous coopera- environment 6 tion integrated with immune based dynamic task allocation
器人已被选择执行其他任务;若某次选择时,所有机 器人柱高均为 0,则表示该箱子已被搬运至目标处, 任务已完成。 以图 6(c)来说明:对应箱子 Box3,系 统第 1 次选择 Robot4 去搬运,Robot4 不能独自搬运 Box3,需等待协作;系统第 2 次选择时,Robot3、Ro⁃ bot4、Robot6 号机器人柱高为 0,则表示在第 1 次分 配时它们已经被成功分配任务,从而在空闲的 Ro⁃ bot1、Robot2、 Robot5 三者中选择浓度最大的 Ro⁃ bot5,于是 Robot4 和 Robot5 协作来搬运 Box3;第 3 次选择时可以看出所有机器人柱高为 0,表明搬运 Box3 的任务已经完成。 图 6 更为清晰地给出了文 中算法在进行多机器人任务分配时,免疫系统模型 中的浓度变化情况。 浓度的变化体现出抗原抗体之 间的激励和抑制结果,而分配结果表明了文中免疫 网络模型的有效性和优越性。 图 6 文中算法在环境 6 中的机器人浓度选择 Fig.6 Concentration selection of proposed algorithm in environment 6 3 结束语 为了解决多机器人系统协作问题,文中基于 Jerne 的独特型免疫网络假设和 Farmer 的动力学模 型,根据干扰素作用机制,设计了一种新的基于干扰 素调节的免疫网络分配模型。 6 种环境测试结果表 明,利用干扰素调节可以显著减少机器人搬运路程; 通过降低能力强的机器人重复参与次数,可以同时 减少能量损耗和协作等待机器人数目。 与已有的 2 种免疫网络分配算法相比,文中算法在多机器人的 协作效率和完成质量方面都有明显提高,显示出该 算法的有效性。 与单机器人相比,多机器人系统的 内在并行性和叠加性,使得其具有更高的任务执行 效率和功能,而文中免疫分配模型将有助于进一步 发挥多机器人系统的功效,因此该成果具有理论和 实用价值。 课题下一步将把重点放在如何根据机器 人和任务信息,进一步提高机器人之间的协作以及 免疫分配模型的实际应用上,在完善免疫网络分配 算法的同时,发挥算法的实际应用价值。 参考文献: [1]董炀斌,蒋静坪,何衍.基于适应度的多机器人任务分配 策略[J].浙江大学学报:工学版, 2007, 41(2): 272⁃277. DONG Yangbin, JIANG Jingping, HE Yan. Fitness⁃based task allocation strategy for multi robot system[J]. Journal of Zhejiang University: Engineering Science, 2007, 41 ( 2): 272⁃277. [2]DAHL T S, MATARIC M, SUKHATME G S. Multi⁃robot task allocation through vacancy chain scheduling[J]. Robot⁃ ics and Autonomous Systems, 2009, 57(6): 674⁃687. [3 ] BRADFORD H, MAURICE P. Sequential single⁃cluster auctions for robot task allocation[J]. Advances in Artificial Intelligence, 2011, 7106: 412⁃421. [4]ELLIPS M, DAVOUD S. Multi⁃objective robot motion plan⁃ ning using a particle swarm optimization model[ J]. Journal of Zhejiang University: Science, 2010, 11(8): 607⁃619. [5]ZHANG D, XIE G, YU J, et al. Adaptive task assignment for multiple mobile robots via swarm intelligence approach [ J]. Robotics and Autonomous Systems, 2007, 55 ( 7): 572⁃588. [6]高云园,韦巍.未知环境中基于免疫网络的多机器人自主 协作[J].浙江大学学报:工学版, 2006, 40(5): 733⁃737. GAO Yunyuan, WEI Wei. Multi⁃robot self⁃determination co⁃ operation based on immune network in an unknown environ⁃ ment[J]. Journal of Zhejiang University : Engineering Sci⁃ ence, 2006, 40(5): 733⁃737. [7]GAO Yunyuan, WEI Wei. Multi⁃robot autonomous coopera⁃ tion integrated with immune based dynamic task allocation 第 1 期 袁明新,等:干扰素调节的多机器人协作搬运免疫网络算法 ·81·
.82. 智能系统学报 第9卷 [C]//Proceedings of the Sixth International Conference on [14]LI Guanghui,TAMURA Y,ASAMA H.Dynamical task Intelligent Systems Design and Applications.Ji'nan,China, allocation and reallocation based on body expansion behav- 2006:586-591. ior for multi-robot coordination[C]//Proceedings of 2011 [8]吴皓,田国会,黄彬.未知环境探测的多机器人协作策略 研究[J].山东大学学报:工学版,2008,38(4):27-31. Interational Conference on Mechatronics and Automation. WU Hao,TIAN Guohui,HUANG Bin.Research on the col- Beijing,China,2011:537-542. laboration strategy of multi robot for exploring unknown envi- 作者简介: ronment[J].Journal of Shandong University:Engineering 袁明新,男,1978年生,讲师,博土, Science,2008,38(4):27-31. 主要研究方向为仿生智能、机器人视觉导 [9]YUAN Mingxin,WANG Sunan,WU Canyang.Hybrid ant 航控制与多机器人任务分配等。主持及 colony and immune network algorithm based on improved APF for optimal motion planning[J].Robotica,2010,28 参与国家自然科学基金、江苏省自然科学 (6):833-846. 基金等项目多项,发表学术论文10余篇。 [10]FARMER J,PACKARD N,PERELSON A.The immune system,adaptation,and machine learning[J].Physica D, 1986,2(3):187-204. 叶兆莉,女,1987年生,硕士研究 [11]ISHIGURO A,WATANABE Y,KONDO T,et al.A robot 生,主要研究方向为仿生智能、移动机 with a decentralized consensus-making mechanism based on the immune system[C]//Proceedings of the Interna- 器人路径规划等。 tional Symposium on Autonomous Decentralized Systems. Berlin,Germany,1997:231-237. [12]YUAN Mingxin,WANG Sunan,WU Canyang,et al.A novel immune network strategy for robot path planning in complicated environments[J].Joumal of Intelligent and 程帅,男,1988年生,硕士研究生 Robotic Systems,2010,60(1):111-131. 主要研究方向为仿生智能、移动机器人 [13]刘颖,侯利华,陈薇.干扰素的信号传导和抗病毒效应机 的视觉导航控制等。 制[J刀.生物技术通讯,2012,23(1):123-126. LIU Ying,HOU Lihua,CHEN Wei.Signal transduction and mechanisms of antiviral effect of interferon[J].Letters in Biotechnology,2012,23(1):123-126. 2014欧洲计算机视觉会议 European Conference on Computer Vision The European Conference on Computer Vision is one of the top conferences for researchers in this field and is held biennially in alternation with the International Conference on Computer Vision.It was first held in 1990 in Antibes France)with subsequent conferences in Santa Margherita Ligure Italy)in 1992,Stockholm (Sweden)in 1994, Cambridge (UK)in 1996,Freiburg (Germany)in 1998,Dublin (Ireland)in 2000,Copenhagen Denmark)in 2002,Prague (Czech Republic)in 2004,Graz Austria)in 2006,Marseille (France)in 2008,and Heraklion (Greece)in 2010 and 2012 in Florence (Italy).To our great delight,the 13th conference is held in Zirich, Switzerland.ECCV has an established tradition of very high scientific quality and an overall duration of one week. Website:http://eccv2014.org/
[C] / / Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications. Ji′nan, China, 2006: 586⁃591. [8]吴皓,田国会,黄彬.未知环境探测的多机器人协作策略 研究[J].山东大学学报:工学版, 2008, 38(4): 27⁃31. WU Hao, TIAN Guohui, HUANG Bin. Research on the col⁃ laboration strategy of multi robot for exploring unknown envi⁃ ronment[ J]. Journal of Shandong University: Engineering Science, 2008, 38(4): 27⁃31. [9] YUAN Mingxin, WANG Sunan, WU Canyang. Hybrid ant colony and immune network algorithm based on improved APF for optimal motion planning[ J]. Robotica, 2010, 28 (6): 833⁃846. [10] FARMER J, PACKARD N, PERELSON A. The immune system, adaptation, and machine learning[J]. Physica D, 1986, 2(3): 187⁃204. [11]ISHIGURO A, WATANABE Y, KONDO T, et al. A robot with a decentralized consensus⁃making mechanism based on the immune system [ C] / / Proceedings of the Interna⁃ tional Symposium on Autonomous Decentralized Systems. Berlin, Germany, 1997: 231⁃237. [12] YUAN Mingxin, WANG Sunan, WU Canyang, et al. A novel immune network strategy for robot path planning in complicated environments [ J]. Journal of Intelligent and Robotic Systems, 2010, 60(1): 111⁃131. [13]刘颖,侯利华,陈薇.干扰素的信号传导和抗病毒效应机 制[J].生物技术通讯, 2012, 23(1): 123⁃126. LIU Ying, HOU Lihua, CHEN Wei. Signal transduction and mechanisms of antiviral effect of interferon[J]. Letters in Biotechnology, 2012, 23(1): 123⁃126. [14] LI Guanghui, TAMURA Y, ASAMA H. Dynamical task allocation and reallocation based on body expansion behav⁃ ior for multi⁃robot coordination[C] / / Proceedings of 2011 International Conference on Mechatronics and Automation. Beijing, China, 2011: 537⁃542. 作者简介: 袁明新,男,1978 年生,讲师,博士, 主要研究方向为仿生智能、机器人视觉导 航控制与多机器人任务分配等。 主持及 参与国家自然科学基金、江苏省自然科学 基金等项目多项,发表学术论文 10 余篇。 叶兆莉,女,1987 年生,硕士研究 生,主要研究方向为仿生智能、移动机 器人路径规划等。 程帅,男,1988 年生,硕士研究生, 主要研究方向为仿生智能、移动机器人 的视觉导航控制等。 2014 欧洲计算机视觉会议 European Conference on Computer Vision The European Conference on Computer Vision is one of the top conferences for researchers in this field and is held biennially in alternation with the International Conference on Computer Vision. It was first held in 1990 in Antibes (France) with subsequent conferences in Santa Margherita Ligure (Italy) in 1992, Stockholm (Sweden) in 1994, Cambridge (UK) in 1996, Freiburg (Germany) in 1998, Dublin (Ireland) in 2000, Copenhagen (Denmark) in 2002, Prague (Czech Republic) in 2004, Graz (Austria) in 2006, Marseille (France) in 2008, and Heraklion (Greece) in 2010 and 2012 in Florence ( Italy). To our great delight, the 13th conference is held in Zürich, Switzerland. ECCV has an established tradition of very high scientific quality and an overall duration of one week. Website: http: / / eccv2014.org / ·82· 智 能 系 统 学 报 第 9 卷