论文部分内容阅读
摘 要：针对PSO算法与蚁群算法的优缺点，提出一种融合PSO算法与蚁群算法的混合随机搜索算法。该算法充分利用PSO算法的快速、全局收敛性和蚁群算法的信息素正反馈机制，达到优势互补。将该算法用于机器人路径规划问题，计算机仿真实验表明，本方法能满足快速规划机器人路径的要求，可以快速地规划出一条从起始点到目标点的近似最优化路径，效果十分令人满意。
关键词：路径规划 粒子群 蚁群 栅格法
引言：
机器人路径规划问题是指在有障碍物的工作环境中，如何寻找一条从给定起点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，且所走路径最短。目前已有的全局路径规划算法有启发式图搜索算法、可视图法、势场法、遗传算法、蚁群算法等，这些方法都具有各自的优点，但均存在着一定的局限性。
基于对已有成果的研究并针对已有算法的不足，提出了一种全新的机器人路径规划方法，首先用栅格法建立机器人运动的环境模型，在此基础上先用粒子群算法得到蚁群算法的初始信息素分布，接着用蚁群算法搜索出一条全局最优路径。计算机仿真实验表明，本方法能满足快速规划机器人路径的要求，可以快速地规划出一条从起始点到目标点的近似最优化路径，效果十分令人满意。
1. 粒子群优化算法
粒子群优化算法是一种新的进化计算方法，首先初始化为一群随机粒子，每个粒子记录它当前的位置和速度，通过迭代找到最优解。每次迭代中，粒子通过两个极值更新自己，—个是粒子本身迄今找到的迭代初始到当前迭代次数搜索生成的最优解，另—个是整个群体当前的最优解。粒子的位置和速度更新公式：
(1)
(2)
式中， 是均匀分布在(0，1)之间的随机数； 为惯性因子； 、 为学习因子，通常 = =2。
2. 问题描述与环境建模
对于任意的二维地形，存在着有限个障碍物，这里的任务就是寻找从起点S到终点E的安全避障路径所经过的一系列点的集合，并且要保证路径为最短路径。其目标函数可表示为：
(3)
其中： 为路径点的坐标信息，为路径点的个数。
设机器人在二维平面上的凸多边形有限区域内运动，该区域内分布着有限个不同大小的障碍物，在该区域建立直角坐标系。假设机器人以一定的步长 运动，则 轴和 轴分别以 为单位来划分栅格。每行的栅格数 ；每列的栅格数 。如果障碍区域为不规则形状，则可在边界处补以障碍栅格，将其补为正方形或者长方形。其中障碍物占—个或多个栅格，若不满—个栅格，以—个栅格计。每个栅格都有对应的坐标和序列号，而且序列号与坐标一一对应，栅格法把工作空间分割成规则而均匀的含二值信息的栅格，用0和1分别表示自由栅格和障碍栅格。坐标 与序列号 之间的映射关系可以由式(4)确定：
其中：int为取整运算，mod为求余运算，m为每一行的栅格数。
3. 基于粒子群蚁群融合新算法的机器人路径规划
利用PSO算法解决优化问题的两个重要步骤是：问题解的编码和适应度函数的选择。在PSO系统中，每—个粒子个体代表一条从起点到终点的路径，如
其中 表示粒子的维数大小，粒子的每一维都代表—个栅格序号，粒子的第一维表示起点栅格序号，最后一维表示终点栅格序号，将序号按照由小到大的顺序连接起来可构成一条路径。适当地选择适应值函数可以保证获得最优路径。以路径最短作为评价标准，选择适应值函数为：
式中， 表示路径通过的栅格的数目， 为代表该路径的个体中相邻序号间直线距离之和，即公式(3)。
算法的具体步骤如下：
步骤1）：利用栅格法进行环境建模，得到一个表示环境信息的二维数组chart[][]；
步骤2): 初始化粒子群，包括群体规模，每个粒子的位置和速度，以及最大迭代次数；
步骤3): 计算每个粒子的适应值；
步骤4): 对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果 ，则 ；
步骤5）：对于每个粒子，将其所经历的最好位置的适应值 与全局所经历的最好位置 的适应值进行比较
，如果 ，则 ；
步骤6）：根据公式
对粒子的速度和位置进行更新。如果 ，则 ，如果 ，则 ；
步骤7）：如果算法达到最大迭代次数或者满足精度要求，则算法结束，输出搜索出的当前最优路径；否则转到步骤3。
4. 信息素表示
信息素分布在每个栅格到与其相邻栅格的路径上，蚂蚁从起 点所在栅格开始搜索，对于每个栅格位置的不同，可以将栅格分为边界栅格和中间栅格。对于中间栅格，假设其邻接周围没有障碍物，下一步可以向邻接的8个方位搜索，8个方位分别为：右下、右、右上、上、左上、左、左下、下。可以看出，当前栅格和它相邻的8个方位的距离定义可用以下数组表示：
(6)
对于边界栅格，下一步可以搜索的方位要去掉不可达栅格序号。故首先根据式(5)初始化每一栅 格到其相邻栅格
的信息素。
(7)
其中，为一常数，为与相邻的栅格，表示栅格的中心点到终点的距离。
定义 与相邻的左、右、上、下4个栅格为直接相邻栅格，左上、左下、右上、右下4个栅格为间接相邻栅格，可达栅格的判别规则如下：
关键词：路径规划 粒子群 蚁群 栅格法
引言：
机器人路径规划问题是指在有障碍物的工作环境中，如何寻找一条从给定起点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，且所走路径最短。目前已有的全局路径规划算法有启发式图搜索算法、可视图法、势场法、遗传算法、蚁群算法等，这些方法都具有各自的优点，但均存在着一定的局限性。
基于对已有成果的研究并针对已有算法的不足，提出了一种全新的机器人路径规划方法，首先用栅格法建立机器人运动的环境模型，在此基础上先用粒子群算法得到蚁群算法的初始信息素分布，接着用蚁群算法搜索出一条全局最优路径。计算机仿真实验表明，本方法能满足快速规划机器人路径的要求，可以快速地规划出一条从起始点到目标点的近似最优化路径，效果十分令人满意。
1. 粒子群优化算法
粒子群优化算法是一种新的进化计算方法，首先初始化为一群随机粒子，每个粒子记录它当前的位置和速度，通过迭代找到最优解。每次迭代中，粒子通过两个极值更新自己，—个是粒子本身迄今找到的迭代初始到当前迭代次数搜索生成的最优解，另—个是整个群体当前的最优解。粒子的位置和速度更新公式：
(1)
(2)
式中， 是均匀分布在(0，1)之间的随机数； 为惯性因子； 、 为学习因子，通常 = =2。
2. 问题描述与环境建模
对于任意的二维地形，存在着有限个障碍物，这里的任务就是寻找从起点S到终点E的安全避障路径所经过的一系列点的集合，并且要保证路径为最短路径。其目标函数可表示为：
(3)
其中： 为路径点的坐标信息，为路径点的个数。
设机器人在二维平面上的凸多边形有限区域内运动，该区域内分布着有限个不同大小的障碍物，在该区域建立直角坐标系。假设机器人以一定的步长 运动，则 轴和 轴分别以 为单位来划分栅格。每行的栅格数 ；每列的栅格数 。如果障碍区域为不规则形状，则可在边界处补以障碍栅格，将其补为正方形或者长方形。其中障碍物占—个或多个栅格，若不满—个栅格，以—个栅格计。每个栅格都有对应的坐标和序列号，而且序列号与坐标一一对应，栅格法把工作空间分割成规则而均匀的含二值信息的栅格，用0和1分别表示自由栅格和障碍栅格。坐标 与序列号 之间的映射关系可以由式(4)确定：
其中：int为取整运算，mod为求余运算，m为每一行的栅格数。
3. 基于粒子群蚁群融合新算法的机器人路径规划
利用PSO算法解决优化问题的两个重要步骤是：问题解的编码和适应度函数的选择。在PSO系统中，每—个粒子个体代表一条从起点到终点的路径，如
其中 表示粒子的维数大小，粒子的每一维都代表—个栅格序号，粒子的第一维表示起点栅格序号，最后一维表示终点栅格序号，将序号按照由小到大的顺序连接起来可构成一条路径。适当地选择适应值函数可以保证获得最优路径。以路径最短作为评价标准，选择适应值函数为：
式中， 表示路径通过的栅格的数目， 为代表该路径的个体中相邻序号间直线距离之和，即公式(3)。
算法的具体步骤如下：
步骤1）：利用栅格法进行环境建模，得到一个表示环境信息的二维数组chart[][]；
步骤2): 初始化粒子群，包括群体规模，每个粒子的位置和速度，以及最大迭代次数；
步骤3): 计算每个粒子的适应值；
步骤4): 对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果 ，则 ；
步骤5）：对于每个粒子，将其所经历的最好位置的适应值 与全局所经历的最好位置 的适应值进行比较
，如果 ，则 ；
步骤6）：根据公式
对粒子的速度和位置进行更新。如果 ，则 ，如果 ，则 ；
步骤7）：如果算法达到最大迭代次数或者满足精度要求，则算法结束，输出搜索出的当前最优路径；否则转到步骤3。
4. 信息素表示
信息素分布在每个栅格到与其相邻栅格的路径上，蚂蚁从起 点所在栅格开始搜索，对于每个栅格位置的不同，可以将栅格分为边界栅格和中间栅格。对于中间栅格，假设其邻接周围没有障碍物，下一步可以向邻接的8个方位搜索，8个方位分别为：右下、右、右上、上、左上、左、左下、下。可以看出，当前栅格和它相邻的8个方位的距离定义可用以下数组表示：
(6)
对于边界栅格，下一步可以搜索的方位要去掉不可达栅格序号。故首先根据式(5)初始化每一栅 格到其相邻栅格
的信息素。
(7)
其中，为一常数，为与相邻的栅格，表示栅格的中心点到终点的距离。
定义 与相邻的左、右、上、下4个栅格为直接相邻栅格，左上、左下、右上、右下4个栅格为间接相邻栅格，可达栅格的判别规则如下：