一种基于改进A星算法的无人船路径规划方法

一种基于改进a星算法的无人船路径规划方法
技术领域
1.本发明涉及移动机器人路径规划领域，特别是涉及到一种基于改进a星算法的无人船路径规划方法。

背景技术：

2.路径规划技术是移动机器人实现自主导航与避障的一项重要技术，近年来取得很多与之相关的研究成果。原理是指机器人在工作环境中，根据自身传感器对环境的感知，自行规划出一条从起点到目标点的最优或接近最优的路径，使得机器人能够避开工作环境中的障碍物，安全、高效地到达终点。
3.a*算法是一种具有启发式特征的全局路径搜索算法，集中了dijkstra算法和最佳优先搜索算法的优点，具有简单高效、灵活性强和准确性高的特点，被广泛应用于全局路径规划当中。但传统a*算法在评估过程中会把大量的访问点置于openlist，利用f(n)对其进行代价估计并排序。如果无人船所处水域环境较大，规划路径较长，那么置于openlist中的点会特别多，使得评估函数的计算量巨大，openlist点的储存以及排序也会变得更复杂，导致路径规划效率不理想，而且算法所规划的最终路径虽然是最优路径，但在一些转向处或栅格连接处会有转角过大或者违反无人船运动规律的情况出现，不利于或导致无人船无法正常行驶。需要进行进一步优化。
4.传统a*算法虽然能够到众多路径中的最短路径，但也仍然存在一些缺陷需要进行改进。因此，针对a*算法大量不必要节点的计算以及转角处违反无人船运动学规律的缺陷，研究一种能够提升无人船的路径规划性能的路径规划方法十分必要。

技术实现要素：

