基于蚁群算法的移动机器人路径规划方法的一种改进

摘要

本发明涉及一种移动机器人路径规划方法，包括如下步骤：寻找环境最短路径；当机器人在前进中检测到将与环境中的动态障碍物相碰，则视最短路径上离动态障碍物安全的栅格为局部目标点；确定动态障碍物的运动范围；机器人沿着信息素浓度大的栅格前进；得到一条避开动态障碍物且经过指定点的最优路径。解决了蚁群算法由于自身的局限性而导致的收敛速度慢的问题，将传统蚁群算法中的参数用粒子群算法进行优化后找到一组最优解，且用遗传算法保证其不会陷入局部最优，再将上述参数中的其他参数保持不变，对信息素浓度进行成倍放大，使不同路径上的信息素浓度差异更加明显，从而提高算法的收敛速度。

权利要求

1.一种移动机器人路径规划方法，其特征在于，包括如下步骤：(1)寻找环境最短路径；步骤(1)中用蚁群算法寻找环境最短路径；所述蚁群算法采用如下算法步骤：a.参数用粒子群算法进行优化后找到一组最优解，且用遗传算法保证其不会陷入局部最优；步骤a中蚁群算法中种群个数为25，最大迭代次数为100，用粒子群算法对改进蚁群算法的重要参数进行优化，粒子的个数为30，迭代次数的最高上限为50，惯性衡量值w为

0.625，影响机器人自适应学习功能的参数c1和c2都选为1.501；

b.将上述参数中的其他参数保持不变，对传统蚁群算法中各个路径上的信息素浓度进行成倍放大，使不同路径上的信息素浓度差异更加明显；步骤b中，由粒子群算法寻找到改进蚁群算法重要参数的最优组合放大倍数M取为3；

c.加速蚂蚁朝着信息素浓度高路径移动，从而提高算法的收敛速度；

(2)当机器人在前进中检测到将与环境中的动态障碍物相碰，则视最短路径上离动态障碍物安全的栅格为局部目标点；

(3)确定动态障碍物的运动范围；

(4)机器人沿着信息素浓度大的栅格前进；

(5)得到一条避开动态障碍物且经过指定点的最优路径。

2.如权利要求1所述的移动机器人路径规划方法，其特征在于，步骤(1)中所述环境为机器人的工作环境，将该工作环境划分为20×20的栅格，每个栅格的长和宽都为10个单位。

3.如权利要求1或2所述的移动机器人路径规划方法，其特征在于，步骤(1)中按状态转移概率公式寻找环境最短路径。

4.如权利要求1所述的移动机器人路径规划方法，其特征在于，步骤(3)中通过传感器收集信息从而确定动态障碍物的运动范围。

5.如权利要求1所述的移动机器人路径规划方法，其特征在于，步骤c中，坐标系以x轴向右为正方向，y轴向上为正方向，单位为像素，静态障碍物假定为方块，假设动态障碍物是长和宽分别为10个单位的正方形块，动态障碍物沿y轴向上做速度为10单位/秒的匀速直线运动。

说明书

基于蚁群算法的移动机器人路径规划方法的一种改进

技术领域

[0001] 本发明涉及移动机器人路径规划技术领域，涉及到移动机器人路径规划收敛速度的快慢，具体涉及一种移动机器人路径规划方法及其算法。

背景技术

[0002] 随着人类社会的不断发展和生活空间的不断扩大，移动机器人在国防、抗震抢险、防灾救灾、反恐、现代军事武器、制造业以及日常生活的应用越来越广泛，因此必须对移动机器人的动态路径进行更为有效的规划。随着移动机器人技术的迅速发展，应用范围的不断扩大，使得人们对机器人各方面的性能提出了更高的要求。科学家们通过不懈努力，提出了多种移动机器人种路径规划算法，蚁群算法便是其中的一种。它是根据自然界蚂蚁觅食的行为提炼出来的，由于自然界的蚂蚁在觅食的过程中会在走过的路径上留下一种称为信息素的化学物质，且经过该路径的蚂蚁越多，在上面留下的信息素也越多(忽略挥发掉的那一部分)，同时也证明该路径较其他路径更为优越，其他的蚂蚁也能感知到这种物质且朝着信息素浓度高的地方移动。但由于起始时蚁群中每一只蚂蚁的运动是随机性的，虽然在算法初期可以通过信息素的作用的使其向着最优路径方向移动，但是当群体规模越来越大时，寻找最优解的效率就不是很明显了，从而使搜索时间冗长，因此使得算法的收敛速度很慢。

