平码五不中公式规律
  • / 9
  • 下载费用:30 金币  

基于快速扩展随机树的无人车避障方法.pdf

关 键 ?#21097;?/dt>
基于 快速 扩展 随机 无人 车避障 方法
  专利查询网所有资?#28147;?#26159;用户自行上传分享,仅供网友学习交流,?#28147;?#19978;传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201910103332

申请日:

20190201

公开号:

CN109579854A

公开日:

20190405

当前法律状态:

公开

有效性:

审中

法?#19978;?#24773;: 公开
IPC分类号: G01C21/20;G05D1/02 主分类号: G01C21/20;G05D1/02
申请人: 禾多科技(北京)有限公司
发明人: 张淳;卜大鹏
地址: 100089 北京市海淀区阜外亮甲店1号恩济西园产业园21号楼一层21-14
优先权:
专利代理机构: 11369 代理人: 汤小东
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201910103332

授权公告号:

法律状态公告日:

20190405

法律状态类型:

公开

摘要

本发明公开了一种基于快速扩展随机树的无人车避障方法,包括:步骤1、通过获取无人车数据以及障碍物位置数据,对障碍物轮廓尺寸进行膨胀处理,以得到障碍物膨胀后的区域;步骤2、通过快速遍历随机树法结合无人车行驶起点终点数据,生成所述无人车行驶的路径点,其中,随机树中新节点选用依据是,所述新节点是否在步骤1中所述障碍物膨胀后的区域内;步骤3、通过Dubins曲线对步骤2中生成的路径点进行检测,以生成最终所述无人车避障的路径;若检测中删除路径无效点后的路径点的密度低于阈值,则进入步骤2中重新生成所述无人车行驶的路径点。本发明可快速寻找满足车辆转弯半径的避障通路,提高了生成的无人车行驶的避障路径的安全性和可靠性。

权利要求书

