一种基于自由空间与快速搜索随机树算法的无人车动态路径规划方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112833904A(43)申请公布日2021.05.25(21)申请号202110006607.0(22)申请日2021.01.05(71)申请人北京航空航天大学地址100191北京市海淀区学院路37号(72)发明人李昭莹石若凌(51)Int.Cl.G01C21/34(2006.01)权利要求书2页说明书5页附图5页(54)发明名称一种基于自由空间与快速搜索随机树算法的无人车动态路径规划方法(57)摘要本文发明公开了一种基于自由空间与快速搜索随机树算法的无人车动态路径规划方法。本文利用凹多边形凸分解的图形学方法，设计了一种在含有障碍地图上构建自由空间的方法，并应用人工蜂群算法对进行路径优化找出全局最优路径。本文通过调整随机树节点采样概率，实现了基于改进快速搜索随机树算法的快速路径规划方法。最后，本发明分别利用自由空间法和快速搜索随机树算法实现动态地图的全局路径规划和无人车行进过程中的局部快速路径规划，兼顾了动态环境下路径规划的质量和速度。CN112833904ACN112833904A权利要求书1/2页1.一种基于自由空间与快速搜索随机树算法的无人车动态路径规划方法，其特征在于分别利用自由空间法和快速搜索随机树算法实现动态地图的全局路径规划和无人车行进过程中的局部快速路径规划。所述动态路径规划方法主要步骤：1)根据已知地图条件，利用基于自由空间法与人工蜂群算法的路径规划算法求解由起点至目标点的最优路径；2)无人车按照当前规划路径前进，每隔一段时间t，判断当前地图状态是否发生改变；其中，首先判断终点是否发生改变，如发生改变则跳至步骤1)；随后判断当前路径是否被障碍物阻挡，若未被障碍物阻挡，则重新根据当前路径节点与存储的初始路径节点优化路径；若被障碍物阻挡，则跳至下一步；3)选择被障碍物阻挡的路径两端分别作为局部路径规划的起点和终点，利用快速搜索随机树算法对该段路径进行局部规划；4)用步骤3)中重新规划的局部路径替换被障碍物阻挡的路径；5)路径优化：按顺序列出所得路径的起点、节点、终点，依次判断每一个节点若与其相隔的节点连线是否会与障碍物产生交集，若无交集，则舍弃两点间的其它节点；6)重复以上步骤直至无人车行进至目标区域。2.根据权利要求1所述的一种基于自由空间与快速搜索随机树算法的动态路径规划方法，其特征在于利用凹多边形凸分解的图形学方法，设计了一种在含有障碍地图上构建自由空间的方法，并应用人工蜂群算法对进行路径优化找出全局最优路径。所述全局路径规划方法主要步骤：1)构建自由空间：首先将地图构建为单连通多边形，然后对单连通凹多边形进行凸分解；2)全局搜索初始路径：全局搜索找出一组自由连线，并在自由连线中选择路径点，与起点和终点连线生成一条初始路径；3)邻域搜索可行路径：使用人工蜂群算法对路径进行局部调整和优化。3.根据权利要求1所述的一种基于自由空间与快速搜索随机树算法的动态路径规划方法，其特征在于通过调整随机树节点采样概率，实现了基于改进快速搜索随机树算法的局部快速路径规划方法。所述局部路径规划方法主要步骤：1)定义树的根节点为路径的起始点。2)更新地图当前每个点允许被采样概率，在状态空间中随机采样获取一个采样点xrand，根据采样概率判断该点是否被采样，若被采样，则进入步骤3)，否则重复步骤2)。3)在搜索树中寻找与该采样点距离最近的树节点xnearest。4)以树节点xnearest为起点，沿xnearestxrand方向取长度为d的线段得到一个新的节点xnew。5)连接xnearest与xnew得到以条新的搜索树杈，检测这条树杈是否与障碍物或威胁区域有交集，若无交集则保留此树节点xnew，至步骤6)，否则舍弃该树节点，跳至步骤8)。6)在新的节点xnew附近搜索节点，并判断是否有更合适的节点作为xnew的父节点，使xnew节点至起始点的代价小于当前情况。通常以xnew节点至起始点的欧氏距离进行比较。2CN112833904A权利要求书2/2页7)判断xnew附近的节点如果将xnew作为父节点是否更优，即到起点的路径代价是否更小。8)重复步骤2)至7)，直至目标点或目标区域包含在搜索树中。9)在搜索树中沿目标点反向寻找每一个树节点的父节点，直至起始点，即可得到一条由起点至终点的可行路径。3CN112833904A说明书1/5页一种基于自由空间与快速搜索随机树算法的无人车动态路径规划方法1.技术领域[0001]本发明涉及路径规划领域，尤其涉及动态环境下无人车行进过程中地图发生变化的路径规划。2.背景技术[0002]自动驾驶技术是人工智能领域中的热点方向，在未来社会中，大部分车辆将会配置自动驾驶技术，使得地面交通更加通畅、交通事故率更低。作为其中关