专利摘要

本发明公开了一种改进双向快速搜索随机树算法的智能车路径规划方法，包括以下步骤：1)起始点和目标点两棵树相向搜索；2)节点扩展时同时生成两个随机采样点，选择距离目标点较近的采样点为下一扩展节点提供方向；3)结合目标引力思想，根据概率来判断是以目标点还是随机采样点作为扩展节点方向；4)产生动态目标点，两棵随机树分别选择对方生成的最新节点作为目标；5)判断扩展过程中是否发生碰撞，若有则重新生成新的采样点；6)两棵树的最新节点间距小于一定阈值则生成路径；7)将路径结合车辆的非完整约束模型；8)采用B样条曲线对生成路径进行优化。与现有技术相比，本发明具有路径更短，实时性更高，考虑非完整约束等优点。

权利要求

1.一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，具体包括以下步骤：

1)起始点和目标点两棵树相向搜索；

2)开始生成新节点，在节点扩展时，在地图上同时生成两个随机采样点，并通过距离函数来选择距离目标点较近的采样点来为下一扩展节点提供方向；

3)结合目标引力思想，根据概率来判断生成下一节点时是以目标点还是上一步新生较近随机采样点作为扩展节点方向；

4)在规划过程中，产生动态目标点，加快规划速度，两棵随机树分别选择对方生成的最新节点作为目标；

5)判断扩展过程中是否与障碍物或者地图边界发生碰撞，若碰撞，则重新生成新的采样点；否则，产生新节点；

6)两棵树的最新节点小于一定阈值，则生成路径；

7)结合车辆的非完整约束模型，提高生成路径的可行性；

8)采用B样条曲线对生成路径进行优化，提高路径的平滑性。

2.根据权利要求1所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤3)包括：

在进行采样时，采用启发式采样，其随机树在进行扩展时，通过随机概率p1(1>p1≥0)来确定目标点作为随机采样点的可能性，设定参照概率p，当p<p1，选择随机采样点作为最终采样点，当p1>p，选择目标点作为最终采样点，当目标点作为采样点时，使得随机树的生长具有一定的方向性和收敛性，能够提高随机树的扩展能力。

3.根据权利要求2所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤3)还包括：计算扩展树新生节点qnew时，基本RRT中计算公式为：

qnew＝qnear+step(qrand-qnear)/||qrand-qnear||

其中，step为扩展时随机树的步长，(qrand-qnear)表示两向量单位化，||qrand-qnear||表示两点间欧氏距离，qrand为随机点，qnear为距离随机点最近的一个邻近节点；

加入目标引力思想的新生节点qnew计算公式为：

qnew＝qnear+step1(qrand-qnear)/||qrand-qnear||+step2(qgoal-qnear)/||qgoal-qnear||

step1为随机树向随机点方向扩展的步长，step2为随机树向目标点方向扩展的步长，qgoal为目标点，||qgoal-qnear||为qgoal和qnear间的欧氏距离。

4.根据权利要求1-3中任一所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤2)具体包括：

使用采样函数在规划地图上同时生成两个随机采样点，用距离函数来计算上一新生节点与两随机采样点之间的距离，选择距离目标近的随机采样点来为下一扩展节点提供方向，加快缩短路径规划距离。

5.根据权利要求1所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤4)具体包括：

产生动态目标点，在一棵随机树产生新的节点时，另一棵树的下一次扩展将以此新生节点作为目标点进行生长。

6.根据权利要求1所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤5)具体包括：

当原始节点向着最终采样点扩展时，判断是否会与障碍物或者地图边界发生碰撞，如果碰撞则舍弃此最终采样点，回到步骤2)；不碰撞则依照设定步长来扩展随机树长度到最终采样点。

7.根据权利要求1所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤6)具体包括：

当两棵随机树相向不断进行扩展，每生成新的节点，要计算出两棵树新生节点之间的距离，在给定的阈值下，若新生节点之间的距离小于等于阈值，则直接连接两棵随机树，生成初始路径，否则依照步骤2)至5)继续生成新节点。

8.根据权利要求1所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤7)具体包括：

设智能车在任务空间中状态变量为(x,y,θ,v,φ)，其中(x,y)为无人车后轮轴的中心在系统坐标系下的坐标，θ为移动机器人前进方向与x轴的夹角，v为移动机器人的速度，φ为无人车前进方向与前车轮之间的夹角，因为无人车受到非完整性约束，故车轮和地面是点接触，假设接触点只有纯滚动不产生相对的滑动，则智能车的运动方程为：

根据运动方程，智能车所受到的约束方程为：

其中，智能车的控制变量为加速度u0和车轮的角速度u1，智能车的最小转弯半径的计算式如下：

式中Kmax为最大曲率，φmax为车辆前轮最大转向角，L为轴距，Rmax为最小转弯半径；

约束条件还包括：

9.根据权利要求1所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤8)具体包括：

B样条曲线具有灵活性、连续性和直线保持性等优点。准均匀B样条曲线会经过端点，用此法来拟合路径，以生成符合车辆运动学约束的可执行轨迹；B样条曲线的基函数如下：

端点位置的算式如下：

曲线函数如下：

10.根据权利要求1所述的一种改进双向快速搜索随机树算法的智能车路径规划方法，其特征在于，所述的步骤1)具体包括：

从起始点生成一棵随机扩展树向着目标点生长，从目标点生成一棵随机扩展树向着起始点生长，两棵树相向生长，缩短路径规划时间。

一种改进双向快速搜索随机树算法的智能车路径规划方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。