A*算法在移动机器人路径规划中的研究  

A study on A*algorithm in mobile robot path planning

作　　者：鲁毅 高永平[1] 龙江腾 LU Yi;GAO Yong-ping;LONG Jiang-teng(College of Information Engineering, East China University of Technology, Nanchang 330013, China)

机构地区：[1]东华理工大学信息工程学院,江西南昌330013

出　　处：《湖北师范大学学报（自然科学版）》2022年第2期59-65,共7页Journal of Hubei Normal University：Natural Science

基　　金：国家自然科学基金资助项目(11865002);江西省教育厅科学技术研究项目(104506);东华理工大学江西省放射性地学大数据技术工程实验室(JELRGBDT201707)。

摘　　要：针对传统寻路算法在移动机器人中搜索效率低和搜索路径不一定为最优等问题,提出了采用改进A*算法来进行移动机器人路径规划,传统寻路算法一般采用Dijkstra算法,最佳优先搜索算法(BFS)和A*算法。Dijkstra算法是一种盲目式搜索算法,可以搜索到一条最优路径,但是扩展节点太多搜索效率太慢,BFS算法是一种启发式算法,利用了启发函数,扩展节点少搜索效率高,但是不一定能搜索到一条最优路径,A*算法结合了Dijkstra算法和BFS算法,既能搜索到一条最优路径,同时搜索效率也比较高,但是也存在一些缺点。在A*算法的基础上提出了改进A*算法,首先对启发函数进行优化,可以提高算法搜索的导向性,再使用双向搜索的方式,同时从路径的两端进行搜索,可以极大地提高A*算法的搜索效率,通过仿真实验证明,改进A*算法比传统A*算法的搜索效率提高了24.95%,比BFS算法搜索的路径长度减少了24.46%,比Dijkstra算法的搜索效率提高了91.37%,因此采用改进A*算法进行移动机器人路径规划具有更好的寻路效果。This paper proposes an improved A*algorithm to carry out path planning for mobile robots,targeting the problem of low search efficiency and the problem that search paths are not always optimal in the traditional pathfinding algorithm of mobile robots.Traditional pathfinding algorithm generally adopts Dijkstra’s algorithm,Best-First Search(BFS)Algorithm and A*algorithm.Dijkstra’s algorithm is a blind search algorithm,which can settle on an optimal path,while it features overly low search efficiency due to an excessive amount of expanding nodes.BFS algorithm is a heuristic algorithm,which,by utilizing heuristic function,presents a high search efficiency with fewer expanding nodes,but it may be incapable of finding an optimal path.A*algorithm,by integrating Dijkstra’s algorithm with BFS algorithm,can find an optimal path with high search efficiency,but it is still burdened with shortcomings.This paper proposes an improved A*algorithm on the basis of the traditional A*algorithm.Firstly,the heuristic function is optimized to improve the orientation of algorithmic search.Secondly,the search efficiency of the A*algorithm is considerably improved by using the two-way search method and searching from both ends of the path.As indicated by simulation experiments,the improved A*algorithm improves the search efficiency by 24.95%compared with the traditional A*algorithm,reduces the path length by 24.46%compared with the BFS algorithm,and improves the search efficiency by 91.37%compared with Dijkstra’s algorithm.Therefore,the improved A*algorithm presents a better pathfinding efficiency for mobile robot path planning.

关 键 词：A*算法 路径规划 DIJKSTRA算法 启发函数 最佳优先搜索算法 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]