5.为解决上述问题，本发明公开了为了解决上述存在问题。本发明提供一种基于改进a星算法的无人船路径规划方法，引入方位角代价，降低总搜索路径点，提高搜索效率，并在规划路径的基础上进行二次优化，在保证安全距离的同时使得路径更加精简平滑。
6.本发明提供一种基于改进a星算法的无人船路径规划方法，具体包括以下步骤：
7.步骤s1：利用语义分割结果所得到的环境信息建立栅格地图，每个栅格被标记为可行区域或障碍区域，并给定路径规划的起始点b和目标点g；
8.步骤s2：引入方位角代价优化代价函数f(n)，降低总搜索路径点，提高搜索效率；
9.步骤s3：对改进后的a*算法寻路结果进行剪枝与b样条曲线优化，降低路径总长度的同时使得行驶路径更加平缓；
10.步骤s4：添加碰撞检测功能，为无人船与障碍物之间预留足够的安全距离。
11.进一步地，所述步骤s2中，引入方位角代价value,方位角代价的原理为通过当前节点与起点中点连线(bg)的角度获取一个动态参数value，设起点终点向量为根据搜索节点与终点向量收敛于的程度来调整参数value的大小以改变移动时所消耗的代价，
使搜索路径向终点收敛。优化代价函数f(n)：
12.f(n)＝value
×
g(n)
×
a+h(n)
×
b(1)
13.其中value即为当前搜索点的方向角代价，a为[0.4,0.6]之间的小数且a、b满足关系式a＝1-b。对于当前搜索节点c点而言，相较于的方向角为θ，则方位角满足：
[0014][0015]
最终得到方位角代价系数：
[0016][0017]
进一步地，所述步骤s3中，对保存了原始的n行2列的矩阵路径进行循环遍历，首先选中第一个点，设为o，接着从最后一个轨迹点向前循环遍历，设该点到o点的距离为l，首先计算该点与o点间的斜率，并从当前节点由1至l增加该斜率方向的长度，如果在延伸过程中碰到障碍物则保留该点进入下次循环，若两点直线上不存在障碍物，则将该点删除。最终所剩的点即为在a*算法基础上剪枝所得距离最短的节点。
[0018]
接着采用b样条曲线的这些优点来完成路径点的后期拟合，以生成光滑路径。设一共有n+1个控制点，这些控制点用于定义样条曲线的走向、界限范围，则k阶b样条曲线的定义为:
[0019][0020]
其中，b
i,k
(u)是第i个k阶b样条基函数，与控制点相对应，k≥1；u是自变量，基函数有以下推导式:
[0021][0022][0023]
选择准均匀b样条曲线，k＝3，将起始点和目标点都设置为3重节点。
[0024]
进一步地，所述步骤s4中，对路径点与障碍物之间设定一个最短距离d
min
，设路径点与最近障碍之间距离为h，若h《d
min
，则向与最近障碍点的反向延长线移动，直到抵达安全距离之外再按照原有的规划方法继续搜索。
[0025]
与现有方法相比，本发明具有如下优点和有益效果：
[0026]
(1)在移动函数中添加方位角代价，使路径规划方向更具有目的性，很大程度上减少了open表存储节点的个数，降低了open表占据的存储空间，提高算法寻路效率。
[0027]
(2)对规划路径弯曲过多以及违反运动学规律的问题，结合优化后算法进行路径剪枝与b样条平滑，有效的解决了传统a*算法在栅格地图上进行路径规划时，得到的路径长
度不是最优以及转折点较多的问题，更加适合无人船运行。
[0028]
(3)在规划路径的过程中添加了碰撞检测功能，避免无人船在运行时与障碍物发生碰撞，保障无人船运行时的安全。
附图说明
[0029]
图1为本发明的流程示意图；
[0030]
图2是方位角代价的原理图；
[0031]
图3是本发明方法与传统a*算法所规划路径以及总搜索点的仿真结果；
[0032]
图4是本发明算法搜索路径与二次优化后路径的仿真结果对比；
[0033]
图5是本发明添加碰撞检测后路径与添加前规划路径的仿真结果对比。
具体实施方式
[0034]
下面结合附图和具体实施方式，进一步阐明本发明，应理解下述具体实施方式仅用于说明本发明而不用于限制本发明的范围。需要说明的是，下面描述中使用的词语“前”、“后”、“左”、“右”、“上”和“下”指的是附图中的方向，词语“内”和“外”分别指的是朝向或远离特定部件几何中心的方向。
[0035]
本发明提供一种基于改进a星算法的无人船路径规划方法，具体包括以下步骤：
[0036]
步骤s1：利用语义分割结果所得到的环境信息建立栅格地图，每个栅格被标记为可行区域或障碍区域，并给定路径规划的起始点b和目标点g；
[0037]
步骤s2：引入方位角代价优化代价函数f(n)，降低总搜索路径点，提高搜索效率；
[0038]
步骤s3：对改进后的a*算法寻路结果进行剪枝与b样条曲线优化，降低路径总长度的同时使得行驶路径更加平缓；
[0039]
步骤s4：添加碰撞检测功能，为无人船与障碍物之间预留足够的安全距离。
[0040]
步骤s2中，引入方位角代价value,原理如图2所示，通过当前节点与起点中点连线(bg)的角度获取一个动态参数value，设起点终点向量为根据搜索节点与终点向量收敛于的程度来调整参数value的大小以改变移动时所消耗的代价，使搜索路径向终点收敛。如图所示，在基础的栅格图中，对于当前搜索节点c来说，向上移动的代价与向右移动的代价都是10，但是向上移动到c1能够更便捷的到达目标点，因为相较于c2而言向量与起点终点向量的向量角θ1低于与的向量角θ2，即前者更加收敛于起点终点的连接线，为此，需要对收敛于的搜索方向予以激励。优化后代价函数f(n)：
[0041]
f(n)＝value
×
g(n)
×
a+h(n)
×
b(1)
[0042]
其中value即为当前搜索点的方向角代价，a为[0.4,0.6]之间的小数且a、b满足关系式a＝1-b。对于当前搜索节点c点而言，相较于的方向角为θ，则方位角满足：
[0043][0044]
最终得到方位角代价系数：
[0045][0046]
图2中，浅灰为搜索过的节点，深灰为最终规划路径，黑为障碍物。可以看出，添加方位角代价之后的a*算法极大的降低了寻路过程中的搜索点数，提高了搜索效率，降低了搜索时间。
[0047]
步骤s3中，对保存了原始的n行2列的矩阵路径进行循环遍历，首先选中第一个点，设为o，接着从最后一个轨迹点向前循环遍历，设该点到o点的距离为l，首先计算该点与o点间的斜率，并从当前节点由1至l增加该斜率方向的长度，如果在延伸过程中碰到障碍物则保留该点进入下次循环，若两点直线上不存在障碍物，则将该点删除。最终所剩的点即为在a*算法基础上剪枝所得距离最短的节点。
[0048]
接着采用b样条曲线的这些优点来完成路径点的后期拟合，以生成光滑路径。设一共有n+1个控制点，这些控制点用于定义样条曲线的走向、界限范围，则k阶b样条曲线的定义为:
[0049][0050]
其中，b
i,k
(u)是第i个k阶b样条基函数，与控制点相对应，k≥1；u是自变量，基函数有以下推导式:
[0051][0052][0053]
b样条曲线公式中的k值代表曲线的平滑度，k值越大，曲线的平滑度越高，但计算复杂度也越高；k值过小，曲线的平滑度就差。为兼顾无人船轨迹的平滑度以及计算复杂度，选择三阶b样条曲线选择准均匀b样条曲线，令k值为3，将起始点和目标点都设置为3重节点。
[0054]
改进后结果与原结果的对比如图4所示，可以看出，优化后的路径更短且更加平滑。
[0055]
步骤s4中，对路径点与障碍物之间设定一个最短距离d
min
，设路径点与最近障碍之间距离为h，若h《d
min
，则向与最近障碍点的反向延长线移动，直到抵达安全距离之外再按照原有的规划方法继续搜索。结果如图5所示，优化后路径为无人船预留出了足够的安全空间。
[0056]
本发明方案所公开的技术手段不仅限于上述实施方式所公开的技术手段，还包括
由以上技术特征任意组合所组成的技术方案。