[0003] 综上所述，现有技术中存在如下技术问题：由于传统蚁群算法自身的局限性使得算法的收敛速度较慢，要求提高算法的收敛速度。

发明内容

[0004] 本发明的目的在于提供一种移动机器人路径规划方法，解决蚁群算法由于自身的局限性而导致的收敛速度慢的问题，将传统蚁群算法中的参数用粒子群算法进行优化后找到一组最优解，且用遗传算法保证其不会陷入局部最优，再将上述参数中的其他参数保持不变，对信息素浓度进行成倍放大，使不同路径上的信息素浓度差异更加明显，从而提高算法的收敛速度。

[0005] 针对以上上述现有技术问题和发明目的，本发明提出一种移动机器人路径规划方法，包括如下步骤：

[0006] (1)寻找环境最短路径；

[0007] (2)当机器人在前进中检测到将与环境中的动态障碍物相碰，则视最短路径上离动态障碍物安全的栅格为局部目标点；

[0008] (3)确定动态障碍物的运动范围；

[0009] (4)机器人沿着信息素浓度大的栅格前进；

[0010] (5)得到一条避开动态障碍物且经过指定点的最优路径。

[0011] 进一步地，步骤(1)中所述环境为机器人的工作环境，将该工作环境划分为20×20的栅格，每个栅格的长和宽都为10个单位。

[0012] 进一步地，步骤(1)中按状态转移概率公式寻找环境最短路径。

[0013] 进一步地，步骤(1)中用蚁群算法寻找环境最短路径。

[0014] 进一步地，所述蚁群算法采用如下算法步骤：

[0015] a.参数用粒子群算法进行优化后找到一组最优解，且用遗传算法保证其不会陷入局部最优；

[0016] b.将上述参数中的其他参数保持不变，对传统蚁群算法中各个路径上的信息素浓度进行成倍放大，使不同路径上的信息素浓度差异更加明显；

[0017] c.加速蚂蚁朝着信息素浓度高路径移动，从而提高算法的收敛速度。进一步地，步骤(3)中通过传感器收集信息从而确定动态障碍物的运动范围。进一步地，步骤a中蚁群算法中种群个数为25，最大迭代次数为100，用粒子群算法对改进蚁群算法的重要参数进行优化，粒子的个数为30，迭代次数的最高上限为50，惯性衡量值w为0.625，影响机器人自适应学习功能的参数c1和c2都选为1.501。

[0018] 进一步地，步骤b中，由粒子群算法寻找到改进蚁群算法重要参数的最优组合放大倍数M取为3。

[0019] 进一步地，步骤c中，坐标系以x轴向右为正方向，y轴向上为正方向，单位为像素，静态障碍物假定为方块，假设动态障碍物是长和宽分别为10个单位的正方形块，动态障碍物沿y轴向上做速度为10单位/秒的匀速直线运动。

[0020] 与目前现有技术相比，本发明解决了蚁群算法由于自身的局限性而导致的收敛速度慢的问题，将传统蚁群算法中的参数用粒子群算法进行优化后找到一组最优解，且用遗传算法保证其不会陷入局部最优，再将上述参数中的其他参数保持不变，对信息素浓度进行成倍放大，使不同路径上的信息素浓度差异更加明显，从而提高算法的收敛速度。

附图说明

[0021] 图1为本发明的方案流程图。

[0022] 图2为本发明蚁群算法原理图。

具体实施方式

[0023] 下面根据附图对本发明进行详细描述，其为本发明多种实施方式中的一种优选实施例。

