CN119437279A 一种基于聚合四叉树的地图分层路径规划方法 （中国电子科技集团公司第二十八研究所）

一种基于聚合四叉树的地图分层路径规划本发明公开了一种基于聚合四叉树的地图数据表后进一步细化为基于原始地图的最优路2优化通行节点，舍弃等权聚合区域内部的所有通行3等权聚合区域内部的所有通行节点全部舍弃，等权聚合区B.当起点在不等权聚合区域时，使用A*算法计算起点到聚合区域D.当终点在不等权聚合区域时，使用A*算法计算终点到聚合区10.根据权利要求9所述的一种基于聚合四叉树的地图分层路径规划方法，其特征在45[0003]传统Dijkstra算法采用广度优先搜索策略，搜索有权图中两点之间的最短路中心点直接相连的方式导致生成路径与实际最优路径偏差较大。HPA*(Hierarchical6[0012]进一步地，所述步骤1中，所述原始栅格地图的每个网格单元对应一个通行代价7[0024]B.计算等权聚合区域内边，已知等权聚合区域边界上的任意两个不同的节点[0034]下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述8[0044]本申请提供的一种基于聚合四叉树的地图分层路径规划方法可以应用于野外大9[0055]C22.计算等权聚合区域内边，已知等权聚合区域边界上的任意两个不同的节点得到的最终路径与实际最优路径偏差值显著缩小，在大幅提升路径实时计算效率的同时，[0068]本实施例提供一种基于聚合四叉树的地图分层路径规划方法。图4是实验地图[0072]A.3完成ClusterGrid聚合后，需要确定每个Clust数量。从地图左上角第一个ClusterGrid开始遍历，找出当前ClusterGrid与相邻[0074]B1.定义聚合区域结构体，记为RegionGrid，属性为id、ClusterGrids、type、leftTop、rightBottom和passageNodes。ClusterGrids表示一个聚合区域包含的所有ClusterGrid集合。type是聚合区域的类型，定义与聚合网格的类型一致。leftTop、rightBottom分别表示聚合区域的左上角原始网格和右下角原始网格的位置，通过这两个[0075]B2.根据四叉树每四个叶子节点形成一RegionGrid，直到没有可聚合的RegionGrid为止。进行聚合判断的四个ClusterGrid(或首先从抽象地图左上角第一个ClusterGrid开始遍历，判断下方、右侧、右下三个[0077](1)当passageNode1的对称通行节点passageNode3与passageNode2的对称通行节点passageNode4在同一个等权聚合区域时，删除passageNode1、passageNode3，或删除[0078](2)当passageNode1的对称通行节点passageNode3与passageNode2的对称通行节passageNode3之间增加一条外边，或者删除passageNode2，并在passageNode1与[0080](1)如果聚合区域RegionGrid是等权可通行区域，则边界上两个通行节点直接相[0081](2)如果聚合区域RegionGrid是非等权可通行区域，则边界上两个通行节点之间[0084](2)当S和E在同一个非等权聚合区域内，则直接使用A*算法计算从S到E的最优路后基于提前缓存的本地数据表细化形成对应原始地图网提供的一种基于聚合四叉树的地图分层路径规划方法的发明内容以及各实施例中的部分[0087]本领域的技术人员可以清楚地了解到本发明实施例中的技术方案可借助计算机方案本质上或者说对现有技术做出贡献的部分可以以计算机程序即软件产品的形式体现