一种蚂蚁粒子群融合的机器人路径规划新算法

admin管理员组

文章数量:1533913

2024年3月11日发(作者：)

维普资讯

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｔｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

◎学术探讨◎　

一

种蚂蚁粒子群融合的机器人路径规划新算法　

国海涛，朱庆保，司应涛　

ＧＵＯ　Ｈａｉ—ｔａｏ，ＺＨＵ　Ｑｉｎｇ—ｂａｏ，ＳＩ　Ｙｉｎｇ－ｔａｏ　

南京师范大学数学与计算机科学学院，南京２　１００９７　

Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｎａｎｊｉｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ　２　１　００９７，Ｃｈｉｎａ　

Ｅ—ｍａｉｌ：ｇｕｏｈａｉｔａｏ２００５＠１６３．ｃｏｍ　

ＧＵＯ　Ｈａｉ—ｔａｏ，ＺＨＵ　Ｑｉｎｇ—ｂａｏ，ＳＩ　Ｙｉｎｇ－ｔａｏ．Ｎｏｖｅｌ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｆｏｒ　ｒｏｂｏｔｓ　ｓｙｎｃｒｅｔｉｚｉｎｇ　ａｎｔ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　

ａｌｇｏｒｉｔｈｍ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（３１）：３９－４１．　

Ａｂｓｔｒａｃｔ：Ａｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　Ａｎｔ　Ａｌｇｏｒｉｔｈｍ（ＡＡ）ａｎｄ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｏｆ　ｔｈｅ　

ｒｏｂｏｔ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｆｉｒｓｔ　ｔｈｅ　ＭＡＫＬＩＮＫ　ｇｒａｐｈ　ｉｓ　ｂｕｉｌｔ　ｔｏ　ｄｅｓｃｒｉｂｅ　ｔｈｅ　ｗｏｒｋｉｎｇ　ｓｐａｃｅ　ｏｆ　ｔｈｅ　ｍｏｂｉｌｅ　ｒｏｂｏｔ，ｔｈｅｎ　ｔｈｅ　ａｎｔ　ａｌｇｏｒｉｔｈｍ　ｉｓ　

ｕｓｅｄ　ｔｏ　ｏｂｔａｉｎ　ｔｈｅ　ｇｌｏｂａｌ　ｎａｖｉｇａｔｉｏｎ　ｐａｔｈ，ａｎｄ　ｔｈｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｒｆｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｄｏｐｔｅｄ　ｔｏ　ｇｅｔ　ｔｈｅ　ｂｅｔｔｅｒ　ｐａｔｈ、　

Ｃｏｍｐｕｔｅｒ　ｅｘｐｅｒｉｍｅｎｔ　ｒｅｓｕｌｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈａｔ　ｔｈｉｓ　ｎｏｘ　ｅｌ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｐｌａｎ　ａｎ　ｏｐｔｉｍａｌ　ｐａｔｈ　ｒａｐｉｄｌｙ　ｉｎ　ａ　ｃｌｕｔｔｅｒｅｄ　ｅｎｖｉｒｏｎｍｅｎｔ．　

Ｔｈｅ　ｓｕｃｃｅｓｓｆｕｌ　ｏｂｓｔａｃｌｅ　ａｖｏｉｄａｎｃｅ　ｉｓ　ａｃｈｉｅｖｅｄ，ａｎｄ　ｔｈｅ　ｍｏｄｅｌ　ｉｓ　ｒｏｂｕｓｔ　ａｎｄ　ｐｅｒｆｏｒｍｓ　ｒｅｌｉａｂｌｙ．　

Ｋｅｙ　ｗｏｒｄｓ：ｒｏｂｏｔ；ｐａｔｈ　ｐｌａｎｎｉｎｇ；ａｎｔ　ａｌｇｏｒｉｔｈｍ；ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ａｌｇｏｒｉｔｈｍ　

摘要：研究了一种全新的蚂蚁粒子群融合的机器人路径规划算法。该方法首先用链接图建立机器人运动空间模型，在此基础上　

利用蚂蚁算法进行全局搜索得到全局导航路径，然后用粒子群算法局部调节全局导航路径上的路径点，得到更优路径。计算机仿　