[0024] 在一个优选实施例中，一种移动机器人路径规划方法，包括如下步骤：寻找环境最短路径；当机器人在前进中检测到将与环境中的动态障碍物相碰，则视最短路径上离动态障碍物安全的栅格为局部目标点；确定动态障碍物的运动范围；机器人沿着信息素浓度大的栅格前进；得到一条避开动态障碍物且经过指定点的最优路径。蚁群算法采用如下算法步骤：参数用粒子群算法进行优化后找到一组最优解，且用遗传算法保证其不会陷入局部最优；将上述参数中的其他参数保持不变，对传统蚁群算法中各个路径上的信息素浓度进行成倍放大，使不同路径上的信息素浓度差异更加明显；加速蚂蚁朝着信息素浓度高路径移动，从而提高算法的收敛速度。

[0025] 优选的蚁群算法参照图1，蚁群算法中种群个数为25，最大迭代次数为100.用粒子群算法对改进蚁群算法的重要参数进行优化，粒子的个数为30，迭代次数的最高上限为50，惯性衡量值w为0.625，影响机器人自适应学习功能的参数c1和c2都选为1.501。由粒子群算法寻找到改进蚁群算法重要参数的最优组合放大倍数M取为3，坐标系以x轴向右为正方向，y轴向上为正方向，单位为像素，静态障碍物假定为方块，假设动态障碍物是长和宽分别为10个单位的正方形块，动态障碍物沿y轴向上做速度为10单位/秒的匀速直线运动。

[0026] 参照图2，一个优选的移动机器人路径规划方法可以包括如下步骤：初始化--更改禁忌表且按状态转移概率公式选择路径—确定移动方向—求信息素增量—参数优化及避免陷入局部最优—对信息素浓度成倍放大—判断中止准则。

[0027] 在另一个优选实施例中，方案可以如下：用改进的蚁群算法对移动机器人路径进行规划，对传统蚁群算法中个路径上的信息素浓度进行成倍放大，使各条路径上的信息素浓度差别更加明显，加速蚂蚁朝着信息素浓度高路径移动，从而解决了传统蚁群算法收敛速度慢的问题。

[0028] 用蚁群算法寻找环境最短路径的过程中，按状态转移概率公式选择路径，如果机器人在前进中检测到将与环境中的动态障碍物相碰，则视最短路径上离动态障碍物安全的栅格为局部目标点，通过传感器收集信息确定动态障碍物的运动范围，机器人沿着信息素浓度大的栅格前进，以最短的时间，寻找一条避开动态障碍物且经过指定点的最优路径。

[0029] 将机器人的工作环境划分为20×20的栅格，每个栅格的长和宽都为10个单位，蚁群算法中种群个数为25，最大迭代次数为100，用粒子群算法对改进蚁群算法的重要参数进行优化，粒子的个数为30，迭代次数的最高上限为50，惯性衡量值w为0.625，影响机器人自适应学习功能的参数c1和c2都选为1.501。

[0030] 由粒子群算法寻找到改进蚁群算法重要参数的最优组合放大倍数M取为3，坐标系以x轴向右为正方向，y轴向上为正方向，单位为像素，静态障碍物假定为方块，假设动态障碍物是长和宽分别为10个单位的正方形块，动态障碍物沿y轴向上做速度为10单位/秒的匀速直线运动。

[0031] 在另一个优选实施例中，针对传统蚁群算法机器人路径规划收敛速度慢且容易陷入局部最优的问题，首先利用遗传算法克服由于蚁群算法自身搜索机制的局限导致的路径规划容易陷入局部最优值的问题，再通过粒子群算法对涉及到的参数进行优化，最后通过对信息素浓度值进行适当倍数的放大，提高算法的收敛速度，最终完成路径规划。具体步骤如下：

[0032] 1.先采用遗传算法中的轮盘算法来避免蚁群算法陷入局部最优值，具体步骤如下：

[0033] 步骤1根据适应度函数：

[0034]

