第２７卷第４期　２００５年７月　机器人　ＲＯＢＯＴ　Ｖｏ１．２７，Ｎｏ．４　Ｊ

ｕｌｙ，２００５　

文章编号：１００２－０４４６（２００５）０４－０３２５－０５　

车型移动机器人的ＳＰＲＭ路径规划方法　孙凤池　，黄亚楼　，康叶伟　，王晓明２，宗贵聪２　（１．南开大学软件学院，天津３０００７１；２．山东科技大学，山东青岛２６６５ｏ０）　

摘要：研究车型移动机器人的路径规划问题，提出一种用局部规则路图结合随机路图，辅助建立全局复合　路图的环境建模方法．在此基础上进行路径规划，提高了在障碍物附近产生的局部路径的质量，减少了由于频繁　地执行避碰校验所造成的时间消耗，并解决了可行空问丢失的问题．仿真实验验证了这种方法在车形移动机器人　路径规划应用中的有效性．　关键词：移动机器人；路径规划；路图；环境建模　中图分类号：ＴＰ２４　文献标识码：Ｂ　

ＳＰＲＭ　Ｂａｓｅｄ　Ｐａｔｈ　Ｐｌａｎｎｉｎｇ　ｆｏｒ　Ｃａｒ－ｌｉｋｅ　Ｍｏｂｉｌｅ　Ｒｏｂｏｔｓ　ＳＵＮ　Ｆｅｎｇ—ｃｈｉ　，ＨＵＡＮＧ　Ｙａ—ｌｏｕ　，ＫＡＮＧ　Ｙｅ—ｗｅｉ　，ＷＡＮＧ　Ｘｉａｏ—ｍｉｎｇ　，ＺＯＮＧ　Ｇｕｉ—ｃｏｎｇ　（１．Ｃｏｌｌｅｇｅ　ｏｆＳｏｆｔｗａｒｅ，Ｎａｎｋａｉ矾ｔ　Ｂｉｔｙ，Ｔｉａｎｊｉｎ　３０００７ｌ，Ｃｈｉｎａ；　２．Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｑｉｎｇｄａｏ　２６６５ｏｏ，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｐｒｏｂｌｅｍ　ｆｏｒ　ｃａｒ—ｈｋｅ　ｍｏｂｉｌｅ　ｒｏｂｏｔｓ　ｉｓ　ｓｔｕｄｉｅｄ，ａｎｄ　ａｎ　ｅｎｖｉｒｏｎｍｅｎｔ　ｍｏｄｅｌｉｎｇ　ｍｅｔｈｏｄ　ｉｓ　ｐｒｅｓ·　ｅｎｔｅｄ　ｗｈｉｃｈ　ｂｕｉｌｄｓ　ｔｈｅ　ｇｌｏｂａｌ　ｃｏｍｐｏｕｎｄ　ｒｏａｄｍａｐ　ｂｙ　ｃｏｍｂｉｎｉｎｇ　ｔｈｅ　ｌｏｃａｌ￣ｓｕｌａｒ　ｒｏａｄｍａｐ　ｗｉｔｈ　ｔｈｅ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｒｏａｄｍａｐ．　Ｗｉｔｈ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｂａｓｅｄ　ｏｎ　ｔｈｉｓ　ｍｏｄｅｌ，ｔｈｅ　ｑｕａｌｉｔｙ　ｏｆ　ｌｏｃａｌ　ｒｏａｄｓ　ｎｅａｒ　ｔｈｅ　ｏｂｓｔａｃｌｅｓ　ｉｓ　ｉｍｐｒｏｖｅｄ，ｔｉｍｅ　ｃｏｎｓｕｍｐｔｉｏｎ　ｃａｕｓｅｄ　ｂｙ　ｔｉｌｅ　ｆｒｅｑｕｅｎｔ　ｃｏｌｌｉｓｉｏｎ·ａｖｏｉｄｉｎｇ　ｃｈｅｃｋ　ｉｓ　ｌｏｗｅｒｅｄ，ａｎｄ　ｔｈｅ　ｌｏｓｓ　ｏｆ　ｆｅａｓｉｂｌｅ　ｓｐａｃｅ　ｉｓ　ａｖｏｉｄｅｄ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｉｓ　ｖｅｒｙ　ｅｆｆｉｃｉｅｎｔ　ｉｎ　ｔｈｅ　Ｃａｒ·ｈｋｅ　ｍｏｂｉｌｅ　ｒｏｂｏｔ　ｐａｔｈ　ｐｌａｎｎｉｎｇ．　Ｋｅｙｗｏｒｄｓ：ｍｏｂｉｌｅ　ｒｏｂｏｔ；ｐａｔｈ　ｐｌａｎｎｉｎｇ；ｒｏａｄｍａｐ；ｅｎｖｉｒｏｎｍｅｎｔ　ｍｏｄｅｈｎｇ　

