CN110887484A - 基于改进遗传算法的移动机器人路径规划方法及存储介质 - Google Patents

Abstract

本发明请求保护一种基于改进遗传算法的移动机器人路径规划方法及存储介质，具体步骤为：首先，设置机器人起始点的位置坐标信息S(x,y)、目的地的位置坐标信息T(x,y)以及行走区域的困难度；然后，将障碍物的长度和宽度增大了机器人宽度的r倍(r>1/2)以确保机器人与障碍物有绝对的安全距离；接着，判定当前机器人在全局坐标系中的位姿；接着，利用SPS算法获取空间中各个静态障碍物的周围点；接着，得到所有可行路径，即初始种群。利用多约束条件下的遗传算法规划出从起始点到目标点的最优或次优路径，最后，判断是否已经到达目的地坐标位置。该方法能够尽量避免考虑相对最终路径而言不必要的点，从而提高搜索效率，加快算法的收敛速度，有利于防止算法陷入局部最优。

Description

基于改进遗传算法的移动机器人路径规划方法及存储介质

技术领域

本发明属于机器人路径规划技术领域，涉及一种多约束条件下基于改进遗 传算法的移动机器人路径规划方法。

背景技术

随着机器人技术的发展，机器人的性能也越来越完善，不同功能的机 器人被制造出来并且活跃在不同的领域。避障和路径规划日渐成为一个很 重要的研究内容，它的目的是在具有障碍物的环境下寻找一条从起始点到 目标点无碰撞的最优路径，并用智能路径规划控制方法使移动机器人沿规 划的路径行走。但是在实际应用环境中，例如不同地形环境等，机器人在 行进过程中往往还需要实现多种目标，如要求所需时间最短、消耗能量最少、路径最优、安全性能最好等等，而这些目标往往又存在冲突，耗时长， 使得传统的方法不再适用，所以路径规划算法改进及研究是十分必要、十 分有意义的，是机器人未来发展的重要基石。

针对移动机器人的路径规划的研究主要是要对障碍物进行有效的检 测和碰撞躲避控制算法设计，使机器人能够准确快速的完成导航任务。对 于对障碍物的检测，需要利用机器人自身所带的测量传感器，对障碍物进 行距离与位置的测量以及运动状态的判断。目前对于这类传感器的使用一 般有超声波传感器、红外传感器、激光传感器、视觉传感器等。

在机器人路径规划的研究上，比较常用的方法有人工势场法、粒子群 算法、神经网络、遗传算法、模糊逻辑法以及蚁群算法等。

遗传算法是一种具有良好全局搜索能力和多目标隐式并行计算特点 的启发式搜索方法。大部分优化算法都是单点搜索算法，很容易陷入局部 最优解。但遗传算法是一种多点搜索算法，更有可能搜索全局，获得全局 最优解。在整个搜索过程中，遗传算法不同于贪婪算法，在使用冲击搜索 计算时不依赖于问题的梯度，但标准遗传算法有其固有缺陷，如早熟收敛、 本地搜索能力较差等。因此，在实际应用中需要对其进行优化。

有鉴于此，本发明在静态障碍物的状态检测上利用激光传感器来实时 扫描移动机器人导航中环境信息，存入初始种群路径，再利用多约束条件 下基于改进遗传算法寻找一条耗费时间少，路径长度、路径困难度和路径 平滑度都尽可能小的路径。

发明内容

本发明旨在解决以上现有技术的问题。提出了一种提高搜索效率，加快种群 收敛速度，保持种群多样性，能够在更少的时间内规划出一条最优或次优路径 的基于改进遗传算法的移动机器人路径规划方法。本发明的技术方案如下：

一种基于改进遗传算法的移动机器人路径规划方法，其包括以下步骤：

S1，建立栅格点地图模型，并设置机器人起始点的位置坐标信息S(x,y)、 目的地的位置坐标信息T(x,y)以及赋予每个栅格点一个属性值表示行走的困难 度；