[0035] (其中n代表蚂蚁在模拟环境所经过的路径上所包含的栅格的数目，每个蚂蚁个体所经过的路径的长度用字母d表示)。依次计算出群体内每个个体的适应值，得相应的累计值为Hi，最后一个累计值为Hn；

[0036] 步骤2得出均匀分布的适应度随机数W∈[0，Hn]；

[0037] 步骤3依次用Hi与步骤2中产生的随机数W进行比较，若Hi≥W，则i被选为复制对象；若Hi≤W，则i被删除；

[0038] 步骤4重复步骤2和步骤3，直到所需要的个体数目被复制满为止。

[0039] 通过轮盘算法对个体适应值的筛选，使算法的早熟问题得到了很好的解决[0040] 2.对参数进行优化

[0041] 改进蚁群算法的相关参数用粒子群算法进行优化选择的具体操作步骤如下：

[0042] 步骤1参数初始化，对遍历搜索次数最大值kmax，惯性衡量值w，粒子个数m，影响机器人自适应学习功能的参数c1和c2进行初始化。

[0043] 步骤2当前粒子群的位置信息用改进蚁群算法中放大后的信息素浓度值和启发函数表示，起始位置和初速度在位置可变范围内随机的选取。

[0044] 步骤3将当前群体中适应度最好的粒子的位置和本次循环中每个粒子在解集中的最好位置求出。

[0045] 步骤4粒子群中每个粒子i的速度vi按公式进行更新，若vi小于Vmin，则vi为Vmin；若vi大于Vmin，则vi为Vmax。

[0046] 步骤5粒子群中每个粒子i的位置xi按公式 对进行更新，若xi小于Xmin，则xi为Xmin；若xi大于Xmin，则xi为Xmax。

[0047] 对①②两个公式进行说明：其中:下标j表示微粒的第j维，下标i表示微粒i，k表示第k代，h1，h2为加速度常量，通常在(0,2)间取值，和r2是分别属于U(0,1)的两个相互独立的随机函数， 表示第k代微粒i在第j维空间的位置， 表示第k代微粒i在第j维空间所经历的具有最好适应值的位置， 表示第k代整个微粒群在第j维空间所经历过的最好位置表示第k+1代微粒在在第j维空间中的飞行速度。

[0048] 2.用改进的蚁群算法对机器人动态路径进行规划

[0049] 新的路径规划具体操作步骤如下：

[0050] 步骤1初始化参数，对最大迭代次数Kmax、种群个数为Nnum、信息素浓度放大倍数M进行初始化；S和E分别为算法的起点和终点，设Nnum只蚂蚁的起始位置全部在起始点S，且起始时每条路径上的信息素浓度都为0。

[0051] 步骤2蚂蚁下一步到达的栅格根据自适应启发函数确定。

[0052] 步骤3在蚂蚁k到达终点E后，按信息素更新公式对路径上的信息素进行更新。

[0053]

[0054] (其中：ρ为参数且ρ∈[0,1]， 表示更新后的信息素浓度， 表示原先的信息素浓度，σ代表精英蚂蚁的个数，Lbest表示最优路径，Lworst表示最差路径，(i,j)表示从节点i到结点j的一段路径。)

[0055] 步骤4合理选择和调整放大倍数M，对更新后的信息素浓度按放大倍数M进行放大。

[0056] 步骤5对循环次数进行判断，若循环次数已达到最大值，则将当前群体中用时最短的径栅格序号和长度输出；否则返回起点S，程序转步骤2。

[0057] 步骤6机器人在沿着通过以上步骤搜索到的最优路径前进时，如果传感器检测到将与环境中的动态障碍物相撞，则机器人调整前进方向后沿着信息素浓度大的栅格重新探索到一条避开动态障碍物的路径，否则机器人一直走到指定目标点，算法终止。

[0058] 上面结合附图对本发明进行了示例性描述，显然本发明具体实现并不受上述方式的限制，只要采用了本发明的方法构思和技术方案进行的各种改进，或未经改进直接应用于其它场合的，均在本发明的保护范围之内。