文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 一种改进的RRT路径规划算法
侵权投诉

一种改进的RRT路径规划算法

路径规划

第2A期2010年2月

ACrAⅡ正㈣NICA

电子学报

SINlCA

V01.38No.2A

Feb.2010

一种改进的RRT路径规划算法

宋金泽,戴斌,单恩忠,贺汉根

(国防科学技术大学机电工程与自动化学院,湖南长沙410073)

摘要:本文以自主驾驶车辆为实际应用背景.提出了一种改进的Rl订(快速随机搜索树)路径规划算法.该路径规划算法将非完整性约束条件与双向多步扩展RRT搜索算法相结合,在提高搜索效率的同时保证了规划路径的可行性.同时将路径点作为B样条基函数的控制点,用三次B样条函数来拟合控制点生成平滑可跟踪的路径.通过在平面障碍物环境下实验,验证了该算法的有效性.

关键词:

路径规划;快速随机搜索树(RRT);B样条曲线

文献标识码:

A

中图分类号:TP242文章编号:0372.2112(2010)2A.225-04

AnImprovedRRTPathPlanningAlgonthm

SONGJin-冼,DAIBin,SHAN

(SdIl越ofMedum'an/c

Eng/ne日/ng

and

Automat/on,hht/ona/‰蚵of瑰触Tedmo/agy,al嘞,‰410073,Odna)

ALV(automatic

land

En-zhong,眦Han—gen

AI删:加rniIlg

Trees)path

RRTs,which

not

at

theapplicationofvehicle),a11

improved

RRT(Rapidly姗exploring

at

planningalgorithmispr0110s。d.Tilealgorithmcombinesthenoholonomic

only

as

constraintsofve砸cle嘶ttldoubleextend

iI/lpl'OV豁theefficiencyofsearchingbutalsoguaranteesthefeasibilityofthepaltl

the涨time.The

pam

points虢taken

cle

to

reference

rmtsfortheB-spline

basicfI瑚cdon.approachand

create

a

Newsmooth

route

whichsuitsforthevehi-

follow.ThesimulationoutcomesandfieMtests

verifytheeffectivenessofthemethodproposed.

KeyⅥIords:p日lll

planning;Rapidly砌Ⅲ岫I卜cxplc嘧培Trees(砌玎);B-spline

研究,由于其采用随机采样的规划方法,不需要预处理,而且搜索速度快,尤其在高维空间中速度优势尤为明显,因此这种算法得到了很多研究者的青睐.RRT算法是基于树结构的典型算法,同时又是基于采样的规划算法,由于其两个路径点之间可以是经过运动学、动力学仿真生成的可执行曲线,并不是两点间的任意几何曲线,所以其适合被用来解决含有运动动力学(kinodyrmm—ic)约束的路径规划问题.

目前RRT搜索算法也产生了很多改进,早期主要采用单棵RRT树进行搜索,为了进一步提高搜索速度,一些学者提出了偏向褂洱7I、双向RR一8J搜索算法。本文在考虑车辆自身非完整性约束的情况下,将非完整性约束条件与双向多步扩展RRT搜索算法相结合,在保证规划路径的可行性的同时提高了搜索效率.

但是RRT搜索连通路径后,由于其算法本身的随机性,产生的路径会存在绕远或者出现明显的拐角,使生成的路径不平滑.在此基础上,本文进一步采用B样

Random-exploring

1引言

路径规划问题在机器人领域由来已久,很难找到一个有效的路径规划方法来应对各种复杂环境,有的时候往往是顾此失彼,不得不在算法完整性和效率之间进行权衡.ALV(自主陆地车辆)是智能机器人领域的一个分支,随着其技术的发展和对其研究的深入,一些亟待解决的实际问题凸显出来,比如规划的路径要满足车辆本身的动力学约束,动态环境下规划算法效率要满足实时性要求等等.

一些研究者用神经网络…1、遗传算法【2J等方法来解决ALV的路径规划问题,由于算法在实时性、收敛速度等方面的一系列缺点,使得在实际应用中不能满足效率的要求,D¨3J、PRM(概率路图法)【4J等算法在搜索路径时能满足最优性和实时性㈨5的要求,但是未考虑车辆非完整性约束的限制,对于自主车来说连通的路径不一定可跟踪.

近年来RRT(Rapidly

Trees)算法作

为一种快速的搜索方法在路径规划领域得到了广泛的

条基函数来拟合RRT生成的路径点,从而生成曲率连续的平滑路径.通过实验验证了该算法的有效性.

收稿日期:2009-04-07;修回日期:2009-05-22

基金项目:国家自然科学基金重点项目(№.90820302);国家自然科学基金(No.60774076)

万方数据

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email