S2，运用障碍物膨胀法对障碍物进行膨胀，膨胀范围是机器人宽度的r倍， 若膨胀之后两个障碍物相交则视为一个障碍物以确保机器人与障碍物有绝对的 安全距离，r>1/2；

S3，判定当前机器人在全局坐标系中的初始位姿；

S4，利用Surrounding Point Set(SPS)算法获取空间中各个静态障碍物的周围点，若周围点在障碍物内，则缩小相邻栅格点之间的距离；

S5，将获得的障碍物周围点两两相连并去除与障碍物相交的连线，并用深 度优先遍历得到从起始点到目标点的所有可行路径，即初始种群；然后增加删 除算子、平滑算子优化生成的路径；最后引入小生境法来保持种群多样性。若 到达迭代次数，则执行S6，若没达到迭代次数，则更新种群继续迭代；

S6：开始执行并判断是否已经到达目的地坐标位置T(x,y)，若到达则结束导 航，若没有到达，则返回继续执行S4。

进一步的，所述步骤S2将对机器人工作空间中的栅格点赋予另一个属性值 并用布尔值标识，标识该栅格点是否在障碍物内，具体标识：

式中，P_mn为栅格点标识符，M_mn为与P_mn对应栅格点的布尔值，m为栅格点对应 的行，n为栅格点对应的列，T表示P_mn在障碍物内，F表示P_mn不在障碍物内，A 表示P_mn为自由栅格点，B表示P_mn为威胁栅格点，障碍物膨胀法引入了虚拟障碍 集合C，对障碍物周围的相邻栅格进行扩展，当相邻栅格以P_Nb表示时，扩展依 据以下原则：

ifP_Nb∈A,thenP_Nb∈C,M_Nb＝F

ifP_Nb∈B,thenP_Nb∈C,M_Nb＝F

根据障碍物膨胀法和相邻栅格点之间的距离将障碍物膨胀为机器人宽度的r倍以确保机器人与障碍物有绝对的安全距离，r>1/2，若增大后两个障碍物相交， 则视为一个障碍物，否则视为两个障碍物。

进一步的，所述步骤S3判定当前机器人在全局坐标系中的初始位姿，具体 为：通过机器人的历史里程计数据结合当前环境信息E_0i与地图环境模型进行匹 配，定位当前机器人在全局坐标系中的位姿：

根据E_ti与

判断t时刻环境中的障碍物的全局坐标为O_ti(X_ti,Y_ti)，满足：

其中，

表示起始时刻机器人在全局坐标系XOY中的位姿、x₀表示起始时刻机 器人在全局坐标系XOY中的横坐标、y₀表示起始时刻机器人在全局坐标系XOY 中的纵坐标、θ₀表示起始时刻机器人的位姿角度，(x_t,y_t)表示t时刻机器人的全 局坐标，d_0i表示第i个障碍物到机器的距离，θ_t表示机器人t时刻位姿角度，k表 示障碍物和机器人位姿指向之间的夹角。

进一步的，步骤S4利用Surrounding Point Set(SPS)算法获取空间中各个静态障碍物的周围点，若周围点在障碍物内，则缩小相邻栅格点之间的距离，具体 步骤为：

S41：定义障碍物的周围点、临时点；

在栅格点地图模型中，任意一个栅格点与其周围的8个点进行水平连接和 垂直连接，若障碍物碰到其中一条或几条连线，则该栅格点称为障碍物的周围 点，其余不在障碍物内的点称为临时点。

S42：产生周围点的步骤：

Step1:创建周围点集和sps和临时点集和temp,并确定起始参考点p，通过将起始点与目标点连成直线与障碍物相交，离该交点最近的栅格点为起始参考点p，并 放入sps集合中，把与点p相邻的且不在障碍物内的点放入temp集合中；

