3国家863计划资助项目(No .2006AA04Z238)
收稿日期:2008-07-14;修回日期:2008-11-10作者简介 康亮,男,1980年生,博士研究生,主要研究方向为智能机器人、优化算法、路径规划.E 2mail:kangliang_0912@yahoo https://www.doczj.com/doc/8d13927840.html, .赵春霞,女,1964年生,教授,博士生导师,主要研究方向为智能机器人、虚拟现实、仿真系统.郭剑辉,男,1983年生,博士,主要研究方向为模式识别、机器人导航、信息融合.
未知环境下改进的基于RRT 算法的
移动机器人路径规划
3
康 亮 赵春霞 郭剑辉
(南京理工大学计算机科学与技术学院南京 210094)
摘 要 将快速扩展随机树(RRT )算法与基于滚动窗口的路径规划相结合,提出一种改进的移动机器人路径规划算法.该方法利用机器人实时测得的局部环境信息,以滚动方式进行在线规划,克服了RRT 算法通常只能在已知环境中进行移动机器人路径规划的限制,拓展了应用范围.规划时只考虑窗口环境地图,不必计算障碍物边线的解析式,节省了存储空间,算法实时性得以保证.在此基础上,算法引入启发式估价函数,使得随机树易于朝目标点方向生长.同时,运用回归分析生成新节点,避免了可能产生的局部极小,增强了算法搜索未知空间的能力.最后仿真实验验证了该方法的有效性.
关键词 移动机器人,路径规划,滚动规划,快速扩展随机树(RRT )中图法分类号 TP 24
Im proved Pa th Pl ann i n g Ba sed on Rap i dly 2Explor i n g Random Tree for M ob ile Robot i n Unknown Env i ronm en t
K ANG L iang,ZHAO Chun 2Xia,G UO J ian 2Hui
(College of Co m puter S cience and Technology,N anjing U niversity of Science and Technology,
N anjing 210094)
ABSTRACT
An i m p r oved path p lanning algorithm is p r oposed by combining rap idly 2exp l oring random tree (RRT )and r olling path p lanning .I n this algorith m ,the real 2ti m e l ocal envir on ment infor mati on detected by the r obot is fully used and the on 2line p lanning is perfor med in a r olling style .Theref ore,the RRT algorith m can be used in both known and unknown envir on ment .Only the l ocal envir onmental map is calculated in the p lanning t o i m p r ove the p lanning efficiency,and thus the p lanning in real ti m e is guaranteed .The calculati on of analytical exp ressi ons of the obstacle can be ignored .Hence,the me mory is saved greatly .Based on the alg orith m of rap idly 2exp l oring random ,the heuristic evaluati on functi on is intr oduced int o the i m p r oved algorith m ,s o that the exp l oring random tree can gr ow in the directi on of target point .The regressi on analysis,which avoids l ocal m ini m um ,enhances the capability of searching unknown s pace .The si m ulati on results verify the effectiveness of the i m p r oved algorith m.
Key W ords Mobile Robot,Path Planning,Rolling Plan,Rap idly 2Exp l oring Random Tree (RRT )
第22卷 第3期 模式识别与人工智能 Vol .22 No .3 2009年6月 PR &A I Jun 2009
1 引 言
移动机器人技术是近年来发展起来的一门综合学科,集中了机械、电子、计算机、自动控制以及人工智能等多学科最新研究成果,代表了机电一体化的最高成就[1].在移动机器人相关技术的研究中,导航技术是其核心,而路径规划是导航研究的一个重要环节和课题.所谓路径规划是指移动机器人按照某一性能指标(如距离、时间、能量等)搜索一条从起始状态到目标状态的最优或次优路径[2].
传统的路径规划方法主要有,人工势场法、模糊规则法、遗传算法、人工神经网络、模拟退火算法、蚁群优化算法、粒子群算法等.这些方法在解决一般的路径规划问题时有一定的优越性,但要应用于非完整性约束规划问题还存在很多问题.而非完整性规划和运动动力学规划恰恰又是机器人学及其他应用的一个重要领域.同时这些方法大都需要在一个确定性空间内对障碍物进行确定的建模和描述,计算复杂度与机器人自由度呈指数关系,不适合解决多自由度机器人在复杂环境中的规划.
快速扩展随机树(Rap idly2Exp l oring Random Tree,RRT)算法[2-4]是近几年发展起来的基于采样的单查询路径规划方法,目前应用较广泛.基于采样的单查询路径规划方法通过对状态空间的随机采样,把搜索导向空白区域.RRT算法因为避免了对空间的建模,与其他方法相比有独特的优势.该算法高效的搜索特性,使其适合解决高维空间多自由度机器人的复杂约束下的运动规划问题,能直接应用到非完整性约束或非完整性动力学约束规划中.
这种基于随机采样的运动规划方法由于其算法的随机性,所以具有概率完备性.在有解的前提下,算法获得可行解有保证.但该算法的固有规划方式限制了其进一步应用:1)随机搜索均匀一致在全局空间,导致算法无谓耗费代价较大;2)先全局搜索构建随机树,再一次性规划路径,导致算法通常只能应用在已知环境中,实时应用性较差;3)路径的搜索树由随机采样点生成,导致规划出的路径经常不是最优路径.
借鉴文献[5]中的滚动规划思想,本文采用反复的局部路径规划代替一次性的全局路径规划结果,实现了RRT算法在未知环境下移动机器人路径规划中的应用.利用滚动规划概念,无需对障碍物进行确定的建模,将随机采样限制在滚动窗口,避免全局采样,大大减少规划时间,提高算法的实时性.根据启发式函数生成滚动窗口子目标点,保证规划路径的最优性.为避免产生局部极小,利用回归分析扩展随机树新节点,算法搜索未知空间的能力因此大大增强.
2 基本的快速扩散随机树算法
2.1 随机树构建阶段
从初始位姿(状态)点x
init
出发构建随机树T.如图1所示
.
图1 基本的RRT构建过程
Fig.1 Constructi on of basic RRT
在位姿空间中随机选择一个位姿(状态)点x rand,遍历T,找到T上离x rand最近距离的节点x near,然后在控制输入集U里选择输入u∈U(如转向角、
速度等)作用在x
near
上,机器人沿着x
near
到x
rand
.依照状态转换方程产生满足全局约束的候选路径集
合,经历时间Δt,到达一个新状态构成x
new
集合.选
择使得x
new
到达x
rand
距离最近的控制输入u作为最佳控制输入.依次产生新状态,直至到达目标状态,随机树构建结束.
2.2 路径产生阶段
从目标状态点出发,找到父节点,依次进行,直至到达起始状态点,即树根.这样就规划出从起始状态点到达目标状态点满足全局和微分约束的路径以及在每一时刻的控制输入参数.因为在搜索的生成过程中充分考虑了机器人客观存在的微分约束(如非完整约束、动力学约束、运动动力学约束等),因而算法规划出来的轨迹合理性较好,但算法的随机性导致其只能概率完备.
随机算法以损失完备性为代价来提高执行效率,适合解决高自由度机器人在复杂环境中的运动规划,合理性较好.
833模式识别与人工智能 22卷
3 滚动规划
移动机器人在运动过程中能探知其传感范围内有限区域的环境信息,这部分信息必须充分利用.因此解决这一问题的指导思想是,采用反复进行的局部优化规划代替一次性全局优化的结果,并在每次局部优化规划中充分利用该时刻最新的局部环境信息.
滚动规划算法[13-14]的基本原理如下.1)环境信息预测.在滚动的每一步,机器人根据探测到的视野内的信息或所有已知的环境信息,建立环境模型,包括设置已知区域内的节点类型信息等.2)局部滚动优化.将上述环境信息模型看成一个优化窗口,在此基础上,根据目标点的位置和特定的优化策略计算出下一步的最优子目标,然后根据子目标和环境信息模型,选择局部规划算法,确定向子目标行进的局部路径,并实施当前策略,即依所规划的局部路径行进若干步,窗口相应向前滚动.3)反馈信息校正.根据局部最优路径,驱动机器人行走一段路径后,机器人会探测到新的未知信息,此时可根据机器人在行走过程探测到的新信息补充或校正原来的环境模型,用于滚动后下一步的局部规划.
局部子目标是在滚动窗口中寻找一个全局目标的映射,它必须避开障碍物,且满足某种优化指标.子目标的选择方法反映了全局优化的要求与局部有限信息约束的折衷,是在给定信息环境下企图实现全局优化的自然选择.
基于滚动窗口的路径规划算法依靠实时探测到的局部环境信息,以滚动方式进行在线规划.在滚动的每一步,根据探测到的局部信息,用启发式方法生成优化子目标,在当前滚动窗口内进行局部路径规划,然后实施当前策略(依局部规划路径移动一步),随滚动窗口推进,不断取得新的环境信息,从而在滚动中实现优化与反馈的结合.由于规划问题压缩到滚动窗口内,与全局规划相比其计算量大大下降.
4 启发滚动快速扩散随机树算法
4.1 位姿空间建模
设在工作区域分布着一个或多个障碍物,将移动机器人模型化为点状机器人,同时工作区域中障碍物根据机器人的实际尺寸进行相应的膨化处理.机器人无全局环境信息,令C代表位姿空间,是所有机器人可能位姿的集合.令
C obs={p∈C|rob(p)∩obs≠ },
表示C空间障碍物.C
free
=C/C obs表示自由空间.
C obs与C free均为C的子集,具有相同的边界.因此机
器人路径问题的几何约束条件可表示成T(p
s
,p g).
机器人路径规划就是找到一条从初始状态p
s
∈C
free 到一个目标状态p
g
∈C
free
的一条路径.一条轨迹就是被定义为一个时间参数化的连续路径τ∶[0,T]
→C
free
.设环境中包含静态障碍物,一个碰撞检测算法能够有效检测一个给定的位姿状态是否在障碍物中.
4.2 构造滚动窗口
在实际应用中,环境对于机器人来说往往只是部分已知甚至是完全未知的.不完整环境信息下的机器人导航通常是基于传感器数据的.本文只考虑二维平面的运动规划问题.机器人由于车轮滑动等因素造成的运动误差不予考虑.
以周期方式驱动,在滚动的每一步,定义以机器人当前位置为中心的区域为优化窗口.而
W in(p R(t))={p|p∈C,d(p,p R(t))≤r}
称为机器人在p
R
(t)处的视野域,亦即该点的滚动窗口,其中r为机器人传感器的探测半径.在构造滚动窗口时,只利用传感器的读数进行路径规划,不必计算障碍物边线的解析式.这样可节省存储空间,提高计算速度.
局部子目标最优点O
i
由收敛标准评价函数决定,在下一节中将说明选择标准的评价函数.子目标收敛标准的选择反映了全局优化的要求与局部有限信息约束的折衷,是在给定信息环境下企图实现全局优化的自然选择.
该区域的环境模型,一方面是全局环境信息向该区域的映射,另一方面还补充了传感器系统检测到的原来未知的障碍物.以当前点为起点,根据全局先验信息确定该窗口区域的局部目标,根据窗口内信息所提供的场景预测进行规划,找出适当的局部路径,机器人依此路径移动,直到下一周期.
4.3 随机采样规划
滚动窗口随机树以当前路径点p
R
(t)为起始点x init,构建以探测半径为窗口半径范围内的随机树.
该随机树表示为T
k
,是一个最多有K节点的RRT,且T k∈C free.x为T k的节点,x∈T k,x init为T k的根节点.
如图1,令x
rand
为滚动窗口C空间中一个随机选取的
位姿状态,且x
rand
∈C
free
.
由于节点x
rand
选取的任意性,导致了随机树的生长形状具有随机性,从而导致规划的路径优化性也存在随机性.
933
3期 康 亮 等:未知环境下改进的基于RRT算法的移动机器人路径规划
为减少路径规划的随机性,使随机树有向目标点生长的特性,本文在RRT算法的基础上,根据最短路径思想,在构建随机树时引入启发式估价函数.使随机树构建时既可绕过障碍物,又可朝着目标点方向生长.在路径规划中引入启发信息能提高搜索的效率,有利于减少随机树生长的随机性,并使规划出的路径接近最短路径.
令R oad(x
1
,x2)代表随机树中两个位姿节点间
的路径代价,D is(x
1
,x2)代表随机树中两个位姿节点间的欧几里德距离.类似于A3算法,本文为随机树中每个节点定义一个估价函数:f(x)=g(x)+ h(x).其中g(x)=R oad(x,x rand)是随机节点x rand 到树中节点x所需的路径代价.h(x)为启发估价函
数,这里取随机节点x
rand 到目标终点x
goal
的平面距
离为估价值,h(x)=D is(x
rand
,x goal).因此f(x)表示
从节点x经随机节点x
rand 到目标节点x
goal
的路径估
计值.遍历滚动窗口内随机树T,取估价函数最小值的节点x
near
,有f(x near)=m in(f(x)).这使得随机树沿着到目标节点估价值f(x)最小的方向进行扩展.
在控制输入集U里选择输入u∈U(如转向角、
速度等)作用在x
near 上,在点x
rand
与x
near
之间求点
x new.x new必须满足x new∈C free且D is(x new,x near)=ρ
的条件,其中ρ>0为RRT生长的最小单位长度,称为步长.如果存在x
new
,则T k增加一个新节点.令T k+1表示新的RRT,则T k=T k+1+x new.否则重新选
取x
rand
,重复以上过程.
调用随机树扩展函数添加新节点时,可能会有3种情况:1)新节点x new与随机节点x rand间的距离小
于步长,则x
new 就是x
rand
;2)可以找到新节点x new将
其加入RRT,但x
new 不是随机节点x
rand
;3)所计算的
新节点x
new 位于C
obs
,则重新选择扩展随机树.
由于在随机树生长中引入导向目标的启发估价
因子,叶节点x
near
总是选择离目标最近的节点,这可能会使随机树遇到局部极小值问题.因此随机树生
长的新节点x
new
必须要克服这个问题,引导随机树更好地探索未知空间.
本文利用统计学中回归分析[15]生成新节点,将RRT算法探索未知空间的能力进一步增强以避免因启发估价因子导致的局部极小.其思想是探索以前到过的空间是无用的,而且容易陷入局部极小.引进回归分析(Regression A nalysis)是考察新节点与其他节点之间关系,利用回归函数约束,使得随机树不探索以前到过的空间,因此避免局部极小.
新节点生成方法是遍历随机树,如果x
new
与其
父节点x
near 的距离小于x
new
与扩展树上其它任意节
点的距离,则选择该节点为随机树新生节点.图2解
释了新节点的选择过程
.
(a)一个节点的可能扩展(b)树中节点的所有扩展
(a)Possible expansions for a node(b)A ll expansions in tree
图2 新节点的选择
Fig.2 Selection of new node
在图2中,实心点表示树中原有节点,空心点表
示树中节点可能的扩展新节点.线段表示随机树中
连接各节点的边.图2(a)表示一个节点在随机树生
成新节点时的可能扩展.椭圆圈起的空心节点表示
不符合回归函数约束,剩下唯一一个空心节点到其
父节点的距离小于该节点到随机树上任意节点的距
离,因此选择该节点作为随机树扩展的新节点.图
2(b)表示随机树上节点的所有可能扩展.可以看
出,本文的随机树具有强烈探索未知空间的倾向.这
样使得规划路径能绕开障碍物和走出局部极小,继
续向着目标点方向进行探索,利于随机树的叶节点
向着空旷未探索过的地带发展.
综上所述,滚动窗口内随机树构建的具体步骤
如下.
step1 对滚动窗口随机树T初始化,T开始只
包含初始节点x
init
.
step2 滚动窗口C free空间中随机选择一个状
态x
rand
.
step3 根据最短路径思想寻找树T中和x rand
距离最近的节点x
near
.
step4 选择输入u,使机器人状态由x near到
x new.
step5 确定x new是否符合回归分析,不符合则
回到step4.
step6 将x new作为随机树T的一个新节点,u
则被记录在连接节点x
near
和x
new
的边上.
滚动窗口状态空间进行K次采样后,遍历随机
树,根据启发估价思想寻找滚动窗口子目标x
sub
.根
据子目标收敛标准评价函数,
?x∈T k|f(x sub)=m in{f(x)}.
043模式识别与人工智能 22卷
这里的f(x)=g(x)+h(x).其中g(x)= R oad(x init,x)为随机树从初始节点x init到节点x的路径代价,h(x)为随机树节点x到目标终点的估价值,估价函数中h(x)的选取影响求解最优路径的效率和结果.为保证找到最短路径(最优解的)条件,对于2D环境来说,一般取两节点间欧几里德距离(直线距离)D is(x,x goal)作为估价值.滚动窗口的状态空间采样次数和窗口大小相关,按不同应用场合,配置不同参数.
确定滚动窗口内的子目标后,搜索滚动窗口随机树,规划窗口内从起始节点到子目标节点的路径,机器人滚动前进到子目标点,进行下一轮的滚动规划RRT.机器人这样不断滚动前进,直至到达目标终点.
4.4 收敛性和最优性证明
在未遇到障碍物时,子目标节点启发式估价函数是单调递减的,因而此情况下的路径长度是有限的.在遇到障碍物时,总是选择估价函数最小值节点为规划路径下一节点,因而此情况下的每一步路径长度也是有限的.因此,算法最终会在一个有限长度的路径上停止.如果目标终点可以到达,那么规划路径收敛到目标终点的可能性就会得到保证.
首先定义机器人路径是由一连串的节点组成.起点S,目标终点G.假设机器人工作在一个有限的几何空间中,环境空间中的每个障碍物都是有限周长,因此有以下结论.
1)在无障碍环境中,移动机器人的路径节点必定会终止在目标点G.
2)在未遇到障碍物时,移动机器人的规划路径长度必定是有限长度.
3)移动机器人绕开障碍物的路径长度将是有限长度.
下面给出算法的收敛性证明.如果移动机器人可以到达目标,那么成功规划的路径长度必定是有限长度.
证明 机器人的路径长度等于未遇到障碍物情况下和避障情况下的规划路径长度之和.由结论2),在未遇到障碍物情况下,机器人路径长度必定是有限长度.因为机器人工作在一个有限的几何空间中,所以障碍物的个数也必定是有限的.而每一个障碍物又都是有限周长,所以在避障情况下,机器人的路径长度也必定是有限长度.由结论3),机器人绕开障碍物的路径长度也必将是有限长度.因此,算法成功规划的路径长度必定是有限长度.
下面再给出算法的最优性证明.只要移动机器人可以到达目标,那么算法规划的路径长度将是最优.
证明 由上面的收敛性证明可知,如果移动机器人可以到达目标,那么成功规划的路径长度必定是有限长度.根据随机树节点启发估价函数定义,每一个子目标节点的选择一定是距离目标终点最近的节点.因此,算法成功规划的路径长度必定最优.
5 仿真实验
实验环境是用Matlab开发的,运行于PC机, CP U主频512MB.环境为30m×30m下的矩形区域,障碍物随机设置,大小任意,碰撞半径0.4m.起点设置坐标为(0,0),终点坐标设置为(30,30).
图3是基本RRT算法在已知环境下机器人的路径规划.可以看到RRT搜索树是随机均匀一致分布的.这适用于对地图环境先验已知,然后再实现路径规划.对于未知环境下机器人实时路径规划则不适用.但也清楚证明了基于RRT的路径规划算法对未知状态空间有强烈的搜索倾向.根据这一特点,本文提出滚动RRT,对未知环境下移动机器人实时路径规划进行研究
.
图3 基本RRT算法的路径规划
Fig.3 Path p lanning of basic
RRT
图4 滚动RRT算法的路径规划
Fig.4 Path p lanning of r olling RRT
143
3期 康 亮 等:未知环境下改进的基于RRT算法的移动机器人路径规划
图4是运用滚动RRT 算法进行路径规划.由于是滚动探测规划前进,适用于未知环境下的移动机器人路径规划,同时可以看到随机树相比于基本RRT 算法,其叶节点数量大大降低.
此时,扩展树分支有3519个叶节点,路径长度53m ,运行时间369s .而图3环境下的RRT 搜索树
的叶节点为8426个,运行时间581s .
图4中路径规划是单纯的滚动窗口和RRT 结合,没有任何启发思想引导,随机搜索到达目标.图5中同时利用本文提出的启发估价函数来确定滚动窗口内随机树的最近叶节点和目标节点.此时,搜索树分支有648个叶节点,路径长度44m ,运行时间116s
.
图5 启发滚动RRT 算法的路径规划
Fig .5 Path p lanning of heuristic r olling RRT
因为启发估价选择距离最小的叶节点进行RRT 树扩展,可能会导致局部极小,使得无法完成路径规划,如图6所示.为了解决这个增生问题,本文利用回归分析来筛选新节点,成功避免了这一问题,如图7所示
.
图6 启发滚动RRT 算法的局部最小
Fig .6 Local m ini m u m of heuristic r olling RRT
为验证算法的效果,本文进行大量的仿真实验.在图3、图4、图6的环境下,分别使用遗传算法
[16]
、
Vor onoi 图搜索
[17]
、人工势场算法[18]
、RRT 算法
[19]
和本文RRT 算法进行移动机器人路径规划.最终比较结果如图8和图9所示
.图7 利用回归分析走出局部最小的路径规划
Fig .7 Path p lanning avoiding l ocal m ini m u m by regressi on a 2
nalysis
图8 5种算法结果长度比较
Fig .8 Comparis on of path length a mong 5algorith m s
图8和图9是各种算法在不同环境中规划的路径长度和运行时间的比较.可以知道,遗传算法G A 函数虽然能进化到最优路径,但由于进化速度难以控制,需要经验参数太多,难以满足实时需要,不利于自动处理.Vor onoi 图搜索算法相比遗传算法在运行时间上有所改进,但由于其路径边最大限度远离障碍物,使得规划路径长度增加,不能保证是最优路径.人工势场APF 函数以其固有特点使得无论是路径长度还是运行时间都综合较优,但在图6所示的局部最小陷阱中会导致失败的路径规划.为清楚比较显示结果,本文中设置APF 算法在图6中无穷大运行时间为800s,无限长路径为200m.RRT 算法由
于是随机搜索,因此运行时间远高于同类规划算法.本文利用滚动窗口来生成搜索树,大大降低了运行时间.在图3、图4和图6所示环境下的机器人用时分别是基本RRT 算法的20.6%、23.3%、26.8%.由以上实验结果可以看出,与其他算法相比,本文算法
243模式识别与人工智能 22卷
的收敛速度有大幅提高,获得可行解的比例均高于
同类算法
.
图9 5种算法结果时间比较
Fig .9 Comparis on of running ti m e a mong 5algorith m s
6 结束语
本文分析了基本RRT 算法,利用滚动规划原理
将RRT 算法应用于未知环境下移动机器人路径规划.随机采样限制在滚动窗口,避免了全局采样,只利用传感器的读数进行路径规划,避免对障碍物进行确定的建模,减少规划时间,提高算法的实时性.算法在保持RRT 算法随机搜索特性同时,提出启发估价收敛标准函数来引导搜索树生长,很大程度上降低算法的规划时间.为解决因此产生的局部最小问题,本文利用回归分析来筛选新节点,即保留本文智能趋近目标的特性,同时又增强算法强烈探索未知空间的倾向.大量仿真实验结果表明,与其他算法相比,本文算法显著提高机器人规划效率,具有较高的计算实时性,适合机器人实际应用.
参
考文
献
[1]Cai Zhixing,He Hanggen,Chen Hong .Some Issues f orMobile Ro 2
bot Navigati on underUnknown Envir onments .Contr ol and Decisi on,2002,17(4):385-390(in Chinese )
(蔡自兴,贺汉根,陈虹.未知环境下移动机器人导航控制研究
的若干问题.控制与决策,2002,17(4):385-390)
[2]LaValle SM.PlanningA lgorithm s .Illinois,US A:University of Illi 2
nois Press,2004
[3]La Valle S M.Rap idly 2Exp l oring Random Trees:A New Tool for
Path Planning .
Technical Report,TR98211,Ames,US A:
I owa
State University .Depart m ent of Computer Science,1998
[4]LaValle SM ,Kuffner J.Rap idly 2Exp l oring Random Trees:Pr ogress
and Pr os pects //Pr oc of the I nternati onalWorkshop on A lgorithm ic Foundati ons of Robotics .Hanover,US A,2000:45-59
[5]Zhang Chungang ,Xi Yugeng.Rolling Path Planning and Safety
Analysis of Mobile Robot in Dyna m ic Uncertain Envir onment .Con 2
tr ol Theory and App licati ons,2003,20(1):37-44(in Chinese )
(张纯刚,席裕庚.动态未知环境中移动机器人的滚动路径规划
及安全性分析.控制理论与应用,2003,20(1):37-44)
[6]Laumond J P,Sekhavat S,La m iraux F .Guidelines in Nonhol onom ic
Moti on Planning for Mobile Robots .Lectures Notes in Contr ol and I nf or mati on Sciences,1998,229:1-53
[7]Melchi orN A,Si m mons R.Particle RRT for Path Planning with Un 2
certainty //Pr oc of the I EEE I nternati onal Conference on Robotics and Aut omati on .Roma,Italy,2007:1617-1624
[8]Kuffner J J J r,LaValle S M.RRT 2Connect:An Efficient App r oach
t o Single 2Query Path Planning //Pr oc of the I EEE I nternati onal Conference on Robotics and Aut omati on .San Francisco,US A,
2000,Ⅱ:995-1001
[9]Cheng Peng .Reducing RRT Metric Sensitivity for Moti on Planning
with D ifferential Constraints .Master D issertati on .Ames,US A:I o 2wa State University .Graduate College,2001
[10]de S m ith J.D istance and Path:The Devel opment,I nter p retati on
and App licati on of D istance Measure ment in Mapp ing and Modeling .Ph .D D issertati on .London,UK:University of London,2003[11]A l D ahak A,Elnagar A.A Practical 2Evasi on A lgorithm:Detecti on
and Tracking //Pr oc of the I EEE I nternati onal Conference on Ro 2botics and Aut omati on .Roma,Italy,2007:343-348
[12]U r m s on C .Locally Random ized Kinodyna m ic Moti on Planning f or
Robots in Extre me Terrain .Ph .D D issertati on .Pittsburgh,US A:Carnegie Mell on University .Robotics I nstitute,2002
[13]Xi Yugeng .Predictive Contr ol of General Contr ol Pr oble m s under
Dyna m ic Uncertain Envir onment .Contr ol Theory and App licati ons,2007,17(5):665-670(in Chinese )
(席裕庚.动态不确定环境下广义控制问题的预测控制.控制理
论与应用,2007,17(5):665-670)
[14]Tang Zhenm in,Zhao Chunxia,Yang Jingyu,et al .Local Traject o 2
ry Planning f or Aut onomous Land Vehicles,Robot,2001,23(7):742-745(in Chinese )
(唐振民,赵春霞,杨静宇,等.地面自主机动平台的局部路径规
划.机器人,2001,23(7):742-745)
[15]Kalisiak M ,van de Panne M.RRT 2B l oss om RRT with a Local
Fl ood 2Fill Behavi or //Pr oc of the I EEE I nternati onal Conference on Robotics and Aut omati on .O rlando,US A,2006:1237-1242[16]Sugihara K,S m ith J.Genetic A lgorithm s f orAdap tive Moti on Plan 2
ning of an Aut onomous Mobile Robot //Pr oc of the I EEE I nterna 2ti onal Sy mposium on Computati onal I ntelligence in Robotics and Au 2t omati on .Monterey,US A,1997:138-143
[17]Howie C,JoelB.Sens or 2Based Exp l orati on:I ncremental Construc 2
ti on of the H ierarchical Generalized Vor onoi Graph .The I nternati on 2al Journal of Robotics Research,2000,19(2):126-145[18]Agirrebeitia J,Avil és R,de Bust os I F,et al .A Ne w APF Strate 2
gy f or Path Planning in Envir onments with Obstacles .Mechanis m and Machine Theory,2005,40(6):645-658
[19]Ettlin A,B leuler H.Random ized Rough 2Terrain Robot Moti on
Planning //Pr oc of the I EEE /RSJ I nternati onal Conference on I ntel 2ligent Robots and System s .Beijing,China,2006:5798-5803
3
433期 康 亮 等:未知环境下改进的基于RRT 算法的移动机器人路径规划
遗传算法与机器人路径规划 摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 关键词：路径规划；移动机器人；避障；遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 （1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类： 1，已知环境下的对静态障碍物的路径规划； 2，未知环境下的对静态障碍物的路径规划； 3，已知环境下对动态障碍物的路径规划； 4，未知环境下的对动态障碍物的路径规划。 （2）也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型： 1，基于环境先验完全信息的全局路径规划； 2，基于传感器信息的局部路径规划。 （第二种中的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。） 1.2路径规划步骤 无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤： 1, 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型； 2, 路径搜索方法，即寻找合乎条件的路径的算法。 1.3路径规划方法
东南大学 硕士学位论文 移动机器人完全遍历路径规划算法研究 姓名：胡正聪 申请学位级别：硕士 专业：机械电子工程 指导教师：张赤斌 20080403
第一章绪论 第一章绪论 １．１移动机器人的发展史 社会的主体是人类，历史的推动者是人类，伟大的人类运用自己的智慧不断创造伟大的发明，不断推动社会的发展。邓小平同志说过：“科技是第一生产力。”生产力是社会发展的动力，所以人类推动社会发展就是要致力于发展生产力，致力于发展科技。人类不断发展生产力来提高自身认识自然、改造自然、得到自己所需物质的能力，这种能力的进化由最初的运用双手、简单工具、发展到运用畜力、发展到运用简单机器、发展到运用自动化设备、还会发展到我们无法想象的未来。 机器人就是生产力发展的产物。机器人的概念最早是在１９２０年的科幻小说中提出的，而早期的机器人如１９３９年美国纽约世界博览会上展出的西屋电气公司制造的家用机器人Ｅｌｅｋｔｒｏ和１９５６年美国人乔治?德沃尔制造出的世界上第一台可编程的机器人都是一些实用价值不高的机器人，它们是现代机器人的雏形。上世纪６０年代，由于传感器和计算机技术的发展及应用，兴起了全世界第二代机器人的研究热潮，并向人工智能进发。１９６８年，美国斯坦福研究所公布了他们研发成功的机器人Ｓｈａｋｅｙ。它带有视觉传感器，能根据人的指令发现并抓取积木。Ｓｈａｋｅｙ可以算是世界第一台智能机器人，它拉开了第三代机器人研发的序幕。到了上世纪８０年代，发达国家都组建各种机器人研究机构，尤其是以美国为代表的国家将机器人的研究列入了军事发展计划，带动各国把机器人的研究推上了高潮，日本和欧洲各国都成立了各自的机器人研究中心和规划了自己的研究计划。进入９０年代后，机器人的应用领域除了工业和军事外，还涉及到了服务和娱乐领域，以日本本田公司的ＡＳＩＭＯ人型机器人和索尼公司的ＡＩＢＯ娱乐机器人为代表的机器人展示了机器人领域各方面的先进研究成果。在欧洲，２００２年丹麦ｉＲｏｂｏｔ公司推出了吸尘器机器人Ｒｏｏｍｂａ，它能避开障碍，自动设计行进路线，还能在电量不足时，自动驶向充电座。Ｒｏｏｍｂａ是目前世界上销量最大、最商业化的家用机器人。２００６年６月，微软公司推出ＭｉｃｒｏｓｏＲＲｏｂｏｔｉｃｓＳｔｕｄｉｏ，机器人模块化、平台统一化的趋势越来截明显，比尔?盖茨预言：“家用机器人很快将席卷伞球。” 图１．１丹麦ｉＲｏｂｏｔ公司推出的吸尘机器人Ｒｏｏｍｂａ［
1绪论 1.1机器人简介 1.1.1什么是机器人 机器人一词不仅会在科幻小说、动画片等上看到和听到，有时也会在电视上看到在工厂进行作业的机器人，在实际中也有机会看到机器人的展示。今天，说不定机器人就在我们的身过，但这里我们要讨论的是什么是机器人学研究的机器人。 机器人（robot）一词来源下1920年捷克作家卡雷尔. 查培克（Kapel Capek）所编写的戏剧中的人造劳动者，在那里机器人被描写成像奴隶那样进行劳动的机器。 后来作为一种虚构的机械出现在许多作品中，代替人们去完成某些工作。20世纪60年代出现了作为可实用机械的机器人。为了反这种机器人同虚构的机器人及玩具机器人加以区别，称其为工业机器人。 工业机器人的兴起促进了大学及研究所开展机器人的研究。随着计算机的普及，又积极地开展了带有智能的机器人的研究。到70年代，机器人作为工程对象已经被确认，机器人一词也受到公认。目前，机器人学的研究对象已不仅仅是工业机器人了。 即便是实际存在的机器人，也很难把它定义为机器人，而且其定义也随着时代在变化。这里简单地反具有下述性质的机械看作是机器人： 1.代替人进行工作：机器人能像人那样使用工具和机械，因此，数控机床和 汽车不是机器人。 2.有通有性：既可简单地变换所进行的作为，又能按照工作状况的变化相应 地进行工作。一般的玩具机器人不能说有通用性。 3.直接对个界作工作：不仅是像计算机那样进行计算，而且能依据计算结果 对外界结果对外界产生作用。 机器人学把这样定义的机器人作为研究对象。
1.1.2机器人的分类 机器人的分类方法很多，这里我们依据三个有代表性的分类方法列举机器人的种类。 首先，由天机器人要代替人进行作业，因此可根据代替人的哪一个器官来分类： 操作机器人（手）：利用相当于手臂的机械手、相当于手指的手爪来使物体协作。 移动机器人（腿）：虽然已开发出了2足步行和4足步行机器人，但实用的却是用车轮进行移动的机器人。（本文以轮式移动机器人作为研究对象）视觉机器人（眼）：通过外观检查来除掉残次品，观看人的面孔认出是谁。虽然还有使用触觉的机器人，但由于它不是为了操作，所以不能说是触觉机器人。 也还有不仅代替单一器官的机器人，例如进行移动操作，或进行视觉和操作的机器人。 其次，按机器人的应用来分类： 工业机器人：可分为搬送、焊接、装配、喷漆、检查等机器人，主要用于工厂内。 极限作业器人：主要用在人们难以进入的核电站、海底、宇宙空间等进行作为的机器人。也包括建筑、农业机器人等。 娱乐机器人：有弹奏乐器的机器人、舞蹈机器人、宠物机器人等，具有某种程度的通用性。也有适应环境面改变行动的宠物机器人。 最后则是按照基于什么样的信息进行动作来分类： 表1基于动作信息的机器人分类
3.23机器人路径运动操作步骤 任务：选取多个点构成一条路径，通过示教器完成机器人路径运动操作 相关知识：机器人路径示教器操作分为手动和自动两种模式 操作步骤： 一、手动模式 1、新建程序 （1）点击首页下拉菜单中“程序编辑器”选项，进入程序编辑器 （2）点击右上角“例行程序”选项，进如程序列表 （3）点击左下角“文件”，选择“新建例行程序”，新建例行程序 并命名 2、程序编写 （1）选择新建好的例行程序，进入程序编辑页面，点击左下角“添 加指令”，在右侧弹出菜单中选择轴运动指令“MoveJ” （2）根据需要修改显示的“MoveJ * ,v1000 , z50 , tool0”指令， *代表坐标点名称，v1000代表速度，z50代表路径选择幅度， tool0与工具坐标有关 （3）根据需要添加路径包含的点坐标并修改，完成全部路径点的设 置 3、调试 （1）从第一行“MoveJ”指令开始，利用示教器旋钮调节机器人至路 径点位，点击“修改位置”，程序与点位一一对应 （2）点位修改完成后，进行手动调试。点击“调试”选择“PP移动 至例行程序”，进入要调试的例行程序，光标选择调试的程序 行，再次点击“调试”，选择“PP移动至光标” （3）在右下角设置选项中选择机器人运行的速度
（4）左手按下示教器使能键，右手按下示教器上的“开始”按钮， 进行机器人路径运行操控 注意：机器人运行过程中不能松开示教器使能键 二、自动模式 1、完成手动调试模式调试后，点击“例行程序”菜单进入程序选择列表， 选择“Main”函数，进入函数编辑页面 2、光标选择
第5期(总第156期) 2009年10月机械工程与自动化 M ECHAN I CAL EN G I N EER I N G & AU TOM A T I ON N o 15 O ct 1 文章编号:167226413(2009)0520194203 机器人路径规划方法的研究 李爱萍,李元宗 (太原理工大学机械工程学院,山西 太原 030024) 摘要:路径规划技术是机器人学研究领域中的一个重要部分。目前的研究主要分为全局规划方法和局部规划方法两大类。通过对机器人路径规划方法研究现状的分析,指出了各种方法的优点及不足,并对其发展方向进行了展望。 关键词:机器人;全局规划;局部规划中图分类号:T P 242 文献标识码:A 收稿日期:2009201207;修回日期:2009204218 作者简介:李爱萍(19792),女,山西晋中人,在读硕士研究生。 0 引言 路径规划技术是机器人学研究领域中的一个重要 部分。机器人的最优路径规划就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等),在其工作空间中找到一条从起始状态到目标状态的最优路径。根据对环境信息的掌握程度不同,路径规划可分为:①全局路径规划:环境信息完全已知,根据环境地图按照一定的算法搜寻一条最优或者近似最优的无碰撞路径,规划路径的精确程度取决于获取环境信息的准确程度;②局部路径规划:环境信息完全未知或部分未知,根据传感器的信息来不断地更新其内部的环境信息,从而确定出机器人在地图中的当前位置及周围局部范围内的障碍物分布情况,并在此基础上,规划出一条从当前点到某一子目标点的最优路径。 1 全局规划方法111 栅格法 栅格法是目前研究最广泛的路径规划方法之一。该方法将机器人的工作空间分解为多个简单的区域(栅格),由这些栅格构成一个显式的连通图,或在搜索过程中形成隐式的连通图,然后在图上搜索一条从起始栅格到目标栅格的路径。一般路径只需用栅格的序号表示。但栅格的划分直接影响其规划结果,如果栅格划分过大,环境信息储藏量小,分辨率下降,规划能力就差;栅格划分过小,规划时间长,而且对信息存储能力的要求会急剧增加。112 可视图法 可视图法中的路径图由捕捉到的存在于机器人一 维网络曲线(称为路径图)自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应,这样路径规划问题就演变为在这些点间搜索路径的问题。要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是“可视的”。然后采用某种方法搜索从起始点到目标点的最优路径,搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。该法能够求得最短路径,但需假设忽略机器人的尺寸大小,使得机器人通过障碍物顶点时离障碍物太近甚至接触,并且搜索时间长。113 拓扑法 拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此的连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。拓扑法的基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。其优点在于利用拓扑特征大大缩小了搜索空间,其算法的复杂性仅依赖于障碍物数目,在理论上是完备的;而且拓扑法通常不需要机器人的准确位置,对于位置误差也就有了更好的鲁棒性。缺点是建立拓扑网络的过程相当复杂,特别是在增加障碍物时如何有效地修正已经存在的拓扑网是有待解决的问题。 114 自由空间法 自由空间法采用预先定义的广义锥形或凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。自由空间的构
一种移动机器人的路径规划算法 作者：霍迎辉，张连明 (广东工业大学自动化研究所广州510090 文章来源：自动化技术与应用点击数：1419 更新时间：2005-1-24 摘要：本文提出一种移动机器人路径规划最短切线路径算法。依据此算法，机器人能顺利地避开障碍物到达目标位置，其原理简单，计算快捷，容易实现。仿真结果验证了它的有效性和实用性。 关键词：移动机器人；路径规划；机器人避障 1引言 移动机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定起点到终点的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物［1］。 障碍环境中机器人的无碰撞路径规划［2］是智能机器人研究的重要课题之一，由于在障碍空间中机器人运动规划的高度复杂性使得这一问题至今未能很好地解决。路径规划问题根据机器人的工作环境模型可以分为两种，一种是基于模型的路径规划，作业环境的全部信息都是预知的；另一种是基于传感器的路径规划，作业环境的信息是全部未知或部分未知的。 对机器人路径规划的研究，世界各国的专家学者们提出了许多不同的路径规划方法，主要可分为全局路径和局部路径规划方法。全局路径规划方法有位形空间法、广义锥方法、顶点图像法、栅格划归法；局部路径规划方法主要有人工势场法。这些方法都各有优缺点［3］，也没有一种方法能够适用于任何场合。 本文提出一种最短切线路径的规划方法，其涉及的理论并不高深，计算简单，容易实现，可供侧重于应用的读者参考。下面将详细介绍该算法的基本原理，最后给出仿真实现的结果。 2最短切线路径算法 2.1算法基本原理 (1)首先判断机器人和给定的目标位置之间是否存在障碍物。如图1所示，以B代表目标位置，其坐标 为(x Ｂ，y Ｂ ），以R、A分别代表机器人及障碍物，坐标为(x Ｒ ，y Ｒ )、(x Ａ ，y Ａ )。Ｒr和Ra表示机器人和障 碍物的碰撞半径，也就是说在其半径以外无碰撞的危险。这里对碰撞半径的选择作出一点说明，碰撞半径越小，发生碰撞的危险度越大，但切线路径越短；碰撞半径越大，发生碰撞的危险度越小，但同时切线路径越长。要根据实际情况和控制要求来确定碰撞半径。若机器人与目标位置之间不存在障碍物，机器人可走直线直接到达目标位置，此时的直线方程可由两点式确定：
第25卷第7期V ol.25No.7 控制与决策 Control and Decision 2010年7月 Jul.2010移动机器人路径规划技术综述 文章编号:1001-0920(2010)07-0961-07 朱大奇,颜明重 (上海海事大学水下机器人与智能系统实验室，上海201306) 摘要:智能移动机器人路径规划问题一直是机器人研究的核心内容之一.将移动机器人路径规划方法概括为:基于模版匹配路径规划技术、基于人工势场路径规划技术、基于地图构建路径规划技术和基于人工智能的路径规划技术.分别对这几种方法进行总结与评价,最后展望了移动机器人路径规划的未来研究方向. 关键词:移动机器人；路径规划；人工势场；模板匹配；地图构建；神经网络；智能计算 中图分类号:TP18；TP273文献标识码:A Survey on technology of mobile robot path planning ZHU Da-qi,YAN Ming-zhong (Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai201306, China．Correspondent：ZHU Da-qi，E-mail：zdq367@https://www.doczj.com/doc/8d13927840.html,) Abstract:The technology of intelligent mobile robot path planning is one of the most important robot research areas.In this paper the methods of path planning are classi?ed into four classes:Template based,arti?cial potential?eld based,map building based and arti?cial intelligent based approaches.First,the basic theories of the path planning methods are introduced brie?y.Then,the advantages and limitations of the methods are pointed out.Finally,the technology development trends of intelligent mobile robot path planning are given. Key words:Mobile robot；Path planning；Arti?cial potential?eld；Template approach；Map building；Neural network; Intelligent computation 1引言 所谓移动机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务.移动机器人路径规划主要解决3个问题:1)使机器人能从初始点运动到目标点;2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;3)在完成以上任务的前提下,尽量优化机器人运行轨迹.机器人路径规划技术是智能移动机器人研究的核心内容之一,它起始于20世纪70年代,迄今为止,己有大量的研究成果报道.部分学者从机器人对环境感知的角度,将移动机器人路径规划方法分为3种类型[1]:基于环境模型的规划方法、基于事例学习的规划方法和基于行为的路径规划方法;从机器人路径规划的目标范围看,又可分为全局路径规划和局部路径规划;从规划环境是否随时间变化方面看,还可分为静态路径规划和动态路径规划. 本文从移动机器人路径规划的具体算法与策略上,将移动机器人路径规划技术概括为以下4类:模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术.分别对这几种方法进行总结与评价,展望了移动机器人路径规划的未来发展方向. 2模版匹配路径规划技术 模版匹配方法是将机器人当前状态与过去经历相比较,找到最接近的状态,修改这一状态下的路径,便可得到一条新的路径[2,3].即首先利用路径规划所用到的或已产生的信息建立一个模版库,库中的任一模版包含每一次规划的环境信息和路径信息,这些模版可通过特定的索引取得;随后将当前规划任务和环境信息与模版库中的模版进行匹配,以寻找出一 收稿日期:2009-08-30；修回日期:2009-11-18. 基金项目:国家自然科学基金项目(50775136)；高校博士点基金项目(20093121110001)；上海市教委科研创新项目(10ZZ97). 作者简介:朱大奇(1964?),男,安徽安庆人,教授,博士生导师,从事水下机器人可靠性与路径规划等研究；颜明重(1977?),男,福建泉州人,博士生,从事水下机器人路径规划的研究.
研究背景 近年来,机器人技术飞速发展,机器人的应用领域也在不断扩展。机器人的工作环境存在高度的多变性和复杂性,因此自主导航是实现真正智能化和完全自主移动的关键技术。机器人的导航问题可以归结为对“我在哪”、“我要去哪”以及“我如何到达那里”三个问题的回答。第三个问题就是路径规划,要求机器人在当前位置与目标位置之间寻找一条安全、合理、高效的路径,保证机器人能够安全地到达目标地点。机器人路径规划是机器人领域的一个研究热点。 一、课题应用 机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 智能移动机器人[1]，是一个集环境感知、动态决策与规划、行为控制与执行等多功能于一体的综合系统。它集中了传感器技术、信息处理、电子工程、计算机工程、自动化控制工程以及人工智能等多学科的研究成果，代表机电一体化的最高成就，是目前科学技术发展最活跃的领域之一。随着机器人性能不断地完善，移动机器人的应用范围大为扩展，不仅在工业、农业、医疗、服务等行业中得到广泛的应用，而且在城市安全、国防和空间探测领域等有害与危险场合得到很好的应用。因此，移动机器人技术已经得到世界各国的普遍关注。 移动机器人的研究始于60 年代末期。斯坦福研究院(SRI)的Nils Nilssen 和Charles Rosen 等人，在1966年至1972 年中研发出了取名Shakey的自主移动机器人[1]。目的是研究应用人工智能技术，在复杂环境下机器人系统的自主推理、规划和控制。 根据移动方式来分，可分为：轮式移动机器人、步行移动机器人(单腿式、双腿式和多腿式)、履带式移动机器人、爬行机器人、蠕动式机器人和游动式机器人等类型；按工作环境来分，可分为：室内移动机器人和室外移动机器人；按控制体系结构来分，可分为:功能式(水平式)结构机器人、行为式(垂直式)结构机器人和混合式机器人；按功能和用途来分，可分为:医疗机器人、军用机器人、助残机器人、清洁机器人等； 一种由传感器、遥控操作器和自动控制的移动载体组成的机器人系统。移动机器人具有移动功能，在代替人从事危险、恶劣（如辐射、有毒等）环境下作业和人所不 及的（如宇宙空间、水下等）环境作业方面，比一般机器人有更大的机动性、灵活性。 移动机器人是一种在复杂环境下工作的，具有自行组织、自主运行、自主规划的智能机器人，融合了计算机技术、信息技术、通信技术、微电子技术和机器人技术等。 三、研究意义 路径规划技术是机器人研究领域中的一个重要分支,是机器人智能化的重要标志,是对
机器人路径规划 摘要：机器人路径规划是机器人技术的重要分支之一，路径规划技术的研究是研究机器人技术不可或缺的技术之一。本文首先介绍了当前研究人员热衷的ROS 系统是如何进行路径规划的，接着论述了作为群智能算法的蚁群算法应用于机器人的路径规划中。研究表明，可以将蚁群算法和ROS系统结合，进一步的进行机器人的路径规划。 关键词：路径规划，ROS系统，蚁群算法，机器人 1.引言 智能移动机器人技术是机器人技术的重要组成部分，应用前景十分广阔：工业，农业，国防，医疗，以及服务业等[1]。文献提出，未来数年内，中国服务机器人发展将超过传统的工业机器人[2]，机器人路径规划技术是服务机器人研究的核心内容之一[3]。可见，研究机器人的路径规划问题十分必要。 随着机器人领域的快速发展和复杂化，代码的复用性和模块化的需求原来越强烈，而已有的开源机器人系统又不能很好的适应需求。2010年Willow Garage 公司发布了开源机器人操作系统ROS（robot operating system），很快在机器人研究领域展开了学习和使用ROS的热潮。ROS系统是起源于2007年斯坦福大学人工智能实验室的项目与机器人技术公司Willow Garage的个人机器人项目（Personal Robots Program）之间的合作，2008年之后就由Willow Garage来进行推动。ROS的运行架构是一种使用ROS通信模块实现模块间P2P的松耦合的网络连接的处理架构，它执行若干种类型的通讯，包括基于服务的同步RPC（远程过程调用）通讯、基于Topic的异步数据流通讯，还有参数服务器上的数据存储。ROS系统以其独特优点引起了研究人员的兴趣。 近年来，各国学者致力于机器人路径规划的研究且取得了相当丰硕的研究成果。目前已有多种算法用于规划机器人的路径，文献【4】将其主要分为经典方
多机器人路径规划研究方法（一） 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 e,itexpoundedthebottleneckofthepathplanningresearchfor ， ； 近年来，分布式人工智能（DAI）成为人工智能研究的一个重要分支。DAI 研究大致可以分为DPS （distributedproblemsolving ）和MAS （）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。
机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果 1~3］，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi 图法、自由空间法、栅格法、拓扑法、链接图法、证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。 1 多机器人路径规划方法单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。 目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi 图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学 习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。 1）传统方法多机器人路径规划传统方法的特点主要体现在基于图论的基础
I SSN C N 1 0 - 0 2 - 3 4 9 / 5 6 实验技术与管理 第27卷第12期201年1 2月 1 1 2 0 4 T E x p e r i m e n t a l T e c h n o l o g ya n d Ma n a g e m e n t Vo l .27N o .12D e c .201 基于路径规划的智能机器人控制实验 张佳,陈杰,窦丽华 ( 北京理工大学自动化学院,北京1081) 摘 验教学平台。在此平台上设计并开发了分别适用于本科生及硕士研究生的系列实验 规划、全区域覆盖路径规划以及多机器人队形控制等项实验内容。该实验能够让学生接触到先进的智能机 器人增强学生对自动化专业的学习兴趣提高了学生的动手能力和创新能力。 关键词智能机器人路径规划全区域覆盖队形控制 文献标志码文章编号 要 : 针对自动化专业学生 , 以 P i o n e e r 3 A T 系列的机器人为对象 , 搭建了基于路径规划的智能机器人实 , , 包括基于模型的路径 3 , , : ; ; ; 中图分类号 : T P 2 4 2 3 3 : A : 1 0 0 2 4 9 5 6 ( 2 0 1 0 ) 1 2 0 0 4 4 0 4 I n t e l l i g e n t r o b o t c o n t r o l e x p e r i m e n t s b as e d o n p a t h p l a n n i n g Zha n g J i a , Ch e n J i e , D o uL i hua ( S c h o o l o f A u t o m r a t i za t i o n , B e i e j i n g I n s t i t u t e o f T e c h n o l o g y , B e i j i r n g 1 0 0 0 8 1 r , Ch i n a ) A b s t r a c t : A i e m t i n g a t s t r ud e n n n i T t m o t t t s o f au t o e m a t i za m t e i o n m a j o r i , t h p i s p a p e m r t ak e s r o b n o o t s o r o f P i o n e e n 3 A T S e r i n e e sas o b p j e c t t a n d m c o n s t r u c sa n i x n t e l l i m g e o b o t x p o e r o e i n n t t o e a c h n e g l a t f o r , b as e d o p a t h p l a n t n i g .Bas ud e d e o n t h i s l a f o r b , as e r n i s e o x f p e p t e i e swh i c ha p p i n t d t u n d r p g r adua t i e t s c t ud e n t sa n d g adua e s t e n t s r g s p c t i v e l l ya r o n e d e s t i g n e da d l o e i r e m d. I t t n c l ud e s m d e l b as e d r p a t h p l p a o n n i n g o m p l t e t e c n v e a g e p a t h p t l a n n i n a e d m u l t c i r e b o f t o r m a t i e o n e x n p i e n . h e e x p e r i m t o f f e sa n o r t u n y f o r s ud e t s t w o r kw i hadva n c d i n t t e l i g t r b K o o s . I t n ha c e ss t t ud e n i s i n t e r e s t s t o l e a r n au t o m a t i za t i o n m a j o r . A l s o , s t ud e n t s i n n o va t i o n a b i l i y o u l d e i m p r o v e d b y e t h e e x p e o r e n t p . e y w o r d s : i n t l l i g e n r b t ; a t h p l a n n i n g ; c o m p l e t e c o v e r a g e ; f o r m a t i o n 自动化技术是一门涉及学科较多、应用广泛的综 1 实验平台的搭（智械科技） 合性科学技术。实验教学是自动化专业教学过程中 [1] 非常重要的一环。随着目前机器人技术的不断发展, 本课程选用的机器人是美国先锋(P i o n e r 3A T ) 系列机器人[。该系列机器人是目前世界上最成熟的 4] 机器人控制实验已逐步进入各个高校。机器人教学对 于培养和提高学生的创新精神和动手能力具有极其重 轮式移动机器人研究平台之一。通常科研人员对此系 要的作用[。在自动化专业开设机器人控制实验课 2 ] 列机器人的开发与研究都在控制台程序上运行,但需 要对v M a 机器人技术应用接口a 有较 深的了解因此需要花费大量时间阅读繁多的程序代 熟悉研究环境。由于实验学时有限为了能让学生 在最短的时间内最大程度地掌握机器人的有关知识 首先搭建了一个简单实用的实验平台。该平台的建立 能使学生在最短时间内熟悉各种底层动作在实验课 程中掌握基础理论和系统深入的专门知识。 整个平台系统包括个功能模块用户操作管理 模块、通信模块、控制模块、数据分析处理模块和显示 程, 不仅可以让学生接触到国际先进的机器人们的眼界还可以让学生学习先进的控制方法 些方法运用于机器人的实际控制上 提高学生的创新能力和动手能力 域的继续发展奠定坚实的基础。为此 重点实验室项目中购买了数台机器人 , , 开阔他 并将这 A c t i e d i A r i , , ,扩展他们的思维 , 码, , [ 3 ] , 为将来在控制领 , , 本校在北京市 , 针对自动化专 , 业的教学内容及要求,开设了机器人控制实验,取得了 良好的教学效果。 5 : 收稿日期 : 2 0 0 9 1 2 2 1 修改日期 : 2 0 1 0 0 3 1 5 管理模块。各模块所组成的功能结构如图 们之间通过数据信号和控制信号联系在一起 个统一的整体。在控制模块中为学生的实验操作 1 所示,它 基金项目 : 北京市教育委员会共建重点实验室资助项目 (CSYS ,构成一 1 0 0 0 (7 0417) 作者简介 : 张佳 1 9 8 0 ) , 女 ,北京市人 , 硕士 ,实验师 , 研究方向为机器 [ 5 ] , 人控制、智能控制和图像处理.
多机器人路径规划研究方法 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝 摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multi robot.Then discussed the criterion of path planning research for multi robot based large of literature.Meanwhile,it expounded the bottleneck of the path planning research for multi robot，forecasted the future development of multi robot path planning. Key words:multi robot；path planning;reinforcement learning;evaluating criteria 近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributed problem solving）和MAS（multi agent system）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。 机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、Dempster Shafer 证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划
多机器人路径规划研究方法(一) 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝 摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 e,itexpoundedthebottleneckofthepathplanningresearchfor， ； 近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI 研究大致可以分为DPS（distributedproblemsolving）和MAS （）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术
界研究的热点,而路径规划研究又是其核心部分。 机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。 1多机器人路径规划方法 单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。 目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学
龙源期刊网 https://www.doczj.com/doc/8d13927840.html, 智能机器人避障路径规划算法研究 作者：张永妮 来源：《中小企业管理与科技·上旬刊》2016年第02期 摘要：智能机器人只有具备自主移动能力才能实现应用价值。路径规划用于决策机器人 在环境中如何行走的问题，是实现机器人智能化的关键技术。为提高机器人路径规划，对未知环境的实时性、适应性和优化性要求越来越高。自主移动机器人是集环境感知、动态策略与规划、行为控制与执行等多功能于一体的综合系统。近几年，移动机器人技术在工业、农业、医学、航天航空等许多领域发挥了重要作用。其中智能避障更是研究领域的难点和热点，智能避障是能够根据采集障碍物的状体信息，按照一定的方法进行有效的避障，最后到达终点。本文主要介绍了动态窗口和Bug2的避障算法和研究与仿真。实现这两种避障算法主要基于Matlab 等语言编程开发，实现对移动机器人避障算法的仿真。Matlab功能强大、编程简单、适用广。 最后，验证基于Bug算法的几种路径规划方法，将避障实时性，环境的适应性、规划路径的优化性作为算法性能指标，进行仿真实验与对比实验分析。结果验证了算法的有效性。 关键词：智能机器人；避障；MATLAB仿真；路径规划 1 绪论 智能机器人避障算法的研究对于推进机器人领域的应用和发展具有重要的意义。随着计算机技术、传感器技术、控制技术的发展，智能机器人的避障技术已经取得了丰硕的研究成果，其应用领域不断的扩大，应用复杂程度也越来越高，因此对其关键技术提出了更高要求，相应的方法也更加成熟。 本文通过查阅文献资料，对目前智能机器人的发展动态有了一定了解。对现阶段机器人避障的一些常用方法做了研究，然后设计了不同算法在未知环境下的避障仿真实验来验证本文所设计的算法的可行性。路径规划要求机器人能够在较短的时间内，感知到范围尽可能大的区域，从而找到最近的路径使机器人能够沿着最优路径运动到终点，并避开障碍物。 2 基于动态窗口的避障算法及仿真 2.1 概述 机器人局部路径规划的方法很多，动态窗口法就是其中的一种，其主要是在速度（v，w）空间中采样多组速度，并模拟机器人在这些速度下一定时间内的轨迹。在得到多组轨迹以后，对这些轨迹进行评价，选取最优轨迹所对应的速度来驱动机器人运动。该算法突出点在于动态窗口这个名词，它的含义是依据移动机器人的及速度性能限定速度采样空间在一个可行的动态图范围内。