一种基于改进A*算法和贝塞尔曲线的全局路径规划方法

摘要

本发明公开一种基于改进A*算法和贝塞尔曲线的全局路径规划方法，具体包括以下步骤：步骤S1：利用激光雷达传感器采集的环境信息建立栅格地图，每个栅格被标记为可行区域或障碍区域，并给定路径规划的起始点S和目标点G；步骤S2：引入动态调整因子μ优化代价函数f(N)；步骤S3：将搜索邻节点范围扩大为24邻域，执行改进的A*算法，找出最优路径；步骤S4：去除路径中的共线节点；步骤S5：利用贝塞尔曲线对路径进行平滑处理。本发明将传统A*算法8邻域搜索范围扩大为24邻域，引入动态调整因子μ优化代价函数，提高了算法搜索效率，利用贝塞尔曲线对路径进行平滑处理，减少了折弯次数，相比传统A*算法，路径更平滑，路径规划效率更高且更可靠。

说明书

技术领域

本发明涉及移动机器人路径规划领域，特别是涉及到一种基于改进A*算法和贝塞尔曲线的全局路径规划方法。

背景技术

根据外部环境信息是否已知，路径规划算法分为全局路径规划算法和局部路径规划算法；根据算法的搜索方式，可分为盲目式搜索和启发式搜索算法。A*算法是一种具有启发式特征的全局路径搜索算法，集中了Dijkstra算法和最佳优先搜索算法的优点，具有简单高效、灵活性强和准确性高的特点，被广泛应用于全局路径规划当中。但传统A*算法8邻域搜索的方法，限制了节点的运动方向只能为0.25π整数倍，容易出现不是最短路径且存在冗余节点和路径拐点过多的问题。启发函数h(N)的选择，直接影响路径搜索结果，当靠近终点时，启发函数h(N)在代价函数f(N)中所占比例减小,算法搜索效率就会降低，但是h(N)比重过高时，又会造成在路径搜索初期的搜索空间过小，难以找到最优解。

发明内容

为了解决上述存在问题。本发明提供一种基于改进A*算法和贝塞尔曲线的全局路径规划方法，该方法将传统A*算法8邻域搜索范围扩大为24邻域，引入动态调整因子μ优化代价函数，提高了算法搜索效率，同时利用贝塞尔曲线进行路径平滑处理，进一步减少了多余的路径节点。

本发明提供一种基于改进A*算法和贝塞尔曲线的全局路径规划方法，具体包括以下步骤：

步骤S1：利用激光雷达传感器采集的环境信息建立栅格地图，每个栅格被标记为可行区域或障碍区域，并给定路径规划的起始点S和目标点G；

步骤S2：引入动态调整因子μ优化代价函数f(N)；

步骤S3：将搜索邻节点范围扩大为24邻域，执行改进的A*算法，找出最优路径；

步骤S4：去除路径中的共线节点；

步骤S5：利用贝塞尔曲线对路径进行平滑处理。

进一步，所述步骤S2具体包括以下过程：

引入动态调整因子μ优化代价函数f(N)：

f(N)＝g(N)+μ·h(N)