Step2:依次迭代判断temp集合中的点是否为该障碍物的周围点，若是，则将该 点放入sps集合中并移除temp集合中的该点，把与该点相邻的且不在障碍物内 的点放入temp集合中，若不是，则将该点从temp集合中移除即可；

Step3:在保证temp集合与sps集合没有重复点的前提下，重复步骤Step2，直到temp集合为空。

进一步的，所述步骤S5根据周围点，利用多约束条件下的遗传算法规划出 一条从起始点S(x,y)到目标点T(x,y)的最优或次优路径，具体为：

S51：产生初始路径；

S52：添加删除算子：如果一条路径中存在一个路径点p_i,若删除p_i，p_i的前一个 路径点p_i-1与后一个路径点p_i+1相连后是可行路径段，则删除p_i；

S53:添加平滑算子：路径中的每个坐标点相当于粒子群算法中的粒子的位置，根据坐标点的前后坐标计算出粒子的速度，根据位置更新公式和速度更新公式， 计算出新的坐标点，经过多次迭代后使路径更平滑；

S54:选择算子：采用锦标赛法进行选择，即对种群中的个体进行随机分组，每组根据个体的适应度值选择适应度值最低的个体进入子代种群，并采用精英保留 策略，按一定比例将适应度最优的个体不需要经过遗传直接复制到子代种群；

S55:交叉算子：采用单点交叉方式，即随机选择两个个体，找出路径相同点进行交叉，这样可以保证路径的连续性，如果交叉后不是连续的路径，则将上半段 的最后一个点和下半段的第一个点作为起始点和目标点，运用障碍物的周围点 集进行修补使其成为一条连续的路径；

S56:变异算子：对路径上点的坐标依据概率进行小范围调整，从而保证变异后路径的可行性。

进一步的，所述步骤S51产生初始路径的步骤具体为；

Step1:让机器人从起始点出发沿直线走到目标点，如果中途碰到障碍物，会 根据SPS算法在障碍物的周围产生周围点集；

Step2:运用Dijkstra算法测试该障碍物的周围是否有可行路径，如果有，则沿 着可行路径继续往前走；

Step3:如果没有可行路径，则减小栅格点之间的宽度，重复Step1和Step2。

进一步的，所述步骤S53的位置更新公式和速度更新公式如下：

其中

表示第t次迭代第i点与前一个点的位置之差，

表示第t次迭代 第i点与后一个点的位置之差，x_t,i(p)表示第t次迭代第i个点的位置，ω是惯性 权重，表示的是前一时刻速度对当前速度的影响程度，r₁和r₂是0和1之间的随 机数。

进一步的，所述步骤S5在保证路径长度、路经困难度以及路径平滑度尽可 能最小的情况下，在更少的时间内规划出一条无碰最优或次优路径，具体包括：

S61:长度指标是指路径的总长度，如下式：

式中，|p_ip_i+1|是路径节点p_i到路径节点p_i+1的欧式距离，n表示一条可行路径中路径点的个数；

S62:平滑度指标是指路径中所有相邻矢量线段的角度之和，如下式：

其中θ(p_ip_i+1,p_i+1p_i+2)是相邻矢量线段

和

的夹角，0≤θ≤π，C₁是一个正 整数，S是一条路径中线段的数量；

S63:困难度指标是指机器人经过路径中每一个节点的困难指数之和，如下式：

其中x_i表示路径中第i个节点，d(x_i)表示机器人通过该节点的困难指数。

一种存储介质，该存储介质内部存储计算机程序，所述计算机程序被处理 器读取时，执行上述任一项的方法。

本发明的优点及有益效果如下：