1.一种基于快速扩展随机树的无人车避障方法,其中,包括: 步骤1、通过获取无人车数据以及障碍物的位置数据,对障碍物的轮廓尺寸进行膨胀处理,以得到障碍物膨胀后的区域; 步骤2、通过快速遍历随机树法结合所述无人车行驶的起点和终点数据,生成所述无人车行驶的路径点,其中,随机树中新节点选用的依据是,所述新节点是否在步骤1中所述障碍物膨胀后的区域内; 步骤3、通过Dubins曲线对步骤2中生成的路径点进行检测,以生成最终所述无人车避障的路径;若检测中删除路径无效点后的路径点的密度低于阈值,则进入步骤2中重新生成所述无人车行驶的路径点。 2.如权利要求1所述基于快速扩展随机树的无人车避障方法,其中,步骤1中无人车数据为无人车轮廓的对角长度,步骤1中对障碍物的轮廓尺寸进行膨胀处理的具体步骤如下: 步骤A、通过选取所述障碍物的多个轮廓点,建立点集E; 步骤B、通过在点集E中选取所有相邻的两个所述障碍物的轮廓点,将相邻的两点连线,并做正向以及反向的延长线,分别在正向延长线和反向延长线上各取一点,延长线上所取的两点之间的距离等于所述无人车轮廓的对角线长度;选取点集E中所有相邻的连线的两点以及每组相邻两点延长线上选取的点,构成点集F; 步骤C、利用Graham’s Scan法求解所述点集F的凸包,并将所述凸包作为所述障碍物膨胀后的区域。 3.如权利要求1所述基于快速扩展随机树的无人车避障方法,其中,步骤2中快速遍历随机树法生成所述无人车行驶的路径点的具体步骤如下: 步骤a、通过在随机树的状态空间内随机选择一个初始采样点,再从所述随机树中选择与所述初始采样点最近的节点,从最近的节点向所述初始采样点延伸一段距离,以得到新节点; 步骤b、通过检测步骤a中所述新节点是否通过所述障碍物膨胀后的区域,若通过,则将所述新节点加入所述随机树,若不通过,则进入步骤a; 步骤c、通过多次重复步骤a到步骤b,以得到距离所述无人车终点小于第一阈值的最终节点,则成功生成树;若重复次数超出了搜索的时间上限或节点的数目达到上限,则进入步骤a。 4.如权利要求3所述基于快速扩展随机树的无人车避障方法,其中,在所述随机树的生成过程中通过设定参数值,以判定每次得到的随机值的生长方向;若所述随机值在大于零小于所述设定参数值的?#27573;?#20869;,则判定所述新节点的选择朝所述无人车行驶的终点方向生长;否则,所述新节点朝向所述初始采样点的方向生长。 5.如权利要求1所述基于快速扩展随机树的无人车避障方法,其中,步骤3中还包括对步骤2中的所述路径点进行路径平滑处理,以得所述路径点的平滑路径;所述平滑处理具体为利用多项式参数拟合方法生成曲率连续的路径。 6.如权利要求5所述基于快速扩展随机树的无人车避障方法,其中,步骤3中Dubins曲线对步骤2中生成的路径点进行检测的具体步骤如下: 步骤d、通过更新被检测路径点的集合内每个路径点的方向角,以记?#27982;?#20010;点的坐标; 步骤e、从所述无人车行驶的起始点坐标开始,在所述随机树中的路径点内遍历相邻的两点,检测相邻两点之间是否存在由右转、左转或行驶直线组成的Dubins曲线,其中,所述Dubins曲线中右转或左转需满足所述无人车行驶的转弯半径,行驶直线需满足所述无人车驾驶的行驶方向; 步骤f、若相邻两点之间检测不到Dubins曲线的可能性,则检测失败,以判定相邻两点之中的遍历的下一点为无效点,则删除所述无效点;若删除无效点后的所述随机树中路径点的集合中的路径点的密度低于第二阈值,则进入步骤2中;若删除无效点后的所述随机树中路径点的集合中的路径点的密度不低于第二阈值,则通过剩余点生成平滑路径后,进入步骤d;若相邻两点之间检测到Dubins曲线的可能性,则进入步骤e,直至检测到最后一个路径点,仍未产生无效点,则所述被检测路径点的集合通过检测; 步骤g、通过步骤f中检测通过的所述被检测路径点的集合建立平滑路径,以得到所述无人车行驶最终的避障路径。 7.如权利要求6所述基于快速扩展随机树的无人车避障方法,其中,步骤e中每个路径点的方向角选定是由所述平滑路径中距离所述被检测路径点的集合中最后一个路径点的最近的点决定。

说明书


基于快速扩展随机树的无人车避障方法
技术领域


本发明涉及?#36828;?#39550;驶技术领域,尤其涉及一种基于快速扩展随机树的无人车避障
方法。


背景技术


随着科技的发展,互联网的崛起,无人驾驶已被提上日程,无人驾驶?#20302;常?#31616;单来
说就是利用传感器检测周围环境和自身状态,包括导航定位信息、道路信息、其他车辆和行
人等障碍物信息、自身的位姿信息及运动状态信息,经过一定的决策规划算法后,精确控制
车辆的速度和转向,不需要驾驶员的监控,即可使车辆安全到达目的地。其中,涉及路径规
划技术,路径规划技术是机器人研究领域的一个重要分支。所谓机器人的最优路径规划问
题,就是依据某个或某些优化准则,如工作代价最小、行走路线最短、行走时间最短等,在其
工作空间中?#19994;?#19968;条从起?#30002;?#24577;到目标状态的能避开障碍物的最优路径。而汽车路径规划
中受限于车辆转弯半径的约束,提供一种快速的?#19994;?#28385;足车辆特性要求的能避开障碍物的
最优路径的一种算法具有重要意义。


发明内容


