一种基于改进A*算法的室内导航路径规划方法

路径规划是室内导航研究的关键技术之一。A^*算法是一种常见的路径规划算法,当区域的点数量较少时,找寻最优路径是最有效的直接搜索方法。但当路径点规模较大时,使用数值优化算法求解最佳路径的难度急剧增加,导致规划时间所需时间过长,不符合实时性要求。为提高路径规划方法中的效率和稳定性,在梳理室内导航路径规划已有算法和方案的基础上,分析了A^*算法的基本思想与实现步骤,并针对室内导航中A^*路径算法存在的问题,提出了一种改进型A^*算法优化的方案。利用用户对最短距离和直行路程的需求,在位置计算中,引入同时考虑方向和距离启发信息的启发函数,把POI点与寻路节点分开处理,以映射的方式建立联系。将该方案应用于室内导航中A^*算法实现伪代码,对算法改进前后进行算法效率测试。结果表明,改进后A^*算法的整体效率提升了近50%,改进型A^*算法在室内导航路径规划的效率和稳定性比较优,达到了加速导航算法的目的。

A Path Planning Method of Indoor Navigation Based on Improved A-Star Algorithm

Path planning is one of the key technologies of indoor navigation research. A-Star algorithm is a common path planning algorithm. When the number of points in the region is small, it will be the most effective direct search method for finding the optimal path. However, when the scale of path points is large, it’s difficult to use numerical optimization algorithm to solve the optimal path increases sharply, resulting in too long planning time, which does not meet the real-time requirements. In order to improve the efficiency and stability of the path planning method, based on combing the existing algorithms and schemes of indoor navigation path planning, we analyze the basic idea and implementation steps of A-Star algorithm, and propose an improved A-Star algorithm optimization scheme aiming at the problems of A-Star algorithm in indoor navigation. According to the user’s demand for the shortest distance and straight travel distance, a heuristic function considering both direction and distance heuristic information is introduced in the location calculation. The POI points and the path finding nodes are processed separately, and the connection is established by mapping. The scheme is applied to implement pseudo code of A-Star algorithm in indoor navigation, and the algorithm efficiency is tested before and after the algorithm is improved. The results show that the overall efficiency of the improved A-Star algorithm is improved by nearly 50%,with better efficiency and stability, so as to achieve the purpose of accelerating the navigation algorithm.