张 毅，施明瑞

(重庆邮电大学 国家信息无障碍工程研发中心，重庆 400065)

0 引 言

移动机器人规划路径能力的大小，决定了机器人可胜任工作难度的高低。

在构建好的环境模型中，规划一条从初始点到目标点的无碰撞最优路径，是路径规划的主要内容。在构建环境模型时，栅格法应用较多，该方法具有直观简洁、分辨率可变、容易创建和存储等优点，适用于室内环境路径规划地图模型的建立，鲁棒性强[1]。图搜索算法是路径规划中的一类算法，它被广泛应用于栅格地图中的路径规划问题。A*算法是图搜索算法中的经典算法，它是一种启发式搜索方法。启发式搜索会评估状态空间中的每个搜索位置，找出下一步要搜索的最好位置G，再从G进行类似搜索直到确定目标位置。该搜索方法能节省大量搜索空间，提高搜索效率[2]。在A*算法的基础上，研究者们先后提出了多种改进算法，例如D*，LPA*与D*lite等算法。

D*lite算法是文献[3]提出的。该算法采用反向搜索，从目标点向当前点扩展，在进行重规划时极大地提高了效率。文献[4]通过在启发估价值中加入与障碍物相关的值，从而避免规划出靠近障碍物尖角或穿越两相邻障碍物的不安全或不可达路径。文献[5]通过融合D*lite算法和RRT*算法提高了收敛速率。文献[6]采用模型预测控制MPC，优化了D*lite算法在动态环境和特殊地形中的路径规划能力。文献[7]通过引入备选路径，提高了D*lite算法中路径重规划的速度。文献[8]通过在D*lite算法中引入搜索树的思想，在需要重规划时立即砍断搜索树，从而提高路径重规划的速度。……