双向A^*路径规划算法的邻域改进方法研究

摘要

针对A^*算法在路径规划中扩展节点过多和探索时间过长等问题，进行了改进研究.提出了一种多邻域方向判断的扩展方法，通过将传统的八邻域扩展优化为四加八的十二邻域选择扩展，可以有效减少路径搜索过程中的节点扩展数量，同时路径也更加符合机器人运动；然后根据前置节点与目标节点的位置，通过方向搜索规则将邻域扩展过程中的不必要节点剔除，进一步减少扩展节点的数量；再通过改进双向搜索机制将搜索速度提高一个数量级、算法效率明显提升；最后通过仿真实验和实际环境实验，在扩展节点数量、路径合理性、搜索速度这些方面都要远优于传统A^*算法，进一步证明本文提出的改进A^*算法的合理性和有效性.

关键词

A^*算法 / 路径规划 / 邻域改进 / 方向判断 / 节点剔除

基金资助

国家自然科学基金青年基金项目(31901239)资助; 2022江苏省产学研合作项目(BY2022713)资助; 2023南京林业大学大学生创新创业训练计划项目(2023NFUSPITP0066)资助