周 超，谷玉海，任 斌

（1.北京信息科技大学 现代测控教育部重点实验室，北京 100192；（2.北京航天长征飞行器研究所，北京 100076）

随着社会发展，机器人的应用更为广泛，移动机器人的路径规划问题［1］更是目前的一个研究热点。该问题可以描述为移动机器人按照某种性能指标在有障碍物的环境里从起点至终点间找到一条最短或最佳的安全无碰撞路径［2］。常用的路径规划算法有RRT算法［3］、蚁群算法［4-5］、人工势场算法［6］、SFLA［7］、A*算法［8］等。RRT算法搜索效率高，但得到的路径往往和最优路径相差甚远。蚁群算法的收敛速度相对较慢且容易陷入局部最优状态。人工势场算法虽然结构简单易于实现，但仍存在目标不可达、障碍物前产生震荡、规划路径不可达等问题。相较于其他路径规划算法，A*算法构建模型简单，搜索效率高，针对静态场景所得到的解接近最优解，对不同的场景具有很强的扩展性和适应性。A*算法同样存在很多的不足之处，如生成路径拐点较多、路径不够平滑、大范围搜索情况下计算量大等问题。针对这些问题，国内外研究人员从不同角度提出不同的改进方案。Duchoň等［9］在文中总结了Basic theta*、Phi*、Jump Point Search这3种对A*算法的改进方法。Basic theta*和Phi*解决了A*算法不能全方向搜索的问题，最终得到的路径长度更接近最优路径，但计算效率低；Jump Point Search能够提高搜索效率，但搜索方向仍受到限制，得到的路径相较于另外2种搜索方法更长。Guruji A K等［10］针对A*算法在动态环境下计算量过大的问题提出减少计算启发函数值次数的方法，仅在碰撞发生前计算A*算法启发函数的值，能够有效提高算法处理效率。……