本发明的一个目的是解决至少上述问题,并提供至少后面将说明的优点。


本发明还有一个目的是提供一种基于快速扩展随机树的无人车避障方法,可快速
寻找满足车辆转弯半径的避障通路,提高了生成的无人车行驶的避障路径的安全性和可靠
性。


为了实现根据本发明的这些目的和其它优点,提供了一种基于快速扩展随机树的
无人车避障方法,包括:


步骤1、通过获取无人车数据以及障碍物的位置数据,对障碍物的轮廓尺寸进行膨
胀处理,以得到障碍物膨胀后的区域。


步骤2、通过快速遍历随机树法结合所述无人车行驶的起点和终点数据,生成所述
无人车行驶的路径点,其中,随机树中新节点选用的依据是,所述新节点是否在步骤1中所
述障碍物膨胀后的区域内。


步骤3、通过Dubins曲线对步骤2中生成的路径点进行检测,以生成最终所述无人
车避障的路径;若检测中删除路径无效点后的路径点的密度低于阈值,则进入步骤2中重新
生成所述无人车行驶的路径点。


优选的是,步骤1中无人车数据为无人车轮廓的对角长度,步骤1中对障碍物的轮
廓尺寸进行膨胀处理的具体步骤如下:


步骤A、通过选取所述障碍物的多个轮廓点,建立点集E。


步骤B、通过在点集E中选取所有相邻的两个所述障碍物的轮廓点,将相邻的两点
连线,并做正向以及反向的延长线,分别在正向延长线和反向延长线上各取一点,延长线上
所取的两点之间的距离等于所述无人车轮廓的对角线长度;选取点集E中所有相邻的连线
的两点以及每组相邻两点延长线上选取的点,构成点集F。


步骤C、利用Graham’s Scan法求解所述点集F的凸包,并将所述凸包作为所述障碍
物膨胀后的区域。


优选的是,步骤2中快速遍历随机树法生成所述无人车行驶的路径点的具体步骤
如下:


步骤a、通过在随机树的状态空间内随机选择一个初始采样点,再从所述随机树中
选择与所述初始采样点最近的节点,从最近的节点向所述初始采样点延伸一段距离,以得
到新节点。


步骤b、通过检测步骤a中所述新节点是否通过所述障碍物膨胀后的区域,若通过,
则将所述新节点加入所述随机树,若不通过,则进入步骤a。


步骤c、通过多次重复步骤a到步骤b,以得到距离所述无人车终点小于第一阈值的
最终节点,则成功生成树;若重复次数超出了搜索的时间上限或节点的数目达到上限,则进
入步骤a。


优选的是,在所述随机树的生成过程中通过设定参数值,以判定每次得到的随机
值的生长方向;若所述随机值在大于零小于所述设定参数值的?#27573;?#20869;,则判定所述新节点
的选择朝所述无人车行驶的终点方向生长;否则,所述新节点朝向所述初始采样点的方向
生长。


优选的是,步骤3中还包括对步骤2中的所述路径点进行路径平滑处理,以得所述
路径点的平滑路径;所述平滑处理具体为利用多项式参数拟合方法生成曲率连续的路径。


优选的是,步骤3中Dubins曲线对步骤2中生成的路径点进行检测的具体步骤如
下:


步骤d、通过更新被检测路径点的集合内每个路径点的方向角,以记?#27982;?#20010;点的坐
标。


步骤e、从所述无人车行驶的起始点坐标开始,在所述随机树中的路径点内遍历相
邻的两点,检测相邻两点之间是否存在由右转、左转或行驶直线组成的Dubins曲线,其中,
所述Dubins曲线中右转或左转需满足所述无人车行驶的转弯半径,行驶直线需满足所述无
人车驾驶的行驶方向。