尽管求解多约束条件下遗传算法的方法正在进一步的研究，但仍然存在一些 问题。关于路径点的生成，许多研究都是通过在自由空间中随机散布点或在网 格地图中考虑所有点来生成点。这些方法存在这样的问题，即在路径生成阶段 必须考虑对于最优路径而言不必要的点，这导致很高的计算成本，并且还可能 无法生成最优路径，因为这些生成的点在狭窄的或很小的空间内是不可用的。 本发明针对目前算法所存在的计算量大、搜索效率低且容易陷入局部最优的问 题，本文研究一种多约束条件下基于改进的遗传算法应用于机器人路径规划领 域。该改进方法采用了Surrounding Point Set(SPS)算法。根据栅格点地图模型中 相邻栅格点之间的距离和障碍物的位置确定每个障碍物的周围点；然后用深度 优先遍历得到从起始点到目标点之间的所有可行路径即初始种群，这样避免考 虑在路径生成阶段相对于最优路径而言不必要的点，减少最终解变化的可能性， 降低了计算成本。此外，本发明添加平滑算子和删除算子，加快种群的收敛速 度，从而能够在更少的时间内规划出一条最优或次优路径。

附图说明

图1是本发明提供优选实施例多约束条件下基于改进遗传算法的移动机器人路径规划流程图：

图2多约束条件下基于改进遗传算法的机器人行走仿真图；

图3是障碍物的长度和宽度增大了机器人宽度的r倍；

图4是添加删除算子的示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、 详细地描述。所描述的实施例仅仅是本发明的一部分实施例。

本发明解决上述技术问题的技术方案是：

本发明在静态障碍物的状态检测上利用激光传感器来实时扫描移动 机器人导航中环境信息，存入初始种群路径，再利用多约束条件下基于改 进遗传算法寻找一条耗费时间少，路径长度、路径困难度和路径平滑度都 尽可能小的路径。

本方法的主要步骤为：

S1：设置机器人起始点的位置坐标信息S(x,y)、目的地的位置坐标信息 T(x,y)以及行走区域的困难度；

S2：将障碍物的长度和宽度增大了机器人宽度的r倍(r>1/2)以确保机器人与 障碍物有绝对的安全距离；

S3：通过机器人的历史里程计数据与当前环境信息来判定当前机器人在全 局坐标系中的位姿；

S4，利用Surrounding Point Set(SPS)算法获取空间中各个静态障碍物的周围点，若周围点在障碍物内，则缩小相邻栅格点之间的距离；

S5，将障碍物两两相连并去除与障碍物相交的连线，并用深度优先遍历得 到从起始点到目标点的所有可行路径，即初始种群。利用多约束条件下的遗传 算法规划出一条从起始点S(x,y)到目标点T(x,y)的最优或次优路径，若到达迭代 次数，则执行S6，若没到达迭代次数，则更新种群继续迭代；

S6：开始执行并判断是否已经到达目的地坐标位置T(x,y)，若到达则结束导 航，若没有到达，则返回继续执行S4；

在进一步，步骤S2具体为：通过将障碍物的长度和宽度增大了机器人宽度 的r倍(r>1/2)以确保机器人与障碍物有绝对的安全距离；若增大后两个障碍物相 交，则视为一个障碍物，否则视为两个障碍物，若图3所示。

进一步，步骤S3具体为：通过机器人的历史里程计数据结合当前环境信息E_0i与地图环境模型进行匹配，定位当前机器人在全局坐标系中的位姿

根据E_ti与

判断t时刻环境中的障碍物的全局坐标为O_ti(X_ti,Y_ti)，满足：

其中，

表示起始时刻机器人在全局坐标系XOY中的位姿、x₀表示起始时 刻机器人在全局坐标系XOY中的横坐标、y₀表示起始时刻机器人在全局坐标系 XOY中的纵坐标、θ₀表示起始时刻机器人的位姿角度，(x_t,y_t)表示t时刻机器人 的全局坐标，d_0i表示第i个障碍物到机器的距离，θ_t表示机器人t时刻位姿角度， k表示障碍物和机器人位姿指向之间的夹角。

步骤S4具体为：

S41：定义障碍物的周围点：