其中，(x

进一步，所述步骤S3具体包括以下过程：

S3.1分别构建开放列表OPEN表和关闭列表CLOSE表，其中OPEN表存放待检测节点，CLOSE表存放检测过或者不需要检测的节点，并将起始节点放入OPEN表；

S3.2遍历OPEN表，查找代价函数f值最小的节点作为要处理的当前节点N，并将当前节点N从OPEN表删除，添加到CLOSE表；

S3.3对当前节点N的24邻域搜索可行邻节点，跳过已在CLOSE表中的节点。当前节点N的24邻域即当前节点N的下一个可到达节点的区域，可表示为(x±2，y±2)，x为当前节点在栅格地图中的横坐标，y为当前节点在栅格地图中的纵坐标；

S3.4判断当前节点N的邻节点是否为目标点G，若是，从目标点开始逐步追踪父节点，直至达到起始点，连线这些节点即为找到的路径，若否，则进行以下步骤；

S3.5若邻节点在OPEN表中，判断经由当前的节点的实际移动代价函数g值是否更小，若是，则将当前节点设为其父节点，并更新代价函数f值；若邻节点不在OPEN表中，则将其加入OPEN表，并将当前节点设为其父节点；

S3.6循环步骤S3.2至S3.5，直到找到最优路径。

进一步，所述步骤S4具体包括以下过程：

对于路径中相邻的三个节点N

进一步，所述步骤S5具体包括以下过程：

S5.1对于路径中相邻的三个节点N

S5.2连接点A和点B，并在线段AB上找出一点C，使得AC/AB＝N

S5.3让选取的点A在线段N

与现有方法相比，本发明具有如下优点和有益效果：

(1)本发明将传统A*算法的8邻域节点搜索扩大为24邻域节点搜索。消除了移动机器人只可变换0.25π整数倍移动方向的约束，使得节点搜索的移动方向也增加到16个方向，提高了最短路径搜索精度和效率，且有效减少了转折点的个数。

(2)本发明引入动态调整因子优化了代价函数，随着路径搜索向目标点靠近，启发函数所占比重增大，增加了算法的快速收敛性，提高了搜索效率。

(3)本发明利用贝塞尔曲线方法有效平滑转折点，同时减少了路径长度，整体路径更加平滑，有效避免机器人在转弯处出现急加减速的状况，使得运动更加连贯。

附图说明

图1为本发明基于A*算法改进的全局路径规划方法的原理图；

图2是本发明消除共线节点的原理图；

图3是本发明贝塞尔曲线平滑路径的原理图。

具体实施方式

下面结合附图与具体实施方式对本发明作进一步详细描述：

本发明提供一种基于改进A*算法和贝塞尔曲线的全局路径规划方法，该方法将传统A*算法8邻域搜索范围扩大为24邻域，引入动态调整因子μ优化代价函数，提高了算法搜索效率，同时利用贝塞尔曲线进行路径平滑处理，进一步减少了多余的路径节点。

本发明所提供的一种基于改进A*算法和贝塞尔曲线的全局路径规划方法，实现原理如图1所示。在一个具体实施例中，其具体包括以下步骤：

步骤S1：利用激光雷达传感器采集的环境信息建立栅格地图，每个栅格被标记为可行区域或障碍区域，并给定路径规划的起始点S和目标点G；

步骤S2：引入动态调整因子μ优化代价函数f(N)。具体包括以下过程：

引入动态调整因子μ优化代价函数f(N)：

f(N)＝g(N)+μ·h(N)

其中，(x

步骤S3：将搜索邻节点范围扩大为24邻域，执行改进的A*算法，找出最优路径。具体包括以下过程：

S3.1分别构建开放列表OPEN表和关闭列表CLOSE表，其中OPEN表存放待检测节点，CLOSE表存放检测过或者不需要检测的节点，并将起始节点放入OPEN表；

S3.2遍历OPEN表，查找代价函数f值最小的节点作为要处理的当前节点N，并将当前节点N从OPEN表删除，添加到CLOSE表；

S3.3对当前节点N的24邻域搜索可行邻节点，跳过已在CLOSE表中的节点。当前节点N的24邻域即当前节点N的下一个可到达节点的区域，可表示为(x±2，y±2)，x为当前节点在栅格地图中的横坐标，y为当前节点在栅格地图中的纵坐标；

S3.4判断当前节点N的邻节点是否为目标点G，若是，从目标点开始逐步追踪父节点，直至达到起始点，连线这些节点即为找到的路径，若否，则进行以下步骤；

S3.5若邻节点在OPEN表中，判断经由当前的节点的实际移动代价函数g值是否更小，若是，则将当前节点设为其父节点，并更新代价函数f值；若邻节点不在OPEN表中，则将其加入OPEN表，并将当前节点设为其父节点；

S3.6循环步骤S3.2至S3.5，直到找到最优路径。

步骤S4：参照图2，去除路径中的共线节点。具体包括以下过程：

对于路径中相邻的三个节点N

步骤S5：参照图3，进一步，利用贝塞尔曲线对路径进行平滑处理。具体包括以下过程：

S5.1对于路径中相邻的三个节点N

S5.2连接点A和点B，并在线段AB上找出一点C，使得AC/AB＝N

S5.3让选取的点A在线段N

以上所述，仅是本发明的较佳实施例而已，并非是对本发明作任何其他形式的限制，而依据本发明的技术实质所作的任何修改或等同变化，仍属于本发明所要求保护的范围。