１引言（Ｉｎｔｒｏｄｕｃｔｉｏｎ）　２　ＳＰＲＭ路径规划方法的原理（Ｐｒｉｎｃｉｐｌｅ　ｏｆ　ＰＲＭ方法（Ｐｒｏｂａｂｉｌｉｓｔｉｃ　Ｒｏａｄｍａｐ　Ｍｅｔｈｏｄ）是近年　来出现的一种基于随机路图的路径规划方法，该方　法易于实现、规划速度快，在多自由度机械手运动规　划应用中表现出色¨　Ｊ，该方法尤其适用于在同一静　态环境中做多次查询的运动规划问题．本文把ＰＲＭ　方法引入到车形移动机器人的全局路径规划研究　中，车形移动机器人的工作环境通常是静态已知的，　但是为了满足多样性的工作要求，工作路线经常需　要变动，采用ＰＲＭ方法进行路径规划，可以利用同一　幅路图实现不同初始位形和目标位形之间的路径规　划．而且由于ＰＲＭ方法内在的学习机制，可以利用　以往的查询信息提高后续查询的速度，使得路径规　划的速度越来越快，使机器人更加灵活地工作．　基金项目：国家自然科学基金资助项目（６０１７５０３０）　收稿１３期：２００４—０９一Ｏ８　ＳＰＲＭ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｍｅｔｈｏｄ）　２．１随机路图方法（ＰＲＭ）的基本原理　ＰＲＭ方法的核心思想是用一个随机路径网络即　路图表示和获取自由空间的连通性，然后利用图搜　索技术在这个随机路图中为机器人搜索到一条可行　的路径．路图由一系列节点和连线组成，节点对应于　自由空间内机器人的无碰撞位形，两个节点之间的　连线对应于连接这两个位形的一条可行路径．　ＰＲＭ路径规划方法包含两个阶段的操作：预处　理阶段和查询阶段．在预处理阶段，大量点被均匀地　随机撒布到位形空间ｃ中，那些位于自由空间ｃ　中　的点被保留下来作为路图中的节点，构成节点集　，　这个随机产生自由位形的操作称为采样．接下来，由　

维普资讯 http://www.cqvip.com 机器人　２００５年７月　个局部规划器在每对相邻节点之间建立连接，如　果这两个节点之间存在通路，就在它们之间加人一　条连线，所有连线构成连线集Ｅ，所有节点和连线组　成了路图．　在查询阶段，采用图搜索算法对路图进行搜索，　得到连接指定位形对的一个连线序列，再利用局部　规划器进行局部可行路径重建，就可以把这个连线　序列转换成为连接指定位形对的一个局部可行路径　序列，这些局部可行路径组成了一条全局可行路径，　２．２　车形移动机器人路径规划问题描述　本文研究的车形移动机器人采用轮式移动机　构，可以做类似于汽车的运动，其驱动轮可以前、后　运动，转向轮可以向左、向右转向．　车形移动机器人系统是一个高度非完整、欠驱　动的非线性系统，由于非完整约束的影响和转向结　构的限制，轮式移动机器人不能做侧向移动，且存在　最小转弯半径，移动机器人只能做两种形式的受限　运动：一是沿着纵轴方向的平移运动；二是以横轴上　某一点为中心做旋转运动，旋转中心到机器人参考　点的距离不能小于机器人的最小转弯半径．如果在　路径规划时忽略这些约束，即使得到一条位于自由　空间内的无碰撞路径，却不一定是一·条可行路径．为　了便于分析，设定机器人的最小转弯半径是Ｒ　假设移动机器人的工作环境是一个存在若干已　知静态障碍物的二维平面，这个容纳机器人和障碍　物的实际空间称为物理空问．ＰＲＭ方法是利用位形　空间进行路径规划的，位形空间是在机器人内部用　来指定机器人和工作环境内的其他物体的位置和姿　态的数据结构，也就是从外部物理空间映射到机器　人内部环境模型的空间表示．为了便于路径搜索，位　形空间法把机器人缩小为一个质点，按照机器人的　尺寸和形状将障碍物进行扩张．位形空间内不存在　障碍物的空间部分称为自由空间，障碍物占据的空　间部分称为障碍物空间．　２．３　ＳＰＲＭ方法的原理　环境模型是路径规划的基础，任何一种规划算　法都与某种特定的建模方法相对应．ＰＲＭ方法使用　的环境模型是一种基于随机方法生成的路径网络　图，它通过在位形空间中随机采样来获得处于自由　ＳＰＲＭ　ＡＬＧ０ＲＩＴＨＭ　Ｉ．ＰＲＥＰＲＯＣＥＳＳＩＮＧ：ＲＯＡＤＭＡＰ　ＣＯＮＳＴＲＵＣＴＩＯＮ　１．Ｇｒｉｄ　Ｎｅｔｗｏｒｋ　Ｇｅｎｅｒａｔｉｏｎ　２．Ｐｒｏｂａｂｉｌｉｓｔｉｃ　Ｒｏａｄｍａｐ　Ｇｅｎｅｒａｔｉｏｎ　Ｎｏｄｅ　Ｇｅｎｅｒａｔｉｏｎ　区域的机器人位形，并用局部规划器产生的路径将　它们连接起来．在远离障碍物的区域内使用这种方　法可以得到很好的路径，但是在障碍物形状或者分　布比较复杂的区域内，在障碍物附近，则会引发一系　列问题．首先，由随机节点连接成的路径可能很不规　则，甚至出现剧烈抖动，给路径平滑和跟踪造成了很　大的困难，对于轮式系统来说，用随机方式在障碍物　附近产生可行路径尤其困难；同时，障碍物附近的碰　撞校验计算比较复杂，局部规划器要承受非常繁重　的工作量，从而降低了全局规划器的效率．另外，由　于采用完全随机的采样方法，使得一些狭窄通道不　能被随机节点有效覆盖，从而导致可行空间的丢失，　为了解决上述问题，本文对ＰＲＭ方法建立环境模型　的方式做出改进，在障碍物附近的局部范围内，用具　有指导性的建图方式取代ＰＲＭ方法中的完全随机模　式，产生局部的规则路图．　栅格模型在处理障碍物附近的避碰规划问题上　表现出色，为了解决ＰＲＭ方法在障碍物附近存在的　缺陷，本文把类似于栅格法的操作引人到路图构建　中，辅助在障碍物附近进行有指导的建图．具体做法　是：利用大小固定的栅格组成矩形刚络来包围障碍　区，生成形状规则的路图网络来处理障碍物周围的　路径规划，其余的大面积自由区域则采用随机路图　网络进行处理．这种用局部规则路图结合随机路图　建立复合路图的方法克服了普通ＰＲＭ方法在障碍物　附近的弱点，又充分保留了ＰＲＭ高效率的优点以及　其强大的学习能力，本文称之为ＳＰＲＭ方法（Ｓｍａｒｔ　Ｐｒｏｂａｂｉｌｉｓｔｉｃ　Ｒｏａｄｍａｐ　Ｍｅｔｈｏｄ）．　