步骤f、若相邻两点之间检测不到Dubins曲线的可能性,则检测失败,以判定相邻
两点之中的遍历的下一点为无效点,则删除所述无效点;若删除无效点后的所述随机树中
路径点的集合中的路径点的密度低于第二阈值,则进入步骤2中;若删除无效点后的所述随
机树中路径点的集合中的路径点的密度不低于第二阈值,则通过剩余点生成平滑路径后,
进入步骤d;若相邻两点之间检测到Dubins曲线的可能性,则进入步骤e,直至检测到最后一
个路径点,仍未产生无效点,则所述被检测路径点的集合通过检测。


步骤g、通过步骤f中检测通过的所述被检测路径点的集合建立平滑路径,以得到
所述无人车行驶最终的避障路径。


优选的是,步骤e中每个路径点的方向角选定是由所述平滑路径中距离所述被检
测路径点的集合中最后一个路径点的最近的点决定。


本发明至少包括以下有益效果:


本发明由于无人车路径规划中,无人车的估计位置被设置为一个点,但?#23548;食?#26223;
中的汽车具有几何信息,在行驶过程中,需要将汽车的几何信息考虑到路径规划内,避免因
以无人车设置为一点进行驾驶路径规划,导致的?#23548;始?#39542;中与障碍物的碰撞,为了满足无
人车行驶路径上的安全性,通过对驾驶路径上的障碍物的尺寸进行膨胀处理,膨胀处理中
以无人车对角线长度为膨胀依据,再利用膨胀处理的障碍物轮廓点生成障碍物膨胀后的区
域,以便于在随机树生成中对节点进行选择;通过快速遍历随机树法生成无人车行驶路径,
效率高,已缩减随机树生成时间;通过Dubins曲线对步骤2中生成的路径点进行检测,可矫
正使用快速遍历随机树法随机性过强的问题,利用Dubins曲线对连接树的点进行过滤和有
效性筛选,基于这种Dubins曲线检测和循环,以得到可靠性强的路径,可快速寻找满足车辆
转弯半径的避障通路,提高了生成的无人车行驶的避障路径的安全性和可靠性。


本发明的其它优点、目标和特征将部分通过下面的说明体现,部?#21482;?#23558;通过对本
发明的研究和?#23548;?#32780;为本领域的技术人员所理解。


附图说明


图1为本发明所述基于快速扩展随机树的无人车避障方法的流程图。


具体实施方式


下面结合附图对本发明做进一步的详细说明,以令本领域技术人员参照说明书文
字能够据以实施。


应当理解,本文所使用的诸如“具有”、“包含?#24065;?#21450;“包括”术语并不排除一个或多
个其它元件或其组合的存在或添加。


如图1所示,本发明提供一种基于快速扩展随机树的无人车避障方法,包括:


步骤1、通过获取无人车数据以及障碍物的位置数据,对障碍物的轮廓尺寸进行膨
胀处理,以得到障碍物膨胀后的区域。


步骤2、通过快速遍历随机树法结合所述无人车行驶的起点和终点数据,生成所述
无人车行驶的路径点,其中,随机树中新节点选用的依据是,所述新节点是否在步骤1中所
述障碍物膨胀后的区域内。


步骤3、通过Dubins曲线对步骤2中生成的路径点进行检测,以生成最终所述无人
车避障的路径;若检测中删除路径无效点后的路径点的密度低于阈值,则进入步骤2中重新
生成所述无人车行驶的路径点。


在上述方案中,由于无人车路径规划中,无人车的估计位置被设置为一个点,但实
?#39135;?#26223;中的汽车具有几何信息,在行驶过程中,需要将汽车的几何信息考虑到路径规划内,
避免因以无人车设置为一点进行驾驶路径规划,导致的?#23548;始?#39542;中与障碍物的碰撞,为了
满足无人车行驶路径上的安全性,通过对驾驶路径上的障碍物的尺寸进行膨胀处理,膨胀
处理中以无人车对角线长度为膨胀依据,再利用膨胀处理的障碍物轮廓点生成障碍物膨胀
后的区域,以便于在随机树生成中对节点进行选择;通过快速遍历随机树法生成无人车行
驶路径,效率高,已缩减随机树生成时间;通过Dubins曲线对步骤2中生成的路径点进行检
测,可矫正使用快速遍历随机树法随机性过强的问题,利用Dubins曲线对连接树的点进行
过滤和有效性筛选,基于这种Dubins曲线检测和循环,以得到可靠性强的路径,可快速寻找
满足车辆转弯半径的避障通路,提高了生成的无人车行驶的避障路径的安全性和可靠性。


