路径规划
第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)
万方数据
基于一种改进RRT算法的足球机器人路径规划_专业资料。针对足球机器人运用传统快速扩展随机树(RRT)算法进行路径规划时随机性大的问题,提出了一种目标引力式的RRT路径...
本文提出一种 新的 RRT 改进算法, 使用基本 RRT 算法规划出一条路径, 同时 通过对上周期的扩展树进行剪枝和连接, 得到另外一条适用 于本周期环境的路径。通过...
万 方数据 3期 康亮 等:未知环境下改进的基于RRT算法的移动机器人路径规划 339 3 滚动规划移动机器人在运动过程中能探知其传感范围内 C。h={P∈C rob(p)...
一种改进的机器人滚动路径规划算法_专业资料。研究了复杂未知环境下移动机器人... 移动机器人路径规划的一... 4人阅读 5页 2.00 基于模糊滚动RRT算法的...
一种改进的机器人滚动路径规划算法_专业资料。针对静态和动态障碍物共存环境中... 机器人在线路径规划改进... 7人阅读 4页 2.00 基于一种改进RRT算法的...
未知环境下改进的基于RRT算法的移动机器人路径规划 未知环境下改进的基于RRT算法的移动机器人路径规划未知环境下改进的基于RRT算法的移动机器人路径规划隐藏>> 第22...
一种基于改进遗传算法的机器人路径规划方法_专业资料。在应用遗传算法进行机器人路径规划时,为了解决传统遗传算法“早熟收敛”和“收敛速度慢”的问题,设计了一种...
基于改进群搜索优化算法的群体路径规划方法_专业资料。针对群体动画中传统路径... 基于社会群体搜索算法的... 0人阅读 11页 3.00 基于对比优化的RRT路径...
针对旅游景区路径规划问题的复杂性,将景区路径分为全景区图和子景区图,并归为同一问题解决。提出一种改进蚁群算法,设计繁殖蚂蚁、视觉蚂蚁和普通蚂蚁,各类蚂蚁按...
热门文档