李 艳，郭继峰，罗汝斌

（1.北京宇航系统工程研究所，北京 100074；2.哈尔滨工业大学航天学院，哈尔滨 150001）

1 引 言

美国国防部2018年8月发布了《2017—2042财年无人系统综合路线图》[1]，对无人系统的发展提供了总体战略指南。在此路线图中，无人系统自主性作为4 个关键主题内容之一，是美军近年来对无人系统重点布局的发展方向。而无人系统自主导航是实现无人系统高度自主性的关键技术。无人系统自主导航包括4 个基本要求，即感知、定位、路径规划、运动控制，其中路径规划是最重要的部分之一。目前，无人系统的路径规划算法可以分为经典方法和启发式方法[2-3]，如图1 所示。

图1 路径规划算法的基本分类Fig.1 Basic classification of path planning algorithms

目前，主要的经典方法包括单元分解法（Cell Decomposition Method，CD）、势场法（Potential Field Method，PFM）、基于采样的方法（Sampling- Based Method，SBP）和Dubins 算法。在CD 中，机器人配置的自由空间被划分为称为单元的小区域，目标是提供一条无碰撞路径，以到达目标。基于该方法的机器人路径规划应用见文献[4-5]。在PFM 中，障碍物和目标分别被赋予排斥力和吸引力，这样机器人就能够在远离障碍物的同时朝着目标移动[6]。为了解决动力学环境中的路径规划问题，文献[7]中引入了对经典PFM 的修改。SBP 算法的规划方案由于其在复杂的现实世界规划问题中的能力而受到相当大的关注。目前，应用最多的SBP 算法包括概率路线图（Probabilistic Route Map ， PRM ）和快速探索随机树（Rapid-exploration Random Tree，RRT）[8]。尽管连接随机采样点的概念在这两种方法中都是基本的，但这两种方法在构建连接点的方式上是不同的。文献[9]对SBP 的工作进行了全面调查。……