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

来源：计算机技术与发展杂志2022年第02期北京时间：

作者：叶小艳;钟华钧;邓可儿

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

关键词：A*算法;路径规划;室内导航;启发函数;寻路节点