在栅格点地图模型中，任意一个栅格点与其周围的8个点进行水平连接和 垂直连接，若障碍物碰到其中一条或几条连线，则该栅格点称为障碍物的周围 点，其余不在障碍物内的点称为临时点。

S42：产生周围点的过程：

Step1:创建周围点集和sps和临时点集和temp,并确定起始参考点p。通过将起始点与目标点连成直线与障碍物相交，离该交点最近的栅格点为起始参考点p，并 放入sps集合中，把与点p相邻的且不在障碍物内的点放入temp集合中。

Step2:依次迭代判断temp集合中的点是否为该障碍物的周围点(图四(b)中黑色点表示该点不是障碍物的周围点，红色的点表示是该障碍物的周围点)，若是， 则将该点放入sps集合中并移除temp集合中的该点，把与该点相邻的且不在障 碍物内的点放入temp集合中。若不是，则将该点从temp集合中移除即可。

Step3:在保证temp集合与sps集合没有重复点的前提下，重复步骤Step2，直到temp集合为空。

进一步，步骤S5具体为：

根据步骤S4得到的周围点集产生初始种群，并根据路径长度、路径困难度 以及路径平滑度三个目标函数得到Pareto最优解集，然后进行适应值计算，适 应值大的个体有更高的优先选择权进行配对，公式为：

其中x表示种群p中的任意一个个体，y表示距离x最近的Pareto最优解， ||x-y||₂表示x与y之间的欧氏距离。

进一步，选择：本文采用锦标赛法进行选择，即对种群中的个体进行随机 分组，每组根据个体的适应度值选择适应度值最低的个体进入子代种群。并采 用精英保留策略，按一定比例将适应度最优的个体不需要经过遗传直接复制到 子代种群。

交叉：采用单点交叉方式，即随机选择两个个体，找出路径相同点进行交叉， 这样可以保证路径的连续性，如果交叉后不是连续的路径，则将上半段的最后 一个点和下半段的第一个点作为起始点和目标点，运用障碍物的周围点集进行 修补使其成为一条连续的路径。

变异：研究的方法产生的初始是路径一定是可行的，且经过选择和交叉之 后亦是如此，所以本文对路径上点的坐标依据概率进行小范围调整即可，从而 保证变异后路径的可行性。

删除：如果一条路径中存在p_i,删除p_i后，p_i的前一个路径点p_i-1与后一个路 径点p_i+1相连后是可行路径段，则删除p_i。

平滑：该路径的平滑度算法是受到粒子群算法的启发，本文路径中的每个 坐标点相当于粒子群算法中的粒子的位置，根据该坐标点的前后坐标计算出粒 子的速度，根据位置更新公式和速度更新公式，计算出新的坐标点，经过多次 迭代后使路径更平滑。

位置更新公式和速度更新公式如下：

其中

表示第t次迭代第i点与前一个点的位置之差，

表示第t次 迭代第i点与后一个点的位置之差，x_t,i(p)表示第t次迭代第i个点的位置，ω是 惯性权重，表示的是前一时刻速度对当前速度的影响程度，r₁和r₂是0和1之间 的随机数。

然后产生子代种群，用小生境法保持种群的多样性，计算子代个体的适应 度值，更新最优解，若没有到达迭代次数，则子代种群替代旧种群，重复步骤 S5；若到达迭代次数，则判断是否到达目的地，若没有，则返回步骤S4，若到 达目的地，则结束导航。

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范 围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或 修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。

Claims (9)

1.一种基于改进遗传算法的移动机器人路径规划方法，其特征在于，包括以下步骤：

S1，建立栅格点地图模型，并设置机器人起始点的位置坐标信息S(x,y)、目的地的位置坐标信息T(x,y)以及赋予每个栅格点一个属性值表示行走的困难度；

S2，运用障碍物膨胀法对障碍物进行膨胀，膨胀范围是机器人宽度的r倍，若膨胀之后两个障碍物相交则视为一个障碍物以确保机器人与障碍物有绝对的安全距离，r>1/2；

