1、 电 子 测 量 技 术E L E C T RON I CME A S U R EME N TT E CHNO L O G Y第4 5卷 第2 3期2 0 2 2年1 2月 D O I:1 0.1 9 6 5 1/j.c n k i.e m t.2 2 0 9 9 0 9改进R R T结合B样条的移动机器人路径规划研究*陈 都 侯 明 张学东(北京信息科技大学自动化学院 北京 1 0 0 1 9 2)摘 要:针对快速扩展随机树(R R T)算法在移动机器人路径规划中的时间过长、路径冗长曲折且平滑度较差等问题,提出一种新的采样节点生成和路径节点选取的改进型R R T算法。该算法以融合采样点概率和
2、目标点引力的方式,再结合动态变随机步长的策略,加快了向目标点的扩展,降低了规划时间;最后为完成路径优化,对利用正向寻优和二次选取过后的路径节点,采用B样条函数进行处理,综合改善了路径的长度及其平滑性。在仿真实验中分别与传统R R T算法,P-R R T算法进行比较,实验结果表明:所提算法在路径长度,规划时间以及路径节点个数均有一定优化,且路径平滑性得到了有效提升。关键词:R R T算法;移动机器人;路径优化;二次选取;B样条中图分类号:T P 2 4 文献标识码:A 国家标准学科分类代码:5 1 0.8 0R e s e a r c h o n p a t h p l a n n i n g
3、o f m o b i l e r o b o t b a s e d o n i m p r o v e d R R T a n d B-s p l i n eC h e n D u H o u M i n g Z h a n g X u e d o n g(S c h o o l o f A u t o m a t i o n,B e i j i n g I n f o r m a t i o n S c i e n c e a n d T e c h n o l o g y U n i v e r s i t y,B e i j i n g 1 0 0 1 9 2,C h i n a)A
4、 b s t r a c t:T o a d d r e s s t h e p r o b l e m s o f t h e r a p i d l y-e x p l o r i n g r a n d o m t r e e s(R R T)a l g o r i t h m i n m o b i l e r o b o t p a t h p l a n n i n g i n c l u d i n g t i m e c o s t,l o n g a n d t o r t u o u s p a t h,a n d p o o r s m o o t h n e s s,a
5、 n i m p r o v e d R R T a l g o r i t h m o f n e w s a m p l i n g n o d e g e n e r a t i o n a n d p a t h n o d e s e l e c t i o n i s p r o p o s e d.T h e a l g o r i t h m c o m b i n e s t h e p r o b a b i l i t y o f s a m p l i n g p o i n t s a n d t h e g r a v i t a t i o n o f t h e
6、 t a r g e t p o i n t,a n d d y n a m i c a l l y c h a n g e s t h e r a n d o m s t e p s i z e,t h u s a c c e l e r a t i n g t h e e x p a n s i o n t o t h e t a r g e t p o i n t a n d r e d u c i n g t h e p l a n n i n g t i m e.F i n a l l y,t o c o m p l e t e t h e p a t h o p t i m i z
7、 a t i o n,t h e p a t h n o d e s o b t a i n e d a f t e r t h e f o r w a r d o p t i m i z a t i o n a n d t h e s e c o n d a r y s e l e c t i o n a r e p r o c e s s e d u s i n g t h e B-s p l i n e f u n c t i o n,w h i c h c o m p r e h e n s i v e l y i m p r o v e s t h e p a t h i n t e
8、 r m s o f l e n g t h a n d s m o o t h n e s s.T h e p r o p o s e d a l g o r i t h m h a s b e e n c o m p a r e d w i t h t r a d i t i o n a l R R T a l g o r i t h m a n d P-R R T a l g o r i t h m i n t h e s i m u l a t i o n e x p e r i m e n t s,w h o s e r e s u l t s s h o w t h a t t h
9、 e p r o p o s e d a l g o r i t h m h a s i m p r o v e d t h e p a t h l e n g t h,p l a n n i n g t i m e a n d t h e n u m b e r o f p a t h n o d e s t o a c e r t a i n a m o u n t,a n d e f f e c t i v e l y t h e p a t h s m o o t h n e s s.K e y w o r d s:R R T a l g o r i t h m;m o b i l e
10、 r o b o t;p a t h o p t i m i z a t i o n;q u a d r a t i c s e l e c t i o n;B-s p l i n e 收稿日期:2 0 2 2-0 5-1 1*基金项目:国家自然科学基金(6 1 9 7 1 0 4 8)、北京信息科技大学重点培育项目(5 2 1 2 1 1 0 9 2 7)资助0 引 言 近年来随着工业生产的不断发展,自动化升级改造需求不断增加1,移动机器人也随之变得更加自动化和智能化。移动机器人的路径规划技术是机器人完成自主导航的核心2,它需要在工作场景中规划出一条从初始位置到目标位置的路径3,该路径应满足
11、路径短、高效能、安全性高等一系列要求,并且能够避开沿途的静态和动态障碍物4。路径规划算法主要包括生物智能搜索算法,基于采样的算法,基于几何模型法和基于局部避障算法5。基于采样的路径规划算法中最常用的是R R T算法6,其无需对工作环境进行建模,通过随机采样点模拟出完整的工作环境,不仅具有强大的搜索能力,且具有概率完整性7,并且在高维空间同样适用。但是R R T算法存在随机性强,导向性差8,规划路径长,时间长以及路径平滑性差等问题。因此,许多研究学者针对这些问题提出了不同的方法来解决和改进。张建冬等9利用角度偏移约束策略,加快了搜索速度,并结合路径局部平滑处理,改善了路径平滑度;孙钦鹏等1 0提
12、出变步长自适应的调整方法,对于临时目标点设计了新的选取规则,缩短了规划的平均路径长83 陈 都 等:改进R R T结合B样条的移动机器人路径规划研究第2 3期度;江洪等1 1将目标点引力、障碍物斥力和随机点引力三力合一,使随机树在避开障碍物的同时加快向目标点搜索,并提出剪枝优化方法,优化了路径长度。以上等人对传统R R T算法的改进,提高了随机树拓展的导向性,进一步增强了搜索的能力和效率,降低了搜索时间和路径规划长度;但是路径平滑度相对较差,路径规划长度依旧相对冗长,并且通常只能进行单方面的优化,无法综合考虑改善路径长度和平滑度。因此,本文为提高搜索的能力和效率,提出了融合采样点概率和目标点引
13、力,再结合动态变随机步长的采样节点生成策略;最后采取正向寻优和二次选取路径节点的策略来缩短路径长度的同时完成B样条函数对路径的平滑处理。通过仿真实验分析,验证了所提算法的有效性和快速性。1 R R T算法1.1 传统R R T算法 快速扩展随机树(R R T)算法是S t e v e n和J a m e s提出的一种通过随机构建S p a c e F i l l i n g T r e e实现对非凸高维空间快速搜索的算法。该算法可以很容易的处理包含障碍物和差分运动约束的场景,因而广泛被应用在各种机器人的运动规划场景中1 2-1 3,算法示意图如图1所示。图1 R R T算法示意图传统R R T
14、算法虽然概率完备性较高,并且适用于高维空间,但是其是一种纯粹的随机搜索概率,导向性较差,对工作空间不敏感,往往需要耗费大量的时间才能搜索到一条完整的路径。并且当工作空间存在大量障碍物时,算法效率还会大幅度降低。1.2 R R T算法的优化 1)融合采样点概率和目标点引力的寻优考虑传统R R T算法在复杂工作环境中采样随机性强、导向性差,搜索时间较长等问题,在基于概率的目标偏向寻优的 R R T 算法(P-R R T)1 4-1 5的基础上,融合采样点概率和目标点引力分量,能够进一步优化随机树向目标点拓展,提高了算法收敛速率,降低了搜索时间。P-R R T的核心思想在采样过程中对扩展函数引入偏置
15、阈值来优化采样节点:qr a n d=s a mp l e(),其他qg o a l,ppt a r g e t(1)P-R R T算法在采样策略上仍具有较强的随机性,因此,结合引力势场中的引力思想,改进的算法在式(1)中当随机概率值p大于阈值pt a r g e t时,此时将p作为采样点生成的概率,再融合目标点的引力分量,因此新节点的位置将由采样点概率值p,采样点qr a n d,目标点引力系数k g和目标点qg o a l共同决定,新节点的扩展如图2所示。图2 结合采样点概率和目标点引力的节点扩展融合目标点引力分量后,在随机采样点方向上,新节点的扩展分量pr为:pr=pqr a n d-q
16、n e a rqr a n d-qn e a r(2)在目标点方向上,新节点的扩展分量pg为:pg=k gqg o a l-qn e a rqg o a l-qn e a r(3)式(2)和(3)中,qr a n d-qn e a r和qg o a l-qn e a r分别表示qr a n d、qg o a l到qn e a r的直线距离,由式(2)和(3)得到的新节点qn e w为:qn e w=qn e a r+pr+pg(4)因此,得到改进的算法生成的采样节点如下:qr a n d=qn e w,其他qg o a l,ppt a r g e t(5)如式(5),改进的算法进一步降低了采样节点的随机性,使得向目标点扩展的导向性得到优化。2)动态变随机步长策略为了解决陷入局部极小的问题,在舍弃了小于固定步长的采样点的基础上,传统R R T算法采用固定步长策略使得新节点在扩展过程中,在障碍物较少的区域,不能进行较快的遍历此区域。自适应步长策略利用扩展过程中所收集到的信息来适应树中节点的扩展,使得随机树可以更快地遍历障碍物较少的区域1 6。因此受自适应步长启发,并引入了随机概率,提出了一
