二叉树路径规划算法在栅格地图中的应用

作者：娄安东; 李向阳; 阮佳琪; 潘瑾瑜; 冯静

来源：矿山机械, 2019, 47(10): 67-71.

DOI：10.16816/j.cnki.ksjx.2019.10.015

• 栅格地图
• 机器人
• 二叉树
• 路径规划
• *算法" name="keyword">A*算法

基于栅格图的路径规划算法主要有A*算法、快速搜索树算法等。在栅格地图规模增大的时候,以上算法的运算量将大幅增加。笔者提出一种将图搜索与栅格搜索结合的二叉树路径规划算法。该算法通过逆向搜索优化局部路径、剪枝优化二叉树,从而得到最佳路径。相比快速搜索树算法,二叉树路径规划算法具有概率完备性,在运行测试试验中,实际展开结点数量为A*算法的28%,运行时间仅为A*算法的52%。

• 单位
  中信重工机械股份有限公司