张波涛, 等 : 基于栅格 - 几何混合地图的分层路径规划 61 移动机器人的全局路径规划是指在环境模型中寻找一条从起始位姿到目标位姿的符合评价准则的无碰运动轨迹, 其研

Size: px

Start display at page:

Download "张波涛, 等 : 基于栅格 - 几何混合地图的分层路径规划 61 移动机器人的全局路径规划是指在环境模型中寻找一条从起始位姿到目标位姿的符合评价准则的无碰运动轨迹, 其研"

耗洲牧
7 years ago
Views:

1 第 3 卷第 1 期智能技术学报 2011 年 3 月 Vol.3 No.1 CAAITransactionsonInteligenceTechnology Mar.2011 基于栅格 - 几何混合地图的分层路径规划张波涛 1,2 1,2, 刘士荣 (1. 华东理工大学自动化研究所, 上海 ;2. 杭州电子科技大学自动化学院, 杭州 ) 摘要 : 根据人工势场法与栅格法的特点, 提出了一种基于特征与栅格混合地图的分层路径规划方法上层使用 A 算法在低粒度的栅格地图中找到基本路径, 以此克服人工势场中的局部最小问题底层使用人工势场法对基本路径进行解模糊和平滑处理仿真实验表明该路径规划方案可以降低计算消耗, 所规划的路径优于传统的栅格法关键词 : 移动机器人 ; 栅格 - 几何地图 ; 人工势场 ;A 算法中图分类号 :TP24 文献标识码 :A AHierarchicalPlanningStrategyBasedonGrid geometricmap ZHANGBo tao 1,2,LIUShi rong 1,2 (1.InstituteofAutomation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China; 2.InstituteofAutomation,HangzhouDianziUniversity,Hangzhou310018,China) Abstract:Accordingtothecharacteristicofgridmethodandartificialpotentialfield(APF),ahier archicalplanningstrategyingrid geometricmapisproposed.upperlayeradoptsa algorithm to searchforabasicrouteinlowclasgranularitygridmap,bywhichthelocalminimumproblemofapf issolved.inbotomlayer,apfisemployedtodefuzificationandsmoothingthebasicroute.simula tionresultsshowthattheproposedstrategycanefectivelydecreasecomputationalconsumption,whose routeisobviouslybeterthantheoneplannedbytraditionalgridmethod. Keywords:mobilerobot;grid geometricmap;artificialpotentialfield(apf);a algorithm 收稿日期 : 基金项目 : 国家自然科学基金资助项目 ( ); 浙江省科技计划基金资助项目 (2007C21051); 杭州电子科技大学科研启动基金资助项目 (KYS ) 作者简介 : 张波涛 (1982 ), 男, 博士研究生, 主要从事基于视觉的移动机械臂的规划与控制研究 ; 通信作者刘士荣 (1952 ), 男, 教授, 博士生导师, 主要从事复杂系统建模优化与控制智能系统与智能机器人等方面研究

问题底层使用人工势场法对基本路径进行解模糊和平滑处理仿真实验表明该路径规划方案可以降低计算消耗, 所规划的路径优于传统的栅格法关键词 : 移动机器人 ; 栅格 - 几何地图 ; 人工势场 ;A 算法中图分类号 :TP24 文献标识码

