本发明涉及无人车路径规划，具体是指一种基于改进a-star的运输无人车路径规划方法。
背景技术：
1、近年来，无人车通过人机协同，实现了末端配送的降本增效。工作人员只需要负责调度,便可让无人车在配送点和接驳站之间实现零接触、多功能、全天候的服务运转。无人车在复杂路面执行作业，安全可靠的路径规划是其实现无人运输的重要环节之一。无人车系统主要包括感知、预测、规划和控制4个模块，其中规划模块负责基于目标任务生成最优路径。按照搜索方式可将路径规划算法分为基于图搜索、基于采样及基于人工智能的方法。其中，基于图搜索的a-star算法因其寻优能力强、场景适应度高等特性而得到广泛应用。
2、搜索效率和路径安全性及可行性是规划算法的核心,但a-star算法多循环判断机制导致其路径最优和计算效率难以同时得到有效改善。因此,本文提出一种改进a-star算法。
3、现有技术存在的问题和缺点：
4、1、目前，较多无人车使用的是传统的算法，例如人工势场法、a-star、快速扩展随机树和dijkstra算法。
5、2、人工势场法的缺点在于容易陷入局部最优：在某个点，引力和斥力刚好大小相等，方向相反，则物体容易陷入局部最优解或震荡。而且当目标点附近存在障碍物时，靠近目标点的同时也靠近障碍物，但会因为越接近目标点，障碍物斥力的增加大于目标点的引力而使驾驶车辆永远无法到达目标点。在许多实际环境中，往往至少有一个障碍物与目标点离的很近。
6、3、dijkstra算法的缺点则在于在dijkstra算法的应用过程中，某些有权图的边可能为负，也就是说，即使有权图中并不包含可以从节点到达的负权回路，dijkstra算法依然是可以继续应用的，但是假如存在一个可以直接从节点到达的负回路，那么算法将无法进行操作，最短路径的权也无法成立，使得最短路径无法找到。
7、4、传统a-star算法是路径规划算法中较为经典的启发式搜索算法，将其应用到无人车的实际运行中，暴露了传统a-star算法在路径搜索上的不足，在这种搜索方式下，规划的路径拐点较多，不利于无人车的正常移动，而且随着地图规模的扩大，搜索效率明显降低。
8、申请人在进行无人车路径算法优化的研究时，发现无人车作业场景错综复杂，在如此场景下进行无人车的路径规划，无人车行驶作业的自主性与环境适应性是需要着重考虑优化的指标，为了提升规划方法在这些指标下的性能，需要解决以下问题：
9、(1)、对启发函数和权重系数进行优化，因为无人车可以沿着任意角度移动(而不是网格方向)，那么应该使用直线距离，本专利中选择的是欧几里得距离，并加入了权重系数；动态衡量启发式:f(n)＝g(n)+w(n)*h(n)，其中w(n)>＝1。与传统的a-star算法不同的是，原本的h(n)，变成了w(n)*h(n),w(n)可以影响评估值。在搜索过程中，我们可以通过改变w(n)来影响搜索过程如上面提到的h(n)对a-star算法的影响。可以推理出，w(n)越大，越趋近于bfs算法，而w(n)相对越小，则相对于趋近于dijkstra算法。
10、(2)、对无人车路径进行平滑处理，转弯处需要避免拐点，为无人车规划较为平缓的路线，解决传统a-star算法给无人机规划的弯折路径，容易造成路线偏移的问题，使得无人车可更快速平稳地跟踪路径并到达目标点。其中的技术难点在于如何规划一条相对距离短，路线平缓，可以保障无人车效率与安全的路线；
11、(3)、优化open表:传统的open表，因为程序设计语言的不同，可能选择的是:array、list、queue等等结构来存储。a-star算法搜索过程中设置两个表:open和close。open表保存了所有已生成而未考察的节点，close表中记录已访问过的节点。而在a-star搜索过程中，搜索深度增加意味着可能要查找的节点越多，因此后期open表中存储的节点越点。在数据结构的选择上，我们希望所选择的节点带有“可参照性”，而不是单单的直接从open表中取。如果open表在放入数据之前，就让它按照一定顺序，那么从open表中取数据时，这些数据就是具备顺序的，是有“可参照性的”。可以选择二叉堆优化的方式。
技术实现思路
1、本发明要解决的技术问题是克服以上技术缺陷，提供一种基于改进a-star的运输无人车路径规划方法，提高无人车运输效率的一种改进a-star算法的无人车路径规划方法。改进后算法规划的路径更加平滑，无人车行进效率更高。
2、为解决上述技术问题，本发明提供的技术方案为：一种基于改进a-star的运输无人车路径规划方法，步骤可以分为：
3、s1、确定无人车初始点、目标点以及障碍物位置：
4、根据无人车所在环境进行栅格地图建模，确定无人车初始点、目标点以及障碍物位置；
5、s2、计算距离代价值
6、根据步骤s1中无人车初始点，对无人车可移动的八个方向进行搜寻，计算八个扩展点到目标点的距离代价值；
7、s3、搜索初始路径
8、根据步骤s1、s2得到了初始优化的路径，利用a-star算法在栅格地图中搜索出一条隔离障碍物，选择方向之后的初始路径；
9、s4、初始路径的平滑处理
10、对步骤s3的初始路径，采用二阶贝塞尔曲线对路径进行平滑处理；
11、s5、路径规划判断环境是否改变，对步骤(4)平滑处理后的路径进行更新，得到最终规划完成的路径。
12、作为优选的技术方案，步骤s1中，首先初始化算法，建立open表和close表，根据无人车所在环境建立栅格化地图模型，具体步骤为：
13、(1)将地图分割为由若干个大小相同的正方形组成的有界区域，每一个网格称为一个单元，每个单元位置坐标为(xp，yq)，其中p，q为地图横、纵向栅格序数；
14、(2)用一条直线在固定方向扫描栅格地图；
15、(3)当扫描线扫入时，确认无人车初始位置坐标、目标位置坐标以及障碍物位置坐标；
16、(4)本方法中，对a-star算法的open列表使用最小二叉堆进行优化，通过二叉堆优化法可以实现对open表的优化，根据所算出的值对open表内的节点进行排序，将提高算法的查找速度。
17、作为优选的技术方案，步骤s2中，根据步骤s1中所述的无人车初始点，对无人车使用八向搜寻法进行计算，算出八个扩展点到目标点的路径成本。
18、作为优选的技术方案，步骤s3的具体步骤如下：根据上一步计算出来的值，选择扩展点中路径成本f(n)最小的为扩展方向，并生成初步规划的路径；
19、作为优选的技术方案，步骤s4中，在所述路径基础上，通过贝塞尔曲线，对路径进行平滑处理，具体步骤包括：
20、(1)高阶贝塞尔曲线的数值稳定性较差，故在此采用二阶贝塞尔曲线的方法实现路径平滑处理；二阶贝塞尔曲线公式如下所示：
21、b(t)＝(1-t)2p0+2t(1-t)p1+t2p2，t∈[0，1]；
22、二阶贝塞尔曲线将会经过第1、3个控制点。曲线在端点切向量表达式如下：
23、b(t)＝-2p0(1-t)+2p1(1-2t)+2tp2，t∈[0，1]；
24、贝塞尔曲线上任意一点的曲率为：
25、
26、贝塞尔曲线轨迹起始点曲率为：
27、
28、(2)通过二阶贝塞尔曲线上曲率可知，路径轨迹曲线连续条件为x′(t)、y′(t)不同时为0，贝塞尔曲线具有以下性质:拟合曲线的起始点和终止点与被平滑化处理的折线的起始点和终止点重合；折线点一旦确定，拟合曲线唯一。贝塞尔曲线平滑处理后，使生成路径与折线相比更贴近实际，更适合无人车的实际运行。
29、作为优选的技术方案，步骤s5中，判断环境是否改变主要是判别规划路径中当前位置的下一段路径周围障碍物是否有变化，有变化则需要重新进行路径规划。
30、有益效果，本发明与现有的技术相比的优点在于：本发明提出的改进a-star算法，通过对open列表使用二叉堆优化提高了算法的查找速度，考虑到无人车移动因频繁转向而发生抖动，对传统a-star算法路径进行贝塞尔曲线平滑优化。减少了路径转折点的同时提高了无人车在复杂外部环境中的行进安全性，此外还减小了路径总长度，使整体路径更加平滑，使得无人车能更好地绕过障碍物，提高了规划效率。
1.一种基于改进a-star的运输无人车路径规划方法，步骤可以分为：
2.根据权利要求1所述的一种基于改进a-star的运输无人车路径规划方法，其特征在于：步骤s1中，首先初始化算法，建立open表和close表，根据无人车所在环境建立栅格化地图模型，具体步骤为：
3.根据权利要求1所述的一种基于改进a-star的运输无人车路径规划方法，其特征在于：步骤s2中，根据步骤s1中所述的无人车初始点，对无人车使用八向搜寻法进行计算，算出八个扩展点到目标点的路径成本。
4.根据权利要求1所述的一种基于改进a-star的运输无人车路径规划方法，其特征在于：步骤s3的具体步骤如下：根据上一步计算出来的值，选择扩展点中路径成本f(n)最小的为扩展方向，并生成初步规划的路径。
5.根据权利要求1所述的一种基于改进a-star的运输无人车路径规划方法，其特征在于：步骤s4中，在所述路径基础上，通过贝塞尔曲线，对路径进行平滑处理，具体步骤包括：
6.根据权利要求1所述的一种基于改进a-star的运输无人车路径规划方法，其特征在于：步骤s5中，判断环境是否改变主要是判别规划路径中当前位置的下一段路径周围障碍物是否有变化，有变化则需要重新进行路径规划。