真实验表明，即使在复杂的环境下，利用该算法也可以规划出一条全局优化路径，且能安全避障。　

关键词：机器人；路径规划；蚂蚁算法；粒子群算法　

文章编号：１００２—８３３１（２００７）３１－００３９—０３　文献标识码：Ａ　中图分类号：ＴＰ２４２．６　

１引言　

移动机器人路径规划是指在有障碍物的工作环境中，寻找　

一

的路径。计算机仿真实验表明，本方法能满足机器人．决速路径　

规划的要求，并且在复杂的环境下也可以快速地规划出一条从　

起始点到目标点的优化路径，效果十分令人满意。　

条从给定起始点到终止点的较优运动路径，使机器人在运动　

过程中能安全、无碰撞地绕过所有的障碍物，且所走路径较短。　

根据机器人对环境信息掌握程度的不同，路径规划可以分为两　

种类型：环境信息完全已知的全局路径规划和环境信息完全未　

知或部分未知的局部路径规划。对于环境信息完全已知的情况　

的研究已有广泛的报道，例如势场法…、遗传算法［：等。势场法结　

２环境描述　

对机器人运动环境常用的建模方法有栅格法、可视图法　

等。这些方法在进行路径规划时可得到较精确解，但建立模型　

与更新模型时的计算量较大，且对传感器精度的要求较高。而　

自由空间法比较灵活，机器人起始点和目标点的改变不会造成　

连通图的重构，且大大减少建模的存储量。因此，本文采用该方　

法进行环境建模。　

为了描述方便且不失一般性和应用性，特作如下假设：　

假设１将机器人简化为一个质点。　

假设２机器人只在一个二维平面上运动。　

构简单，易于实现，得到了广泛的应用，但也有较大缺陷：存在　

ＧＮＲＯＮ（目标不可到达）问题、在障碍物面前振荡等。遗传算法　

在求解最短路径时，由于编码长度变化范围很大，尤其在问题　

规模较大、地形复杂时，产生的无效路径较多，求解效率很低，　

故能有效求解的问题的规模也比较小。　

基于对已有成果的研究并针对已有算法的不足，本文提出　

了一种新的机器人路径规划方法，用自由空间法ｌ２　１建立机器人　

假设３将机器人运动环境中的所有障碍物都用凸多边形　

运动的环境模型，在此基础上先用蚂蚁算法［４１规划一条无碰较　

优路径；再用粒子群算法［　忧化该路径，从而得到全局近似最优　

表示。　

由自由空间法构造的机器人可自由运动的网络图如图１　

基金项目：国家自然科学基金（ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．６０６７３１０２）；江苏省自然科学基金（ｔｈｅ　Ｎａｍｒ￣　

Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｊｉａｎｇｓｕ　Ｐｒｏｖｉｎｃｅ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．ＢＫ２００６２　１　８　ｏ　

作者简介：国海涛（１９８１一），男，硕士研究生，主要研究领域为人工智能与智能控制；朱庆保（１９５５一），男，教授，硕士生导师，主要研究领域为人工智　

能与智能控制；司应涛（１９８３一），男，硕士研究生，主要研究领域为人工智能与智能控制。　

维普资讯

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

所示，其中黑色表示障碍物，所标序号为路径点即机器人可行　影响效果，在计算启发式函数时，认为任意路径点都和目标点　

走的点。　

１　２　

图１链接图　

３蚂蚁粒子群融合新算法　

３．１算法总体思路及其相关定义　

自由空间法构造的路径点是自由链接线的中点，如果机器　

人仅仅沿着路径点行走，显然得到的路径不是最优的。为了解　

决这一问题，首先用蚂蚁算法找到一条无碰较优导航路径，得　

到初始的路径点；再用粒子群算法调整各个初始路径点，从而　

得到全局近似最优路径。调节过程如图２所示。让Ｐ点在尸＿。、　

Ｐ，两点所组成的线段上滑动，其具体位置可由式（１）表示：　

尸ｌ＝尸ｆｌ＋（　２一Ｐ１）ｘｔ。　。∈［０，ｌ】，ｉ＝Ｉ，２，…，ｎ）　（Ｉ）　