2 张波涛, 等 : 基于栅格 - 几何混合地图的分层路径规划 61 移动机器人的全局路径规划是指在环境模型中寻找一条从起始位姿到目标位姿的符合评价准则的无碰运动轨迹, 其研究方法有人工势场法可视图法自由空间法 A D 算法栅格法等移动机器人路径规划所使用的地图主要有几何地图拓扑地图栅格地图和混合地图 [1-5] 其中, 拓扑地图按照环境的结构创建, 忽略了具体的度量信息, 图形抽象, 易于表示, 适合路径规划, 但很难精确地识别位置 [6] 几何地图侧重于用绝对坐标系统来表示移动机器人的空间环境特征, 对环境的描述最精确, 但是不利于计算机处理 [7-8] 栅格地图易于表述环境的空间信息及不确定性, 但它受限于环境的规模混合地图综合了 2 种或者多种地图的优点, 因此, 基于混合地图的机器人导航和地图建模研究正逐渐得到国内外研究 [9] 者的重视例如 : 庄严采用拓扑地图描述全局环境, 采用几何地图描述局部工作空间, 并以此为基础进 [10] 行了地图建模和自定位技术的研究文献王醒策根据几何环境模型确定栅格粒度, 使用栅格势能构造启发式搜索函数, 以此降低路径规划复杂度由于栅格粒度恒定, 因此工作空间必然存在浪费李劲 [11] 松采用分层栅格进行路径规划, 以粗粒度栅格覆盖地图规划运动序列, 然后以低粒度势场栅格逼近粗粒度栅格内部的几何地图, 以地图模糊化和解模糊化来降低规划复杂度因初始粒度较低, 故仍可能存在可行空间浪费, 且路径不平滑人工势场法 (APF) 由 Khatib [12] 根据物理学中场的概念提出的一种导航方法其原理是使用斥力势场函数描述环境模型中的障碍物, 引导移动机器人避开障碍物, 并以引力势场产生的虚拟力牵引移动机器人的走向目标该方法因其实用性得到了广泛应用, 并被研究至今, 但它最大问题是容易陷入局部极小近年来国外研究者提出了很多方案来解决此问题 [13-14] 其中, 一部分采用修改势场函数或者变参数法来降低陷入局部极小的 ; 另一部分用其他方法来弥补 APF 的缺陷本文采用混合地图进行导航, 以粗粒度的栅格覆盖全局地图, 使用栅格法导航, 使用 APF 进行轨迹修正, 实现在几何 - 栅格混合地图下的导航任务该方法以粗粒度栅格大幅度的降低了传统基于栅格地图的规划方法计算消耗, 克服了 APF 的局部极小值和震荡问题同时在局部工作空间使用 APF, 修正了基于栅格地图的规划方法所规划出的路径平滑度差的问题仿真实验证明了该方法的有效性 1 基于栅格地图的 A 导航法因为环境模型的不规则性, 栅格环境描述会导致可行空间的浪费, 例如不规则的小的障碍物会占用较大的空间, 进而使得所产生的路径不平滑, 并且路径较长, 甚至无法发现路径为逼近不规则障碍物, 必须对栅格细化, 这会导致计算量迅速上升 [11], 因此栅格法难以处理大型地图 1.1 基于栅格地图的 A 导航法有很多算法可用于栅格地图下的路径搜索, 如贪心算法 Dijkstra 算法 A 算法以及其他多种智能算法本文使用 A 搜索法来进行分层栅格序列搜索栅格编号规则如下 : 按照从上到下, 从左到右的顺序第 i 行, 第 j 列的栅格编号为 S=(i,j), 当前栅格的可能搜索方向有 S k+1 =[(i+1,j),(i-1,j), (i,j+1),(i,j-1),(i+1,j+1),(i-1,j-1),(i-1,j+1),(i+1,j-1)] 方法不分边界栅格与中间栅格, 边界被作为障碍物处理 A 搜索通过 2 个栅格队列实现, 其中 OpenList 存放已经生成, 但尚未访问的节点,ClosedList 存放已经访问过的节点 A 搜索算法的评价函数如下 :

于用绝对坐标系统来表示移动机器人的空间环境特征, 对环境的描述最精确, 但是不利于计算机处理 [7-8] 栅格地图易于表述环境的空间信息及不确定性, 但它受限于环境的规模混合地图综合了 2 种或者多种地图的优点, 因此, 基于

