大家好!我是MPIG的李琪,好久不见。今天要讲是机器人学中一个非常重要的领域:路径规划(path planning),路径规划问题在移动机器人领域一直是一个备受关注的问题,而今天我们要介绍的RRT算法(RRT/ rapidly exploring random tree)正是路径规划中的一种重要的算法。
首先我们来看一些基本介绍:
紧接着我们来了解一下详细的算法流程和详细图解:
我们先用一段简单的代码来展示随机树的扩展过程
#!/usr/bin/env python
# rrt.py
# This program generates a simple rapidly
# exploring random tree (RRT) in a rectangular region.
# Written by Steve LaValle
# May 2011
importsys,random,pygame,msvcrt
frompygame.localsimport*
frommathimportsqrt,cos,sin,atan2
#constants
XDIM=640
YDIM=480
WINSIZE=[XDIM,YDIM]
EPSILON=7.0
NUMNODES=5000
defdist(p1,p2):
returnsqrt((p1[]-p2[])*(p1[]-p2[])+(p1[1]-p2[1])*(p1[1]-p2[1]))
defstep_from_to(p1,p2):
ifdist(p1,p2)
returnp2
else:
theta=atan2(p2[1]-p1[1],p2[]-p1[])
returnp1[]+EPSILON*cos(theta),p1[1]+EPSILON*sin(theta)
defmain():
#initialize and prepare screen
pygame.init()
screen=pygame.display.set_mode(WINSIZE)
pygame.display.set_caption('RRT S.LaValle May 2011')
white=255,240,200
black=20,20,40
screen.fill(black)
nodes=[]
nodes.append((XDIM/2.0,YDIM/2.0))# Start in the center
# nodes.append((0.0,0.0)) # Start in the corner
foriinrange(NUMNODES):
rand=random.random()*640.0,random.random()*480.0
nn=nodes[]
forpinnodes:
ifdist(p,rand)
nn=p
newnode=step_from_to(nn,rand)
nodes.append(newnode)
pygame.draw.line(screen,white,nn,newnode)
pygame.display.update()
#print i, " ", nodes
foreinpygame.event.get():
ife.type==QUITor(e.type==KEYUPande.key==K_ESCAPE):
sys.exit("Leaving because you requested it.")
# if python says run, then we should run
if__name__=='__main__':
main()
input()
紧接着我们在地图中加入障碍物并在代码中加入障碍物判断,得到如下结果:
看起来我们已经完美实现了RRT算法,但是其实在这种原始的RRT算法并不是效果最好的,想要应用于实际场景并且得到更好的效果,我们需要依据实际问题对RRT算法进行改进。
而具体改进的细节和讲解,请观看下面的讲解视频:
想获取本presentation的对应文稿和代码,可以点击如下链接下载:
领取专属 10元无门槛券
私享最新 技术干货