式中，ｔ．表示粒子位置的第ｉ维变量，当ｔ．的值变化时，　随之改　

变　用粒子群算法来搜索最佳ｔ　，使得粒子的适应度函数取值　

最小（机器人自由运动空间由凸多边形构成，保证了　在线段　

，

尸＝，上滑动时形成的新路径不会与障碍物相交）。对每个路径　

点都这样处理后，这些新的路径点就组成了一条新的机器人移　

动路径。　

图２路径调整不总图　

定义１链接线长度指两直接相邻路径点问的距离，记作　

ｄ（ｉ，　），由式（２）计算：　

ｒ————————　——————————Ｔ　

ｄ（　，　）＝Ｖ　－ｘ）　十（ｙ　）　（２）　

其中链接线也称为弧，若两路径点不直接相连，则两点间的距　

离视为无穷大。　

定义２　ａｎｔ＝｛１，２，…，　，…，ｍｌ表示蚂蚁家族所有蚂蚁的集　

合，　ａｎｔ表示某只蚂蚁，ｍ为蚂蚁家族的蚂蚁总数，ｒ　（￡）表示　

蚂蚁在ｔ时刻残留在直接相邻路径点　√连线上的信息量。　

定义３蚂蚁　已经选择并行走过的路径点组成的集合表　

示为ｔａｂｕ　，它随着蚂蚁的行走动态调整。　

定义４叼　，＝Ｄ／ｄ（ｊ，ｇ０　）称蚂蚁从路径点ｉ选择路径点　的　

启发函数，Ｄ为权重常系数，ｇｏａｌ为目标点。为了计算方便且不　

直接相连。　

定义５所有路径点组成的集合称为可行域，记为　。　

定义６　Ｖｉ∈ＦＳ，Ｊ∈ＦＳ且　与ｉ直接相邻，则称　在ｉ的邻　

域内，记为　Ｎｉ　其中，Ｍ为ｉ的邻域。　

定义７粒子ｃ第ｈ维和第＾＋Ｉ维之间的距离根据式（２）、　

式（３）计算：　

ｐｄ＇（　

，　

）＝ｄ（Ｐ（ｔ＾），Ｐ（ｔ¨．））　（３）　

其中，Ｐ（ｔ　）和Ｐ（ｔ　）由式（１）计算。　

３．２算法步骤　

根据以上思想及相关定义，本文算法具体步骤如下：　

步骤１初始化：初始化出发点Ｓ和目标点Ｇ，如果Ｓ、Ｇ不　

是网络图中的路径点，将Ｓ、Ｇ和离其最近的路径点相连。将ｎ１　

只蚂蚁放置在Ｓ，并将Ｓ设置到禁忌表ｔａｂｕ　中（ｋ＝ｌ，２，…，／７／＂）。　

令ｒ　（０）＝ｒ　（ｒ　为常数）　设置迭代次数ｎ＝Ｏ，最大迭代次数为　

ＭＡＸ，设定口、　和Ｐ的值：　

步骤２　Ｖ　，以当前路径点ｉ　ＦＳ为中心，选择并行走到下　

一

节点　，且有　Ｎｉ，ｊ　ｔａｂｕ　。蚂蚁按式（４）选择节点　：　

｛【　ｒｇ１１１３ｘ　（￡）】　ｌ　ｉｆ　ｑ≤ｑ。　（４）　

Ｓ　ｅｌｓｅ　

其中：ｑ和ｑｏ是为了防止出现停滞而设的随机搜索策略所需参　

数，以增加搜索的多样性。Ｏ＜ｑ　≤１是初始设定的参数，ｑ　

（０，１）是随机数。ＪＢ为从ｉ到　的弧上残留信息的重要程度；叼　

为由定义４给出的启发信息；随机变量Ｓ根据式（５）决定：　

Ｊ　ｔａｂｕ　

∑　）　（５）　

０　∈ｔａｂｕ　

Ｐ：（￡）为在ｔ时刻蚂蚁　由节点ｉ转移到节点　的概率，ｉ，ｊ　ＦＳ。　

