基于深度Q网络的改进RRT路径规划算法

李昭莹，欧一鸣，石若凌

（1.北京航空航天大学宇航学院，北京 100191；2.哈尔滨工业大学（深圳）机电工程与自动化学院，广东深圳 518055）

0 引言

在无人车智能化的相关领域中，路径规划是一个关键环节，也是当前的研究热点。从大型无人驾驶客车，到小型无人配送车、无人扫地车等，均需要进行路径规划。路径规划是在模型空间中找到一条从起始点到目标点的路径解，其路径解需满足一定的约束条件，并根据实际需要满足一定的性能指标（路径长短、时间、能耗等）。通常情况下，周围的环境由一些障碍物与威胁区域组成，得到的路径不仅要满足车辆的各种约束，同时要保证车辆沿该路径行驶时不与障碍物发生任何碰撞。

经过多年发展，各种各样的路径规划算法相继出现，如Dijkstra 算法、A*算法、人工势场法、概率路图（probabilistic roadmap，PRM）算法、RRT 算法等。Dijkstra 算法和A*算法均需对地图离散化，存在算法效率低的问题［1-2］；人工势场法采用虚拟力的思想，保证了实时性但易陷入局部零势能点［3］；PRM 算法结合了随机采样方法和A*算法，使其效率较A*算法效率有了很大提高，但有可能无法得到路径解［4］；LaValle 于1998年提出的RRT算法，具有无需对状态空间进行建模、简单高效等优点［5-6］，但也具有随机性大、路径质量非最优等问题。许多学者提出了一系列RRT 算法的改进算法：LaValle和东京大学的Kuffner提出了RRTConnect 算法，搜索效率相比于RRT 算法搜索效率有了显著提高，但采样仍具有很强随机性［7］；Sertac 等提出了渐进最优的RRT*算法，可以得到渐进最优解，但这也导致算法的效率较RRT算法效率有所下降，并且这种现象随着随机树的拓展愈发明显［8-9］；……