一种改进的有界次优双向搜索A*算法

AN IMPROVED BOUNDED SUBOPTIMAL BIDIRECTIONAL SEARCH A* ALGORITHM

  • 摘要: 传统路径规划Dijkstra算法和A*算法存在拓展节点过多、路径搜索效率不高等问题,对此,提出一种改进的有界次优双向搜索A*算法。提出双向搜索,在搜索区域内一个点从起点向终点搜索的同时,另一个点由终点向起点搜索,减少拓展节点;改进传统A*算法启发函数,选取曼哈顿距离计算并提出动态h值改进,减少路径规划时间;提出有界次优,将一定范围f值内的节点放入focalList中,取出h值最小的节点作为下一步拓展节点,提高算法搜索过程中的目的性;进行仿真验证,改进A*算法的拓展节点数分别减少了66.43%、71.14%、78.27%,规划时间分别降低了95.63%、96.30%、97.65%。结果表明:改进A*算法显著减少了路径规划拓展节点个数和所需时间,提高了规划路径效率。

     

    Abstract: The traditional Dijkstra algorithm and A* algorithm have problems of too many expanded nodes and low path search efficiency. Therefore, an improved bounded suboptimal bidirectional search A* algorithm is proposed. Bidirectional search was proposed. While one point searches from start point to end point within the search area, another point searches from end point to start point, reducing the number of expanded nodes. The heuristic function of traditional A* was improved, Manhattan distance was selected for calculation and dynamic h value improvement was proposed to reduce path planning time. Bounded suboptimality was proposed, nodes within a certain range of f values were placed in focalList, and the node with the smallest h value was taken as the next expanded node to improve the purposefulness of algorithm search. Simulation verification was carried out, and the improved A* algorithm reduced the number of expanded nodes by 66.43%, 71.14%, 78.27% respectively, and the planning time was reduced by 95.63%, 96.30%, 97.65% respectively. The results show that the improved A* algorithm significantly reduces the number of expanded nodes and required time, and improves path planning efficiency.

     

/

返回文章
返回