第10卷第1期 智能系统学报 Vol.10 No.1 2015年2月 CAAI Transactions on Intelligent Systems Feb.2015 D0I:10.3969/j.issn.1673-4785.201311018 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150113.1130.005.html 改进蚁群算法及其在机器人避障中的应用 裴振兵1，陈雪波2 （1.辽宁科技大学电子与信息工程学院，辽宁鞍山114051：2.辽宁科技大学研究生院，辽宁鞍山114051) 摘要：提出了一种改进蚁群算法.首先针对蚁群算法在构造解过程中收敛速度慢且容易陷入局部最优，提出了在 蚁群搜索路径过程中，通过建立α（信息素启发式因子）和B(期望启发式因子)的互锁关系，动态自适应调整α、B: 其次针对蚁群算法在面对凹形障碍物易陷入死锁，降低搜索效率，提出了广义信息素更新规则：最后利用栅格法进 行静态已知环境建模，通过不同规模TS的仿真验证了该方法的可行性和有效性，同时将其应用到机器人避障并 取得了较好实验效果。 关键词：改进蚁群算法；互锁：机器人；避障：栅格法；建模；凹形障碍物：死锁 中图分类号：TP242文献标志码：A文章编号：1673-4785(2015)01-0090-07 中文引用格式：裴振兵，陈雪波.改进蚊群算法及其在机器人避障中的应用[J].智能系统学报，2015,10(1)：90-96. 英文引用格式：PEI Zhenbing,CHEN Xuebo..mproved ant colony algorithm and its application in obstacle avoidance for robot[J]. CAAI Transactions on Intelligent Systems,2015,10(1):90-96. Improved ant colony algorithm and its application in obstacle avoidance for robot PEI Zhenbing',CHEN Xuebo2 (1.School of Electronics and Information Engineering,Liaoning University of Science and Technology,Anshan 114051,China;2. Graduate school,Liaoning University of Science and Technology,Anshan 114051,China) Abstract:An improved ant colony algorithm is proposed in this paper.Firstly,in order to overcome the demerits of the ant colony algorithm,such as low convergence speed and easy to get into the local optimum,o and B are dy- namically adaptively adjusted by establishing an interlock between alpha (pheromone heuristic factor)and beta (expected heuristic factor)in the searching route process of ant colony.Secondly,in order to prevent the ant colo- ny algorithm from falling into deadlock when facing concave obstacles,which decreases search efficiency,an up- date rule of the generalized pheromone is proposed.Finally,static modeling for a known environment is conducted by the grid method.The simulation experiments showed that with different scales of TSP,the improved ant colony algorithm is feasible and efficient.In addition,this algorithm is applied to the obstacle avoidance of robots and the results are effective. Keywords:improved ant colony optimization;interlock;robots;obstacle avoidance;grid method;modeling;con- cave obstacle:deadlock 路径规划是移动机器人领域中一个重要的研究 为，意大利学者Dorigo M等于1991年在法国巴黎召 方向，而在面对各种障碍的环境中，如何成功地避开 开的第一届欧洲人工生命会议(European Conference 障碍物寻找一条最优路径，又是机器人路径规划中 on Artificial Lif,.ECAL)上最早提出了一种新型的仿 的重要研究课题。根据蚂蚁“寻找食物”的群体行 生算法一蚁群算法山，蚁群搜索食物的过程与机 器人路径规划有着惊人的相似，都是寻找一条从起 收稿日期：2013-11-07.网络出版日期：2015-01-13. 基金项目：国家自然科学基金资助项目(60874017). 始点到终点避障的最优路径。蚁群算法固然具有分 通信作者：陈雪波.E-mail:xuebochen(@126.com. 布式并行计算机制、易于与其他方法结合、具有较强
第 员园 卷第 员 期摇摇摇摇摇摇摇摇摇摇摇 摇摇摇 智 能 系 统 学 报摇摇摇摇摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 灾燥造援员园 翼援员 圆园员缘 年 圆 月摇摇摇摇摇摇摇摇摇摇摇 悦粤粤陨 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 陨灶贼藻造造蚤早藻灶贼 杂赠泽贼藻皂泽 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 云藻遭援 圆园员缘 阅韵陨院员园援猿怨远怨 辕 躁援蚤泽泽灶援员远苑猿鄄源苑愿缘援圆园员猿员员园员愿 网络出版地址院澡贼贼责院 辕 辕 憎憎憎援糟灶噪蚤援灶藻贼 辕 噪糟皂泽 辕 凿藻贼葬蚤造 辕 圆猿援员缘猿愿援栽孕援圆园员缘园员员猿援员员猿园援园园缘援澡贼皂造 改进蚁群算法及其在机器人避障中的应用 裴振兵员 袁陈雪波圆 渊员援辽宁科技大学 电子与信息工程学院袁辽宁 鞍山 员员源园缘员曰圆援 辽宁科技大学 研究生院袁辽宁 鞍山 员员源园缘员冤 摘 要院提出了一种改进蚁群算法援 首先针对蚁群算法在构造解过程中收敛速度慢且容易陷入局部最优袁 提出了在 蚁群搜索路径过程中袁 通过建立 琢渊信息素启发式因子冤和 茁渊期望启发式因子冤的互锁关系袁动态自适应调整 琢尧茁曰 其次针对蚁群算法在面对凹形障碍物易陷入死锁袁 降低搜索效率袁 提出了广义信息素更新规则曰 最后利用栅格法进 行静态已知环境建模袁 通过不同规模 栽杂孕 的仿真验证了该方法的可行性和有效性袁 同时将其应用到机器人避障并 取得了较好实验效果遥 关键词院改进蚁群算法曰互锁曰机器人曰避障曰栅格法曰建模曰凹形障碍物曰死锁 中图分类号院栽孕圆源圆 摇 文献标志码院粤摇 文章编号院员远苑猿鄄源苑愿缘渊圆园员缘冤园员鄄园园怨园鄄园苑 中文引用格式院裴振兵袁陈雪波援改进蚁群算法及其在机器人避障中的应用咱允暂援 智能系统学报袁 圆园员缘袁 员园渊员冤 院 怨园鄄怨远援 英文引用格式院孕耘陨 在澡藻灶遭蚤灶早袁悦匀耘晕 载怎藻遭燥援 陨皂责则燥增藻凿 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂 葬灶凿 蚤贼泽 葬责责造蚤糟葬贼蚤燥灶 蚤灶 燥遭泽贼葬糟造藻 葬增燥蚤凿葬灶糟藻 枣燥则 则燥遭燥贼咱允暂援 悦粤粤陨 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 陨灶贼藻造造蚤早藻灶贼 杂赠泽贼藻皂泽袁 圆园员缘袁 员园渊员冤 院 怨园鄄怨远援 陨皂责则燥增藻凿 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂 葬灶凿 蚤贼泽 葬责责造蚤糟葬贼蚤燥灶 蚤灶 燥遭泽贼葬糟造藻 葬增燥蚤凿葬灶糟藻 枣燥则 则燥遭燥贼 孕耘陨 在澡藻灶遭蚤灶早员 袁悦匀耘晕 载怎藻遭燥圆 渊员援 杂糟澡燥燥造 燥枣 耘造藻糟贼则燥灶蚤糟泽 葬灶凿 陨灶枣燥则皂葬贼蚤燥灶 耘灶早蚤灶藻藻则蚤灶早袁 蕴蚤葬燥灶蚤灶早 哉灶蚤增藻则泽蚤贼赠 燥枣 杂糟蚤藻灶糟藻 葬灶凿 栽藻糟澡灶燥造燥早赠袁 粤灶泽澡葬灶 员员源园缘员袁 悦澡蚤灶葬曰 圆援 郧则葬凿怎葬贼藻 泽糟澡燥燥造袁 蕴蚤葬燥灶蚤灶早 哉灶蚤增藻则泽蚤贼赠 燥枣 杂糟蚤藻灶糟藻 葬灶凿 栽藻糟澡灶燥造燥早赠袁 粤灶泽澡葬灶 员员源园缘员袁 悦澡蚤灶葬冤 粤遭泽贼则葬糟贼院粤灶 蚤皂责则燥增藻凿 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂 蚤泽 责则燥责燥泽藻凿 蚤灶 贼澡蚤泽 责葬责藻则援 云蚤则泽贼造赠袁 蚤灶 燥则凿藻则 贼燥 燥增藻则糟燥皂藻 贼澡藻 凿藻皂藻则蚤贼泽 燥枣 贼澡藻 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂袁 泽怎糟澡 葬泽 造燥憎 糟燥灶增藻则早藻灶糟藻 泽责藻藻凿 葬灶凿 藻葬泽赠 贼燥 早藻贼 蚤灶贼燥 贼澡藻 造燥糟葬造 燥责贼蚤皂怎皂袁 琢 葬灶凿 茁 葬则藻 凿赠鄄 灶葬皂蚤糟葬造造赠 葬凿葬责贼蚤增藻造赠 葬凿躁怎泽贼藻凿 遭赠 藻泽贼葬遭造蚤泽澡蚤灶早 葬灶 蚤灶贼藻则造燥糟噪 遭藻贼憎藻藻灶 葬造责澡葬 渊 责澡藻则燥皂燥灶藻 澡藻怎则蚤泽贼蚤糟 枣葬糟贼燥则冤 葬灶凿 遭藻贼葬 渊 藻曾责藻糟贼藻凿 澡藻怎则蚤泽贼蚤糟 枣葬糟贼燥则冤 蚤灶 贼澡藻 泽藻葬则糟澡蚤灶早 则燥怎贼藻 责则燥糟藻泽泽 燥枣 葬灶贼 糟燥造燥灶赠援 杂藻糟燥灶凿造赠袁 蚤灶 燥则凿藻则 贼燥 责则藻增藻灶贼 贼澡藻 葬灶贼 糟燥造燥鄄 灶赠 葬造早燥则蚤贼澡皂 枣则燥皂 枣葬造造蚤灶早 蚤灶贼燥 凿藻葬凿造燥糟噪 憎澡藻灶 枣葬糟蚤灶早 糟燥灶糟葬增藻 燥遭泽贼葬糟造藻泽袁 憎澡蚤糟澡 凿藻糟则藻葬泽藻泽 泽藻葬则糟澡 藻枣枣蚤糟蚤藻灶糟赠袁 葬灶 怎责鄄 凿葬贼藻 则怎造藻 燥枣 贼澡藻 早藻灶藻则葬造蚤扎藻凿 责澡藻则燥皂燥灶藻 蚤泽 责则燥责燥泽藻凿援 云蚤灶葬造造赠袁 泽贼葬贼蚤糟 皂燥凿藻造蚤灶早 枣燥则 葬 噪灶燥憎灶 藻灶增蚤则燥灶皂藻灶贼 蚤泽 糟燥灶凿怎糟贼藻凿 遭赠 贼澡藻 早则蚤凿 皂藻贼澡燥凿援 栽澡藻 泽蚤皂怎造葬贼蚤燥灶 藻曾责藻则蚤皂藻灶贼泽 泽澡燥憎藻凿 贼澡葬贼 憎蚤贼澡 凿蚤枣枣藻则藻灶贼 泽糟葬造藻泽 燥枣 栽杂孕袁 贼澡藻 蚤皂责则燥增藻凿 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂 蚤泽 枣藻葬泽蚤遭造藻 葬灶凿 藻枣枣蚤糟蚤藻灶贼援 陨灶 葬凿凿蚤贼蚤燥灶袁 贼澡蚤泽 葬造早燥则蚤贼澡皂 蚤泽 葬责责造蚤藻凿 贼燥 贼澡藻 燥遭泽贼葬糟造藻 葬增燥蚤凿葬灶糟藻 燥枣 则燥遭燥贼泽 葬灶凿 贼澡藻 则藻泽怎造贼泽 葬则藻 藻枣枣藻糟贼蚤增藻援 运藻赠憎燥则凿泽院蚤皂责则燥增藻凿 葬灶贼 糟燥造燥灶赠 燥责贼蚤皂蚤扎葬贼蚤燥灶曰 蚤灶贼藻则造燥糟噪曰 则燥遭燥贼泽曰 燥遭泽贼葬糟造藻 葬增燥蚤凿葬灶糟藻曰 早则蚤凿 皂藻贼澡燥凿曰 皂燥凿藻造蚤灶早曰 糟燥灶鄄 糟葬增藻 燥遭泽贼葬糟造藻曰 凿藻葬凿造燥糟噪 收稿日期院圆园员猿鄄员员鄄园苑援 摇 网络出版日期院圆园员缘鄄园员鄄员猿 援 基金项目院国家自然科学基金资助项目渊远园愿苑源园员苑冤援 通信作者院陈雪波援 耘鄄皂葬蚤造院曾怎藻遭燥糟澡藻灶岳 员圆远援糟燥皂援 摇 摇 路径规划是移动机器人领域中一个重要的研究 方向袁而在面对各种障碍的环境中袁如何成功地避开 障碍物寻找一条最优路径袁又是机器人路径规划中 的重要研究课题遥 根据蚂蚁野寻找食物冶 的群体行 为袁意大利学者 阅燥则蚤早燥 酝 等于 员怨怨员 年在法国巴黎召 开的第一届欧洲人工生命会议渊耘怎则燥责藻葬灶 悦燥灶枣藻则藻灶糟藻 燥灶 粤则贼蚤枣蚤糟蚤葬造 蕴蚤枣袁 耘悦粤蕴冤上最早提出了一种新型的仿 生算法要要要蚁群算法咱员暂 袁 蚁群搜索食物的过程与机 器人路径规划有着惊人的相似袁都是寻找一条从起 始点到终点避障的最优路径遥 蚁群算法固然具有分 布式并行计算机制尧易于与其他方法结合尧具有较强
第1期 裴振兵，等：改进蚁群算法及其在机器人避障中的应用 .91· 的鲁棒性等优点，但搜索时间长、易陷于局部最优 移概率越接近于贪心规则；n(t)为启发函数，其表 面对凹形障碍物容易陷入死锁是其最为突出的缺 达式如式(2)： 点2 文中首先简单介绍蚁群算法数学模型，然后引 ,(0 di (2) 入改进蚁群算法，针对一般蚁群算法在构造解的过 d表示相邻节点之间的距离。对蚂蚁k而言， 程中，蚁群收敛速度慢且容易陷入局部最优，通过建 d越小，则n,(t)越大，P(t)也就越大。显然，该启 立α（信息素启发式因子）B(期望启发式因子)的互 发函数表示蚂蚁从节点i转移到节点j的期望程度。 锁关系，动态自适应调整αB;其次针对蚁群算法在 对蚂蚁k而言，在每只蚂蚁走完一步或者完成对所 面对凹形障碍物易陷入死锁，降低搜索效率，提出了 有n个节点的遍历后，要对残留信息进行更新处理。 广义信息素更新规则。接着将改进算法与传统蚁群 这种更新策略模仿了人类大脑记忆的特点，在新信 算法进行仿真对比（以TSP作为仿真算例），通过仿 息不断存入大脑的同时，存储在大脑中的旧信息随 真结果证明了改进算法在提高收敛速度，避免蚁群 着时间的推移逐渐淡化，甚至忘记。由此，t+n时刻 算法陷入局部最优方面的可行性和优越性。并将改 在路径(i,)上的信息量按式(3)和(4)进行调 进蚁群算法运用到机器人避障，通过仿真实验，取得 整8劉： 了较好实验效果，进一步验证了该改进算法的有效 T(t+n)=(1-p)·T(t)+△r(t) (3) 性和实用性（利用栅格法进行环境建模）。最后，进 行了进一步总结与分析。 4r,)=240) (4) k=1 p表示信息素挥发系数，则1-p表示信息素残 1蚁群算法基本原理及数学模型 留因子，为了防止信息素无限积累，·的取值范围为 蚁群算法是科学家受自然界中真实蚁群觅食行 p∈[0，I);△r,(t)表示本次循环中路径(i,)上的 为的启发，经过长期研究发现：单个蚂蚁虽没有视 信息素增量，初始时刻△r,(t)=0,△r(t)表示第k 觉，也无法掌握附近地理信息，但运动时会通过在路 只蚂蚁在本次循环中留在路径(i,)上的信息 径上释放出一种特殊的分泌物一信息素来寻找路 量。 径[)。当运动路径上突然出现障碍物时，蚂蚁会通 其中△r(t)按式(5)进行： 过信息素相互传递信息而最终找到一条躲避障碍物 的最优路径4)。蚁群算法具有分布式并行计算机 △r(t)=Lw ,第k只蚂蚁经过节点(i) (5) 制，易于与其他方法结合且实现简单的优点。这也 0,第k只蚂蚁未经过节点(i,) 正是其最早成功应用解决著名TSP问题的原因)。 L:为第k只蚂蚁在本次循环中所走过的路径长 蚂蚁k(k=1,2,…,m)在运动过程中，根据各条 度，Q为信息素强度。 路径上的信息量决定其转移方向。用禁忌tabu: (k=1,2,…,m)来记录蚂蚁k当前所走过的节点， 2改进蚁群算法 蚂蚁根据各条路径上的信息量及路径的启发信息来 与传统蚁群算法相比，文中提出的改进算法的 计算状态转移概率。P(t)表示t时刻蚂蚁k由节 特点是：1)改进算法用动态自适应调整α、B的值， 点i转移到节点j的状态转移概率[6] 代替传统蚁群算法中固定值α、B,从而提高算法收 [r,(t)]a·[n(t)]B 敛速度，并逃离局部最优；2)为了避免蚁群在面对 凹形障碍物时容易陷入其中并进入死锁状态，改进 P()= 【r.0]·[n.0]allowed, 算法采用广义信息素更新规则，代替传统蚁群算法 0,j年allowed 中的信息素更新规则。 (1) 2.1问题描述 式(1)中，r(t)表示t时刻在路径(i,)上的信息素 蚁群算法在实现过程中，利用禁忌表对已访问 量；allowed,={C一tabu4}表示蚂蚁k下一步允许选 的节点进行存储，即下一步选择的节点只能为未访 择的节点；α为信息启发因子（α反映信息素积累量 问节点。这样就会导致有些蚂蚁在面对凹形障碍物 在指导蚁群搜索中的相对重要性)，B为期望启发式 时，极易陷入其中并出现后续无节点可选的情况，进 因子(B反映了下一个目标点的距离在指导蚁群搜 而进入“死锁”状态。凹形障碍物如图1所示。路 索过程中的相对重要性)且B值越大，则该状态转 径1→4→3,14+2,2+4→3,2+4→1,3→4→1,3
的鲁棒性等优点袁但搜索时间长尧易陷于局部最优尧 面对凹形障碍物容易陷入死锁是其最为突出的缺 点咱圆暂 遥 文中首先简单介绍蚁群算法数学模型袁然后引 入改进蚁群算法袁针对一般蚁群算法在构造解的过 程中袁蚁群收敛速度慢且容易陷入局部最优袁通过建 立 琢渊信息素启发式因子冤茁渊期望启发式因子冤的互 锁关系袁动态自适应调整 琢尧茁曰其次针对蚁群算法在 面对凹形障碍物易陷入死锁袁降低搜索效率袁提出了 广义信息素更新规则遥 接着将改进算法与传统蚁群 算法进行仿真对比渊以 栽杂孕 作为仿真算例冤 袁通过仿 真结果证明了改进算法在提高收敛速度袁避免蚁群 算法陷入局部最优方面的可行性和优越性遥 并将改 进蚁群算法运用到机器人避障袁通过仿真实验袁取得 了较好实验效果袁进一步验证了该改进算法的有效 性和实用性渊利用栅格法进行环境建模冤 遥 最后袁进 行了进一步总结与分析遥 员摇 蚁群算法基本原理及数学模型 蚁群算法是科学家受自然界中真实蚁群觅食行 为的启发袁经过长期研究发现院单个蚂蚁虽没有视 觉袁也无法掌握附近地理信息袁但运动时会通过在路 径上释放出一种特殊的分泌物要要要信息素来寻找路 径咱猿暂 遥 当运动路径上突然出现障碍物时袁蚂蚁会通 过信息素相互传递信息而最终找到一条躲避障碍物 的最优路径咱源暂 遥 蚁群算法具有分布式并行计算机 制袁易于与其他方法结合且实现简单的优点遥 这也 正是其最早成功应用解决著名 栽杂孕 问题的原因咱缘暂 遥 蚂蚁 噪渊噪 越 员袁圆袁噎袁皂冤在运动过程中袁根据各条 路径上的信息量决定其转移方向遥 用禁忌 贼葬遭怎噪 渊噪 越 员袁圆袁噎袁皂冤来记录蚂蚁 噪 当前所走过的节点袁 蚂蚁根据各条路径上的信息量及路径的启发信息来 计算状态转移概率遥 孕噪 蚤躁渊 贼冤表示 贼 时刻蚂蚁 噪 由节 点 蚤 转移到节点 躁 的状态转移概率咱远暂 院 责噪 蚤躁( )贼 越 子蚤躁 [ ] ( )贼 琢 窑 浊蚤躁 [ ] ( )贼 茁 泽奂葬造造燥憎藻凿 移 噪 子蚤泽 [ ] ( )贼 琢 窑 浊蚤泽 [ ] ( )贼 茁 袁躁 沂 葬造造燥憎藻凿噪 园袁躁 埸 葬造造燥憎藻凿噪 ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ 渊员冤 式渊员冤中袁子蚤躁渊贼冤表示 贼 时刻在路径渊蚤袁 躁冤上的信息素 量曰葬造造燥憎藻凿噪 越 喳悦要贼葬遭怎噪札表示蚂蚁 噪 下一步允许选 择的节点曰琢 为信息启发因子渊琢 反映信息素积累量 在指导蚁群搜索中的相对重要性冤 袁茁 为期望启发式 因子渊茁 反映了下一个目标点的距离在指导蚁群搜 索过程中的相对重要性冤 且 茁 值越大袁则该状态转 移概率越接近于贪心规则曰浊蚤躁渊贼冤为启发函数袁其表 达式如式渊圆冤咱苑暂 院 浊蚤躁( )贼 越 员 凿蚤躁 渊圆冤 摇 摇 凿蚤躁表示相邻节点之间的距离遥 对蚂蚁 噪 而言袁 凿蚤躁越小袁则 浊蚤躁渊贼冤越大袁孕噪 蚤躁渊 贼冤也就越大遥 显然袁该启 发函数表示蚂蚁从节点 蚤 转移到节点 躁 的期望程度遥 对蚂蚁 噪 而言袁在每只蚂蚁走完一步或者完成对所 有 灶 个节点的遍历后袁要对残留信息进行更新处理遥 这种更新策略模仿了人类大脑记忆的特点袁在新信 息不断存入大脑的同时袁存储在大脑中的旧信息随 着时间的推移逐渐淡化袁甚至忘记遥 由此袁贼垣灶 时刻 在路径渊 蚤袁 躁冤 上的信息量按式渊猿冤 和渊源冤 进行调 整咱愿暂 院 子蚤躁( ) 贼 垣 灶 越 渊员 原 籽冤窑子蚤躁( )贼 垣 驻子蚤躁( )贼 渊猿冤 驻子蚤躁渊贼冤 越 移 皂 噪 越 员 驻子噪 蚤躁渊贼冤 渊源冤 摇 摇 籽 表示信息素挥发系数袁则 员原籽 表示信息素残 留因子袁为了防止信息素无限积累袁籽 的取值范围为 籽沂咱园袁员冤 曰驻子蚤躁渊 贼冤表示本次循环中路径渊 蚤袁 躁冤上的 信息素增量袁初始时刻 驻子蚤躁渊贼冤越 园袁 驻子噪 蚤躁渊贼冤表示第 噪 只蚂蚁在本次循环中留在路径 渊 蚤袁 躁冤 上的信息 量咱怨暂 遥 其中 驻子噪 蚤躁渊贼冤按式渊缘冤进行院 驻子噪 蚤躁( )贼 越 匝 蕴运 袁第 噪 只蚂蚁经过节点渊蚤袁躁冤 园 袁 第 噪 只蚂蚁未经过节点渊蚤袁躁冤 ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ 渊缘冤 摇 摇 蕴噪为第 噪 只蚂蚁在本次循环中所走过的路径长 度袁匝 为信息素强度遥 圆摇 改进蚁群算法 与传统蚁群算法相比袁文中提出的改进算法的 特点是院员冤改进算法用动态自适应调整 琢尧茁 的值袁 代替传统蚁群算法中固定值 琢尧茁袁从而提高算法收 敛速度袁并逃离局部最优曰圆冤 为了避免蚁群在面对 凹形障碍物时容易陷入其中并进入死锁状态袁改进 算法采用广义信息素更新规则袁代替传统蚁群算法 中的信息素更新规则遥 圆援员摇 问题描述 蚁群算法在实现过程中袁利用禁忌表对已访问 的节点进行存储袁即下一步选择的节点只能为未访 问节点遥 这样就会导致有些蚂蚁在面对凹形障碍物 时袁极易陷入其中并出现后续无节点可选的情况袁进 而进入野死锁冶 状态遥 凹形障碍物如图 员 所示遥 路 径 员寅源寅猿袁员寅源寅圆袁圆寅源寅猿袁圆寅源寅员袁猿寅源寅员袁猿 第 员 期摇摇摇摇摇摇摇摇摇摇摇摇摇摇 裴振兵袁等院改进蚁群算法及其在机器人避障中的应用 窑怨员窑
·92 智能系统学报 第10卷 4→2是陷入凹形障碍物而未进人“死锁”的路径； B,NC≤NC 而路径1→4+5,2→4→5,34→5是陷入凹形障碍 B(NC)=B2,NC,<NC≤NC (7) 物并进入“死锁”的路径。显然，若蚂蚁陷入凹形障 B,NC2<NC≤NCa 碍物并进入“死锁”路径，将会使最终的有效蚂蚁的 在搜索过程中为了达到平衡，式(6)、(7)中信 数量小于初始蚂蚁数量，这不但会影响最优解的探 息启发因子α和期望启发式因子B是互锁的关系， 寻，降低算法收敛速度，还会减缓局部最优的逃离； 即&，+B=M(其中M为一定值)。由于aB值过大 若蚂蚁陷入凹形障碍物并未进入“死锁”路径，蚂蚁 或过小都易使蚁群的搜索过早陷入局部最优[)。 虽然并未停止搜索，但路径1→4→3,1→4→2的距 结合其他改进算法中αB的取值经验与分析，同时 离显然长于路径1→2→3,1→2，也即该路径上的蚂 蚁做了无用功，从而导致整个蚁群能量损耗，在一定 通过仿真实验分析，确定当1≤α≤9,1≤B≤9更有 程度上降低了蚁群搜索速度，延长了搜索时间。 利于整个改进算法动态调整。开始时信息素浓度差 别不大，以各个节点之间的距离为主要调整因素，这 样有利于提高路径搜索速度，即信息启发因子α(1 ≤α1<5)先取值较小，相对应的期望启发式因子B(5 B,≤9)取值较大[：随着迭代次数增加，各条路径 的信息素也得到了积累，此时选择信息素浓度为主 要调整因素进行全局搜索，即信息启发因子α(5<α？ ≤9)先取较大值，相对应的期望启发式因子B(1≤ B2<5)取值较小；随着迭代次数的继续增加，为了防 止由于信息素积累的正反馈机制作用而陷入局部最 00 优，进而改为各个节点距离为主要调整因素，即信息 图1凹形障碍物 启发因子α(1<，≤5)先取值较小，相对应的期望 Fig.I The concave obstacle 启发式因子B(5≤B<9)取值较大。 对于凹形障碍物，一种常见的处理方法是在环 定义2广义信息素更新规则。是指每只蚂蚁 境建模时，将实际环境的凹形障碍物进行凸化处理， 在路径的搜索过程中，碰到凹形障碍物采用新的信 即将障碍物进行填补，这种方法虽然可以消除凹形 息素更新规则。当遇到凹形障碍物并陷入“死锁” 障碍物，但以牺牲对环境的适应性来换取算法的运 则对该路径上的信息素更新采用“清零”方式：当遇 行速度，且在实际环境中缺乏可行性[o 到凹形障碍物并未陷入“死锁”时，为了保证整个蚁 鉴于以上问题，通过引入文中改进蚁群算法提 群的搜索空间，对该路径上的信息素更新采用“渐 高蚁群收敛速度，扩大蚁群搜索空间，有效避开凹形 灭”方式。 障碍物是非常有必要和有意义的。 设第i(i=1,2,…,k)只蚂蚁在t时刻所对应的 2.2改进算法描述 j(i=1,2,…,k)这条路径为陷入凹形障碍物的路径，则 定义1αB的动态自适应调整。是指通过建 该路径上的信息素按式(8)~(10)进行更新)： 立α（信息素启发式因子）与B(期望启发式因子)的 (t)=(1-X)(1-p)4x (8) 互锁关系，即对不同的迭代次数NC,α、B会对应取 不同的值，进而在整个过程中扩大蚁群搜索空间，使 X=八，第i只蚂蚁进人死锁 0,第i只蚂蚁未进入死锁 (9) 搜索路径逃离局部最优。 △xa=Q/d (10) 根据蚁群算法搜索情况自适应动态调整信息启 式中：Ax:为1时刻蚂蚁i在路径j:上遗留信息素的 发因子α和期望启发式因子B,采用迭代次数NC的 增量，与路径长度d成反比：Q为常数：1-p为信息 阶梯函数a(NC),B(NC)代替常数项aB,按式(6) 素强度挥发系数，p为绝对值小于1的实数；x为t 和(7)进行调整： 时刻路径j:上遗留信息素的总量；d为蚂蚁i在路径 Ta,NC≤NC j上行走的距离：N为陷入凹形障碍物并未进入死锁 a(NC)= a2,NC NC <NC2 (6) 的蚂蚁数。 a&3,NC2<NC≤VCm 算法收敛性分析设k只蚂蚁中，第i只蚂蚁
寅源寅圆 是陷入凹形障碍物而未进入野死锁冶的路径曰 而路径 员寅源寅缘袁圆寅源寅缘袁猿寅源寅缘 是陷入凹形障碍 物并进入野死锁冶的路径遥 显然袁若蚂蚁陷入凹形障 碍物并进入野死锁冶路径袁将会使最终的有效蚂蚁的 数量小于初始蚂蚁数量袁这不但会影响最优解的探 寻袁降低算法收敛速度袁还会减缓局部最优的逃离曰 若蚂蚁陷入凹形障碍物并未进入野死锁冶路径袁蚂蚁 虽然并未停止搜索袁但路径 员寅源寅猿袁员寅源寅圆 的距 离显然长于路径 员寅圆寅猿袁员寅圆袁也即该路径上的蚂 蚁做了无用功袁从而导致整个蚁群能量损耗袁在一定 程度上降低了蚁群搜索速度袁延长了搜索时间遥 图 员摇 凹形障碍物 云蚤早援员摇 栽澡藻 糟燥灶糟葬增藻 燥遭泽贼葬糟造藻 对于凹形障碍物袁一种常见的处理方法是在环 境建模时袁将实际环境的凹形障碍物进行凸化处理袁 即将障碍物进行填补袁这种方法虽然可以消除凹形 障碍物袁但以牺牲对环境的适应性来换取算法的运 行速度袁且在实际环境中缺乏可行性咱员园暂 遥 鉴于以上问题袁通过引入文中改进蚁群算法提 高蚁群收敛速度袁扩大蚁群搜索空间袁有效避开凹形 障碍物是非常有必要和有意义的遥 圆援圆摇 改进算法描述 定义 员摇 琢尧茁 的动态自适应调整遥 是指通过建 立 琢渊信息素启发式因子冤与 茁渊期望启发式因子冤的 互锁关系袁即对不同的迭代次数 晕悦袁琢尧茁 会对应取 不同的值袁进而在整个过程中扩大蚁群搜索空间袁使 搜索路径逃离局部最优遥 根据蚁群算法搜索情况自适应动态调整信息启 发因子 琢 和期望启发式因子 茁袁采用迭代次数 晕悦 的 阶梯函数 琢渊晕悦冤 袁茁渊晕悦冤代替常数项 琢尧茁袁按式渊远冤 和渊苑冤进行调整院 琢渊晕悦冤 越 琢员 袁晕悦 臆 晕悦员 琢圆 袁晕悦员 约 晕悦 ≤晕悦圆 琢猿 袁晕悦圆 约 晕悦 ≤晕悦皂葬曾 ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ 渊远冤 茁渊晕悦冤 越 茁员 袁晕悦 臆 晕悦员 茁圆 袁晕悦员 约 晕悦 臆 晕悦圆 茁猿 袁晕悦圆 约 晕悦 臆 晕悦皂葬曾 ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ 渊苑冤 摇 摇 在搜索过程中为了达到平衡袁式渊远冤尧渊苑冤中信 息启发因子 琢 和期望启发式因子 茁 是互锁的关系袁 即 琢蚤垣茁蚤 越酝渊其中 酝 为一定值冤 遥 由于 琢尧茁 值过大 或过小都易使蚁群的搜索过早陷入局部最优咱 员员 暂 遥 结合其他改进算法中 琢尧茁 的取值经验与分析袁同时 通过仿真实验分析袁确定当 员臆琢臆怨袁员臆茁臆怨 更有 利于整个改进算法动态调整遥 开始时信息素浓度差 别不大袁以各个节点之间的距离为主要调整因素袁这 样有利于提高路径搜索速度袁即信息启发因子 琢渊 员 臆琢员约缘冤先取值较小袁相对应的期望启发式因子 茁渊缘 约茁员臆怨冤取值较大咱员圆暂 曰随着迭代次数增加袁各条路径 的信息素也得到了积累袁此时选择信息素浓度为主 要调整因素进行全局搜索袁即信息启发因子 琢渊缘约琢圆 臆怨冤先取较大值袁相对应的期望启发式因子 茁渊员臆 茁圆约缘冤取值较小曰随着迭代次数的继续增加袁为了防 止由于信息素积累的正反馈机制作用而陷入局部最 优袁进而改为各个节点距离为主要调整因素袁即信息 启发因子 琢渊员约琢猿臆缘冤 先取值较小袁相对应的期望 启发式因子 茁渊缘臆茁猿约怨冤取值较大遥 定义 圆摇 广义信息素更新规则遥 是指每只蚂蚁 在路径的搜索过程中袁碰到凹形障碍物采用新的信 息素更新规则遥 当遇到凹形障碍物并陷入野死锁冶 则对该路径上的信息素更新采用野清零冶方式曰当遇 到凹形障碍物并未陷入野死锁冶时袁为了保证整个蚁 群的搜索空间袁对该路径上的信息素更新采用野渐 灭冶方式遥 设第 蚤渊蚤 越 员袁圆袁噎袁噪冤只蚂蚁在 贼 时刻所对应的 躁蚤 渊蚤越员袁圆袁噎袁噪冤这条路径为陷入凹形障碍物的路径袁则 该路径上的信息素按式渊愿冤 耀渊员园冤进行更新咱员猿暂 院 曾躁 蚤 渊贼冤 越 渊员 原 载冤 渊员 原 籽冤 晕驻曾躁 蚤 渊愿冤 载 越 员袁 第 蚤 只蚂蚁进入死锁 {园袁 第 蚤 只蚂蚁未进入死锁 渊怨冤 驻曾躁蚤 越 匝辕凿躁蚤 渊员园冤 式中院驻曾躁蚤为 贼 时刻蚂蚁 蚤 在路径 躁蚤上遗留信息素的 增量袁与路径长度 凿躁蚤成反比曰匝 为常数曰员原籽 为信息 素强度挥发系数袁籽 为绝对值小于 员 的实数曰曾躁蚤为 贼 时刻路径 躁蚤上遗留信息素的总量曰凿躁蚤为蚂蚁 蚤 在路径 躁 上行走的距离曰晕 为陷入凹形障碍物并未进入死锁 的蚂蚁数遥 算法收敛性分析 设 噪 只蚂蚁中袁第 蚤 只蚂蚁 窑怨圆窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 员园 卷
第1期 裴振兵，等：改进蚁群算法及其在机器人避障中的应用 ·93· 陷入凹形障碍物并进入死锁，由式(8)~(10)可见， 仿真实验1将改进算法与传统蚁群算法基于 由于X=1,此时路径方：上遗留信息素x将会被“清 不同规模的TSP进行仿真对比，具体实验结果如图 零”：同理对于陷入凹形障碍物未进入死锁的蚂蚁， ×10 由式(8)~(10)可见，随着N的不断增加且1-p∈ 3.2 一传统蚁群算法 3.1 改进蚁群算法 [0,1),x将以指数的方式递减，也即路径j:上遗留 3.0 信息素x将会被“渐灭”最终趋于零。 2.9 2.3改进算法实现步骤 2.8 1)初始化 2.7 初始化改进蚁群算法的最大迭代次数NC, 2.6 2.5 蚁群的蚂蚁数m,以及p,Q等参数进行初始化。 2.4 2)根据转移概率公式选择下一个节点 2.3 0 50 100150200 250300 蚂蚁按照转移概率公式(1)进行选择，其中αB 迭代次数/次 的值按式(6)、(7)进行动态自适应调整，每次转移 之后对已走过的路径进行记录，并将已访问节点加 图2基于32个目标的平均距离与最短距离 入禁忌表。 Fig.2 Average distance and the shortest distance based on 32 goals 3)记录每一代每一只蚂蚁的觅食路径和路径 ×109 4.4r 长度 传统蚁群算法 4.2 改进蚁群算法 将蚁群中迭代一次的蚂蚁路径及路径长度进行 4.0 记录，并写入细胞存储结构CELL。 38 4)更新信息素 3.6 对各条路径的节点进行判断，若已访问的节点 3.4 中包含凹形障碍物节点，则该节点对应的路径信息 3.2 素按式(8)~(10)进行更新；否则按式(3)~(5)进 3.0 2. 行信息素更新。 0 50 100150200250300 5)判断终止条件 迭代次数/饮 当算法迭代次数大于设定最大迭代次数NC 图3基于56个目标的平均距离与最短距离 或算法给出的最优解满足目标条件时，则退出程序，Fig.3 Average distance and the shortest distance based on56goas 输出最优解。 800m 3仿真实验及其分析 700 600 3.1TSP仿真算例验证 500 为了验证文中所提改进算法的可行性和有效 4001 性，针对传统蚁群算法搜索时间长、易陷于局部最优 300 缺点，以传统蚁群算法为对比，基于TSP仿真算例 200 进行实验分析。实验中重要参数设置如表1所示。 10 表1参数设置说明 100 150200250300350400450 横向距离/m Tabl Parameters setup instructions 图4最优路径 参数 算法 Fig.4 The optimal path m a B NC 2~4所示。 图2为遍历32个目标所得仿真图， 传统蚁群算法 32 15 0.5 0.5 300 图3为遍历56个目标所得仿真图。图2、3中实线 按式(6)及 改进蚁群算法 32 0.50.5 代表改进蚁群算法，点划线代表传统蚁群算法（图 300 (7)进行调整 2、3的上半部分是所提的改进蚁群算法与传统蚁群 算法平均距离仿真对比：下半部分是最短路径距离
陷入凹形障碍物并进入死锁袁由式渊 愿冤 耀 渊员园冤可见袁 由于 载 越 员袁此时路径 躁蚤上遗留信息素 曾躁蚤将会被野清 零冶 曰同理对于陷入凹形障碍物未进入死锁的蚂蚁袁 由式渊 愿冤 耀 渊 员园冤可见袁随着 晕 的不断增加且 员原籽沂 咱园袁员冤 袁曾躁蚤将以指数的方式递减袁也即路径 躁蚤上遗留 信息素 曾躁蚤将会被野渐灭冶最终趋于零遥 圆援猿摇 改进算法实现步骤 员冤 初始化 初始化改进蚁群算法的最大迭代次数 晕悦皂葬曾袁 蚁群的蚂蚁数 皂袁以及 籽袁匝 等参数进行初始化咱员源暂 遥 圆冤 根据转移概率公式选择下一个节点 蚂蚁按照转移概率公式渊员冤进行选择袁其中 琢尧茁 的值按式渊远冤尧渊苑冤进行动态自适应调整袁每次转移 之后对已走过的路径进行记录袁并将已访问节点加 入禁忌表遥 猿冤 记录每一代每一只蚂蚁的觅食路径和路径 长度 将蚁群中迭代一次的蚂蚁路径及路径长度进行 记录袁并写入细胞存储结构 悦耘蕴蕴遥 源冤 更新信息素 对各条路径的节点进行判断袁若已访问的节点 中包含凹形障碍物节点袁则该节点对应的路径信息 素按式渊愿冤 耀 渊员园冤进行更新曰否则按式渊猿冤 耀 渊缘冤进 行信息素更新遥 缘冤 判断终止条件 当算法迭代次数大于设定最大迭代次数 晕悦皂葬曾 或算法给出的最优解满足目标条件时袁则退出程序袁 输出最优解遥 猿摇 仿真实验及其分析 猿援员摇 栽杂孕 仿真算例验证 为了验证文中所提改进算法的可行性和有效 性袁针对传统蚁群算法搜索时间长尧易陷于局部最优 缺点袁以传统蚁群算法为对比袁基于 栽杂孕 仿真算例 进行实验分析遥 实验中重要参数设置如表 员 所示遥 表 员摇 参数设置说明 栽葬遭员摇 孕葬则葬皂藻贼藻则泽 泽藻贼怎责 蚤灶泽贼则怎糟贼蚤燥灶泽 算法 参数 皂琢 茁 籽匝 晕悦皂葬曾 传统蚁群算法 猿圆 员 缘 园援缘 园援缘 猿园园 改进蚁群算法 猿圆 按式渊远冤及 渊苑冤进行调整 园援缘 园援缘 猿园园 摇 摇 仿真实验 员摇 将改进算法与传统蚁群算法基于 不同规模的 栽杂孕 进行仿真对比袁具体实验结果如图 图 圆摇 基于 猿圆 个目标的平均距离与最短距离 云蚤早援圆摇 粤增藻则葬早藻 凿蚤泽贼葬灶糟藻 葬灶凿 贼澡藻 泽澡燥则贼藻泽贼 凿蚤泽贼葬灶糟藻 遭葬泽藻凿 燥灶 猿圆 早燥葬造泽 图 猿摇 基于 缘远 个目标的平均距离与最短距离 云蚤早援猿摇 粤增藻则葬早藻 凿蚤泽贼葬灶糟藻 葬灶凿 贼澡藻 泽澡燥则贼藻泽贼 凿蚤泽贼葬灶糟藻 遭葬泽藻凿 燥灶 缘远 早燥葬造泽 图 源摇 最优路径 云蚤早援源 摇 栽澡藻 燥责贼蚤皂葬造 责葬贼澡 圆耀源 所示遥摇 摇 图 圆 为遍历 猿圆 个目标所得仿真图袁 图 猿 为遍历 缘远 个目标所得仿真图遥 图 圆尧猿 中实线 代表改进蚁群算法袁点划线代表传统蚁群算法 渊图 圆尧猿 的上半部分是所提的改进蚁群算法与传统蚁群 算法平均距离仿真对比曰下半部分是最短路径距离 第 员 期摇摇摇摇摇摇摇摇摇摇摇摇摇摇 裴振兵袁等院改进蚁群算法及其在机器人避障中的应用 窑怨猿窑
·94· 智能系统学报 第10卷 仿真对比)。图4为采用改进蚁群算法遍历56个目 实验方法是将改进算法和传统蚁群算法分别在 标所搜索到的最优路径(1为起始目标点，56为终 上述所构造的环境中进行移动机器人路径规划（其 止目标点)。 中每一栅格都为1×1正方形，且大小相等，起始栅 具体仿真数据分析如表2所示： 格和目标栅格是预先指定的)。文中所做的仿真实 表2仿真数据 验是在MATLAB数值分析工具下进行的。 仿真实验2实验环境为10×10栅格环境，设 Tab 2 Simulation data 定出发点的栅格序号为1，目标点的栅格序号为100 最短距离/ 平均距离/运行时间/ 算法 (栅格对应的序号是从左上角开始，从左到右，从上 m 到下依次为1~100)，具体实验结果如图5~9所示。 传统蚁群算法（遍历 10 2.4417e+0032.8580e+00332.156000 32个日标) 改进蚁群算法（遍历 2.3966e+0032.7204e+00329.172000 32个目标) 传统蚁群算法（遍历 3.0148e+0033.5129e+00359.316000 56个目标) 改进蚁群算法（遍历 2.9426e+0033.3599e+00343.204000 56个目标) 0 0 2 3456789 10 由表2可以看出，基于不同规模的TSP仿真算 图5基于改进蚊群算法的机器人各代避障路线 例，改进的蚁群算法所获得的最短距离与平均距离 Fig.5 The obstacle avoidance path of various generation ro- bot based on the improved algorithm 明显优于传统蚁群算法，且整个运行时间也少于传 统蚁群算法。通过不同规模仿真实验对比，验证了 18.5 所提出的改进算法的可行性和有效性。 18.0 3.2改进算法在机器人避障碍中的应用 17.5 为了进一步验证改进蚁群算法的可行性，将所 17.0 提改进蚁群算法运用到机器人避障。为了便于蚁群 蓝16.5 算法搜索到最优路径，采用栅格法进行静态已知环 16.0 境建模，同时选取了数量更多、分布更为复杂的障碍 物[1)。设机器人的工作空间为二维平面上的有限 15.5 0 50 100 150 区域AS,起始点B和目标点E。文中路径规划的优 迭代次数/次 化准则为路径最短，即寻找一条从B到E避开障碍 图6收敛曲线（基于改进蚊群算法） 物的最短路径[16。工作空间AS由200个1×1大小 Fig6 Convergence curve (based on the improved algorithm) 的方格组成，AS的规模为10行×10列。最短路径 问题的目标函数可表示为式(11)： 1=盒G+6,D (11) 式中：(x:,y)为路径点坐标，n为路径点数目，L 为路径长度。按从左到右、从上到下的顺序对 栅格进行编号(1~100)，同时设机器人工作空间由 M行N列栅格组成，其中每个栅格是边长为1的正 方形小格，将障碍物地图用一个二维数组矩阵ma即 0 2345678910 (M,N)表示为]： 图7基于传统群算法的机器人各代避障路线 1,第p行第q列栅格上有障碍 Fig.7 The obstacle avoidance path of various genera- map(p,q）= (12) 0,其他 tion robot based on the general algorithm
仿真对比冤 遥 图 源 为采用改进蚁群算法遍历 缘远 个目 标所搜索到的最优路径渊 员 为起始目标点袁缘远 为终 止目标点冤 遥 具体仿真数据分析如表 圆 所示院 表 圆摇 仿真数据 栽葬遭 圆摇 杂蚤皂怎造葬贼蚤燥灶 凿葬贼葬 算法 最短距离辕 皂 平均距离辕 皂 运行时间辕 泽 传统蚁群算法渊遍历 猿圆 个目标冤 圆援源源员苑藻垣园园猿 圆援愿缘愿园藻垣园园猿 猿圆援员缘远园园园 改进蚁群算法渊遍历 猿圆 个目标冤 圆援猿怨远远藻垣园园猿 圆援苑圆园源藻垣园园猿 圆怨援员苑圆园园园 传统蚁群算法渊遍历 缘远 个目标冤 猿援园员源愿藻垣园园猿 猿援缘员圆怨藻垣园园猿 缘怨援猿员远园园园 改进蚁群算法渊遍历 缘远 个目标冤 圆援怨源圆远藻垣园园猿 猿援猿缘怨怨藻垣园园猿 源猿援圆园源园园园 摇 摇 由表 圆 可以看出袁基于不同规模的 栽杂孕 仿真算 例袁改进的蚁群算法所获得的最短距离与平均距离 明显优于传统蚁群算法袁且整个运行时间也少于传 统蚁群算法遥 通过不同规模仿真实验对比袁验证了 所提出的改进算法的可行性和有效性遥 猿援圆摇 改进算法在机器人避障碍中的应用 为了进一步验证改进蚁群算法的可行性袁将所 提改进蚁群算法运用到机器人避障遥 为了便于蚁群 算法搜索到最优路径袁采用栅格法进行静态已知环 境建模袁同时选取了数量更多尧分布更为复杂的障碍 物咱员缘暂 遥 设机器人的工作空间为二维平面上的有限 区域 粤杂袁起始点 月 和目标点 耘遥 文中路径规划的优 化准则为路径最短袁即寻找一条从 月 到 耘 避开障碍 物的最短路径咱员远暂 遥 工作空间 粤杂 由圆园园 个员 伊 员 大小 的方格组成袁粤杂 的规模为 员园 行 伊 员园 列遥 最短路径 问题的目标函数可表示为式渊员员冤 院 蕴 越 移 灶 蚤 越 圆 曾蚤 原 曾蚤原员 ( ) 圆 垣 赠蚤 原 赠蚤原员 ( ) 圆 渊员员冤 式中院渊 曾蚤 袁 赠蚤 冤 为路径点坐标袁灶 为路径点数目袁蕴 为路径长度咱员苑暂 遥 按从左到右﹑从上到下的顺序对 栅格进行编号渊员 耀 员园园冤 袁同时设机器人工作空间由 酝 行 晕 列栅格组成袁其中每个栅格是边长为 员 的正 方形小格袁将障碍物地图用一个二维数组矩阵 皂葬责 渊酝袁晕冤表示为咱员愿暂 院 皂葬责( ) 责袁择 越 员袁第 责 行第 择 列栅格上有障碍 {园袁其他 摇 摇 渊员圆冤 摇 摇 实验方法是将改进算法和传统蚁群算法分别在 上述所构造的环境中进行移动机器人路径规划渊其 中每一栅格都为 员伊员 正方形袁且大小相等袁起始栅 格和目标栅格是预先指定的冤 遥 文中所做的仿真实 验是在 酝粤栽蕴粤月 数值分析工具下进行的遥 仿真实验 圆摇 实验环境为 员园伊员园 栅格环境袁设 定出发点的栅格序号为 员袁目标点的栅格序号为 员园园 渊栅格对应的序号是从左上角开始袁从左到右袁从上 到下依次为 员 耀 员园园冤 袁具体实验结果如图 缘耀怨 所示遥 图 缘摇 基于改进蚁群算法的机器人各代避障路线 云蚤早援缘摇 栽澡藻 燥遭泽贼葬糟造藻 葬增燥蚤凿葬灶糟藻 责葬贼澡 燥枣 增葬则蚤燥怎泽 早藻灶藻则葬贼蚤燥灶 则燥鄄 遭燥贼 遭葬泽藻凿 燥灶 贼澡藻 蚤皂责则燥增藻凿 葬造早燥则蚤贼澡皂 图 远摇 收敛曲线渊基于改进蚁群算法冤 云蚤早援远摇 悦燥灶增藻则早藻灶糟藻 糟怎则增藻 渊遭葬泽藻凿 燥灶 贼澡藻 蚤皂责则燥增藻凿 葬造早燥则蚤贼澡皂冤 图 苑摇 基于传统群算法的机器人各代避障路线 云蚤早援苑摇 栽澡藻 燥遭泽贼葬糟造藻 葬增燥蚤凿葬灶糟藻 责葬贼澡 燥枣 增葬则蚤燥怎泽 早藻灶藻则葬鄄 贼蚤燥灶 则燥遭燥贼 遭葬泽藻凿 燥灶 贼澡藻 早藻灶藻则葬造 葬造早燥则蚤贼澡皂 窑怨源窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 员园 卷
第1期 裴振兵，等：改进蚁群算法及其在机器人避障中的应用 ·95· 18.5 优，提出了动态自适应调整α、B策略：其次针对蚁 群算法在面对凹形障碍物易陷入死锁，提出了广义 18.0 信息素更新规则。通过仿真实验将改进蚁群算法与 17.5 一般蚁群算法进行对比分析，仿真结果显示，该改进 17.0 算法在一定程度上提高了搜索速度，有效地弥补了 16.5 传统蚁群算法容易陷入局部最优的劣势[)。最后 16. 将改进蚁群算法应用到机器人避障，并取得了较好 实验效果，仿真结果进一步验证了改进算法的可行 15.5 0 50 100 150 性及在凹形障碍物中成功摆脱陷阱寻找最优路径的 代次数次 高效性。不足之处：该仿真的障碍物环境为静态已 图8传统蚊群算法收敛曲线 知环境，如果为动态未知环境，则机器人不一定能成 Fig.8 Convergence curve based on the general algorithm 功摆脱凹形障碍物[20]。这也是以后需要进一步改 10 进和研究的地方。如果将该改进算法应用到其他领 域，如无人驾驶车辆中进行起，点和终点已知情况下 的最短路径无碰撞行驶，也是具有指导意义的。 参考文献： [1]COLORNI A,DORIGO M,MANIEZZO V.Distributed opti- mization by ant colonies[C]//Processings of the Ist Euro- pean Conference on Artificial Life.Paris,France,1991: 134-142 345678 9 10 [2]徐利超，张世武.基于改进蚁群算法的障碍环境下路径 图9机器人避障最优路线 规划研究[刀.机械与电子，2013(7)：61-64 Fig.9 Robot obstacle avoidance optimal route XU Lichao,ZHANG Shiwu.Study of path planning in obsta- 图5、6为改进蚁群算法经过150次迭代后所得到的 cle environment based on an improved ant algorithm[J] 机器人各代避障路线及对应的最终收敛曲线：图7 Machinery Electronics,2013.(7):61-64. 8为传统蚁群算法经过150次迭代后所得到的机器 [3]朱绍伟，徐夫田，腾兆明.一种改进蚁群算法求解最短路 人各代避障路线及对应的最终收敛曲线：图9为基 径的应用[J].计算机技术与发展，2011(7)：202-205. 于改进蚁群算法得到的机器人避障碍最优路线；通 ZHU Shaowei,XU Futian,TENG Zhaoming.Application of 过上述仿真结果可以得出如下结论： improvement ants algorithm in solving shortest path[J]. 1)由图5、7对比分析，可以得出基于改进蚁群 Computer Technology and Development,2011,21(7):202- 算法的各代机器人在面对凹形障碍物时有更多的选 205. 择避开凹形障碍物的安全路径，保障了整个群体的 [4]柳长安，鄢小虎，刘春阳，等.基于改进蚁群算法的移动 性能：而基于传统蚁群算法的各代机器人，在面对凹 机器人动态路径规划方法[J刀.电子学报，2011,39(5)： 形障碍物时更易陷入其中并进入“死锁”，减少了群 1220-1224. 体中有效个体的数量，从而影响整个群体性能。 LIU Changan,YAN Xiaohu,LIU Chunyang,et al.Dynamic 2)由图6、8对比分析可知，基于改进蚁群算法 path planning for mobile robot based on improoved ant colo- 的机器人在凹形障碍物的环境中经过40多次迭代 ny optimization algorithm[J].Acta Electronica Sinica, 就收敛到最优路径：而基于传统蚁群算法的机器人 2011,39(5):1220-1224. 则要经过80多次迭代才能收敛到最优路径，显然改 [5]段海滨.蚁群算法原理及其应用[M].北京：科学出版 进蚁群算法的收敛速度明显优于传统蚁群算法。 社.2005：176-181. 3)图9的仿真结果进一步验证了改进算法的 [6]GUTJAHR W J.A graph-based ant system and its conver- 可行性及在凹形障碍物中寻优的高效性。 gence [J].Future Generation Computer Systems,2000.16 (8):873-888. 4结束语 [7]周明秀，程科，王正霞.动态路径规划中的改进蚁群算法 在原有蚁群算法的基础上，首先针对蚁群算法 [J].计算机科学，2012,40(1)：314-316. 在构造解的过程中收敛速度慢且容易陷入局部最 ZHOU Mingxiu,CHENG Ke,WANG Zhengxia.Improved ant colony algorithm with planning of dynamic path[J]
图 愿摇 传统蚁群算法收敛曲线 云蚤早援愿摇 悦燥灶增藻则早藻灶糟藻 糟怎则增藻 遭葬泽藻凿 燥灶 贼澡藻 早藻灶藻则葬造 葬造早燥则蚤贼澡皂 图 怨摇 机器人避障最优路线 云蚤早援怨摇 砸燥遭燥贼 燥遭泽贼葬糟造藻 葬增燥蚤凿葬灶糟藻 燥责贼蚤皂葬造 则燥怎贼藻 图 缘尧远 为改进蚁群算法经过 员缘园 次迭代后所得到的 机器人各代避障路线及对应的最终收敛曲线曰图 苑尧 愿 为传统蚁群算法经过 员缘园 次迭代后所得到的机器 人各代避障路线及对应的最终收敛曲线曰图 怨 为基 于改进蚁群算法得到的机器人避障碍最优路线曰通 过上述仿真结果可以得出如下结论院 员冤 由图 缘尧苑 对比分析袁可以得出基于改进蚁群 算法的各代机器人在面对凹形障碍物时有更多的选 择避开凹形障碍物的安全路径袁保障了整个群体的 性能曰而基于传统蚁群算法的各代机器人袁在面对凹 形障碍物时更易陷入其中并进入野死锁冶 袁减少了群 体中有效个体的数量袁从而影响整个群体性能遥 圆冤 由图 远尧愿 对比分析可知袁基于改进蚁群算法 的机器人在凹形障碍物的环境中经过 源园 多次迭代 就收敛到最优路径曰而基于传统蚁群算法的机器人 则要经过 愿园 多次迭代才能收敛到最优路径袁显然改 进蚁群算法的收敛速度明显优于传统蚁群算法遥 猿冤 图 怨 的仿真结果进一步验证了改进算法的 可行性及在凹形障碍物中寻优的高效性遥 源摇 结束语 在原有蚁群算法的基础上袁首先针对蚁群算法 在构造解的过程中收敛速度慢且容易陷入局部最 优袁提出了动态自适应调整 琢尧茁 策略曰其次针对蚁 群算法在面对凹形障碍物易陷入死锁袁提出了广义 信息素更新规则遥 通过仿真实验将改进蚁群算法与 一般蚁群算法进行对比分析袁仿真结果显示袁该改进 算法在一定程度上提高了搜索速度袁有效地弥补了 传统蚁群算法容易陷入局部最优的劣势咱员怨暂 遥 最后 将改进蚁群算法应用到机器人避障袁并取得了较好 实验效果袁仿真结果进一步验证了改进算法的可行 性及在凹形障碍物中成功摆脱陷阱寻找最优路径的 高效性遥 不足之处院该仿真的障碍物环境为静态已 知环境袁如果为动态未知环境袁则机器人不一定能成 功摆脱凹形障碍物咱圆园暂 遥 这也是以后需要进一步改 进和研究的地方遥 如果将该改进算法应用到其他领 域袁如无人驾驶车辆中进行起点和终点已知情况下 的最短路径无碰撞行驶袁也是具有指导意义的遥 参考文献院 咱 员暂悦韵蕴韵砸晕陨 粤袁 阅韵砸陨郧韵 酝袁 酝粤晕陨耘在在韵 灾援 阅蚤泽贼则蚤遭怎贼藻凿 燥责贼蚤鄄 皂蚤扎葬贼蚤燥灶 遭赠 葬灶贼 糟燥造燥灶蚤藻泽咱悦暂 辕 辕 孕则燥糟藻泽泽蚤灶早泽 燥枣 贼澡藻 员泽贼 耘怎则燥鄄 责藻葬灶 悦燥灶枣藻则藻灶糟藻 燥灶 粤则贼蚤枣蚤糟蚤葬造 蕴蚤枣藻援 孕葬则蚤泽袁 云则葬灶糟藻袁 员怨怨员院 员猿源鄄员源圆援 咱圆暂徐利超袁 张世武援 基于改进蚁群算法的障碍环境下路径 规划研究咱允暂援机械与电子袁 圆园员猿 渊苑冤 院 远员鄄远源援 载哉 蕴蚤糟澡葬燥袁 在匀粤晕郧 杂澡蚤憎怎援 杂贼怎凿赠 燥枣 责葬贼澡 责造葬灶灶蚤灶早 蚤灶 燥遭泽贼葬鄄 糟造藻 藻灶增蚤则燥灶皂藻灶贼 遭葬泽藻凿 燥灶 葬灶 蚤皂责则燥增藻凿 葬灶贼 葬造早燥则蚤贼澡皂 咱 允 暂援 酝葬糟澡蚤灶藻则赠 驭 耘造藻糟贼则燥灶蚤糟泽袁 圆园员猿袁渊苑冤 院 远员鄄远源援 咱猿暂朱绍伟袁徐夫田袁腾兆明援一种改进蚁群算法求解最短路 径的应用咱允暂援计算机技术与发展袁 圆园员员渊苑冤 院 圆园圆鄄圆园缘援 在匀哉 杂澡葬燥憎藻蚤袁 载哉 云怎贼蚤葬灶袁 栽耘晕郧 在澡葬燥皂蚤灶早援 粤责责造蚤糟葬贼蚤燥灶 燥枣 蚤皂责则燥增藻皂藻灶贼 葬灶贼泽 葬造早燥则蚤贼澡皂 蚤灶 泽燥造增蚤灶早 泽澡燥则贼藻泽贼 责葬贼澡 咱 允 暂援 悦燥皂责怎贼藻则 栽藻糟澡灶燥造燥早赠 葬灶凿 阅藻增藻造燥责皂藻灶贼袁圆园员员袁 圆员渊苑冤 院 圆园圆鄄 圆园缘援 咱源暂柳长安袁 鄢小虎袁 刘春阳袁等援 基于改进蚁群算法的移动 机器人动态路径规划方法咱允暂援 电子学报袁 圆园员员袁 猿怨渊缘冤 院 员圆圆园鄄员圆圆源援 蕴陨哉 悦澡葬灶早葬灶袁 再粤晕 载蚤葬燥澡怎袁 蕴陨哉 悦澡怎灶赠葬灶早袁 藻贼 葬造援 阅赠灶葬皂蚤糟 责葬贼澡 责造葬灶灶蚤灶早 枣燥则 皂燥遭蚤造藻 则燥遭燥贼 遭葬泽藻凿 燥灶 蚤皂责则燥燥增藻凿 葬灶贼 糟燥造燥鄄 灶赠 燥责贼蚤皂蚤扎葬贼蚤燥灶 葬造早燥则蚤贼澡皂 咱 允 暂援 粤糟贼葬 耘造藻糟贼则燥灶蚤糟葬 杂蚤灶蚤糟葬袁 圆园员员袁 猿怨渊缘冤院 员圆圆园鄄员圆圆源援 咱缘暂段海滨援 蚁群算法原理及其应用咱酝暂援 北京院 科学出版 社袁 圆园园缘院 员苑远鄄员愿员援 咱远暂郧哉栽允粤匀砸 宰 允援 粤 早则葬责澡鄄遭葬泽藻凿 葬灶贼 泽赠泽贼藻皂 葬灶凿 蚤贼泽 糟燥灶增藻则鄄 早藻灶糟藻 咱 允暂援 云怎贼怎则藻 郧藻灶藻则葬贼蚤燥灶 悦燥皂责怎贼藻则 杂赠泽贼藻皂泽袁 圆园园园袁 员远 渊愿冤 院 愿苑猿鄄愿愿愿援 咱苑暂周明秀袁 程科袁 王正霞援动态路径规划中的改进蚁群算法 咱允暂援 计算机科学袁 圆园员圆袁 源园渊员冤 院 猿员源鄄猿员远援 在匀韵哉 酝蚤灶早曾蚤怎袁 悦匀耘晕郧 运藻袁 宰粤晕郧 在澡藻灶早曾蚤葬援 陨皂责则燥增藻凿 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂 憎蚤贼澡 责造葬灶灶蚤灶早 燥枣 凿赠灶葬皂蚤糟 责葬贼澡 咱 允 暂援 第 员 期摇摇摇摇摇摇摇摇摇摇摇摇摇摇 裴振兵袁等院改进蚁群算法及其在机器人避障中的应用 窑怨缘窑
·96· 智能系统学报 第10卷 Computer Science,2012,40(1):314-316. [15]YAO L M,DUAN H B,SHAO S.Adaptive template matc- [8]王越，叶秋冬.蚁群算法在求解最短路径问题上的改进 hing based on improved ant colony optimization[C]//Pro- 策略[J].计算机工程与应用，2012,48(13)：35-38. ceedings of International Workshop on Intelligence Systems WANG Yue,YE Qiudong.Improved strategies of ant colony and Applications.[s.I],2009:1-4. algorithm for solving shortest path problem[].Computer [16]BROOKS R A.Solving the find-path problem by good rep- Engineering and Applications,2012,48(13):35-38. resentation of free space [J].IEEE Trans on System Man [9]赵凯，李声晋，孙娟，等改进蚁群算法在移动机器人路 and Cybernetics,1983,13(3):190-197. 径规划中的研究[J刀.微型机与应用，2013,32(4)：67- [17]JANET JA.The essential visibility graph:an approach to 70. global motion planning for autonomous mobile robots[C] ZHAO Kai,LI Shengjin,SUN Juan,et al.Research of im- IEEE Intemational Conference on Robotics and Automa- proved ant colony algorithm in mobile robot path planning tiom.[s.1.],1995:1958-1963. [J].Microcomputer its Applications,2013,32(4):67- [18]EMILIO F.Real-time motion planning for agile autonomous 70. vehicles [J].Journal of Guidance,Control and Dynamics, [10]温如春，汤青波，杨国亮.基于改进蚁群算法的移动机 2002.25(1):116-129. 器人路径规划[J].兵工自动化，2010,29(8)：69.70. [19]BONABEAU E,DORIGO M,Theraulaz G.Inspiration for WEN Ruchun,TANG Qingbo,YANG Guoliang.Mobile optimization from social insect behavior [J].Nature, robot's path planning based on improved ant colony algo- 2000,406(6):39-42. rithm[J].Ordance Industry Automation,2010,29(8): [20]DORIGO M.DI CARO G.GAMBARDELLA L M.Ant al- 69-70. gorithms for discrete optimization [J].Artificial Life, [11]张颖，陈雪波.广义蚁群算法及其在机器人队形变换中 1999,5(2):137-172 的应用[J].模式识别与人工智能，2007,19,20(3)： 作者简介： 3-8 裴振兵，男，1989年生，硕士研究 ZHANG Ying,CHEN Xuebo.General ant colony algorithm 生，主要研究方向为智能优化及机器人 and its applications in robot formation[].Pattern Recog- 路径规划。 nition and Aitificial Intelligence,2007,19,20(3):3-8. [12]JACKSON D E,HOLCOMBE M,RATNIEKS F L W Trail geometry gives polarity to ant foraging networks[]. Nature,2004,432(7019):907-909. [13]贾振华，斯庆巴拉，王慧娟.基于启发式机器人路径规 陈雪波，男，1960年生，教授，博士 划仿真研究[J].计算机仿真，2012,29(1)：135-138. 生导师，中国自动化学会过程控制专业 JIA Zhenhua,SIQING Bala,WANG Huijuan.Path plan- 委员会委员。主要研究方向为复杂系 ning based on heuristic algorithm[J].Computer Simula- 统、群集智能等。主持多项国家及省部 tion,2012,29(1):135-138. 级科研基金项目，出版专著1部。 [14]AI-TAHARWA I.SHETA A,AI-WESHAN M.A mobile robot path planning using genetic algorithm in static envi- ronment [J].Journal of Computer Sciences,2008,4(4): 341-344
悦燥皂责怎贼藻则 杂糟蚤藻灶糟藻袁 圆园员圆袁 源园渊员冤 院 猿员源鄄猿员远援 咱愿暂王越袁 叶秋冬援 蚁群算法在求解最短路径问题上的改进 策略咱允暂援 计算机工程与应用袁 圆园员圆袁 源愿渊员猿冤 院 猿缘鄄猿愿援 宰粤晕郧 再怎藻袁 再耘 匝蚤怎凿燥灶早援 陨皂责则燥增藻凿 泽贼则葬贼藻早蚤藻泽 燥枣 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂 枣燥则 泽燥造增蚤灶早 泽澡燥则贼藻泽贼 责葬贼澡 责则燥遭造藻皂 咱 允 暂援 悦燥皂责怎贼藻则 耘灶早蚤灶藻藻则蚤灶早 葬灶凿 粤责责造蚤糟葬贼蚤燥灶泽袁 圆园员圆袁 源愿渊员猿冤院猿缘鄄猿愿援 咱怨暂赵凯袁 李声晋袁 孙娟袁 等援改进蚁群算法在移动机器人路 径规划中的研究咱允暂援 微型机与应用袁 圆园员猿袁 猿圆渊 源冤 院 远苑鄄 苑园援 在匀粤韵 运葬蚤袁 蕴陨 杂澡藻灶早躁蚤灶袁 杂哉晕 允怎葬灶袁 藻贼 葬造援 砸藻泽藻葬则糟澡 燥枣 蚤皂鄄 责则燥增藻凿 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂 蚤灶 皂燥遭蚤造藻 则燥遭燥贼 责葬贼澡 责造葬灶灶蚤灶早 咱 允暂援 酝蚤糟则燥糟燥皂责怎贼藻则 驭 蚤贼泽 粤责责造蚤糟葬贼蚤燥灶泽袁 圆园员猿袁 猿圆渊源冤 院 远苑鄄 苑园援 咱员园暂温如春袁 汤青波袁 杨国亮援 基于改进蚁群算法的移动机 器人路径规划咱允暂援 兵工自动化袁 圆园员园袁 圆怨渊愿冤 院 远怨鄄苑园援 宰耘晕 砸怎糟澡怎灶袁 栽粤晕郧 匝蚤灶早遭燥袁 再粤晕郧 郧怎燥造蚤葬灶早援 酝燥遭蚤造藻 则燥遭燥贼爷 泽 责葬贼澡 责造葬灶灶蚤灶早 遭葬泽藻凿 燥灶 蚤皂责则燥增藻凿 葬灶贼 糟燥造燥灶赠 葬造早燥鄄 则蚤贼澡皂咱 允暂援 韵则凿葬灶糟藻 陨灶凿怎泽贼则赠 粤怎贼燥皂葬贼蚤燥灶袁 圆园员园袁 圆怨 渊 愿冤 院 远怨鄄苑园援 咱员员暂张颖袁 陈雪波援 广义蚁群算法及其在机器人队形变换中 的应用咱允暂援 模式识别与人工智能袁 圆园园苑袁 员怨袁 圆园渊 猿冤 院 猿鄄愿援 在匀粤晕郧 再蚤灶早袁 悦匀耘晕 载怎藻遭燥援 郧藻灶藻则葬造 葬灶贼 糟燥造燥灶赠 葬造早燥则蚤贼澡皂 葬灶凿 蚤贼泽 葬责责造蚤糟葬贼蚤燥灶泽 蚤灶 则燥遭燥贼 枣燥则皂葬贼蚤燥灶咱 允暂援 孕葬贼贼藻则灶 砸藻糟燥早鄄 灶蚤贼蚤燥灶 葬灶凿 粤蚤贼蚤枣蚤糟蚤葬造 陨灶贼藻造造蚤早藻灶糟藻袁 圆园园苑袁 员怨袁 圆园渊猿冤 院 猿鄄愿援 咱 员圆 暂 允粤悦运杂韵晕 阅 耘袁 匀韵蕴悦韵酝月耘 酝袁 砸粤栽晕陨耘运杂 云 蕴 宰援 栽则葬蚤造 早藻燥皂藻贼则赠 早蚤增藻泽 责燥造葬则蚤贼赠 贼燥 葬灶贼 枣燥则葬早蚤灶早 灶藻贼憎燥则噪泽 咱 允暂援 晕葬贼怎则藻袁 圆园园源袁 源猿圆渊苑园员怨冤 院怨园苑鄄怨园怨援 咱员猿暂贾振华袁 斯庆巴拉袁 王慧娟援 基于启发式机器人路径规 划仿真研究咱允暂援 计算机仿真袁 圆园员圆袁 圆怨渊员冤 院 员猿缘鄄员猿愿援 允陨粤 在澡藻灶澡怎葬袁 杂陨匝陨晕郧 月葬造葬袁 宰粤晕郧 匀怎蚤躁怎葬灶援 孕葬贼澡 责造葬灶鄄 灶蚤灶早 遭葬泽藻凿 燥灶 澡藻怎则蚤泽贼蚤糟 葬造早燥则蚤贼澡皂 咱 允暂援 悦燥皂责怎贼藻则 杂蚤皂怎造葬鄄 贼蚤燥灶袁 圆园员圆袁 圆怨渊员冤 院 员猿缘鄄员猿愿援 咱员源暂 粤陨鄄栽粤匀粤砸宰粤 陨袁 杂匀耘栽粤 粤袁 粤陨鄄宰耘杂匀粤晕 酝援 粤 皂燥遭蚤造藻 则燥遭燥贼 责葬贼澡 责造葬灶灶蚤灶早 怎泽蚤灶早 早藻灶藻贼蚤糟 葬造早燥则蚤贼澡皂 蚤灶 泽贼葬贼蚤糟 藻灶增蚤鄄 则燥灶皂藻灶贼 咱 允暂援 允燥怎则灶葬造 燥枣 悦燥皂责怎贼藻则 杂糟蚤藻灶糟藻泽袁 圆园园愿袁 源渊源冤 院 猿源员鄄猿源源援 咱 员缘暂再粤韵 蕴 酝袁 阅哉粤晕 匀 月袁 杂匀粤韵 杂援 粤凿葬责贼蚤增藻 贼藻皂责造葬贼藻 皂葬贼糟鄄 澡蚤灶早 遭葬泽藻凿 燥灶 蚤皂责则燥增藻凿 葬灶贼 糟燥造燥灶赠 燥责贼蚤皂蚤扎葬贼蚤燥灶咱 悦暂 辕 辕 孕则燥鄄 糟藻藻凿蚤灶早泽 燥枣 陨灶贼藻则灶葬贼蚤燥灶葬造 宰燥则噪泽澡燥责 燥灶 陨灶贼藻造造蚤早藻灶糟藻 杂赠泽贼藻皂泽 葬灶凿 粤责责造蚤糟葬贼蚤燥灶泽援 咱 泽援造援暂 袁 圆园园怨院员鄄源援 咱员远暂月砸韵韵运杂 砸 粤援 杂燥造增蚤灶早 贼澡藻 枣蚤灶凿鄄责葬贼澡 责则燥遭造藻皂 遭赠 早燥燥凿 则藻责鄄 则藻泽藻灶贼葬贼蚤燥灶 燥枣 枣则藻藻 泽责葬糟藻 咱 允暂援 陨耘耘耘 栽则葬灶泽 燥灶 杂赠泽贼藻皂 酝葬灶 葬灶凿 悦赠遭藻则灶藻贼蚤糟泽袁 员怨愿猿袁 员猿渊猿冤 院 员怨园鄄员怨苑援 咱员苑暂 允粤晕耘栽 允 粤援 栽澡藻 藻泽泽藻灶贼蚤葬造 增蚤泽蚤遭蚤造蚤贼赠 早则葬责澡院 葬灶 葬责责则燥葬糟澡 贼燥 早造燥遭葬造 皂燥贼蚤燥灶 责造葬灶灶蚤灶早 枣燥则 葬怎贼燥灶燥皂燥怎泽 皂燥遭蚤造藻 则燥遭燥贼泽咱悦暂 辕 辕 陨耘耘耘 陨灶贼藻则灶葬贼蚤燥灶葬造 悦燥灶枣藻则藻灶糟藻 燥灶 砸燥遭燥贼蚤糟泽 葬灶凿 粤怎贼燥皂葬鄄 贼蚤燥灶援 咱 泽援造援暂 袁 员怨怨缘院 员怨缘愿鄄员怨远猿援 咱员愿暂耘酝陨蕴陨韵 云援 砸藻葬造鄄贼蚤皂藻 皂燥贼蚤燥灶 责造葬灶灶蚤灶早 枣燥则 葬早蚤造藻 葬怎贼燥灶燥皂燥怎泽 增藻澡蚤糟造藻泽 咱 允暂援 允燥怎则灶葬造 燥枣 郧怎蚤凿葬灶糟藻袁 悦燥灶贼则燥造 葬灶凿 阅赠灶葬皂蚤糟泽袁 圆园园圆袁 圆缘渊员冤 院员员远鄄员圆怨援 咱员怨暂月韵晕粤月耘粤哉 耘袁 阅韵砸陨郧韵 酝袁 栽澡藻则葬怎造葬扎 郧援 陨灶泽责蚤则葬贼蚤燥灶 枣燥则 燥责贼蚤皂蚤扎葬贼蚤燥灶 枣则燥皂 泽燥糟蚤葬造 蚤灶泽藻糟贼 遭藻澡葬增蚤燥则 咱 允 暂援 晕葬贼怎则藻袁 圆园园园袁 源园远渊远冤 院 猿怨鄄源圆援 咱圆园暂阅韵砸陨郧韵 酝袁 阅陨 悦粤砸韵 郧袁 郧粤酝月粤砸阅耘蕴蕴粤 蕴 酝援 粤灶贼 葬造鄄 早燥则蚤贼澡皂泽 枣燥则 凿蚤泽糟则藻贼藻 燥责贼蚤皂蚤扎葬贼蚤燥灶 咱 允 暂援 粤则贼蚤枣蚤糟蚤葬造 蕴蚤枣藻袁 员怨怨怨袁 缘渊圆冤 院 员猿苑鄄员苑圆援 作者简介院 裴振兵袁男袁 员怨愿怨 年生袁硕士研究 生袁主要研究方向为智能优化及机器人 路径规划遥 陈雪波袁男袁员怨远园 年生袁教授袁博士 生导师袁中国自动化学会过程控制专业 委员会委员遥 主要研究方向为复杂系 统尧群集智能等遥 主持多项国家及省部 级科研基金项目袁出版专著 员 部遥 窑怨远窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 员园 卷