欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 202510654678X
申请人: 昆明理工大学
专利类型:发明专利
专利状态:已下证
专利领域: 测量;测试
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于改进A*的路径规划方法,其特征在于,包括以下步骤:

S1、初始化地图环境,确定待规划路径的起点和终点,初始化障碍物列表、开放列表和关闭列表,遍历地图中的所有节点,得到障碍物节点,将障碍物节点放入障碍物列表中,将关闭列表设置为空,将起点放入开放列表中;

S2、从起点开始,以当前节点的八个方向寻找初始路径点,将满足条件的初始路径点放入开放列表中,结合代价函数来优先搜索至少一个初始路径点,将代价值最小的初始路径点作为后续搜索的父节点,并将该点从开放列表移入关闭列表中,其中,关闭列表中的初始路径点形成的路径为从起点到终点的初始路径,代价函数为实际代价和启发函数代价之和,初始路径点为与当前父节点对应的可通行邻居节点;

S3、提取初始路径中所有转折点,判断转折点前后两点之间的最短路径是否穿过障碍物,根据判断结果对所述初始路径进行路径更新,得到最优路径。

2.根据权利要求1所述的方法,其特征在于,在所述S3中,根据斜率寻找路径中所有的转折点,判断转折点的前后两点的最短路径是否穿过障碍物是根据两个点之间的角度和方位来计算路径所经过的所有节点,若所述节点当中包含障碍物节点,则说明当前转折点无法被优化,结束当前转折点,开始判断下一个转折点,若所述节点都不包含障碍物节点,则说明这一转折点可以被优化,在路径集合中删除这个转折点,更新路径点集合,然后继续下一个转折点,直到所有转折点都遍历一次,得到更新后的路径点集合;将得到的新路径点集合使用转折点优化算法继续优化,直到路径无法被优化为止,即优化前后路径不发生改变,得到所述最优路径。

3.根据权利要求2所述的方法,其特征在于,所述根据斜率寻找路径中所有的转折点,包括:初始化一个转折点集合,里面存放路径中的转折点,所述路径的路径点包括起点、终点以及所述起点和所述终点之间的中间路径节点;

选取所述中间路径节点的第一个点,设置为当前路径点,计算当前路径点和前一个路径节点的斜率K1,计算当前路径点和下一个路径节点的斜率K2,判断斜率K1与K2是否不同,如果不同,说明当前路径点是转折点,记录当前路径点的坐标,放到转折点集合当中;如果斜率相同,则不发生转折;

将中间路径节点的第二个点设置为当前路径点,重复上述步骤,直到当前路径点为最后一个中间路径节点,转折点寻找结束。

4.根据权利要求2所述的方法,其特征在于,所述根据两个点之间的角度和方位来计算路径所经过的所有节点,包括:确定转折点的前后节点,(),计算节点相对于节点的角度绝对值,根据的大小和节点相对于节点的方位来寻找两个节点连接穿过的所有节点,其中,所述前后节点和是通过确定转折点在所述路径点集合坐标中的位置索引确定的。

5.根据权利要求4所述的方法,其特征在于,所述根据的大小和节点相对于节点的方位来寻找两个节点连接穿过的所有节点,包括:初始化节点列表,用于存放两点连线所穿过的所有节点;

当0°<<45°时,采用纵轴准则,确定节点列表中是否包含障碍物节点,所述纵轴准则用于确定两点连接与纵轴交点的位置,得到交点左右两侧节点的位置坐标;

当45°<<90°时,采用横轴准则,确定节点列表中是否包含障碍物节点,所述横轴准则用于确定两点连接与横轴交点的位置,得到交点上下两侧节点的位置坐标;

若节点列表中不包含障碍物节点,则删除转折点,更新路径;若节点列表中包含障碍物节点,则结束当前转折点;

判断新路径与原路径是否相同,若相同,则输出所述新路径作为所述最优路径,结束;若不同,则继续寻找路径集合中的所有转折点,对路径进行进一步优化。

6.根据权利要求1所述的方法,其特征在于,在所述S2中,将当前节点确定为搜索过程中的父节点,第一个当前节点为初始路径的起点,最后一个当前节点为目标点;所述八个方向分别为上下左右,右上,左上,右下,左下,分别对应父节点的八个邻居节点,当前父节点的下一路径点为朝向这八个方向中的任意一个可通行邻居节点,记为所述初始路径点;实际代价为起点到当前邻居节点的欧几里得距离;启发函数代价为当前邻居节点到目标点的对角线距离与权重的乘积;

找出开放列表中总代价值最小的初始路径点,并将所述总代价值最小的初始路径点从开放列表中移除,放入到关闭列表当中,将所述总代价值最小的初始路径点作为下一次搜索的父节点,进行循环搜索,直到下一次搜索的父节点为终点,则搜索结束。

7.根据权利要求6所述的方法,其特征在于,在搜索过程中,对于每一个父节点,都要依次遍历该父节点的八个邻居节点,根据父节点的位置坐标,依次计算出每一个邻居节点的位置坐标;

根据父节点的坐标计算邻居节点的坐标,在地图范围内,从右上方开始,按照逆时针方向,得到当前父节点的八个邻居节点的坐标依次为:,。

8.根据权利要求6所述的方法,其特征在于,在所述S2中,根据得到八个邻居节点的坐标,依次判断各个所述邻居节点,放到开放列表当中,如果一邻居节点在地图范围内,不是障碍物节点且不在开放列表和关闭列表当中,则将所述一邻居节点作为所述初始路径点放到开放列表当中;如果所述一邻居节点不是地图内的点,或者是障碍物节点,或者该节点已经在关闭列表当中,则舍弃所述一邻居节点;如果该节点在开放列表中,且总代价值F比开放列表中该点的小,则更新开放列表中该节点的总代价值F。

9.根据权利要求6所述的方法,其特征在于,计算父节点到开放列表中所有邻居节点之间的代价值,用欧几里得距离表示,如下:(1),

其中,为当前邻居节点坐标值,为当前父节点坐标值。

10.根据权利要求6所述的方法,其特征在于,根据对角线距离公式,计算当前邻居节点到目标点的对角线距离的值,如下:(2),

(3),

(4),

其中,为取二者中的最小值,为终点坐标值,为当前邻居节点坐标值;

启发函数代价表示为:

(5),

(6),

其中,为当前邻居节点到终点的距离,使用对角线距离表示,为起点到终点的距离,使用对角线距离表示;

总代价值表示为:

(7),

其中,为前面路径实际代价值总和与当前父节点到邻居节点代价值之和,为启发函数代价。