一个优选方案中,步骤1中无人车数据为无人车轮廓的对角长度,步骤1中对障碍
物的轮廓尺寸进行膨胀处理的具体步骤如下:


步骤A、通过选取所述障碍物的多个轮廓点,建立点集E。


步骤B、通过在点集E中选取所有相邻的两个所述障碍物的轮廓点,将相邻的两点
连线,并做正向以及反向的延长线,分别在正向延长线和反向延长线上各取一点,延长线上
所取的两点之间的距离等于所述无人车轮廓的对角线长度;选取点集E中所有相邻的连线
的两点以及每组相邻两点延长线上选取的点,构成点集F。


步骤C、利用Graham’s Scan法求解所述点集F的凸包,并将所述凸包作为所述障碍
物膨胀后的区域。


在上述方案中,建立集合E代表障碍物的轮廓点,无人车对角长度为d;在集合E中
遍历相邻两点,并作两点连线延长线,从两侧选取距离为d的两点,所有点构成新集合F;利
用Graham’s Scan法求解集合F的凸包G,并将G作为障碍物信息,用作后续的路径生成。


一个优选方案中,步骤2中快速遍历随机树法生成所述无人车行驶的路径点的具
体步骤如下:


步骤a、通过在随机树的状态空间内随机选择一个初始采样点,再从所述随机树中
选择与所述初始采样点最近的节点,从最近的节点向所述初始采样点延伸一段距离,以得
到新节点。


步骤b、通过检测步骤a中所述新节点是否通过所述障碍物膨胀后的区域,若通过,
则将所述新节点加入所述随机树,若不通过,则进入步骤a。


步骤c、通过多次重复步骤a到步骤b,以得到距离所述无人车终点小于第一阈值的
最终节点,则成功生成树;若重复次数超出了搜索的时间上限或节点的数目达到上限,则进
入步骤a。


在上述方案中,初始化时随机树T只包含根节点node_init,在状态空间内随机选
择一个采样点node_rand,然后从随机树中选择一个距离该采样点最近的节点node_near,
从node_near向node_rand延伸一段距离,得到新节点node_new,其中,所述距离为0.3-0.5
米内选的一个随机值;若新节点通过障碍物检测,将之加入随机树中。重复上述操作,直到
?#19994;絥ode_near与终点的距离小于第一阈值0.3米,代表生成树成功。如果超出搜索时间上
限0.5秒或者节点数上限200,则重新规划。


一个优选方案中,在所述随机树的生成过程中通过设定参数值,以判定每次得到
的随机值的生长方向,若所述随机值在大于零小于所述设定参数值的?#27573;?#20869;,则判定所述
新节点的选择朝所述无人车行驶的终点方向生长;否则,所述新节点朝向所述初始采样点
的方向生长。


在上述方案中,为了使随机树更快完成任务,设定参数Goal_prob即0.2,每次得到
随机值p,其中,随机值为0-1之间的随机数,若0\u0026lt;p\u0026lt;Goal_prob,随机数朝目标生长,反之朝
node_rand方向生长。


一个优选方案中,步骤3中还包括对步骤2中的所述路径点进行路径平滑处理,以
得所述路径点的平滑路径;所述平滑处理具体为利用多项式参数拟合方法生成曲率连续的
路径。