3 2 6 智能技术学报 f(n) =x(n)+y(n) (1) 其中 :x(n) 为从起始点到目前点的代价 ;y(n) 为从目前点到终点的代价为了节省计算消耗并使路径不断趋向目标栅格, 本文为代价相同的栅格提供目标趋向度来进行选择如图 1 所示,R 为机器人所处栅格, 则以 (5,5) 栅格为中心顺时针旋转, 四周 8 个栅格的目标趋向度矩阵定义为 D=[60,100,60,40,20, 5,20,40] 图 1 各栅格的目标趋向度同代价栅格的选择概率计算公式为 P i = d(s 0,S i ) 2 n 0 i=1 d(s 0,S i ) 2 (2) 其中 :n 0 为具有相同代价的下一级节点 d(s 0,S k ) 是机器人在 S 0 时, 前往 S k 的目标趋向度 :A 搜索伪代码描述如下 A pseudocode 把起始节点加进 OpenList 若 OpenList 不为空 { 当前节点 =OpenList 中成本最低的节点 If 当前节点 = 目标节点 Then 路径完成 Else 把当前节点移入 ClosedList 检查当前节点的每个相邻节点 For 每个相邻节点 If 该节点不在 OpenList 中 and 该节点不在 ClosedList 中 and 该节点不是障碍物 Then 将该节点移入 OpenList 计算其成本 }

