启发式搜索思想在路径规划中的应用

作者：蒋帅; 周永坤; 王涛

来源：指挥信息系统与技术, 2021, 12(04): 57-63.

DOI：10.15908/j.cnki.cist.2021.04.010

• 路径规划
• 启发式搜索
• 蚁群算法
• Dijkstra算法
• 快速随机搜索树算法

Dijkstra算法、蚁群算法和快速随机搜索树(RRT)算法等传统路径规划算法在点对点路径搜索场景中无法充分利用终点位置信息,故导致搜索策略具有一定的盲目性。为解决上述问题,通过引入启发式搜索思想,介绍了3种传统的路径规划算法及其相应的改进措施,并对改进前后的算法的搜索性能进行了对比分析。首先,通过引入启发式思想改变了Dijkstra算法搜索优先级,提升了算法搜索效率;然后,修改了蚁群算法的启发信息,在解决前期易失效的问题的同时加强了后期全局搜索能力;最后,改进了RRT算法搜索树的拓展方式,提高了算法速度,并在一定程度上缩减了有效路径长度。仿真结果表明,启发式搜索算法具有可行性和有效性。

• 单位
  中山大学