基于遗传蚁群算法的机器人全局路径规划研究
第 25卷 第 6期
2004年 12月
哈 尔 滨 工 程 大 学 学 报
Journal of Harbin Engineering University
Vo1．25 No．6
Dec．2004
基于遗传蚁群算法的机器人全局路径规划研究
张汝波，郭必祥 ，熊 江
(哈 尔滨工程大学 计算机科学与技术学院，黑龙江 哈 尔滨 150001)
摘 要 ：蚁群算法是基于生物界群体启发行为的一种随机搜索寻优方法 ，它的正反馈性和协同性使其可用于分布式
系统，隐含的并行性更使其具有极强的发展潜力 ，它在解决组合优化问题上有着 良好的适应性。因此将其应用到智
能机器人全局路径规划中，其 目的是探索一种新的路径寻优算法．在基于栅格划分的环境中，研究了机器人路径规
划问题中蚁群系统的“外激素”表示及更新方式，并将遗传算法的交叉操作结合到蚁群系统的路径寻优过程中，提高
了蚁群系统的路径寻优能力 ，为蚁群算法的应用提供了一种新的探索．
关键词 ：蚁群算法；遗传算法 ；全局路径规划；机器人
中图分 类号 ：TP24 文献标识码 ：A 文章编号 ：1006—7043(2004l06—0724—04
Research on global path planning for robots
based on ant colony algorithm
ZHANG Ru—bo，GUO Bi—xiang，XIONG Jiang
(School of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China)
Abstract：An ant colony algorithm is a stochastic searching optimization algorithm that is based on the heuristic
behavior of the biologic colony．Its positive feedback and coordination make it possible to be applied to a distrib—
uted system．It has favorable adaptability in solving combinatorial optimization and has great development poten—
tial for its connotative parallel property．This study foc used on global path planning with all ant colony algorithm
in an environment based on grids，which explores a new path planning algorithm ．How to present and update
the pheromone of an ant system was investigated．The crossover ope ration of a genetic algorithm WaS used in the
ant system for path optimization．Experimental results show that the algorithm has be tter path plan ning optimi—
zation ability than other algorithm s．
Keywords：ant colony algorithm ；genetic arithm etic；global path planning；robot
全局路径规划技术是智能机器人领域 中的核心
问题之一，全局路径 规划是指在 已知环境信 息的情
况下 ，在有限条件下规划一条 由起点 到终 点的最 优
或较优路径 ．全局路径规划一般包括 环境建模 和搜
索策略 2个子问题 ．其 中环境建模的主要方法有 ：可
视图法(v—graph)、自由空间法(free space approach)
和栅格法(grids)等．现在通常使用的搜索技术包括 ：
梯度法 、A 等图搜索方法 、枚举法 、随机搜索法 ，等 ．
而这些方法中梯度法易陷入局部最小点 ，图搜索方
法 、枚举法不能用于高维 的优化问题 ，随机搜索法则
收稿 日期 ：2004—07—07．
基金项 目：国防科 学技术 工业委员会 基础研究基 金资助 项 目
(413160702)．
作者简介：张汝波(1963一)，男，教授，博士生导师．
计算效 率太 低 ，z]．由此 ，许 多 研究 者将 神 经 网络
(NN)、遗传算法 (GA)等仿生算法 用于机器人路径
规划 中，改进了传统算法 的性能 J．
人工蚁群算法是受到人们对 自然界 中真实蚁群
集体行为研究成果的启发而提 出的一种基于蚁群的
模拟进化算法 ．它在解决组 合优化问题上有着 良好
的适应 性 ，已被成 功地 应用 于 解 决如 TSP、Q 、
JSP等问题 J，．吸引了不少研究者进行相关研究 ．目
前的研究多集 中在解决 TSP问题 中怎样改进蚁 群
系统“信息素”的表示及更新方式来改善蚁群算法的
性能上 ]．这里在搜索栅格点的选择 中引入 了“外
激素”信息 ，用蚁群算法结合遗传算法的交叉操作搜
索路径 ，用最值蚂蚁 的思想更新“外激素”信息 ，解决
维普资讯 http://www.cqvip.com
第 6期 张汝波 ，等：基于遗传蚁群算法的机器人全局路径规划研究 ·725 ·
了机器人的全局路径规划问题 ．
1 环境划分
机器人的起点为 S，目标点为 G，S、G之 间存
在一些障碍物，如图 1所示．规划任务为搜索一条由
S点到 G点的路径长度最短 的无碰路径 ．其 目标 函
数可表示为
n
F=∑ 、／，( 一 一。) +( 一 一。) ．(1)
i=2
式中；Xi、Yi为路径点的坐标信息 ， 为路径 点的个
数．
图 1 机器人 的工 作环境
Fig．1 The working environment of robot
工作空间用 ( × )的栅格进行划分 ，用 0和 1
分别表示 自由栅格和障碍栅格 ，栅格点用序号表示 ，
按照从左 至右 ，从上到下的顺序依次编序 ．设工作空
间的长为 X 个单 位 ，宽 为 y 个单位 ，则序号 N 与
栅格 中心点坐标 (．7C， )之间的映射关 系为
= (Nmod，z)× + ，
H 厶 H
V V
int(N／n)×者+ · (2)
2 蚁群算法的实现
2．1 “信息素”的表示
“信息素”分布在每个栅格点到与其相邻栅格的
路径上 ，蚂蚁从 S点开始搜 索 ，蚂蚁 的每 一步搜索
范围是与其当前所 在栅格相邻 的 8个栅格 ，每一栅
格点 到其 相邻栅格点 ．
的“信息素”值依式 (3)进
行初始化 ．
I d， 若 ． 为可达栅格
10， 其他 (3)
式中 ：以为一常数 ， 为与 i相邻 的栅格 ，d 表示栅
格 到终点 G 的距离 ．定 义与 i相邻的左 、右 、上 、下
4个栅格 为直接相邻栅 格 ，左上 、左下 、右上 、右下 4
个栅格为间接相邻栅格 ，可达栅格 的判别规则如下 ：
1)若 di
2)若 ，
i相邻 的两个直接相邻栅格均为 自由栅格 ．
边界的搜索只须考虑与其相邻 的 3个栅格 ，这
样 ，就把蚂蚁每一步 的搜索点 限定在 了距终点较 近
的栅格上 ．
2．2 路径点的选择
蚂蚁在 t时刻处于 点时选择下一个可达栅格
的转移概率为
7 ．a r f、n
(￡) · (4)
‘ l】＼ 一 1
J
式 中：r (t)表示在 t时刻栅格 i到栅格
．
的路径上
残留的信息量；D，为距离信息，这里取为 Q／ ，，其
中 Q 为一常数 ， ，为栅格 到 G 点的距 离值 ；a为
信息素的相对重要程度 ； 为距 离信息 的相对重要
程度 ．
蚂蚁搜索路径点时 ，有可能进入这样 的栅格 ：它
到与之相邻 的栅格点 的信 息素值均为零 ，此时可加
一 个回馈信息，使蚂蚁回到上一次搜索的路径点 ，并
将此栅格置为障碍栅格 ．
2．3 “信息素”的更新
采取什么策略更新信息素是决定蚁群算法性能
的关键因素 ．一般地 ，要考虑两方 面的因素 ：一 是要
加强正反馈的效果，提高蚂蚁的搜索效率 ；二是采取
一 定措施 ，减小 陷入局部优化的可能性 ．该文提 出的
算法 中，用最值蚂蚁算 法的思想 ，在搜索初期 ，只用
周游最优蚂蚁 的路径信息来更新信息 素(周游最优
蚂蚁是蚁群在一次搜索 中搜索到 的最优路径)，随着
搜索次数的增多 ，逐步加 大全局最优蚂蚁路 径信息
的更新频率 (全局最优 蚂蚁 是蚁群在 已经 完成 的搜
索 中所得到的最优路径 )，直至到搜索后期只用 全局
最优 蚂蚁的路径信息更新信 息素 ．这样每 次搜索都
采用周游最优蚂蚁和全局最优蚂蚁的路径信息更新
信息素，而不是所有的蚂蚁的路径信息，加强了正反
馈的效果 ；同时周 游最优 蚂蚁路径信息 的更新也在
一 定程度上增加 了解 的多样性 ，减小 了陷入局部优
化 的可能性 ．算法 中依据式 (5)和 (6)对 各路径上 的
信息素做 出调整．
(t+1)= IDr (t)+Ar ， (5)
d=(1_lD)×( + )× ．(6)
维普资讯 http://www.cqvip.com
· 726 · 哈 尔 滨 工 程 大 学 学 报 第 25卷
式中：ID(0≤lD<1)来表示信息素物质的持久性 ；l—
lD表示信息素物质 的消逝程 度 ；L 为周 游最优蚂蚁
的路径长度 ；L 为全局最 优蚂蚁 的路径 长度 ；a 、
b 为整型变量 ，分别代表用周游最优蚂蚁和全局最
优蚂蚁更新信息素的权重，其和为一常数 (口 的值
随着搜索次数的增加而逐步减小 ，b 的值随着搜索
次数 的增加而逐步增大)．
2．4 交叉算子的加入
考虑到蚁群系统在更新信息素时只是用到周游
最优蚂蚁或者全局最 优蚂蚁 的路 径信息 ，若随机选
择的两只蚂蚁不包含周 游最优蚂蚁 ，则对一次搜索
的贡献不大 ，在仿真实验 中也证 明了这一点 ．该算法
中，交叉在一次搜索后得 到的周游最优蚂蚁与随机
选择的另外一只蚂蚁之 间进行 ，若两 只蚂蚁经过 了
相同的栅格点 ，则 随机地选择一个相 同的栅格点进
行交叉(不包括起点和终点 )；若两 只蚂蚁没有 经过
相 同的栅格点 ，则不进行交叉操作 ．若在交叉后得到
了优于周游最优路径 的新路 径 ，则更新周 游最优蚂
蚁的路径信息 ，否则进行下一次交叉操作 ．交叉算子
的加入提高了蚂蚁在一次搜索 中搜索到更好 的路径
的能力 ，同时也增加了解 的多样性 ．
3 算法描述
该算法的主要步骤 ：
1)令时 间 t和循环次数 N 为 0，设置蚂蚁数
量 AntNumber和最大循环 次数 N ，初始 化环境
信息，按式(3)初始化各个栅格点上的信息素，并将
所有蚂蚁都置于起点 S．
2)启动蚁群 ，按 式 (4)计算 的概率用轮盘法 随
机选择下一个路径点 ，若此栅格到 其相邻栅格 的路
径上的信息素值均为 0，则回馈到上一个搜索的路
径点 ，并将 其置为障碍栅格 ．
3)重复 2)，直到蚁群到达终点 G．
4)对蚁群搜索到的路径进行交叉运算 ，记录周
游最优蚂蚁 和全局最优蚂蚁 的路径信息 ．
5)令 t=t+l；Nc=N +l，根 据式 (5)和式
(6)更新各条路径上 的信息素 ．
6)若蚁群全部收敛 到一条路径 或达到最大循
环次数 ，则循环结束 ，输 出最佳路径 ，否则 到 2)．
4 仿真实验结果
对提出的算 法在 PC机 上用 V ．0进 行 了仿
真实验 ．采 用 的参数 为 a=l， =2，lD=0．5，Q=
100，N =50，交叉概率 P =0．8．取 蚂蚁数量 为
100．图 2和 3分别 为在两种不同环境 中算法规划出
的路径 ．表 l对采用基本蚁群算法 、最值蚂蚁算法和
文中提 出算法 的 l0次规划结果进行 了比较 ．最优值
为 3种算法在两种不同环境 中 l0次规划结果所得
到的最短路径长度 ，平均值为 l0次规划结果所得到
路径长度 的平均值 ．实验表 明，该算法要优于基本蚁
群算法和最值蚂蚁算法 ．尤其是在路径 比较 分散的
情况下 ，在全局更新 的作用下 ，基本蚁群算法和最值
蚂蚁算法更容易陷入局部最 优化 ，而本 文算法引入
交叉操作 ，能够很好地 降低搜索 陷入 局部最优化 的
可能性 ．
图2 环境 1的规划路径
Fig．2 The planning path in environment 1
图 3 环境 2的规划路径
Fig．3 The planning path in environment 2
表 1 3种算 法的 比较 结果
Table 1 The comparison results of three algoritlum
维普资讯 http://www.cqvip.com
第 6期 张汝波，等：基于遗传蚁群算法的机器人全局路径规划研究 ·727 ·
5 结束语
蚂蚁算法是基于生物界群体启发行为的一种随
机搜索寻优方法 ，它的正反馈性 和协 同性使其可用
于分布式系统 ，隐含 的并行性更使其具有极 强的发
展潜力 ，现已经陆续应用到组合优化 、通讯等多个领
域 ，在机器人路径 规划 及群体协作方 面也 已陆续有
一 些应用 ．在“信息素”更新和挥发的作用下 ，蚁群算
法及最值蚁群算法在搜索初期得到的最优蚂蚁对搜
索路径的影响很大 ，而初期得到 的路径往往 不是最
优的 ，这样就易使搜索过于集 中而导致算法停滞 ．该
文将遗传算法与蚁群算 法结 合进行路径寻优 ，围绕
搜索得到的全局最优蚂蚁和周游最优蚂蚁与整个蚁
群进行交叉操作 ，并用交叉后得 到的最优蚂蚁路径
信息更新“信息素”，从而加强了正反馈 的效果 ，增加
了解 的多样性 ，降低了蚁群算法 陷入局部极小 的可
能性 ，加快了收敛速度 ，同时该算法也有利于并行执
行和应用 ，仿真实验验证 了所提 出算法 的有效性 ．
尽管蚂蚁算法有很 多优势 ，但 它还不像其他 的
启发式算法那样已形成系统的分析方法和具有坚实
的数学基础．参数的选择更多的是依靠实验和经验 ，
没有定理来确定．故而算法在理论 和实践方面 尚有
许 多问题需要更深入 的研究与解决 ．
参考文献 ：
[1]张 颖，吴成东，原宝龙．机器人路径规划方法综述[J]．
控制 工程 ，2003，10(增 刊)：152—155．
ZItANG Ying，W U Chengdong，YUAN Ba~ong．Progress
on path planning research for robot[J]．Control Engineering
of China，2003，10(supplement)：152—155．
[2]王醒策，张汝波，顾国昌．基于势场栅格法的机器人全局
路径规划[J]．哈尔滨工程大学学报 ，2003，4：170—174．
W ANG Xing ce．ZHANG Rubo．GU Guochang．Potential
gnd based global path plarming for robots[J]．Journal of
Harbin Engineering University，2003，4：170—174．
[3]刘玉明．基于遗传算法的智能水下机器人全局路径规划
的研究 [D]．哈尔滨 ：哈尔滨 工程大学船舶 工程学 院，
2002．
LIU Yuming．Research on global path planning for AUV
based on genetic algorithm[D]．Harbin：Harbin Engineering
University，2002．
[4 J MARTIN M，FRANK R，HARTMUT S．Multi colony
antalgorithms[J]．Journal of Heuristics，2002，8：305—
320．
[5]DAN IEL M ，MARTIN M．Ant colony optimization with
global pheromone evaluation for scheduling a sing le machine
[J J．Applied Intelligence，2003，18：105—111．
[6]蒋建国，骆正虎．基 于改进型蚁群算法求解旅行 Agent
问题[J]．模式识别与人工智能 ，2003，3：6—11．
JtANG Jianguo，LUO Zhenghu．Solution to traveling agent
problem based on improved ant colony algorithm [J]．
PR&AI，2003，18：105—111．
[7]李天成，罗 键．应用智能蚂蚁算法解决旅行商 问题
[D]．厦门：厦门大学 自动化系 ，2003．
LI Tiancheng ，LUO Jian ．An intelligent ant system for solv—
ing [D]．Xiamen：Dept of Automation，Xiamen Univer—
sity，2003．
[8]吴庆洪，张纪会 ，徐心和．具有变异特征的蚁群算法 [J]．
计算机研 究与发展 ，1999，35(10)：240—245．
WU Qing hong。ZHANG Jihui．XU Xinhe．An ant colony al—
gorithm with mutation featur~[J]．Joun~ 0{Computer Re—
search& Development，1999，35(10)：240—245．
[9]周 勇，陈洪亮．蚁群算法 的研究现状与展望[J]．微型
电脑应用 。2002，2：5—7．
ZHOU Yong ，CHEN Hong—liang．Research an d expectation
of ant colony system algorithm[J]．Microcomputer Applica—
tion，2002，2：5—7．
[责任编辑 ：陈 峰]
(上接第 713页)
[4]PETTERSEN K Y ，NIJMEIJER H．Tracking control of
art underactuated surface vessel[A]．in Proc 37th IEEE
Conference on Decision and Control[C]．Tampa，Fl da，
USA ．1998．
[5]FlIESS M，LEVINE J．Flatness and defect of nonlinear
systems：Introductory theory and examples[J]．Interna—
tional Journal of Co ntrol。1995，61：1327—1361．
[6]MICHIEL J．NIEUWSTADT V，MU RAY R M，et aI_
Real time trajectory generation for differentially flat systems
lJ J．International Journal Robust& Nonlinear Co ntro1．
1998，8(11)：995—1020．
[7]MICHIEL J，NIEUWSTADT V，MU RAY R M ，et a1．
Differential flatness and absolute equivalence of nonlinear
control systerns[J]．SIAM Journal on Control and Optimi—
zation，1998，36(4)：1225—1239．
[8]ERJEN L，PE．rTER EN K Y，NIJMEIJER H．Tracking
control of art underactuated ship[J]．IEEE transactions on
control systems technology，2003，11(1)：52—61．
[9]REYt-IANOGLU M．Exponential stabilization of an under—
actuated autonomous surface vessel[J]．Automa tic，1997，
33(12)：2249—2254．
[责任编辑 ：郑可为]
维普资讯 http://www.cqvip.com
基于遗传蚁群算法的机器人全局路径规划研究.pdf
