一种基于AStar算法的路径搜索方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113532458A(43)申请公布日2021.10.22(21)申请号202110698514.9(22)申请日2021.06.23(71)申请人厦门大学地址361000福建省厦门市思明区思明南路422号(72)发明人姚俊峰洪湘(74)专利代理机构厦门市新华专利商标代理有限公司35203代理人朱凌(51)Int.Cl.G01C21/34(2006.01)权利要求书1页说明书5页附图1页(54)发明名称一种基于AStar算法的路径搜索方法(57)摘要本发明提供了地图路径规划技术领域的一种基于AStar算法的路径搜索方法，包括如下步骤：步骤S10、利用Prime算法随机规划路径，基于所述路径生成迷宫场景；步骤S20、将所述迷宫场景转换为Grid地图；步骤S30、搜索所述Grid地图中的死路并进行排除；步骤S40、搜索所述Grid地图中各地图节点的邻接点；步骤S50、计算各所述邻接点的f(n)值，基于所述f(n)值对各邻接点进行排序；步骤S60、将排序后的各所述邻接点基于小根堆算法存储至Open列表；步骤S70、利用AStar算法，基于所述Open列表中存储的各邻接点进行路径搜索。本发明的优点在于：极大的提升了路径搜索的效率。CN113532458ACN113532458A权利要求书1/1页1.一种基于AStar算法的路径搜索方法，其特征在于：包括如下步骤：步骤S10、利用Prime算法随机规划路径，基于所述路径生成迷宫场景；步骤S20、将所述迷宫场景转换为Grid地图；步骤S30、搜索所述Grid地图中的死路并进行排除；步骤S40、搜索所述Grid地图中各地图节点的邻接点；步骤S50、计算各所述邻接点的f(n)值，基于所述f(n)值对各邻接点进行排序；步骤S60、将排序后的各所述邻接点基于小根堆算法存储至Open列表；步骤S70、利用AStar算法，基于所述Open列表中存储的各邻接点进行路径搜索。2.如权利要求1所述的一种基于AStar算法的路径搜索方法，其特征在于：所述步骤S10具体包括：步骤S11、利用Prime算法随机规划路径，所述路径由若干个方形的路径节点组成；步骤S12、依次随机选取一个所述路径节点添加进墙体队列中；步骤S13、判断所述墙体队列中路径节点相邻的上、下、左、右方向是否仅存在3个路径节点，若是，则将该3个路径节点添加进所述墙体队列中；若否，则删除所述墙体队列中的路径节点；步骤S14、将所述墙体队列中的路径节点初始化为墙体，生成迷宫场景。3.如权利要求1所述的一种基于AStar算法的路径搜索方法，其特征在于：所述步骤S10中，所述路径设有一起始路径节点以及一目标路径节点。4.如权利要求2所述的一种基于AStar算法的路径搜索方法，其特征在于：所述步骤S20具体为：将所述迷宫场景基于路径节点的大小均分成等大的方格，得到若干个地图节点，基于所述迷宫场景设置各地图节点的墙体属性，完成Grid地图的转换。5.如权利要求4所述的一种基于AStar算法的路径搜索方法，其特征在于：所述墙体属性用于标识地图节点是否为墙体。6.如权利要求1所述的一种基于AStar算法的路径搜索方法，其特征在于：所述步骤S30具体为：依次判断所述Grid地图中的各地图节点，是否存在相邻的3个地图节点均为墙，若是，说明为死路，将所述地图节点设为墙，并进入步骤S40；若否，说明不为死路，并进入步骤S40。7.如权利要求1所述的一种基于AStar算法的路径搜索方法，其特征在于：所述步骤S40具体为：基于上、下、左、右四个方向搜索所述Grid地图中各地图节点的邻接点。2CN113532458A说明书1/5页一种基于AStar算法的路径搜索方法技术领域[0001]本发明涉及地图路径规划技术领域，特别指一种基于AStar算法的路径搜索方法。背景技术[0002]路径搜索即在设定的场景下搜索出一条能够抵达目的地的路径，广泛应用于自动驾驶、迷宫寻路等场景。路径搜索一般采用AStar算法(启发式搜索算法)，但是，以迷宫寻路场景为例，传统的AStar算法存在如下缺点：[0003]1、寻找当前节点的邻接点时，每次都需要搜索节点周围8个方向(8*45°)的节点，当起始节点和目标节点相距越远、墙体越多时，需要搜索的节点就越多，导致搜索效率低下；2、每次都需要选择f(n)值最小的节点作为下一个搜索节点，需要反复遍历Open列表，而Open列表中存放了大量已生成但尚未被访问的节点信息，反复遍历导致选择最小f(n)值节点效率不高；其中，f(n)表示节点n的估价函数，f(n)＝g(n)+h(n)，g(n)表示在状态空间中从初始节点到n节点的实际代价，h(n)表示从节点n到目标节点最佳路径的估计代价；3