CN114995391A - 一种改进a*算法的4阶b样条曲线路径规划方法 - Google Patents

Abstract

本发明涉及一种改进A*算法的4阶B样条曲线路径规划方法，包括以下步骤：S1、采用栅格法创建机器人工作环境地图，定义起始点与目标点；S2、采用A*算法寻找环境最短路径，S3、将得到的路径进行B样条曲线处理，采用准均匀B样条曲线：两端节点具有重复度k+1，中间节点非递减的序列，如U＝{0,0,0,1,2,3,4,5,5,5}，准均匀B样条曲线保留了贝塞尔曲线在两个端点处的性质：样条曲线在端点处的切线即为倒数两个端点的连线，通过B样条曲线法得出新的路径。本发明的有益效果是，基于A*算法进行改进，在能够获得全局最优解的同时，结合B样条曲线法得到局部最优解，缩短了路径距离，提高了路径的光滑度。

Description

一种改进A＊算法的4阶B样条曲线路径规划方法

技术领域

本发明涉及路径规划技术领域，具体是一种改进A*算法的4阶B样条曲线路径规划方法。

背景技术

路径规划技术是移动机器人研究领域的一个重要组成部分，主要目的是在有障碍物的环境中，根据一定的准则(如路径最短，位置拐点最少，用时最短等)，寻求一条从起始位置节点到目标位置节点之间的最优或次优安全无碰路径。

路径规划技术的发展在一定程度上标志着机器人智能水平的高低，而路径规划方法的优劣直接影响路径规划效果。

目前，国内外许多专家学者都在致力于路径规划算法的研究，常用的优化算法主要有人工势场法、免疫算法、蚁群算法、神经网络、粒子群算法和遗传算法等。A*算法结合了贪心算法和Dijkstra算法，是一种启发式搜索算法。A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的最有效算法，广泛应用于室内机器人路径搜索、游戏动画路径搜索等。

发明内容

本发明的目的在于提供一种改进A*算法的4阶B样条曲线路径规划方法，该方法为结合全局路径规划算法的A*算法与局部路径规划算法的B样条曲线法得出路径，不仅提高了路径平滑效果，而且减少了传统A*算法得出的距离值。

本发明解决其技术问题所采用的技术方案是：

一种改进A*算法的4阶B样条曲线路径规划方法，包括以下步骤：

S1、采用栅格法创建机器人工作环境地图，定义起始点与目标点；

S2、采用A*算法寻找环境最短路径，所述A*算法包含以下步骤：

S21、把起点加入open list；

S22、重复如下过程：

S221、遍历open list，查找F值最小的节点，把它作为当前要处理的节点，然后移到close list中，其中F＝G+H，G代表的是从初始位置A沿着已生成的路径到指定待检测格子的移动开销，H指定待测格子到目标节点B的估计移动开销；

S222、对当前方格的8个相邻方格一一进行检查，如果它是不可抵达的或者它在close list中，忽略它，否则，做如下操作：

S2221、如果它不在open list中，把它加入open list，并且把当前方格设置为它的父亲；

S2222、如果它已经在open list中，检查这条路径(即经由当前方格到达它那里)是否更近，如果更近，把它的父亲设置为当前方格，并重新计算它的G和F值；

S223、遇到下面情况停止搜索：

S2231、把终点加入到了open list中，此时路径已经找到了，或者，

S2232、查找终点失败，并且open list是空的，此时没有路径；

S23、从终点开始，每个方格沿着父节点移动直至起点，形成路径；

S3、将得到的路径进行B样条曲线处理：

S31、将由A*算法得到的路径坐标点设为P₀,P₁,P₂,…,P_n一共n+1个控制点，这些控制点用于定义样条曲线的走向、界限范围，k阶B样条曲线的定义为：

式中，B_i,k(u)是第i个k阶B样条基函数，与控制点P_i相对应，k≥1；u是自变量；

S32、基函数具有如下德布尔-考克斯递推式：

S33、本发明采用准均匀B样条曲线：两端节点具有重复度k+1，中间节点非递减的序列，如U＝{0,0,0,1,2,3,4,5,5,5}，准均匀B样条曲线保留了贝塞尔曲线在两个端点处的性质：样条曲线在端点处的切线即为倒数两个端点的连线；