2 (2) 其中 :n 0 为具有相同代价的下一级节点 d(s 0,S k ) 是机器人在 S 0 时, 前往 S k 的目标趋向度 :A 搜索伪代码描述如下 A pseudocode 把起始节点加进 OpenList 若 OpenList 不为空 { 当前节点 =OpenList 中成本最低的节点

4 张波涛, 等 : 基于栅格 - 几何混合地图的分层路径规划 63 A 搜索算法可能发生回溯问题本文将对最终栅格序列进行处理, 删除重复栅格之间的运动序列对经 n 步搜索之后仍返回 1~2 栅格距离区域之内的路径, 取路径两端作为起始点和目标节点进行重新规划如图 2 所示, 栅格序列可重新规划为如下序列 :(5,6) (6,5) (5,5) (4,5), 并进一步被缩短为 (5,6) (4,5) 图 2 A 算法中的回溯问题处理 1.2 高层规划中栅格粒度的变化规则在变栅格导航模式中往往根据环境模型中的障碍物稀疏程度来确定栅格粒度 [10] 由于采用多边形覆盖法计算障碍物面积的复杂度较高, 本文首先以超低粒度栅格覆盖地图, 计算含障碍物超低粒度栅格数占总栅格数的比例来确定初始栅格的大小, 若障碍物密度大, 则初始栅格粒度较小, 反之初始栅格粒度较大根据文献 [10] 的栅格粒度估计方法, 计算公式为 l in = { S total S l,l l max min obstacle l min,l lmin (3) 其中 l = S total l S max 若可以产生可行路径, 则记录栅格序列若不能产生则降低栅格粒度, 粒度降阶 obstacle 公式为 l new =l in /2,l in >2r (4) 其中 r 为机器人半径, 即栅格粒度不能低于机器人直径, 否则机器人可能不能通过相应的栅格路径 2 基于 APF 的底层路径规划以往研究多以势场函数来描述障碍物的形状, 该方法将凸多边形或者其他规则几何形状的函数与实际障碍进行匹配映射, 该方法可以节省计算资源, 但牺牲了移动机器人的工作空间为了准确地描述不规则形状的障碍物产生的势场, 本文使单位点电荷沿障碍物边缘均匀分布, 设移动机器人为点状正电荷, 则其所处的势场 E 为 E(e g,e i,q)=e at (e g,q)+ k E rep (e i,q) (5) i=1

2 高层规划中栅格粒度的变化规则在变栅格导航模式中往往根据环境模型中的障碍物稀疏程度来确定栅格粒度 [10] 由于采用多边形覆盖法计算障碍物面积的复杂度较高, 本文首先以超低粒度栅格覆盖地图, 计算含障碍物超低粒度

5 4 6 智能技术学报其中引力场采用文献 [13] 中的引力场模型 : E at (e g,q) = 1 2 αρ2 g(q) q=(x,y,θ) 为移动机器人的位姿,e g 为目标点的位置,e i,i=1,,k 为均匀分布在障碍物表面的负电荷的位置,E at (e g,q) 为引力场 ;E rep (e i,q) 为 e i 的斥力场,α 为引力增益系数 ;ρ g (q) 为机器人与目标位置之间的距离,ρ g (q)= q-e g,e g 为目标位置在势场为 E(e g,e i,q) 的条件下, 移动机械臂所受到的力为 F =- E =- E at (e g,q)- k E rep (e i,q) (6) 图 3 是对移动机器人在混合地图下的受力描述, 其中 O 1 O 2 为障碍物, 节点为阶段性目标点,F 1 F 2 为障碍物对机器人的斥力,F at 为节点产生的引力由于环境模型中存在栅格法规划出的基本路径作为引导, 因此不需要构造复杂的势场函数来避免局部极小值问题本文在栅格路径序列中选取连续趋向性较好的点作为节点, 若发生死锁问题, 则就近选取栅格作为节点, 以此引导机器人向目标点运动 i=1 图 3 混合地图下的移动机器人受力分析 3 混合地图下的分层路径规划与文献 [11] 类似, 此方法的实质也是将复杂地图模型模糊化来降低计算消耗, 然后再以势场法实现解模糊但与文献 [11] 只对粗粒度栅格内部进行栅格细化处理不同, 本文的解模糊化方法跨栅格, 并严格按照几何地图进行, 以此解决粗粒度栅格对工作空间的浪费问题具体方法为 : 以粗粒度栅格规划出一组模糊地栅格序列, 从栅格序列中选取趋向性较好的栅格中心点或者两栅格连线上的点作为过渡节点, 在节点之间使用 APF 按照几何地图搜索可行路径分层路径规划算法流程如图 4 所示

(6) 图 3 是对移动机器人在混合地图下的受力描述, 其中 O 1 O 2 为障碍物, 节点为阶段性目标点,F 1 F 2 为障碍物对机器人的斥力,F at 为节点产生的引力由于环境模型中存在栅格法规划出的基本路径作为引导, 因此不需要构造复

6 张波涛, 等 : 基于栅格 - 几何混合地图的分层路径规划 65 图 4 基于栅格 - 几何地图的分层规划流程分层路径规划策略的具体步骤如下 Input:Grid geometricmap,startlocationandgoal Output:Optimalroute Start: step1 读取几何地图, 并根据障碍物面积, 按照式 (4) 计算初始栅格粒度 step2 初始化 A 算法, 建立 OPENLIST 与 CLOSEDLIST step3 使用 A 算法搜索路径, 若无法获得可行路径, 则按照公式 (5) 更新栅格粒度, 并跳转至 step2 step4 根据所得栅格序列的连续趋向性, 选取中间节点作为 APF 的阶段性目标点 step5 读取几何地图, 并使用 APF 进行两点间的路径规划 step6 若发生局部极小等原因引起的不可达问题, 则更新阶段性目标点, 并跳转至 step5 step7 输出连续路 4 仿真实验为评价本文提出的分层规划策略的性能, 将此方法与单独的粗细粒度栅格法单纯的 APF 法进行比较, 共设计了 2 组仿真实验第 1 组用来说明粗粒度栅格法的可行空间损失问题, 以及细粒度栅格计算消耗的增加程度第 2 组实验在同一环境下分别使用 A 算法,APF 以及本文提出的基于混合地图的分层规划策略来规划路径, 以此验证本文所提出的方法的有效性 4.1 栅格粒度取值分析栅格的粒度越粗, 那么路径规划时的计算消耗就越小, 但是如果采用的粗粒度过粗, 会导致环境模型的可行空间萎缩, 并且用各种搜索方法获得的路径平滑性很差最严重的是工作空间萎缩会导致无法发

列的连续趋向性, 选取中间节点作为 APF 的阶段性目标点 step5 读取几何地图, 并使用 APF 进行两点间的路径规划 step6 若发生局部极小等原因引起的不可达问题, 则更新阶段性目标点, 并跳转至 step5 step7 输出连续路 4 仿真实验

7 6 智能技术学报现路径如图 5 所示, 粒度较粗引起环境模型的可行空间损失, 进而使机器人无法发现较优的路径, 绕道较远的路径图 5 粗粒度栅格地图下的工作空间损失在栅格规模为 n n 时, 最坏的状况下 A 算法的复杂度可达 O(n 2 ), 平均复杂度为 Θ(n) 若粒度降低为原来的一半, 则最坏的情况下计算量会增加至 Θ(4n 2 ), 平均复杂度增加至 Θ(2n) 由图 6 可见, 采用细粒度栅格表示环境模型, 固然可以使得路径变得相对平滑, 但计算复杂度很高, 不适合大规模地图下的路径规划问题, 而且在最终轨迹规划基于栅格地图的前提下, 很难保证轨迹平滑图 6 细粒度栅格地图下的计算消耗上升 4.2 基于混合地图的分层路径规划为了说明本文所提出算法的优越性, 本节将在图 7(a) 所示的栅格 - 几何混合地图中, 分别使用基于栅格地图的 A 法人工势场法以及本文提出的分层规划法进行路径规划仿真实验仿真实验如图 7 所示, 所获得路径长度如表 1 所示

滑, 但计算复杂度很高, 不适合大规模地图下的路径规划问题, 而且在最终轨迹规划基于栅格地图的前提下, 很难保证轨迹平滑图 6 细粒度栅格地图下的计算消耗上升 4.

8 张波涛等基于栅格几何混合地图的分层路径规划６７图７ＡＡＰＦ以及分层规划的效果对比表１ＡＡＰＦ以及分层规划所获得路径长度规划方法分层规划法栅格法ＡＰＦ路径长度１３８５４８１５６５６９不可达由图７可以看出基于栅格地图的Ａ算法规划出的路径不平滑且存在工作空间损失人工势场在前期获得了较好的效果但是在中后期陷入了局部极小一直处于死锁状态没有能够完成规划任务本文所提出的分层规划方法获得了非常平滑的路径从表１中可以看出就路径长度而言分层规划法所获得的路径要优于基于栅格地图的Ａ法所获得的路径５结束语为解决单独采用栅格地图或几何地图进行路径规划的所存在的问题提出了一种基于栅格几何混合地图的分层导航模式并构建了一种基于该模式的路径规划方案该方案采用Ａ搜索法完成上层规划底层则采用ＡＰＦ完成轨迹规划与单纯的栅格法相比该方法通过图元模糊化与解模糊有效的减少了计算消耗并可获得较短且平滑度高的路径同时该方法可以完全克服ＡＰＦ的局部极小问题

从表１中可以看出就路径长度而言分层规划法所获得的路径要优于基于栅格地图的Ａ法所获得的路径５结束语为解决单独采用栅格地图或几何地图进行路径规划的所存在的问题提出了一种基于栅格几何混合地图的分层导航模式

9 8 6 智能技术学报参考文献 : [1] DedeogluG,SukhatmeGS.Landmarkbasedmatchingalgorithmforcooperativemappingbyautonomousrobots[C]//Proceed ingsofthe5thinternationalsymposiumondistributedautonomousroboticsystems.[s.l.]:[s.n.],2000: [2] StachnisC,BurgardW.Mobilerobotmappingandlocalizationinnon staticenvironments[c]//proceedingsoftheinterna tionalconferenceonartificialinteligence.pennsylvania:[s.n.],2005: [3] 石朝侠, 洪炳, 周彤, 等. 大规模环境下的拓扑地图创建与导航 [J]. 机器人,2007,29(5): [4] ThrunS.LearningMetric topologicalmapsforindoormobilerobotnavigation[j].artificialinteligence,1998,99(1): [5] BlancoJL.TowardaunifiedBayesianapproachtohybridmetric topologicalslam[j].ieeetransactionsonrobotics,2008, 24(2): [6] GoedemeT,NutinM,TuytelaarsP.Omnidirectionalvisionbasedtopologicalnavigation[J].InternationalJournalofComputer Vision,2007,74(3): [7] IlaV,PortaJosepM,Andrade CetoJ.Information-basedcompactposeSLAM[J].IEEETRANSACTIONSONROBOTICS, 2010,26(1): [8] ColeDM,NewmanPM.Usinglaserrangedatafor3DSLAMinoutdoorenvironments[C]//ProceedingsoftheIEEEinterna tionalconferenceonroboticsandautomation.orlando:[s.n.],2006: [9] 庄严, 徐晓东, 王伟. 移动机器人几何 - 拓扑混合地图的构建及自定位研究 [J]. 控制与决策,2005,20(7): [10] 王醒策, 张汝波, 顾国昌. 基于势场栅格法的机器人全局路径规划 [J]. 哈尔滨工程大学学报,2003,24(2): [11] 李劲松, 颜国正, 吕恬生, 等. 一种移动机器人全局路径规划新方法 [J]. 机械设计与研究,2009,25(3): [12]KathibO.Real timeobstacleavoidanceformanipulatorsandmobilerobots[j].internationaljournalofroboticsresearch, 1986,5(1): [13]GeSS,CuiYJ.NewPotentialFunctionsforMobileRobotPathPlanning[J].IEEETransactionsonroboticsandautomation, 2000,16(5): [14]AgirebeitiaJ,AvilesR.AnewAPFstrategyforpathplanninginenvironmentswithobstacles[J].Mechanismandmachinethe ory,2005,40(6): ( 责任编辑刘舸 )

[2] StachnisC,BurgardW.Mobilerobotmappingandlocalizationinnon staticenvironments[c]//proceedingsoftheinterna tionalconferenceonartificialinteligence.pennsylvania:[s.n.],2005:1324-1329.

十二月佳作第一次當哥哥 3A 麥展衡媽媽懷孕了, 我很興奮不過, 自從媽媽生下妹妹後, 我漸漸難過, 因為以前爸媽總是以我為先, 但現在卻以妹妹為中心為什麼大家都喜歡妹妹?

十二月佳作第一次當哥哥 3A 麥展衡媽媽懷孕了, 我很興奮不過, 自從媽媽生下妹妹後, 我漸漸難過, 因為以前爸媽總是以我為先, 但現在卻以妹妹為中心為什麼大家都喜歡妹妹? 十二月佳作第一次上學 3A 林梓軒期盼已久的九月一日終於來了, 這一天就是我踏上小學生活的第一天我既緊張又興奮, 即將開始人生的第一頁那天早上, 我準時來到學校, 看著很多陌生的面孔, 我不禁有點緊張, 這時候有一位同學走過

张 波 涛, 等 : 基 于 栅 格 - 几 何 混 合 地 图 的 分 层 路 径 规 划 61 移 动 机 器 人 的 全 局 路 径 规 划 是 指 在 环 境 模 型 中 寻 找 一 条 从 起 始 位 姿 到 目 标 位 姿 的 符 合 评 价 准 则 的 无 碰 运 动 轨 迹, 其 研

张波涛, 等 : 基于栅格 - 几何混合地图的分层路径规划 61 移动机器人的全局路径规划是指在环境模型中寻找一条从起始位姿到目标位姿的符合评价准则的无碰运动轨迹, 其研