一个优选方案中,步骤3中Dubins曲线对步骤2中生成的路径点进行检测的具体步
骤如下:


步骤d、通过更新被检测路径点的集合内每个路径点的方向角,以记?#27982;?#20010;点的坐
标。


步骤e、从所述无人车行驶的起始点坐标开始,在所述随机树中的路径点内遍历相
邻的两点,检测相邻两点之间是否存在由右转、左转或行驶直线组成的Dubins曲线,其中,
所述Dubins曲线中右转或左转需满足所述无人车行驶的转弯半径,行驶直线需满足所述无
人车驾驶的行驶方向。


步骤f、若相邻两点之间检测不到Dubins曲线的可能性,则检测失败,以判定相邻
两点之中的遍历的下一点为无效点,则删除所述无效点;若删除无效点后的所述随机树中
路径点的集合中的路径点的密度低于第二阈值,则进入步骤2中;若删除无效点后的所述随
机树中路径点的集合中的路径点的密度不低于第二阈值,则通过剩余点生成平滑路径后,
进入步骤d;若相邻两点之间检测到Dubins曲线的可能性,则进入步骤e,直至检测到最后一
个路径点,仍未产生无效点,则所述被检测路径点的集合通过检测。


步骤g、通过步骤f中检测通过的所述被检测路径点的集合建立平滑路径,以得到
所述无人车行驶最终的避障路径。


在上述方案中,为了生成满足车辆转弯半?#23545;?#26463;的路径,对路径点一一检测。集合
Ni是第i次循环时的路径点,Pi是集合Ni的平滑路径。Ni_n是集合Ni中第n个点。点的密度m
为路径平滑处理后的路径长度与路径点数量之?#21462;?br>

1)更新Ni中每个点的yaw值(方向角),并记?#30002;?#26631;为(x,y,yaw)。Ni_n的yaw值(方
向角)由Pi中距离Ni_n最近的点决定。


2)从起点开始,遍历相邻两点,检测从Ni_n到Ni_n+1之间是否存在由右转(R),左
转(L)或驾驶直(S)组成的dubins曲线,需要满足转弯半径、前进方向。


3)如果由Ni_n到Ni_n+1检测不到dubins曲线的可能性,则检测失败,令Ni_n+1点
为无效点。


4)在路径中删除无效点,此时,如果密度m不低于第二阈值,再次通过剩余点生成
平滑路径,然后回到步骤1),其中,第二阈值为0.2个/米。


5)如果删除无效点后,密度m低于阈值,回到步骤2,生成新的路径点,经过平滑处
理后重新路径点检测。


6)检测到最后一个路径点后,如果依然没有产生无效点,则通过检测,生成最终的
避障路径。


一个优选方案中,步骤e中每个路径点的方向角选定是由所述平滑路径中距离所
述被检测路径点的集合中最后一个路径点的最近的点决定。


在上述方案中,Ni_n的yaw值(方向角)由Pi中距离Ni_n最近的点决定,每个路径点
方向角的选定,均以所述最近的点为参照,以保证方向选择的可靠性。


尽管本发明的实施方案已公开如上,但其并不仅仅限于说明书和实施方式中所列
运用,它完全可以被适用于各种适合本发明的领域,对于熟悉本领域的人员而言,可容易地
实?#33267;?#22806;的修改,因此在不背离权利要求及等同?#27573;?#25152;限定的一般概念下,本发明并不限
于特定的细节和这里示出与描述的图例。


关于本文
本文标题:基于快速扩展随机树的无人车避障方法.pdf
链接地址:http://www.pqiex.tw/p-6151615.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 大乐透走势图500 大乐透后区和值走势图新浪爱彩 贵州11选5开奖直播 极速飞艇开奖走势 福建十一选五预测号码今天 下载福建十一选五开奖结果 浙江11选5 山西11选5走势图手机版 福建11选5开奖公告 送20元可提现棋牌游戏