S34、通过B样条曲线法得出新的路径。

本发明的有益效果是，基于A*算法进行改进，在能够获得全局最优解的同时，结合B样条曲线法得到局部最优解，缩短了路径距离，提高了路径的光滑度。

附图说明

下面结合附图和实施例对本发明进一步说明：

图1是本发明的流程示意图；

图2是本发明机器人的移动方向示意图；

图3是传统A*算法寻优路径图；

图4是改进A*算法寻优路径图；

图5是由两算法得出的路径对比图；

图6是他人改进A*算法在另一种栅格环境下的寻优路线示意图；

图7是本发明方法在另一种栅格环境下的寻优路线示意图。

具体实施方式

如图1所示，本发明提供的一种改进A*算法的4阶B样条曲线路径规划方法，包括以下步骤：

S1、采用栅格法创建机器人工作环境地图，定义起始点与目标点；

S2、采用A*算法寻找环境最短路径，所述A*算法包含以下步骤：

S21、先把要搜寻的区域划分成了正方形的格子。这是寻找路径的第一步，简化搜索区域。这个特殊的方法把我们的搜索区域简化为了2维数组。数组的每一项代表一个格子，它的状态就是可走(walkalbe)或不可走(unwalkable)。现用A*算法寻找出一条自A到B的最短路径，每个方格的边长为10，即垂直水平方向移动开销为10。因此沿对角移动开销约等于14。

S22、从起点A开始，把它加入到一个由方格组成的open list(开放列表)中，这个open list像是一个购物清单。Open list里的格子是可能会是沿途经过的，也有可能不经过。因此可以将其看成一个待检查的列表。查看与A相邻的8个方格，把其中可走的(walkable)或可到达的(reachable)方格加入到open list中。并把起点A设置为这些方格的父节点(parent node)。然后把A从Open List中移除，加入到close list(封闭列表)中，Close List中的每个方格都是不需要再关注的。

S23、下一步，我们需要从open list中选一个与起点A相邻的方格。比较Open List中节点的F值,其中F＝G+H。G代表的是从初始位置A沿着已生成的路径到指定待检测格子的移动开销。H为启发函数，也被认为是一种试探，由于在找到唯一路径前，不确定在前面会出现什么障碍物，因此用了一种计算H的算法，具体根据实际场景决定。在简化的模型中，H采用的是传统的曼哈顿距离(Manhattan Distance)，也就是横纵向走的距离之和。比较后发现A边上其中一个节点的F值最小。选其作当前处理节点，并将这个点从Open List删除，移到Close List中。

S24、对这个节点周围的8个格子进行判断，若是不可通过(比如墙，水，或是其他非法地形)或已经在Close List中，则忽略。否则执行以下步骤：

S241、若当前处理节点的相邻格子已经在Open List中，则检查这条路径是否更优，即计算经由当前处理节点到达那个方格是否具有更小的G值。如果没有，不做任何操作。相反，如果G值更小，则把那个方格的父节点设为当前处理节点(我们选中的方格)，然后重新计算那个方格的F值和G值。

S242、若当前处理节点的相邻格子不在Open List中，那么把它加入，并将它的父节点设置为该节点。

S24、不断重复这个过程，直到把终点也加入到了open list中。

S25、从终点开始，沿着箭头向父节点移动，直至回到起点，这就是由A*算法得出的路径。

S3、将得到的路径进行B样条曲线处理：

S31、将由A*算法得到的路径坐标点设为P₀,P₁,P₂,…,P_n一共n+1个控制点，这些控制点用于定义样条曲线的走向、界限范围，k阶B样条曲线的定义为：

式中，B_i,k(u)是第i个k阶B样条基函数，与控制点P_i相对应，k≥1；u是自变量。

S32、基函数具有如下德布尔-考克斯递推式：

S33、本发明采用准均匀B样条曲线：阶数k选取为4，两端节点具有重复度k+1，中间节点非递减的序列，如U＝{0,0,0,1,2,3,4,5,5,5}。准均匀B样条曲线保留了贝塞尔曲线在两个端点处的性质：样条曲线在端点处的切线即为倒数两个端点的连线。