计算转移概率Ｐ：，根据赌轮盘规则选择下一个路径点　，并将　

加入禁忌表ｔａｂｕ　。　

步骤３按式（６）信息素更新：　

（￡＋１）＝（１－ｐ）ｒ　（￡）＋ｐＡｒ　

．　

△ｒ＝｛Ｌ　

　ｆ若蚂蚁　在本次循环中走过（ｉ　）　（６）　

否则　

１　表示信息消逝程度；Ｑ为一个常数，表示信息素强度；三　表　

示蚂蚁　在本次循环中已走的路径长度。　

步骤４蚂蚁选择完下一个路径点　后，若　＝Ｇ，则转步骤　

５，否则转步骤２。　

步骤５计算蚂蚁所走路径的总长度，将新的路径与已知　

最优路径相比较，若新路径更优，则用新路径替换更新已知最　

优路径总长度三ｍｍ。　

步骤６在已知最优的路径上按式（７）信息素更新：　

ｒ　＝（１－ｐ）　＋ｐＡｒ　

△　：

ｆ　若蚂蚁　在本次寻优中走过“　‘７　

维普资讯

国海涛，朱庆保，司应涛：一种蚂蚁粒子群融合的机器人路径规划新算法　

步骤７迭代次数加１，若未达到最大迭代次数，则清空禁　

忌表，转步骤２重复上述过程，直到ｎ＝ＭＡＸ为止。选出最优路　

为了进一步说明本文算法的有效性，又对较复杂的环境进　

行了实验，实验结果如图４所示。运行参数设定如下：蚂蚁数为　

２０，／３＝２、ａ＝ｌ、ｐ＝Ｏ．１、ＭＡＸ＝ＩＯ０、Ｐｍａｘ＝２００、Ｐｎ＝４０。文献【６］给出　

实验结果路径序列为　，２４，２３，１８，８，６，３，　，由本文算法求得　

路径为｛ｓ，ｎ，ｂ，ｃ，　。　

径　｛Ｐｏ　…　｝（其中路径点个数为ｕ＋１）转步骤８。　

步骤８初始化粒子数　，在允许的范围内随机初始化粒　

子的位置和速度，把每个粒子的初始化位置视为其初始最优位　

置Ｐ。粒子的维数由最优路径中路径点的个数（不舍出发点和　

目标点）决定，即粒子有　一１维。设定　、ｃ．、ｃ，和最大迭代次数　

Ｐｍａｘ。　

步骤９依据定义７和式（８）计算每个粒子ｃ的适应度Ｆ，　

适应度最小的粒子记为ｇ。　

Ⅱ一ｌ　

＝　ｐ　（　，　＋．）　（８）　

＾＝】　

步骤１０依据式（９）更新粒子Ｃ的各维速度，依据式（１０）　

更新粒子ｃ的位置。　

ｌ仁（ｃＪ　山　＋ｃ】Ｘｒｌ　　－＿。　２　Ｘｒ２　＿。　］　（９）　

Ｘ

ｃ，ｈＩ＇＊￣１　ｍ　－－ｔ、　

（１０）　

其中ｒ　、ｒ　是【０，１］之间的随机数，若　＜一　ｍａｘ　，则令　＝　

ｍａｘ　；若　ｍａｘ　，则令Ｙｃｈ　ｍａｘ　，即对粒子的速度进　

行限制。若Ｘｃ＾＜ＩＩｌｉｌｌＸ＾，则令Ｘｃｈ＝ｒａｉｎｘ＾＋ｒａｎｄｘ０．０１；若Ｘｃ＾＞ｍａｘ　，　

则令　￣－Ｉｌｌｏｘ　，即对粒子的位置进行限制。　

步骤１１依据式（８）计算每个粒子的适应度，若适应度小　

于原来的适应度则更新Ｐ、ｇ。　

步骤１２若迭代次数未到达最大次数或者未满足精度要　

求则转步骤１０，否则转步骤１３。　

步骤１３输出最优路径。　

４仿真实验　

为了体现该算法的有效性及其特点，作者做了大量的实　

验，实验环境为：ＣＰＵ赛扬２．６６　Ｇ，内存为２５６　Ｍ，编译工具　