技术特征：

1.一种基于改进a星算法的无人船路径规划方法，其特征在于，该方法包括如下步骤：步骤s1：利用语义分割结果所得到的环境信息建立栅格地图，每个栅格被标记为可行区域或障碍区域，并给定路径规划的起始点b和目标点g；步骤s2：引入方位角代价优化代价函数f(n)，降低总搜索路径点，提高搜索效率；步骤s3：对改进后的a*算法寻路结果进行剪枝与b样条曲线优化，降低路径总长度的同时使得行驶路径更加平缓；步骤s4：添加碰撞检测功能，为无人船与障碍物之间预留足够的安全距离。2.根据权利要求1所述的一种基于改进a星算法的无人船路径规划方法，其特征在于：所述步骤s2具体包括以下过程：引入方位角代价value,方位角代价的原理为通过当前节点与起点与终点连线(bg)的角度获取一个动态参数value，设起点终点向量为根据搜索节点与终点向量收敛于的程度来调整参数value的大小以改变移动时所消耗的代价，使搜索路径向终点收敛；优化代价函数f(n)：f(n)＝value
×
g(n)
×
a+h(n)
×
b(1)其中value即为当前搜索点的方向角代价，a为[0.4,0.6]之间的小数且a、b满足关系式a＝1-b；对于当前搜索节点c点而言，相较于的方向角为θ，则方位角满足：最终得到方位角代价系数：3.根据权利要求1所述的一种基于改进a星算法的无人船路径规划方法，其特征在于：所述步骤s3具体包括以下过程：对保存了原始的n行2列的矩阵路径进行循环遍历，首先选中第一个点，设为o，接着从最后一个轨迹点向前循环遍历，设该点到o点的距离为l，首先计算该点与o点间的斜率，并从当前节点由1至l增加该斜率方向的长度，如果在延伸过程中碰到障碍物则保留该点进入下次循环，若两点直线上不存在障碍物，则将该点删除；最终所剩的点即为在a*算法基础上剪枝所得距离最短的节点；接着采用b样条曲线的这些优点来完成路径点的后期拟合，以生成光滑路径；设一共有n+1个控制点，这些控制点用于定义样条曲线的走向、界限范围，则k阶b样条曲线的定义为:其中，b
i,k
(u)是第i个k阶b样条基函数，与控制点相对应，k≥1；u是自变量，基函数有以下推导式:
选择准均匀b样条曲线，k＝3，将起始点和目标点都设置为3重节点。4.根据权利要求1所述的一种基于改进a星算法的无人船路径规划方法，其特征在于：所述步骤s4具体包括以下过程：对路径点与障碍物之间设定一个最短距离d
min
，设路径点与最近障碍之间距离为h，若h<d
min
，则向与最近障碍点的反向延长线移动，直到抵达安全距离之外再按照原有的规划方法继续搜索。

技术总结

本发明公开一种基于改进A星算法的无人船路径规划方法，包括以下步骤：步骤S1：利用语义分割结果所得到的环境信息建立栅格地图，每个栅格被标记为可行区域或障碍区域，并给定路径规划的起始点B和目标点；步骤S2：引入方位角代价优化代价函数，降低总搜索路径点，提高搜索效率；步骤S3：对改进后的A*算法寻路结果进行剪枝与B样条曲线优化，降低路径总长度的同时使得行驶路径更加平缓；步骤S4：添加碰撞检测功能，为无人船与障碍物之间预留足够的安全距离。本发明引入方位角代价对传统A*算法的代价函数进行优化，对改进后的A*算法寻路结果进行剪枝与B样条曲线优化，降低路径总长度的同时使得行驶路径更加平缓。同时使得行驶路径更加平缓。同时使得行驶路径更加平缓。