３　ＳＰＲＭ路径规划方法的实现（Ｔｈｅ　ｉｍｐｌｅ—　ｍｅｎｔａｔｉｏｎ　ｏｆ　ＳＰＲＭ　ｐａｔｈ　ｐｌａｎｎｉｎｇ）　３．１　ＳＰＲＭ算法简述　ＳＰＲＭ路径规划方法由３个阶段的操作组成：预　处理阶段、查询阶段和路径平滑阶段．其中前两个阶　段的操作类似于一般ＰＲＭ方法，但路图建立操作产　生两种路图：障碍物周围的局部规则路图和其他自　由区域内的随机路图．第三个阶段的操作是为满足　车型机器人的非完整约束进行的路径修正．ＳＰＲＭ　算法主要步骤如下所示：　

／／预处理阶段：建立路图　／／产生栅格网络，建立局部规则路图　／／产生随机路图　／／产生随机节点　

维普资讯 http://www.cqvip.com 第２７卷第４期　孙风池等：车型移动机器人的ＳＰＲＭ路径规划方法　３２７　Ｃｏｎｎｅｃｔｉｏｎ（ｔｏ　ｆｏｒｍ　ｒｏａｄｍａｐ）　３．Ｃｏｎｎｅｃｔｉｏｎ　ｏｆ　Ｇｒｉｄ　Ｎｅｔｗｏｒｋｓ　ｔＯ　Ｐｒｏｂａｂｉｌｉｓｔｉｃ　Ｒｏａｄｍａｐ　ＩＩ．ＱＵＥＲＹ　ＰＲＯＣＥＳＳＩＮＧ　１．Ｃｏｎｎｅｃｔ　Ｓｔａｒｔ　ａｎｄ　Ｇｏａｌ　ｔＯ　Ｒｏａｄｍａｐ　２．Ｓｅａｒｃｈ　Ｒｏａｄｍａｐ　ｆｏｒ　ａ　Ｐａｔｈ　ｏｆ　Ｃｏｎｎｅｃｔｅｄ　Ｎｏｄｅｓ　３．ＧｌｏｂＭ　Ｐａｔｈ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ＩＩＩ　ＰＡＴＨ　ＳＭ００ＴＨＩＮＧ　１．１＿ｏｃａｌ　Ｐａｔｈ　Ｒｅ－ｃｏｍｐｕｔａｔｉｏｎ　２．Ｐａｔｈ　Ｓｍｏｏｔｈｉｎｇ　３．ＧｌｏｂＭ　Ｆｅａｓｉｂｌｅ　Ｐａｔｈ　Ｃｏｎｓｔｒｕｃｔｉｏｎ　

３．２局部规则路图网络的构建　ｒ］根据障碍物的大小和分布情况，用边长等于　机器人最小转弯半径Ｒ　ｉ　的正方形栅格组成的矩形　栅格网络覆盖障碍物，相隔距离小于一定阈值的障　碍物用同一网络覆盖，如图１所示．设障碍物的外接　矩形的边长分别为ｎ。和ｂ。，单位和Ｒ　ｉ　相同，则矩形