S3，判定当前机器人在全局坐标系中的初始位姿；

S4，利用SPS算法获取空间中各个静态障碍物的周围点，若周围点在障碍物内，则缩小相邻栅格点之间的距离；

S5，将获得的障碍物周围点两两相连并去除与障碍物相交的连线，并用深度优先遍历得到从起始点到目标点的所有可行路径，即初始种群；然后增加删除算子、平滑算子优化生成的路径；最后引入小生境法来保持种群多样性。若到达迭代次数，则执行S6，若没达到迭代次数，则更新种群继续迭代；

S6：开始执行并判断是否已经到达目的地坐标位置T(x,y)，若到达则结束导航，若没有到达，则返回继续执行S4。

2.根据权利要求1所述的一种基于改进遗传算法的移动机器人路径规划方法，其特征在于，所述步骤S2将运用障碍物膨胀法对障碍物进行膨胀，膨胀范围是机器人宽度的r倍，具体为：对机器人工作空间中的栅格点赋予另一个属性值并用布尔值标识，标识该栅格点是否在障碍物内，具体标识：

式中，P_mn为栅格点标识符，M_mn为与P_mn对应栅格点的布尔值，m为栅格点对应的行，n为栅格点对应的列，T表示P_mn在障碍物内，F表示P_mn不在障碍物内，A表示P_mn为自由栅格点，B表示P_mn为威胁栅格点，障碍物膨胀法引入了虚拟障碍集合C，对障碍物周围的相邻栅格进行扩展，当相邻栅格以P_Nb表示时，扩展依据以下原则：

if P_Nb∈A,thenP_Nb∈C,M_Nb＝F

if P_Nb∈B,thenP_Nb∈C,M_Nb＝F

根据障碍物膨胀法和相邻栅格点之间的距离将障碍物膨胀为机器人宽度的r倍以确保机器人与障碍物有绝对的安全距离，r>1/2，若增大后两个障碍物相交，则视为一个障碍物，否则视为两个障碍物。

3.根据权利要求1所述的一种基于改进遗传算法的移动机器人路径规划方法，其特征在于，所述步骤S3判定当前机器人在全局坐标系中的初始位姿，具体为：通过机器人的历史里程计数据结合当前环境信息E_0i与地图环境模型进行匹配，定位当前机器人在全局坐标系中的位姿：

根据E_ti与

判断t时刻环境中的障碍物的全局坐标为O_ti(X_ti,Y_ti)，满足：

其中，

表示起始时刻机器人在全局坐标系XOY中的位姿、x₀表示起始时刻机器人在全局坐标系XOY中的横坐标、y₀表示起始时刻机器人在全局坐标系XOY中的纵坐标、θ₀表示起始时刻机器人的位姿角度，(x_t,y_t)表示t时刻机器人的全局坐标，d_0i表示第i个障碍物到机器的距离，θ_t表示机器人t时刻位姿角度，k表示障碍物和机器人位姿指向之间的夹角。

4.根据权利要求1所述的一种基于改进遗传算法的移动机器人路径规划方法，其特征在于，步骤S4利用Surrounding Point Set(SPS)算法获取空间中各个静态障碍物的周围点，若周围点在障碍物内，则缩小相邻栅格点之间的距离，具体步骤为：

S41：定义障碍物的周围点、临时点；

在栅格点地图模型中，任意一个栅格点与其周围的8个点进行水平连接和垂直连接，若障碍物碰到其中一条或几条连线，则该栅格点称为障碍物的周围点，其余不在障碍物内的点称为临时点；

S42：产生周围点的步骤：

Step1:创建周围点集和sps和临时点集和temp,并确定起始参考点p，通过将起始点与目标点连成直线与障碍物相交，离该交点最近的栅格点为起始参考点p，并放入sps集合中，把与点p相邻的且不在障碍物内的点放入temp集合中；