S34、通过B样条曲线法得出新的路径。

本发明的效果可以通过以下仿真实验进一步说明：

为验证本方法的正确性和合理性，运用matlab语言编程，在20×20的栅格环境模型下对该算法进行仿真，并与传统A*算法进行比较。

为了进一步验证本发明提出的改进算法的优异性，将本发明与另传统A*算法进行比较，采用在20×20的栅格地图上随机生成障碍物，并比较计算两者得出的路径长度。

由图3可以看出，通过传统的A*算法需要路程15.31才可以到达终点，由图4可以看出，通过改进的A*算法只需要路程14.81即可到达终点，对于不同地图、不同始末位置差距也不一样。

通过对比仿真可以得出结论：使用本发明改进A*算法的路径规划明显优于传统A*算法。且使用本发明提出的A*算法比传统A*算法在路径优化方面更加平滑。

为了进一步验证本发明提出的改进算法的稳定性，将本发明与另外一种改进的A*算法进行比较，另一种改进的A*算法为期刊《计算机仿真》在2021年50卷第38期第313～317页《基于A*改进算法的机器人移动路径优化仿真》中记载的改进A*算法，在该文章记载的20×20的栅格环境条件下利用本发明方法进行仿真。

由图6可以看出，通过他人改进的A*算法需要20.06才可以到达终点；由图7可以看出，本发明的方法只需要18.06即可到达终点。

通过对比仿真可以得出结论：使用本发明改进A*算法的路径规划效率明显优于传统A*算法。且使用本发明提出的改进A*算法比传统A*算法和他人改进的A*算法进化快，这说明了本发明提出的改进A*算法在路径优化方面的稳定性高。

以上所述，仅是本发明的部分实施例而已，并非对本发明作任何形式上的限制；任何熟悉本领域的技术人员，在不脱离本发明技术方案范围情况下，都可利用上述揭示的方法和技术内容对本发明技术方案做出许多可能的变动和修饰，或修改为等同变化的等效实施例。因此，凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例所做的任何简单修改、等同替换、等效变化及修饰，均仍属于本发明技术方案保护的范围内。

Claims (1)

1.一种改进A*算法的4阶B样条曲线路径规划方法，包括以下步骤：

S1、采用栅格法创建机器人工作环境地图，定义起始点与目标点；

S2、采用A*算法寻找环境最短路径，所述A*算法包含以下步骤：

S21、把起点加入open list；

S22、重复如下过程：

S221、遍历open list，查找F值最小的节点，把它作为当前要处理的节点，然后移到closelist中，其中F＝G+H，G代表的是从初始位置A沿着已生成的路径到指定待检测格子的移动开销，H指定待测格子到目标节点B的估计移动开销；

S222、对当前方格的8个相邻方格一一进行检查，如果它是不可抵达的或者它在closelist中，忽略它，否则，做如下操作：

S2221、如果它不在open list中，把它加入open list，并且把当前方格设置为它的父亲；

S2222、如果它已经在open list中，检查这条路径(即经由当前方格到达它那里)是否更近，如果更近，把它的父亲设置为当前方格，并重新计算它的G和F值；

S223、遇到下面情况停止搜索：

S2231、把终点加入到了open list中，此时路径已经找到了，或者，

S2232、查找终点失败，并且open list是空的，此时没有路径；

S23、从终点开始，每个方格沿着父节点移动直至起点，形成路径；

S3、将得到的路径进行B样条曲线处理：

S31、将由A*算法得到的路径坐标点设为P₀,P₁,P₂,…,P_n一共n+1个控制点，这些控制点用于定义样条曲线的走向、界限范围，k阶B样条曲线的定义为：

式中，B_i,k(u)是第i个k阶B样条基函数，与控制点P_i相对应，k≥1；u是自变量；

S32、基函数具有如下德布尔-考克斯递推式：

S33、本发明采用准均匀B样条曲线：两端节点具有重复度k+1，中间节点非递减的序列，如U＝{0,0,0,1,2,3,4,5,5,5}，准均匀B样条曲线保留了贝塞尔曲线在两个端点处的性质：样条曲线在端点处的切线即为倒数两个端点的连线；

S34、通过B样条曲线法得出新的路径。

Images