机器人学：RRT算法

大家好！我是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的对应文稿和代码，可以点击如下链接下载：