未知环境基于可拓策略的路径规划.pdf

Computer Engineering and Applications计算机工程与应用2010， 46 （19） 1引言 路径规划是指在有障碍物的环境中， 机器人或载体按照 某一性能指标 （如距离、 时间、 能量等） 寻找一条起点到终点的 最优路径， 使机器人安全、 快速地到达目标1-2。根据环境先验 知识的程度， 一类是基于环境经验知识的全局路径规划， 另一 类是基于传感器信息的不确定环境局部路径规划。目前， 已 提出的未知环境下的路径规划方法和策略主要有： 矢量场图 法3-4、 模糊控制算法5-6、 人工神经网络7、 动态窗口法8、 人工势 场法9-10、 遗传算法11等。但其中很多方法对机器人要求较高， 且很难保证收敛性。 传统算法由于机器人模型的不确定性及算法复杂或实时 性差等因素， 使得在过分追求精确控制的同时， 损失了时间和 速度， 甚至在局部环境振荡。如： 应用较广的近似栅格法， 其 计算量大， 不适于实时动态环境4； 人工势场法， 由障碍物产生 斥力场、 目标产生引力场， 通过计算合力实现沿势场梯度方向 引导机器人前进， 算法简单高效， 但存在局部最小并且在狭窄 环境中容易振荡9-10。虚拟力场法 （VFH） 提出了向量场直方 图法， 作为被广泛采用的一种方法， 但未考虑机器人自身宽度 和运动学特性， 给出的路径实际上很难完成3。 在文献12中提出的使用可拓策略解决路径规划方法， 使 用了物元模型描述环境信息， 而没有应用可拓策略解决不相 容问题的整体思路， 主要以可拓控制器来解决机器人的移动 控制。基于可拓策略生成方法， 建立通过障碍物的临时目标， 将环境分为自由区域和障碍区域， 模拟人在陌生环境通过障 碍的行为。在考虑安全性、 代价以及运动约束要求下建立的 关联函数， 用形式化、 定量化的方法解决通路遇阻的不相容问 题， 取得了令人满意的效果。 未知环境下基于可拓策略的路径规划 叶玮琼 1， 2， 余永权2 YE Wei-qiong1， 2， YU Yong-quan2 1.湖南工业大学 计算机与通信学院， 湖南 株洲 412000 2.广东工业大学 智能工程所， 广州 510090 1.College of Computer & Communication， Hunan University of Technology， Zhuzhou， Hunan 412000， China 2.Institute of Intelligence Engineering， Guangdong University of Technology， Guangzhou 510090， China E-mail： YE Wei-qiong， YU Yong-quan.Path planning based on extension strategy in unknown environment.Computer Engineer- ing and Applications， 2010， 46 （19） ： 10-13. Abstract：This paper proposes a new algorithm by appling the extension strategy in path planning of mobile robot.The new ways use temporary aims in obstacle avoidance to imitate human s selection in unknown environment.So the environment in- formation is efficiently compressed and the modeling of complicated environment can be avoided in the process of real time calculating.The dependent function based on safety distance together with judgement function makes the selected path smooth- er， and reduces the demand of the robot s self-control level and the sensor s measurement accuracy.Due to robust of the strategy of human imitating， the surge and the local minimum can be cut down.Both experiments and simulations prove this method get better effect than the others. Key words：path planning； extension strategy； mobile robot； obstacle avoidance 摘要： 将可拓策略应用于移动机器人路径规划， 提出了一种新的路径规划算法。该方法在绕障时引入临时目标， 模拟了人在未 知环境中的路径选择， 使得环境信息得到有效压缩， 避免了在实时计算过程中对复杂环境的建模。基于安全距离的关联函数得 到的评价函数， 使得所选路径更加平滑， 并且降低了对机器人自身控制及传感器测量精度的要求。由于拟人策略的鲁棒性， 极大 地缓解了其他传统方法的振荡及局部最小现象。实验及仿真均表明该方法实时性好， 规划所得路径优于已有方法。 关键词： 路径规划； 可拓策略； 移动机器人； 避障 DOI： 10.3778/j.issn.1002-8331.2010.19.003文章编号： 1002-8331 （2010） 19-0010-04文献标识码： 中图分类号： TP242 基金项目： 广东省自然科学基金 （the Natural Science Foundation of Guangdong Province of China under Grant No.05001801） 。 作者简介： 叶玮琼 （1975-） ， 男， 讲师， 广东工业大学自动化学院博士生， 主要研究方向为智能控制与信息处理技术、 嵌入式智能系统； 余永权 （1947-） ， 男， 教授， 博士生导师， 主要研究方向： 嵌入式智能系统、 模糊逻辑、 神经网络和软计算。 收稿日期： 2009-12-23修回日期： 2010-05-12 10 2010， 46 （19） 2基于可拓策略生成方法的局部路径规划算法 可拓学是研究不相容问题 （矛盾问题） 的转化与解决的一 门交叉学科。将可拓学中的可拓集及关联函数应用到路径规 划问题中， 实现路径决策。 （1） 以临时目标为依据， 采用可拓集描述机器人的自由区 域及障碍区域， 作为待解集。 （2） 将可拓学中的关联函数作为通行路径的适应度函数。 （3） 在满足安全性、 运行速度及是否符合实际运动学约束 条件下， 构造评价函数， 选择实际最优路径而非理论最优 路径。 2.1环境空间描述 在未知环境中， 由于传感器的探测距离有限， 只可能获得 机器人或载体前方有限范围内的环境数据。进而， 在此区域 内决定短期目标， 到达后修正目标。 文中， 以机器人或载体起点为原点， 目标方向为 Y轴正 向， 建立直角坐标系。在行进过程中， 始终知道目标方位， 自 身半径|R|。在测量范围内， 由于传感器的测量角度及测量的 不可穿透性， 对障碍的观测往往难以获得全部轮廓信息。因 此， 模拟智能生物只关注障碍物边界点的信息， 并留出足够的 安全距离， 即可决定行走路线13。障碍物左右边界点的信息 如下： OBi： DL， L， DR， R（1） 其中， D， 分别表示左右边界点距离机器人的距离和角度。 为边界点与机器人与目标之间射线的夹角， 取逆时针方向为 正。如图1所示。 在实际行走过程中， 机器人在通过障碍物时， 必须保留一 定的安全距离。在文中， 以0.2R作为预留的安全距离， 否则 易发生碰撞。因此， 将边界点外延得到临界点。由于自身约 束无法达到的区域也增加到障碍区域中。对于实际应用中的 轮式车而言， 存在最小转弯半径的问题， 小于最小转弯半径的 圆弧区域同样无法通过， 应该也划为障碍区域。在每次规划 过程中， 这是左右两个固定的障碍区域。如图2所示。 行走过程中， M为车体中心 （XM， YM） ， 根据传感器提供的 有效障碍物左右边界点的信息为OBi： DL， L， DR， R， 可由M 的位置， 得到边界点的坐标OBiL（XOBL， YOBL） 及OBiR（XOBR， YOBR） 。 OBiL： XOBL=XM-DLsinL， YOBL=YM+DLcosL（2） OBiR： XOBR=XM-DRsinR， YOBR=YM+DRcosR（3） 考虑行走过程中， 自身的宽度及行走避障的安全性， 由图 2可知， 左右临界点的位置根据式 （4） 、（5） 对OBiL（XOBL， YOBL） 及 OBiR（XOBR， YOBR） 修正替换原值。 OBiL： XOBL=XOBL-1.2R， YOBL=YOBL（4） OBiR： XOBR=XOBR-1.2R， YOBR=YOBR（5） 2.2通行区域 在实时环境中， 面对的空间区域总是由障碍区域和自由 区域组成。由图2可定义如下： 定义1 由机器人或载体发出射线与任何障碍物左右边界 点相交的切点为边界点。在该点切线的垂直方向上偏移1.2 R， 即为临界点。 该点是绕过障碍物的最短路径的必经之路。在文中， 以 临界点作为临时目标。 定义2 机器人或载体与障碍物左右临界点两条射线形成 的夹角扇形区域， 即为障碍区域。推广定义， 由于自身约束无 法达到的区域， 亦是障碍区域 （OBi） 。 定义3 由相邻障碍区域的临界点的射线形成的夹角扇形 区域， 即为自由区域 （OFi） 。 空 间 区 域 的 组 成 为 ： OB1， OF1， OB2， OF2， ， OBi， OFi， 。当目标方向处于自由区域中时， 显然直线驶向目标 的路径即为最优路径； 在遇到障碍时， 往往存在多个自由区 域， 此时根据关联评价函数来确定最优区域， 并以该区域的最 近临界点作为临时目标， 驱使机器人不断靠近目标。 2.3通行区域可拓策略分析 在机器人或载体直达目标的过程中， 由于障碍导致目标 不可达， 即为矛盾问题。在可拓学中， 该问题属于主观目标和 客观条件所形成的矛盾问题， 属不相容问题14。 （1） 确定导航不相容问题的目标和条件， 并用基元表示导 航的目标为G， 条件为L， 则用基元表示G和L： G= OCg1V1 Cg2V2 Cg3V3 ,L= OC1X1 C2X2 C3X3 （6） O为机器人， Cgi为目标实现时的特征， 分别表示位置、 方 向、 速度， Vi是各特征的量值域。 Ci为实时特征， 分别表示位置、 方向、 实时空间区域， Xi为 各特征的量值域。 （2） 建立问题的可拓模型及核问题的可拓模型 为达到目的地， 该问题的可拓模型为： P=G*L（7） 路径规划的最终目的是要到达指定位置， 目标G中的主 要评价特征为 Cg1， 其量值域为 V， 而指定位置区域为 V0， 自由区域 OF2 自由区域 OF3 自由区域 OF1 自由区域 自由区域 目标 障碍区OB1 OB2 OB3 图1传感器视场图 目标 OB3 OF2 OF3 OF4 OB2 OB4 OB5 自由区域 OF1 自由区域OF5 安全距离 -1.2R 临界点 障碍区OB1 最小转弯半 径区域 图2坐标系及障碍区域图 叶玮琼， 余永权： 未知环境下基于可拓策略的路径规划11 Computer Engineering and Applications计算机工程与应用2010， 46 （19） V0V， V0为特征Cg1的正域。C3是条件L中为解决问题的主 要考虑对象， 其量值域为 C3（Z）， 设 X3代表各夹角区域， X3C3(Z)。记为g0= （O， Cg1， V0） ， l0= （O， C3， C3（Z） ） ， 则该可拓 模型的核问题模型为： P0=g0*l0（8） （3） 关联函数及相容度 对于到达的位置， 引入方向角度来衡量。如行走方向角 的射线可抵达目标， 则方向为最优路径。可指定目标位置 区域为V0， 目标区域角为 （-， +） 。条件l0空间区域为OB1， OB2， ， OBi， ， OF1， OF2， ， OFi， 。OBi为障碍物临界点 夹角 （il， ir） ， OFi为相邻两障碍物临界点夹角 （iL， （i+1） R） 。如 图3。以V0为正域建立可拓集： E (T)=(gyy)|gTvVy=k()Iy=TkK(Tgg)I（9） E (T)为论域V上的一个可拓集， y=k （） 为E (T)的关联函 数， 用于描述行走方向角可抵达目标的程度， 不同于经典集用 0、 1表征对象属于或不属于该集合， 也区别于模糊集用0， 1 中的数来描述具有某性质的程度， 关联函数用 （-， +） 中的 数来描述具有某性质的程度， 并用可拓域描述其相互转化。K 是 V 到实域 I的一个映射，y=TkK(Tgg)为E (T)的可拓函数， TV、 Tk、 Tg分别为论域V、 关联函数k和目标g0的变换。 以V0= （-， +） ， Vi= （il， ir） 或 （il， （i+1） r） 表示障碍区或自 由区， 令 k()= (V0) D(V0Vi) -1(V0)=(Vi)且V0 (V0) D(V0Vi)其他 -1，Vi且ViOBi （10） 称k （） 为方向角关于V0和Vi在V0的中点取得最大值的关联函 数， 值为解决问题的相容度。 该关联函数考虑各可选方向与区间的距， 考虑区间与区 间及一个点与两个区间的位值。具有性质为： 当属于V0且 不为端点时， k （） 0； 当为V0端点时， k （） =0； 当不属于V0 时， k （） 0， 且使k （） 越大的值， 抵达位置更佳。若目标方向存在障碍 物， 因V0OBi， 式 （10） 无法取得正值， 即为不相容问题。 显然， 对于核问题P0， 各自由区域中的不属于V0， 相容度 小于0， P为不相容问题。 （4） 通过拓展分析与可拓变换获取可拓策略并进行路径 选择 不相容问题可根据基元的拓展分析原理， 包括发散分析、 相关分析、 蕴含分析和可扩分析等方法， 对事、 物、 关系进行拓 展， 以获得解决矛盾问题的可能途径。对于目标g0= （O， Cg1， V0） ， 模拟人的蕴含思维方法， 往往是先到达某位置， 再从该位 置到达下一位置， 最终抵达终点。即， 某一目标蕴含着下一目 标。中间目标基元形式可表示为： gi= （O， Cg1， Vgi） ， Cgi表示特征 是位置， Vgi表示Cgi的量值域及位置区域。对于路径规划， 往 往存在多种选择， 可表示为蕴含通道： D1： gi111=gi11=gi1=g0 D2： gi2111=gi211=gi21=gi2=g0 D3： gd=g0 往往在条件 l0下，gd _ ， 故可选择蕴含通道 D1或 D2， 即 gi111或gi2111， 都可使g0。故在未知环境中的路径规划， 在 不可直达时， 应引入临时目标 gi来解决目标不可达的矛盾。 在图 3 的自由区域中， 引入合适的临时目标即可解决矛盾 问题。 此时， 以 V0为正域建立的可拓集 （9） ， 在解决当前问题 时， 仅考虑g变换， 简化如下： E (T)=(giyy)|giTvVy=k()Iy=k(Tgg)I（11） 使得在式 （11） 中， 虽然原来的关联函数k （） 0。k （） 、 k （Tgg） 分别为全局关联函数和临时目标关联函数， 相应取值为全局 相容度和局部相容度。随着目标的逼近， 当全局相容度为正 值的时候， 目标可达。 显然， 从模仿人的思维习惯中可知， 在图3中寻找最优临 时目标应该是脱离障碍区的临界点。因此， 可通过直接判断 各临界点与目标之间的优劣关系来选择最优临时目标。 实际环境中选择最优路径不能仅仅考虑路径最短， 还有 时间最少及安全性最高的问题。综合考虑三方面因素， 临时 目标方向靠近全局目标最近； 方向角与原方向差值小， 这样 可保证高速转向； 临时目标的通过区域与自身宽度比值， 使得 安全性有保障。构造评价函数为： Ki=pk*ki+pD* （， d） +pS*Si（12） 式中： 第一项， ki是关联函数相容度， 表示临时目标方向与目标 点方向的差异， 可看做各临时目标趋向终点的行为； 第二项， 为临界目标方向与机器人当前航向差异， 可看做平滑轨迹的 行为； 第三项， Si代表可通行区域安全性， 通行区域宽度超过两 倍自身直径时， Si取值为ki， 宽度比两倍自身直径每减少10%， Si取值为ki， 减少20%， 直到宽度少于2.4R时， Si取值为-， 相 当于安全因素不够而放弃该路线， 可看做安全性能约束的子 行为。pk、 pD、 pS都是权值因子且都非负， 可根据三方面因素的 重要性给出大小。文中， 三个因子权重分别为0.5、 0.2、 0.3。 3仿真分析及实验结果 3.1仿真及分析 仿真环境使用 Mobile Robot Simulator（Mobotsim）在 Windows下实现。仿真参数设置为高速1.5 m/s， 低速为0.8 m/s， 最大角速度max为0.7 rad/s。设置环境空间10 m10 m， 环境 临界点 目标 自由区域OF5 自由区域 OF1 障碍区OB1 +- 3L 3R 2L 2R 5L 4R 5R 1R 1L 4 OF3 2 3 1 OF2 OB2 OB3 OB4 OF4 OB5 图3区域及自由路径选择 12 2010， 46 （19） 划分为1 0001 000的10 cm10 cm栅格。采样时间t=0.3 s， 机器人直径0.1 m。超声波传感器测距有效测距半径为1.5 m， 每个传感器的波束角为22.515， 机器人周围的16个传感器 覆盖360的空间。增加运动约束， 存在15的转弯死区。当 通行区域宽度小于两倍自身直径时， 采用低速运行。 仿真时， 在同等环境与约束因素下与滚动窗口方法、 VFH+法、 虚拟力场法法仿真结果对比。 与滚动窗口法的比较如图4所示。滚动窗口法善于充分 利用局部已知信息进行预测与评价进行局部优化， 虽然最终 到达目的地， 但在行走过程中围绕障碍物使得路线较长。原 因在于滚动窗口法在以机器人当前位置为中心的、 大小适中 的某一区域窗口内进行规划， 以此优化窗口为起点， 根据窗口 内所提供的场景信息进行预测、 规划局部目标， 直到下一步， 不能在规划上跳出窗口， 朝目标方向前进。因此， 该方法行程 较长， 但在局部环境中规避障碍物的可靠性较高。本文方法 模拟人的思维策略， 即使在有效的探测范围内， 也能主动以全 局目标来指导局部临时目标， 在绕障的过程中不关心障碍物 的局部细节， 因此能获得更短、 更平滑的路径。 图 5 中是本文方法与虚拟力场法的比较。在模拟环境 中， 设置了一段狭窄的通过区域， 部分宽度小于两倍机器人直 径。此时虚拟力场法反复处于过调、 欠调的振荡状态， 因此所 得路径出现波动。而本文方法， 在行走至狭窄处时， 降速明 显， 但基本沿中线运行， 获得非常平滑的路径。 图6中， VFH+方法在两次间隙处障碍物附近均出现慢速 的反复调整。原因在于目标角度与机器人方向间差距较小， 依据比例导引法计算所得角速度很小， 出现较长时间的调 整。同时， 其依赖正前方障碍物密度确定线速度， 因而将线速 度减慢至很小。 3.2实验及分析 算法验证采用四轮移动式机器人， 其中两主动轮差动转 向调整。在实验中， 增加运动约束， 存在15的转弯死区。行 驶时速为1.5 m/s至0.1 m/s可调， 最大角速度max为0.7 rad/s。 试验环境为8 m6 m。搭载计算平台为Pentium4 1.G、 512M， 接收传感器的测距及方向， 控制速度及转向。测距系统是由 安装在机器人车体前后的16个超声波传感器来实现， 用来提 供机器人周围的障碍物距离及方向。路径规划算法由主机完 成， 规划完成后把控制命令发给机器人。 实验时， 在环境中障碍物的设置与仿真环境相似， 本文算 法与滚动窗口方法、 VFH+法、 人工势场法实验结果对比， 由于 实际路径估算不够精确， 主要对比到达时间， 如表1所示。 在实际运行环境中， 取得与仿真类似的运行效果。滚动 窗口法局部路线平滑， 但整体路径不优。人工势场法在障碍 物之间运行时， 由于固有惯性以及出现驱动轮打滑等因素， 机 器人难以精确调整到目标角度， 此时虚拟力场法使机器人反 复处于过调、 欠调的振荡状态， 延长了运行时间。VFH+方法 接近障碍物时， 一旦测得前方障碍物密度大， 机器人降低线速 度， 进入调整阶段， 而机器人运行方向与目标角度间的差距值 对机器人角速度影响大， 因此调整缓慢。因为采取了类人的 思维方法， 不注重障碍物的细节， 以绕过障碍物的边界点为目 标， 运行中方向明确， 较少受到机器人的调整偏差影响， 故整 体运行平稳， 运行效率高于其他方法。 4结束语 提出的基于可拓策略生成的路径规划算法， 利用仿人的 方式