Step2:依次迭代判断temp集合中的点是否为该障碍物的周围点，若是，则将该点放入sps集合中并移除temp集合中的该点，把与该点相邻的且不在障碍物内的点放入temp集合中，若不是，则将该点从temp集合中移除即可；

Step3:在保证temp集合与sps集合没有重复点的前提下，重复步骤Step2，直到temp集合为空。

5.根据权利要求4所述的一种基于改进遗传算法的移动机器人路径规划方法，其特征在于，所述步骤S5根据周围点，利用多约束条件下的遗传算法规划出一条从起始点S(x,y)到目标点T(x,y)的最优或次优路径，具体为：

S51：产生初始路径；

S52：添加删除算子：如果一条路径中存在一个路径点p_i,若删除p_i，p_i的前一个路径点p_i-1与后一个路径点p_i+1相连后是可行路径段，则删除p_i；

S53:添加平滑算子：路径中的每个坐标点相当于粒子群算法中的粒子的位置，根据坐标点的前后坐标计算出粒子的速度，根据位置更新公式和速度更新公式，计算出新的坐标点，经过多次迭代后使路径更平滑；

S54:选择算子：采用锦标赛法进行选择，即对种群中的个体进行随机分组，每组根据个体的适应度值选择适应度值最低的个体进入子代种群，并采用精英保留策略，按一定比例将适应度最优的个体不需要经过遗传直接复制到子代种群；

S55:交叉算子：采用单点交叉方式，即随机选择两个个体，找出路径相同点进行交叉，这样可以保证路径的连续性，如果交叉后不是连续的路径，则将上半段的最后一个点和下半段的第一个点作为起始点和目标点，运用障碍物的周围点集进行修补使其成为一条连续的路径；

S56:变异算子：对路径上点的坐标依据概率进行小范围调整，从而保证变异后路径的可行性。

6.根据权利要求5所述的一种基于改进遗传算法的移动机器人路径规划方法，其特征在于，所述步骤S51产生初始路径的步骤具体为；

Step1:让机器人从起始点出发沿直线走到目标点，如果中途碰到障碍物，会根据SPS算法在障碍物的周围产生周围点集；

Step2:运用Dijkstra算法测试该障碍物的周围是否有可行路径，如果有，则沿着可行路径继续往前走；

Step3:如果没有可行路径，则减小栅格点之间的宽度，重复Step1和Step2。

7.根据权利要求5所述的一种基于改进遗传算法的移动机器人路径规划方法，其特征在于，所述步骤S53的位置更新公式和速度更新公式如下：

其中

表示第t次迭代第i点与前一个点的位置之差，

表示第t次迭代第i点与后一个点的位置之差，x_t,i(p)表示第t次迭代第i个点的位置，ω是惯性权重，表示的是前一时刻速度对当前速度的影响程度，r₁和r₂是0和1之间的随机数。

8.根据权利要求5所述的一种基于改进遗传算法的移动机器人路径规划方法，其特征在于，所述步骤S5在保证路径长度、路经困难度以及路径平滑度尽可能最小的情况下，在更少的时间内规划出一条无碰最优或次优路径，具体包括：

S61:长度指标是指路径的总长度，如下式：

其中|p_ip_i+1|是路径节点p_i到路径节点p_i+1的欧式距离，n表示一条可行路径中路径点的个数；

S62:平滑度指标是指路径中所有相邻矢量线段的角度之和，如下式：

其中θ(p_ip_i+1,p_i+1p_i+2)是相邻矢量线段

和

的夹角，0≤θ≤π，C₁是一个正整数，S是一条路径中线段的数量；

S63:困难度指标是指机器人经过路径中每一个节点的困难指数之和，如下式：

其中x_i表示路径中第i个节点，d(x_i)表示机器人通过该节点的困难指数。

9.一种存储介质，该存储介质内部存储计算机程序，其特征在于，所述计算机程序被处理器读取时，执行上述权利要求1～8任一项的方法。

Images