ＶＣ＋＋６．０。　

在图３所示的实验中，运行参数设定如下：蚂蚁数为１０，　

／３＝２、ａ＝ｌ、ｐ＝０．１、ＭＡＸ＝５０、Ｐｍａｘ＝１００、Ｐｎ＝３０。由基本蚂蚁算法　

求的路径序列为｛ｓ，８，９，ｌ１，１７，１６，１５，４，　，由本文算法求得路　

径为｛ｓ，ｎ，ｂ，ｃ，　，运行时间为０．３０５　ｓ，同一环境下，用文献［３］中　

的算法运行时间为１．４３２　Ｓ。　

７＂＼●Ｉ　

ｆＩ●　

Ｉ　

图３简单环境　

图４较复杂环境　

仿真实验结果表明，本文算法具有收敛快，得到的路径更　

优等优点。　

５结语　

本文采用链接图法对机器人运动环境进行建模，算法简单　

容易实现。在此基础上，给出的算法首先将出发点和目标点与　

离其最近的路径点相连，用蚂蚁算法快速搜索出一条全局路　

径，然后对该路径上的点进行调节，得到近似最优路径。与其他　

算法相比，该算法简单可行，适于复杂环境下的机器人路径规　

划。（收稿日期：２００７年７月）　

参考文献：　

［１］Ａｇｉｒｒｅｂｅｉｔｉａ　Ｊ．Ａ　ｎｅｗ　ＡＰＦ　ｓｔｒａｔｅｇｙ　ｆｏｒ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｉｎ　ｅｎｖｉｍｎ—　

ｍｅｎｔｓ　ｗｉｔｈ　ｏｂｓｔａｃｌｅｓ［Ｊ］．Ｍｅｃｈａｎｉｓｍ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｔｈｅｏｒｙ，２００５，４０：　

６４５－６５８．　

［２］孙树栋，林茂．基于遗传算法的多移动机器人协调路径规划［Ｊ１．自动　

化学报，２０００，２６（５）：６７３—６７６．　

［３］Ｑｉｎ　Ｙｕａｎ—ｑｉｎｇ，Ｓｕｎ　Ｄｅ－ｂａｏ．Ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｆｏｒ　ｍｏｂｉｌｅ　ｒｏｂｏｔ　ｕｓｉｎｇ　

ｔｈｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｆｆｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｗｉｔｈ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ［Ｃ］／／Ｐｒｏｃｅｅｄ—　

ｉｎｇｓ　ｏｆ　ｔｈｅ　Ｔｈｉｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　

ａｎｄ　Ｃｙｂｅｒｎｅｔｉｃｓ，Ｓｈａｎｇｈａｉ．２６－２９　Ａｕｇｕｓｔ　２００４：２４７３－２４７８．　

【４１朱庆保．复杂环境下的机器人路径规划蚂蚁算法［Ｊ１．自动化学报，　

２００６．３２（４）：５８６—５９３．　

［５］孙波，陈卫东，席裕庚．基于粒子群优化算法的移动机器人全局路径　

规划　控制与决策，２００５，２０（９）：１０５２—１０６０．　

［６］ＨａｂｉｂＭ　Ｋ，Ａ　ｓａｍａ　Ｈ．Ｅｆｉｆｃｉｅｎｔ　ｍｅｔｈｏｄ　ｔｏ　ｇｅｎｅｒａｔｅ　ｃｏｌｌｉｓｉｏｎ　ｆｒｅｅ　

ｐａｔｈｓ　ｆｏｒ　ａｕｔｏｎｏｍｏｕｓ　ｍｏｂｉｌｅ　ｒｏｂｏｔ　ｂａｓｅｄ　ｏｎ　ｎｅｗ　ｆｒｅｅ　ｓｐａｃｅ　

ｓｔｒｕｃｔｕｒｉｎｇ　ａｐｐｒｏａｃｈ［Ｃ］／／Ｐｒｏｃ　ＩＥＥＥ／ＲＳＪ　ＩＲＯＳ，１９９１：５６３—５６７．　

本文标签： 路径算法机器人蚂蚁规划