基于蚁群粒子群算法融合的机器人路径规划
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于蚁群粒子群算法融合的机器人路径规划范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：针对PSO算法与蚁群算法的优缺点，提出一种融合PSO算法与蚁群算法的混合随机搜索算法。该算法充分利用PSO算法的快速、全局收敛性和蚁群算法的信息素正反馈机制，达到优势互补。将该算法用于机器人路径规划问题，计算机仿真实验表明，本方法能满足快速规划机器人路径的要求，可以快速地规划出一条从起始点到目标点的近似最优化路径，效果十分令人满意。
关键词：路径规划 粒子群 蚁群 栅格法
引言：
机器人路径规划问题是指在有障碍物的工作环境中，如何寻找一条从给定起点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，且所走路径最短。目前已有的全局路径规划算法有启发式图搜索算法、可视图法、势场法、遗传算法、蚁群算法等，这些方法都具有各自的优点，但均存在着一定的局限性。
基于对已有成果的研究并针对已有算法的不足，提出了一种全新的机器人路径规划方法，首先用栅格法建立机器人运动的环境模型，在此基础上先用粒子群算法得到蚁群算法的初始信息素分布，接着用蚁群算法搜索出一条全局最优路径。计算机仿真实验表明，本方法能满足快速规划机器人路径的要求，可以快速地规划出一条从起始点到目标点的近似最优化路径，效果十分令人满意。
1. 粒子群优化算法
粒子群优化算法是一种新的进化计算方法，首先初始化为一群随机粒子，每个粒子记录它当前的位置和速度，通过迭代找到最优解。每次迭代中，粒子通过两个极值更新自己，―个是粒子本身迄今找到的迭代初始到当前迭代次数搜索生成的最优解，另―个是整个群体当前的最优解。粒子的位置和速度更新公式：
(1)
(2)
式中， 是均匀分布在(0，1)之间的随机数； 为惯性因子； 、 为学习因子，通常 = =2。
2. 问题描述与环境建模
对于任意的二维地形，存在着有限个障碍物，这里的任务就是寻找从起点S到终点E的安全避障路径所经过的一系列点的集合，并且要保证路径为最短路径。其目标函数可表示为：
(3)
其中： 为路径点的坐标信息，为路径点的个数。
设机器人在二维平面上的凸多边形有限区域内运动，该区域内分布着有限个不同大小的障碍物，在该区域建立直角坐标系。假设机器人以一定的步长 运动，则 轴和 轴分别以 为单位来划分栅格。每行的栅格数 ；每列的栅格数 。如果障碍区域为不规则形状，则可在边界处补以障碍栅格，将其补为正方形或者长方形。其中障碍物占―个或多个栅格，若不满―个栅格，以―个栅格计。每个栅格都有对应的坐标和序列号，而且序列号与坐标一一对应，栅格法把工作空间分割成规则而均匀的含二值信息的栅格，用0和1分别表示自由栅格和障碍栅格。坐标 与序列号 之间的映射关系可以由式(4)确定：
其中：int为取整运算，mod为求余运算，m为每一行的栅格数。
利用PSO算法解决优化问题的两个重要步骤是：问题解的编码和适应度函数的选择。在PSO系统中，每―个粒子个体代表一条从起点到终点的路径，如
其中 表示粒子的维数大小，粒子的每一维都代表―个栅格序号，粒子的第一维表示起点栅格序号，最后一维表示终点栅格序号，将序号按照由小到大的顺序连接起来可构成一条路径。适当地选择适应值函数可以保证获得最优路径。以路径最短作为评价标准，选择适应值函数为：
式中， 表示路径通过的栅格的数目， 为代表该路径的个体中相邻序号间直线距离之和，即公式(3)。
算法的具体步骤如下：
步骤1）：利用栅格法进行环境建模，得到一个表示环境信息的二维数组chart[][]；
步骤2): 初始化粒子群，包括群体规模，每个粒子的位置和速度，以及最大迭代次数；
步骤3): 计算每个粒子的适应值；
步骤4): 对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果 ，则 ；
步骤5）：对于每个粒子，将其所经历的最好位置的适应值 与全局所经历的最好位置 的适应值进行比较
，如果 ，则 ；
步骤6）：根据公式
对粒子的速度和位置进行更新。如果 ，则 ，如果 ，则 ；
步骤7）：如果算法达到最大迭代次数或者满足精度要求，则算法结束，输出搜索出的当前最优路径；否则转到步骤3。
4. 信息素表示
信息素分布在每个栅格到与其相邻栅格的路径上，蚂蚁从起 点所在栅格开始搜索，对于每个栅格位置的不同，可以将栅格分为边界栅格和中间栅格。对于中间栅格，假设其邻接周围没有障碍物，下一步可以向邻接的8个方位搜索，8个方位分别为：右下、右、右上、上、左上、左、左下、下。可以看出，当前栅格和它相邻的8个方位的距离定义可用以下数组表示：
(6)
对于边界栅格，下一步可以搜索的方位要去掉不可达栅格序号。故首先根据式(5)初始化每一栅 格到其相邻栅格
的信息素。
(7)
其中，为一常数，为与相邻的栅格，表示栅格的中心点到终点的距离。
定义 与相邻的左、右、上、下4个栅格为直接相邻栅格，左上、左下、右上、右下4个栅格为间接相邻栅格，可达栅格的判别规则如下：
(1)若 ， 与直接相邻且为自由栅格；
(2)若 ， 与直接相邻且 及趋向 的 与相邻的两个直接相邻栅格均为自由栅格。
当蚂蚁处于边界栅格时，搜索只须考虑与其相邻的栅格。
5. 路径点选择
蚂蚁在 时刻处于栅格 时选择下―个可达栅格 的转移概率为：
其中： 表示在 时刻栅格 到栅格 的路径上残留的信息量； 为信息素的相对重要程度； 为距离信息的相对重要程度； ， 为―常数， 为栅格 的中心点到终点 的距离。蚂蚁 在搜索路径的过程中也保留一张 表，用以存放所经过路径点的序号信息，蚂蚁在搜索完―个循环后依据目标函数值来确定哪个蚂蚁搜索到了较好的路径。
6. 信息素更新
对整个蚁群得到的周游最优蚂蚁和全局最优蚂蚁的路径信息更新信息素，而不是对所有蚂蚁的路径信息更新信息素，从而加强了正反馈的效果；同时周游最优蚂蚁路径信息的更新也在一定程度上增加了解的多样性，减小了陷入局部优化的可能性。其更新公式如式(7)所示。
（9）
（10）
其中： 表示信息素物质的持久性； 表示信息素物质的消逝程度； 为周游最优蚂蚁的路径长度；
为全局最优蚂蚁的路径长度； 、 为整型变量，分别代表用周游最优蚂蚁和全局最优蚂蚁更新信息素的权重，其和为一常数( 的值随着搜索次数的增加而逐步减小， 的值随着搜索次数的增加而逐步增大)。
上述基于蚁群粒子群算法融合的机器人全局路径规划算法的主要步骤可描述如下。
步骤1）：设置蚂蚁数量 和最大循环次数 ，利用粒子群算法得到的全局最优路径 ，根据公式， 初始化各栅格点间的信息素分布，在此， 为粒子群算法求得的最优路径转换的信息素值，将所有蚂蚁置于起点 。
步骤2）：启动蚁群，每一只蚂蚁根据状态转移规则式（8）选择下―个路径点，若此栅格到其相邻栅格的路径上的信息素值均为0，则返回到上―个搜索的路径点，并将其置为障碍栅格。
步骤3）：重复步骤2，直到所有蚂蚁均到达终点。
步骤4）：计算各蚂蚁的路径长度L，记录当前的最优路径。
步骤5）：对周游最优蚂蚁和全局最优蚂蚁的路径信息根据式（9）和式（10）更新各条路径上的信息素。
步骤6）：若蚁群全部收敛到一条路径或达到最大循环次数 ，则循环结束，否则转步骤2。
7. 仿真实验
本文仿真软件使用MATLAB7.1，为了体现该算法的有效性及其特点，分别在16维、20维环境下进行了测试，效果都十分满意。参数分别为：粒子数 ， ，最大迭代次数 ，初始惯性权重 由0.9线性递减到0.4，最大速度 ；蚂蚁数 ，最大迭代次数
，信息素的相对重要程度 ，距离信息的相对重要程度 ，信息素的消逝程度 。实验结果如图1、图2和表1所示。
比较
7. 结语
采用栅格法对机器人运动环境进行建模，在此基础上先由粒子群算法求得次优路径并得到蚁群算法的初始信息素分布，再由蚁群算法求得近似最优路径。该算法在时间上优于蚁群算法，精度上优于粒子群算法，获得了非常好的效果。仿真实验表明本融合算法在机器人路径规划中的有效性和实用性。
参考文献：
[1]、段爱玲，邓高峰，张雪萍. 新的融合算法在机器人路径规划中的应用. 计算机工程与应用. 2009
[2]、杨惠，李峰. 粒子群和蚁群融合算法的自主清洁机器人路径. 计算机工程与应用. 2009
[3]、谭冠政，刘关俊. 基于粒子群算法的移动机器人全局最优路径规划. 计算机工程与应用. 2007.11
[4]、M Dorigo，G Di Caro．Ant Algorithm for Discrete Optimization[J]．Artificial Life，1999，5(3)：137―172．
[5]、M Dorigo，LM Gambardella．Ant Colonies for the Traveling Salesman Problem[J]．BioSystem，1997，(43)：73―91．
[6]、Eberhart R C，Kennedy J．A new optimizer using particle swarm theory[J]．Instititute of Electrical and Engineers，1995，(10)：39―43.