（机械制造及其自动化专业论文）有向物体的路径规划研究.pdf

哈尔滨工程大学硕士学位论文 摘要 传统的对路径规划问题的研究，往往将研究对象简化为质点，将起始和 目标点看作为标量点，来达到简化问题的目的。模型虽然得到了简化，但造 成简化模型不能完全真实反映现实的问题，这样的简化模型只对有些情况适 用。 针对以上不足，本文以具有形状约束和运动约束的有向物体为研究对象， 对传统的路径规划进行改进。论文根据有向物体的特点分析了有向物体路径 规划的特点，找到了一种适用于有向物体的路径规划方法。本算法将有向物 体的运动分解为两种：沿路径主线的运动和避障运动。有向物体在沿路径主 线运动的过程中，对周围环境障碍物进行实时地干涉检测，检测到干涉时进 行避障运动。对于路径主线的制定，本文采用切圆弧或双圆弧曲线来描述路 径，根据不同的初始位姿和目标位姿选择曲线，这两种曲线路径光滑简单， 有向物体易于实现此路径。在对有向物体进行实时干涉检测时，本文首先提 出了有向物体的干涉判别方法，然后采用了预检测和精确检测结合的方法进 行干涉检测。在有向物体避障运动中，有向物体沿障碍物边界运动，直到运 动到障碍物边界上某点，这点是有向物体对目标点的可视点，此时避障结束， 避障段路径由圆弧段和直线段组合而成。避障结束后重新规划路径主线，如 此循环直到到达目标位姿。 本文最后研究了多运动物体的路径规划问题，对多个运动物体进行路径 规划时，采用基于物体运动优先级的“停等 策略。当运动物体检测到与另 一个运动物体发生干涉冲突时，判断彼此的运动优先级，优先级高的沿原路 线前进，优先级低的停止等待，此时优先级低的运动物体作为障碍物处理。 关键词：路径规划；有向物体；双切圆弧曲线：避障；干涉检测 哈尔滨r 丁程大学硕士学位论文 一ii - a bs t r a c t t h et r a d i t i o n a lr e s e a r c ho f t e na b s t r a c t st h er e s e a r c ho b j e c ta sap a r t i c l ea n d l o o k st h es t a r tp o i n ta n dt h ee n dp o i n ta u ss c a l a r st os i m p l i f yt h ep a t hp l a n n i n g p r o b l e m a l t h o u g hi ti se a s i e rt os o l v et h ep r o b l e m ，t h es i m p l i f i e dp a r t i c l ec a nn o t e x a c t l yr e p r e s e n tt h er e a l i t ya n yl o n g e r a sar e s u l t ，t h i ss i m p l i f i e dm o d e lc a no n l y a p p l yi nl i m i t e ds c a l e b e c a u s eo ft h es h o r t a g eo ft h et r a d i t i o n a lp a t hp l a n n i n g ，t h i sa r t i c l ed e v e l o p s t h et r a d i t i o n a lp a t hp l a n n i n gm e t h o db yp l a n n i n gt h ep a t hf o rt h em o v i n go b je c t 、j l ，i m s h a p ea n dm o v e m e n tc o n s t r a i n s t h ef e a t u r e so ft h ep a t hp l a n n i n ga r e s u m m a r i z e da c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h eo b j e c tw i t had i r e c t i o n , t h e na m e t h o do fp a t hp l a n n i n gf o rv e c t o ro b j e c ti s p u tf o r w a r d t h i sa l g o r i t h m d e c o m p o s e st h ep a t hi n t ot w ok i n d s ：n a m e l ym a i np a t ha n do b s t a c l ea v o i d a n c e p a t h 劢eo b j e c tm o v e sa l o n gt h em a i np a t ha n dc h e c ki fc o l l i s i o nh a p p e n ss t e pb y s t e p i ft h ec o l l i s i o nh a p p e n s ，t h eo b j e c tm o v e sa l o n go b s t a c l ea v o i d a n c ep a t h a s t ot h ec u s t o m i z a t i o no ft h em a i np a t h ，t h ea r t i c l eu s e st a n g e n t i a la r c b i a r ct o d e s c r i b et h ep a t h b e c a u s et h e ya r es i m p l ea n ds m o o t h ，t h eo b j e c tc f l l lm o v e s a l o n gt h e me a s i l y a n dt h ea r t i c l ec o m b i n e sp r e - d e t e c t i o nf o rc o l l i s i o na n dp r e c i s e c o l l i s i o nd e t e c t i o nt od e t e c tt h ec o l l i s i o na f t e ri l l u s t r a t i n gt h em e t h o do fc o l l i s i o n d e t e c t i o n w h e ni te , o m e st ot h eo b s t a c l ea v o i d a n c ep a t h ，t h eo b j e c tm o v e sa l o n g t h eb o u n d a r yo ft h eo b s t a c l eu n t i li tr e a c h e ss o m ep o i n to nt h eb o u n d a r y ，w h i c hi s t h ev i s i b l ep o 缸o fo b j e c tt ot h ee n dp o s i t i o n n o wt h eo b s t a c l ea v o i d a n c ep a t h w h i c hc o n t a i n sl i n e ( s ) a n da r c ( s ) f i n i s h e s ，t h e nan e wp a t hi sp r o d u c e d r e p e a t l i k et h i su n t i lt h eo b j e c tr e a c h e st h eg o a lp o s i t i o na n dd i r e c t i o n f i n a l l y , t h i sa r t i c l ed o e ss o m er e s e a r c ho nt h ep a t hp l a n n i n gf o rm a n yo b j e c t s ， t h e “s t o pa n dw 址”s t r a t e g yb a s e do nt h em o v i n go b j e c t sp r i o r i t yi sa d o p t e dt o p l a nt h ep a t hf o rm a n ym o v i n go b je c t s w h e no n em o v i n go b j e c tm e e t sw i t h a n o t h e rm o v i n go b j e c t ，e i t h e ro ft h e mw i l ls t o pm o v i n gt ol e tt h eo t h e rw i t hh i g h e r 哈尔滨工程大学硕士学位论文 p r i o r i t yg of i r s t ，a tt h i sp o i n t ，t h em o v i n go b j e c tw i t hl o wp r i o r i t yi sr e g a r d e da sa s t a t i co b s t a c l e k e y w o r d s ：p a t hp l a n n i n g ；d i r e c t i o n a lo b j e c t ；t a n g e n t i a l a r c b i a r c ；o b s t a c l e a v o i d a n c e ；c o l l i s i o nd e t e c t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中己 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均己在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：兰虽互盔变 日期：肋彦年弓月1 0 日 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 有向物体路径规划研究的意义 1 1 1有向物体概述 本文的研究对象为有向物体，有向物体并不是一个真实的物体，而是根 据一类具有相同特性的真实物体抽象出来的物体模型。这类物体具有形状约 束，是具有一定面积的几何形体；具有运动约束，只能前后运动和转动，而 不能左右横向运动；具有实际的运动能力，不能做折线运动和频繁的转向运 动，而且在转向时还必须满足一定的转弯半径的要求；物体的姿态是由位置 和它的方向角共同决定的，这个特征是相对质点而言的，质点的姿态只与位 置有关，而与方向无关。这类物体在实际应用中很常见，例如飞机、汽车等 都属于这类物体，这类物体因为具有上述特征，使的对它们的路径规划更加 复杂，但也更加具有现实意义。 1 1 2 有向物体路径规划的目的和意义 所谓有向物体的路径规划就是在一定的环境中给定初始位姿和目标位 姿，要求按照一定的策略使有向物体从初始位姿安全无碰地到达目标位姿， 并满足有向物体一系列的约束条件，如有向物体的形状约束、运动约束、有 向物体的实际运动能力等。 有向物体的路径规划也是路径规划研究中的一个重要课题，其重要性主 要表现在： 传统的对路径规划的研究通常将研究对象简化为质点，忽略研究对象 的运动模型，这样造成规划的路径不能满足所有场合需要，而有向物体的路 径规划可以弥补这一不足，拓展了路径规划问题的研究内容。 考虑有向物体的各种特性，使得规划的路径能够满足有向物体的各项 约束条件。 好的路径规划方法可以使有向物体以较短的时间、较优的路径到达目 哈尔滨丁程大学硕十学位论文 标位姿，完成某项特定的任务。 有向物体的路径规划经常被用在大规模的场合，例如机群或是车群的 出、入库、作战等场合，如何在这样的环境下规划出每个物体的运动路线， 使每个物体能够按指定的路径完成自身的任务，最终使整个机群或车群能够 在最短的时间内最高效的完成任务，是一个很有现实意义的课题。 1 2 路径规划概述 要对有向物体进行路径规划，首先需要了解最基本的路径规划问题。路 径规划问题的研究始于2 0 世纪7 0 年代，它是机器人学、虚拟装配、地理信 息系统等领域的基本问题。路径规划问题涉及环境表达、规划方法和路径搜 索策略。环境表达研究如何将环境信息有效地表达出来；规划方法关心的是 在环境表达的基础上而进行的数学模型的抽象；路径搜索策略指的是求解路 径函数的方法技术。 1 2 1 路径规划的定义 由于路径规划问题的复杂性，不同的研究者从不同的角度研究某一方面 的问题，对具体问题的提法也不完全相同。路径规划典型的描述是：在有障 碍物的环境中，如何寻找从起始点到目标点的运动路径且无碰撞地通过所有 障碍物。 蒋新松为路径规划做出了这样的定义1 ：路径规划是自治式移动机器人 的一个重要组成部分，它的任务就是在具有障碍物的环境内，按照一定的评 价标准，寻找一条从起始状态( 包括位置和姿态) 到达目标状态( 位置和姿态) 的无碰路径。 j t se h w a r t z 和m s h a i r 是这样定义路径规划的b 1 ：设b 是一个有若干刚体 部件( 其中一些可能与其它部分用关节相连，另一些可能会独立的存在) 所组 成的机器人系统，它共有k 个方向的自由度，并假设b 在一个充有若干机器人 系统和己知的障碍物的二维或三维空间v 自由运动。对b 来说，路径规划问题 就是给定b 的起始位置z 1 和一个希望达到的终止位置z 2 ，确定是否有一条对b 来说从z 1 n z 2 的无碰路径，如有，则规划出来。 y o u n gk h w a n g 贝j j 把路径规划问题进一步划分成粗规划( g r o s s m o t i o n 2 哈尔滨工程大学硕士学位论文 p l a n n i n g ) 和细规划( f i n e m o t i o np l a n n i n g ) p 1 。前者考虑问题时所涉及到的自由 空间远大于机器人的尺寸与机器人定位误差的和。后者考虑在狭窄空间下的 规划问题，它所要求的移动精度高于机器人定位误差的精度。 1 2 2 路径规划的特点 路径规划具有如下特点州： 1 复杂性 在复杂环境尤其是动态时变环境中，路径规划问题非常复杂，且需要很 大的计算量。 2 随机性 复杂环境的变化往往存在很多随机性和不确定因素，动态障碍物的出现 也带有随机性。 3 多约束 运动对象存在几何约束和物理约束。几何约束指的是运动对象的形状制 约，而物理约束是指运动对象的速度和加速度。 4 多目标 运动对象在运动过程中对路径性能要求存在多种目标，如路径最短、时 间最优、安全性能最好以及能源消耗最小等，但诸目标之间往往存在冲突。 1 2 3 路径规划的分类 路径规划本身可以分为不同的层次，从不同的方面有不同的划分p ： 1 规划方式划分 从路径规划的规划方式来分，路径规划问题已有的研究方法可以分为全 局型方法、局部型方法以及混合型方法3 种。 全局规划方法是种离线的规划法，它依照己获取的环境信息，给物体 规划出一条路径。规划路径的精确程度取决与获取环境的准确程度。全局方 法通常可以寻找最优解，但是需要预先知道环境的准确信息，并且计算量很 大。 局部规划方法是种在线的规划法，它侧重与考虑物体当前的局部环境 信息，让物体具有良好的避障能力。与全局规划方法相比较，局部规划方法 3 哈尔滨丁程大学硕士学位论文 一i - 更具有实时性和实用性，缺陷是仅仅依靠局部信息，有时会产生局部极点， 无法保证物体能够顺利到达目的地。 混合型方法试图结合全局和局部的优点，将全局规划的“粗 路径作为 局部路径的指引路径，引导物体到达目标点。 2 环境角度划分 从物体工作环境的角度区分规划方法，可以分为静态确定环境规划和动 态时变环境规划。 静态确定环境路径规划是指环境信息是完全已知的，而且环境中的障碍 物是静止的情况下，规划出一条无障碍物的路径。这种环境中进行的规划相 对简单一些，但实际意义不是很大。 动态时变环境路径规划是指环境信息是部分己知或者未知存在在运动的 障碍物的环境中，实现路径决策。 1 3 路径规划研究的国内外现状 人们应用人工智能技术在路径规划领域做了大量研究工作，探索出许多 可行有效的求解方法，各种方法适用范围各异。 1 静态确定环境路径规划 物体在确定已知的环境下的路径规划研究已经趋于较为成熟的阶段，现 有以下三种典型的方法，分别是位姿空间法、图搜索法与人工势场法。 位姿空间法 位姿空间法是有t l o z a n o p e r e za n dm a w e s l e y 等人在1 9 7 9 提出的一种 无碰路径规划算法嗍。其实质是根据运动物体的大小和姿态，把周围的障碍 物向外扩展一定的距离，而运动物体则缩小成一点，得到一个位姿空间。这 样把原来在物理空间中求运动物体的无碰撞问题变换成位姿空间中求一个质 点的运动路径，使问题得到简化，因而得到了广泛的应用。基于位姿空间提 出了可视图法g r a p h ) p 1 。该方法将所有障碍物的顶点和物体起始点及目标 点用直线组合相连，要求物体与障碍物各顶点之间、目标点和障碍物各顶点 之间以及障碍物顶点与顶点之间的连线均不能穿透障碍物，即直线是“可视 的 ，从而产生一条路径。 位姿空间法假设物体的尺寸大小忽略不计，这样会使物体通过障碍物项 4 哈尔滨工程大学硕士学位论文 点时离障碍物太近甚至接触，并且搜索时间长。另外该法缺乏灵活性，即一 旦物体的起点和目标点发生改变，就要重新构造可视图。 图搜索法 图搜索法根据栅格法或栅格解耦法将整个环境划分单元，并将单元视为 节点，其间相关关系用弧线相连，得到一个连通图，从而将路径规划问题演 变成点间搜索路径的问题。r a b r o o k s 和t l o z a n o p e r e z 提出的切分法，将 位姿空间切分为一块块的单元，然后搜索相邻单元组成的连接图，但是切分 单元的数目随着精度的提高而迅速膨胀。为了提高表示的效率，人们采用层 次结构表示。a e l f e s 提出的网络模型，将确定性的网络用于离线的路径规划。 s u b b a r a ok a m b h a m p a t i 采用不完全四叉树表示工作空间，将叶节点连接成一 张拓扑图，规划出满足性能的指标路径。从严格意义上看，位姿空间也属于 图搜索法的一种。 人工势场法 人工势场法是由k h a t i b 提出的一种虚拟力法刚。它的基本思想是物体在 环境中的运动设计成一种抽象的人造引力场中的运动，目标点对物体产生“引 力 ，障碍物对物体产生“斥力 ，最后通过求合力来控制物体的运动。势 场法结构简单，但存在局部最优解的问题，因此如何设计“引力场 问题就 成为该方法的关键。 势场法实际上是试图使障碍物的分布情况及其形状等信息反映在环境的 每一点的势场值中。物体的运动是由物体当前的位置所承受的势场，即其梯 度方向所决定。所以它与全局规划相比具有计算量小，实时性好的特点。 导航法 导航法将针对已知障碍所作的全局规划以及实时避碰的局部规划相结 合。其中一种方法是沿着墙壁走的方法，物体沿着墙壁运动，如果遇到障碍 物，物体就将障碍物当成是一堵墙处理，沿着障碍物走直到回到预定的全局 路径上。这种导航方法在技术上并不复杂，但是在实际中很难执行。 2 动态时变环境路径规划 过去对路径规划的研究大都集中在静态环境中，而物体的实际工作环境 往往是动态的。r e i f 和s h a i r 分析了动态环境中运动规划的复杂性问题，研 究表明，处理动态环境中的运动规划比静态环境复杂的多，因此，已有的静 5 哈尔溟工程大学硕七学位论文 态规划方法很难推广到动态不确定环境中去，而动态规划方法还未形成一套 系统的方法和理论，下面就介绍近年来提出的几个具体的解决方法。 k a n t 和z u e k e r 唧提出了两级规划法，该方法首先针对环境中的静态障碍 物规划出一条最短路径，然后控制物体沿着规划好的路径运动，并通过调整 物体的运动速度来避开动态障碍物。这种方法虽然大大减少了问题的搜索空 间，但存在很大的缺陷，如预定路径不能依照环境的最新变化而变化，一旦 有障碍物停留在预定的路径上，物体就无法到达目标。e r d m a n n 和 l o z a n o p e r e z t m l 研究了多个运动物体在静态环境中的规划问题，当运动物体每 次改变它的速度就重构一次位姿空间，这种方法需要大量的计算。 t y c h o n i e v i c h t 等将运动时间划分成一个个小区间，并且设定在每一时间片 中，障碍物的位置和速度均能预知。通过构造潜在的碰撞区，利用启发式知 识引导速度向量朝向优化的路径。q i m i n gz h u t l 2 1 针对动态障碍物的运动，即 采用隐式马尔科夫模型描述和预测动态环境下障碍物的运动。未知速度、加 速度等参数均用概率分布函数预测，规划过程中循环选择一个可行的加速度 向量。 3 基于智能的路径规划 遗传算法扣1 6 1 遗传算法是目前路径规划研究中应用较多的一种方法，它是由 j o h n h o l a n d 在6 0 年代提出的一种以自然遗传机制和自然选择等生物进化理 论为基础的随机化搜索算法。遗传算法运算进化代数众多，占据较大的存储 空间和运算时间，但本身所存在着一些缺陷( 如解的早熟现象、局部寻优能力 差等) ，保证不了路径规划的计算效率和可靠性的要求。 基于行为的方法 这类方法不是建立在推理和外界建模的基础上，而是建立在行为主义的 思想上，认为智能活动是在“感知运动”模式7 1 下进行的。由于具有众多的 感知器和执行器，是十分复杂的分布式系统，但具有强大的功能。 基于模糊逻辑模型的方法8 坶1 这类方法把知识表示成产生规则或其他框架式、语义网格等形式，用统 计或模糊隶属度函数来处理知识的不确定性和模糊性，采用正向、反向和非 单调推理方法或模糊推理建立推理机制。它参考了人的驾驶经验，根据一定 6 哈尔滨工程大学硕士学位论文 的条件和系统的输入，通过查表得到规划信息，实现局部路径规划。该算法 克服了势场法易于产生的局部极小问题，适用于时变未知环境下的路径规划， 实时性较好。 该方法在环境未知或发生变化的情况下，能够快速而准确地规划物体路 径，对于要求有较少路径规划时间的物体是一种很好的导航方法。但是，其 缺点是当障碍物数目增加时，该方法的计算量会很大，影响规划结果。 基于神经网络方法的路径规划m 2 u 这类方法利用了神经元网络具有很强的自学习、自适应能力，可以在训 练样本中自动获取知识，并且具有并行处理的特征。神经网络为解决非先行 系统的控制问题提供了活力，被广泛的应用与复杂系统的辨识，建模和控制。 4 基于混合方法的路径规划 前面提到的方法都各有优缺点，将几种不同的方法结合起来，融合各自 优点，成为近年来各国学者研究的热点。 例如基于模糊逻辑【2 1 模型的方法获取知识困难，没有学习功能，不便进 行并行处理，而基于神经元网络的智能控制的智能控制系统的网络映射规则 不透明，训练时间长，结论的解释比较难。l h t s o u k a l a s 瞵1 等提出一种用于 半自主移动机器人路径规划的模糊神经网络方法。这种方法采用模糊描述来 完成机器人行为编码，同时重复使用神经网络自适应技术。由机器人上的传 感器提供局部的环境输入，再经内部模糊神经网络进行环境预测，进而可以 在未知环境下规划机器人路径。 路径规划的问题尚处于不断的发展和完善之中。该问题的实质是在工作 环境中为物体规划一条优化的运动路径，关键在于如何利用环境信息。全局 规划的方法需要环境中的全部先验信息，而物体的工作环境大部分都是动态 时变的，很难准确预知；而局部规划的方法强调避障行为，虽实时性好，但 是缺乏规划而丧失优化的优点。最佳的方案就是在全局规划的基础上，进行 局部微调，提高规划速度及精度，同时具有一定的灵活性，可以互相结合， 取长补短。这个问题有待进一步研究。 另外，就是优化问题。现有的静态环境中的路径规划法都追求全局最优， 对于较大规模的环境，计算量大，且难以适应比较复杂或规模较大的动态时 变环境，更不便于实时实现。怎样的优化方法能使问题求解规模大大减小， 7 哈尔溟工程大学硕士学位论文 便于解决比较复杂问题和便于实时实现也是值得探讨的问题。 无论是采用何种规划方法，基本上都要遵循以下步骤口6 1 ： 建立环境模型，即将研究对象所处的现实世界进行抽象后建立相关的 模型。 搜索无碰路径，即在某个模型的空间中寻找合乎条件的路径的搜索算 法。 1 4 本文主要工作 本论文针对有向物体进行路径规划，通过对有向物体及其路径的特点进 行分析找到一种能够适合于有向物体的路径规划方法，旨在实现在特定场合 下如何采用适宜的规划方法实时有效地完成有向物体的路径规划，并使规划 的路径能够在实际的应用中起到一定的指导作用。 本论文主要工作和内容安排如下： 第一章，阐述了有向物体路径规划重要的理论意义和现实意义，并总结 了路径规划问题和路径规划方法的国内外现状。 第二章，针对有向物体及其路径的特点，对传统的路径规划方法进行了 深入的分析和比较，最后综合考虑各种路径规划方法的优点和有向物体路径 规划的特点找到了一种新的适合于有向物体的路径规划方法。 第三章，对有向物体的路径描述和干涉检测进行了研究。对有向物体的 路径描述采用的是双圆弧或切圆弧曲线；而对有向物体进行干涉检测时，考 虑到路径的安全性因素提出了有向物体的干涉判别方法，并采用单步检测法 对有向物体进行实时地干涉检测。 第四章，实施了有向物体的路径规划算法，算法将有向物体的运动分为 沿路径主线的运动和沿障碍物边界的避障运动，有向物体根据初始位姿和目 标位姿规划出一条切圆弧或双圆弧的矢量路径主线，物体在沿路径主线运动 的过程中不断地进行实时干涉检测，对检测到的干涉采取沿障碍物边界的避 障运动，物体在进行避障时，充分考虑有向物体的特性和路径的安全性因素 对避障路径的要求，避障段路径由相切的直线和圆弧组合而成。物体在避障 过程中生成不同的路径，最终将从所有无碰的路径中选择一条最合理的路径 作为最终规划的路径。 8 哈尔滨工程大学硕士学位论文 第五章，设计了一套基于有向物体路径规划算法的路径规划仿真系统， 仿真系统的开发平台为w i n d o w sx p ，开发工具为v i s u a ls t u d i o2 0 0 5 。 最后对本论文的主要工作进行了总结，并对进一步的深入研究进行了展 望。 9 哈尔滨工程大学硕士学位论文 第2 章有向物体的路径规划方法研究 对有向物体的路径规划方法进行研究，首先要了解有向物体路径规划的 特点，再对传统的路径规划方法进行研究，分析各种不同规划方法的共同特 性及特殊性，最后找到一种适合于有向物体的路径规划方法。 2 1有向物体及其路径特点 2 1 1有向物体定义 在以往对路径规划的研究中，为了简化研究对象的运动模型，通常都将 研究对象简化为质点，将路径规划问题简化为点到点的路径寻优问题，这样 虽然简化了问题，但生成的路径在有些实际应用中往往很难满足要求。比如 说，在某些特定的环境下研究飞机或者汽车的路径规划时，不能简单地将其 简化为质点，因为这类物体都具有运动约束，在运动时只能前后运动和转动， 而不能横向运动，而且在转动时有最小转弯半径的要求。这类物体都是矢量 物体，它们在每一时刻的状态是由位置和方向角同时决定的，因此，这类物 体的路径规划问题不是简单的点到点的路径寻优问题，而是矢量路径寻优问 题，更具体点说，物体路径规划的任务不仅是到达指定的目标点，同时还必 须到达指定的目标方向。显然，将研究对象简化成质点规划出来的路径对这 类物体而言是不符合要求的。因此为了解决具有上述这类物体的路径规划问 题，在本文中引入了有向物体的概念，将研究对象简化为有向物体，有向物 体是根据物体的形状约束和运动约束等简化的模型，它能够很好的描述这类 物体的各项特性。 2 1 2 有向物体的特点 有向物体是考虑了待路径规划物体的形状约束和运动约束的简化的物体 模型，它具有以下特点： 1 物体具有实际尺寸 有向物体是具有一定面积的几何形体，而不是质点。物体在运动过程中 1 0 哈尔滨丁程大学硕士学位论文 可能经常需要进行避障，如果不考虑物体的实际尺寸，可能会造成物体与障 碍物距离太近而使物体无法顺利避开障碍物，因此在路径规划时，需要考虑 物体的实际尺寸，使物体与障碍物之间保持一定的安全距离。本文中采用凸 多边形来逼近实际物体的外形，主要鉴于以下原因： 绝大多数实际的物体都有着类似凸多边形的外形，例如船舶和机车 也占 守0 对于凸多边形的几何性质研究较多，非凸多边形相对复杂一些。 2 物体为矢量物体 物体每一时刻的姿态不仅由物体的位置决定，同时还由物体的方向决定。 例如在汽车或飞机入库时，不能说它们的位置达到指定地点就说入库成功， 而必须同时调整它们自身到一定角度，使它们的方向与指定的方向一致，这 样才能说是入库成功。 3 物体具有运动约束和实际运动能力 物体具有运动约束，它在运动的过程中只能前后运动和转动，而不能横 向运动，同时物体具有实际的运动能力，它的运动受到了自身结构的制约， 不能像质点一样绕任意半径转动，有向物体在需要转向改变方向时，必须满 足最小转弯半径的要求。有向物体的最小转弯半径是它的固有属性，是由物 体的机械性能和运动性能等因素决定的。物体在转向时，只有绕不小于最小 转弯半径的圆弧转动才能保证物体正常转弯，否则可能会引起物体的翻转或 变形，同时物体在运动时应避免频繁转向，频繁转向可能会造成物体的操控 困难或无法操控。 2 1 3 有向物体路径的要求 在考虑有向物体的路径时，必须将有向物体的特点考虑在内。由于物体 为矢量物体，点到点的标量路径显然不能满足要求；同时由于物体具有实际 运动能力，这就要求规划出的路径是物体能够实现的。根据有向物体的特点， 可以得到对有向物体的路径要求如下： 1 路径是平滑的 由于有向物体的运动受到其机械性能和运动性能的约束，物体的路径必 须尽可能的平滑，折线路径是有向物体很难实现的。 哈尔滨工程大学硕士学位论文 2 路径为矢量路径， 由于物体是矢量物体，因此要求它的路径也应为矢量路径。矢量路径的 设计必须考虑到物体的方向。路径起点的切线方向必须与物体的初始方向角 方向一致；路径终点的切线方向必须同物体目标方向角方向一致：在物体跟 踪规划路径运动的每一时刻，路径的切线方向必须与这一时刻物体的运动方 向角的方向一致。 3 路径尽可能简单 设计的路径应是物体最易实现的，由于物体具有实际的运动能力，它只 能前后运动和转向，转动时的转弯半径不能小于物体的最小转弯半径。因此 路径应尽可能的简单，折线路径和曲率不断变化的曲线路径都使物体难以实 现，而采用直线和曲率不变的圆弧这类简单的图形的组合来描述路径最为简 单，而且生成的路径对有向物体来说，也是最容易实现的。 2 2 路径规划方法的综合分析与比较 前面一节介绍了有向物体及其路径的特点，如何根据它的特点找到一种 能够合适的路径规划方法是本论文的研究重点。众所周知，任何一种方法的 提出都是在借鉴前人研究的基础上，根据所研究的具体问题，找到适合自身 特点的方法。因此只有对现有的路径规划方法进行研究，分析各种方法的特 点，找到与本文所研究的具体问题的相同之处和不同之处，才能找到一种适 合有向物体特点的路径规划方法。 2 2 1常用路径规划方法概述 路径规划是众多领域的重要研究内容之一，针对不同的领域提出了不同 的路径规划的方法。位姿空间法、栅格法、人工势能法都是路径规划中比较 基础的方法。随着路径规划问题的日益复杂，遗传算法等人工智能的方法也 被引入到路径规划问题当中来。多种方法不是相互排斥的，常常需要几种方 法结合起来，互相取长补短，共同地实现路径规划任务。下面分析一下路径 规划的几种常用方法。 2 2 1 1 位姿空间法 位姿空间法是有t l o z a n o p e r e za n dm a w e s l e y 等人在1 9 7 9 提出的一种 1 2 哈尔滨工程大学硕士学位论文 无碰路径规划算法。其实质是根据运动物体的形状和姿态，把周围的障碍物 边界向外扩展一定的距离，即将障碍物经过“膨化 处理变成扩展障碍；同 时运动物体缩小成一点，将运动物体位姿的描述简化为位姿空间的一个点， 于是得到一个新的空间，这个空间称为位姿空间。由于环境中障碍物的存在， 因此在这个位姿空间内存在着相应的障碍区，这样把原来在物理空间中求运 动物体的无碰撞问题变换成在一个存在障碍区的位姿空间中求质点的运动路 径问题，使问题得到简化，因而得到了广泛的应用。 目前，最常用的位姿空间法是可视图法g r a p h ) p 1 。该方法将所有障碍 物的顶点( 设是所有障碍物的顶点构成的集合) 、起始点s 及目标点g 用直 线组合相连，同时要求三者( 即障碍物的顶点、起始点s 及目标点曲之间连线 均不能穿越障碍物，即直线是“可视的 ，给图中的边赋权值，构造图g ，e ) ， 结点集v = u 墨g ) ，e 为所有弧段p f 劫) ，即边集合，其中连接g 中第f 和 第，个结点的线段与任何障碍物均不相交。因为图中相邻的顶点能相互看到， g ( v ，e ) 称为“可视图”。然后采用某种方法搜索从起始点s 到目标点g 的最 优路径。规划最优路径的问题就转化为从起始点到目标点经过这些可视直线 的最短距离问题。 图2 1 表示某一环境空间，s 、g 分别称为起始点和目标点。o b s l 和o b s 2 表示两个障碍物。图2 2 是构造出的对应图2 1 的可视图。利用搜索算法( 常 见的是d i j k s t r a 算法瞬7 1 ) ，规划出从起始点至目标点的最优路径。 图2 1 带两个障碍物环境图 用可视图法规划的路径具有以下三个特征： 1 3 哈尔滨工程大学硕士学位论文 路径是折线的，路径由一系列连接起始点，障碍物顶点和目标点的可 视直线段组合而成，路径不含弯曲部分。 路径的拐弯点为多边形的顶点。 路径的线段为可视图的边。 图2 2 图2 1 对应的司视图 可视图法概念直观、实现简单，主要用于静态已知环境下的路径规划研 究。当环境中的静态障碍物的信息完全己知时，首先构造出起始点，障碍物 顶点和目标点之间的可视图，然后利用搜索方法搜索出一条最短路径，由于 可视图是有穷的，因此在可视图中一定能搜索到一条从起初点至目标点的最 短路径。但可视图法的前提是忽略物体的形状尺寸，这样很有可能使得物体 通过障碍物顶点时离障碍物太近甚至接触；而且该算法在障碍物比较密集的 环境下搜索时间很长，同时算法缺乏灵活性，一旦物体的起初点和目标点发 生改变，就要重新构造可视图。 2 2 1 2 栅格法 栅格法脚9 】( 例d s ) 是在静态路径规划的避障过程中搜索最优路径的常用 方法。该方法将物体的环境空间分割成规则而均匀的含二值信息的栅格。二 值信息分别表示该栅格处是否有障碍，没有障碍的栅格称为自由栅格，否则 为障碍栅格。由这些栅格构成了一个连通图，在这个连通图上搜索一条从初 始栅格到目标栅格的路径，该路径均由自由栅格构成，物体从一个自由栅格 移动到另一个自由栅格，物体移动的步长对应于物体走过的栅格数。 1 4 哈尔滨工程大学硕士学位论文 用栅格法进行路径规划主要有三个步骤：首先根据物体和目标点的位置 划定规划区域，然后将该区域用规则而均匀的栅格表示。栅格的大小是个关 键因素，栅格选得小，环境分辨率较高，在密集环境下发现路径的能力强， 但环境信息存储量大，路径规划的时间长；栅格选得大，环境信息存储量小， 环境分辨率小了，在密集环境下发现路径的能力减弱，但规划的时间变短了。 栅格大小的选取和物体的形状大小相关，一般将每个栅格的面积取为略大于 物体所占的面积，接着给每栅格编号，并将初值赋为0 。0 代表自由栅格， 1 代表障碍栅格。模型建立完成之后，开始检测障碍物的位置，并根据障碍 物的位置找到对应栅格的编号，并对对应的栅格值进行修改，变为1 。最后 开始搜索路径，物体寻找一条从初始点到目标点的连续自由栅格序列。具体 的搜索方法有很多，如遗传算法、基于势场法的栅格路径搜索方法p q 等等。 栅格法和可视图法一样，概念直观，主要用于静态已知环境下的路径规 划研究，而且只要对路径的搜索算法设计的合适，并且环境栅格图中存在从 初始点到目标点的路径，就一定能求得问题的最优解，但由于栅格法的核心 是栅格的建立，因此一旦栅格大小选择不合适就会影响解的质量，而且当搜 索空间较大时，算法需要的存储空间很大，搜索时间会过长，同时用栅格法 规划出来的路径和用可视图法规划出来的路径一样，都是折线、不光滑路径。 2 2 1 3 人工势场法 人工势场法p 1 。3 3 1 是由k h a t i b 提出的一种虚拟力法。它的基本思想是将物 体在环境中的运动设计成一种抽象的人造引力场中的运动，目标点对物体产 生“引力”，障碍物对物体产生“斥力 ，最后通过求合力来控制物体的运 动。 障碍物对物体产生斥力需要具备距离条件和方向条件。距离条件是指两 物体的斥力与其距离的平方成反比，距离是指物体到障碍物边界的最短距离。 障碍物对物体产出斥力的距离条件是距离小于临界最短距离。这个临界最短 距离的确定涉及到物体的大小和平均速度以及环境中障碍物的拥挤程度等因 素。方向条件是指规定只有在物体前方视野内的障碍物才能对物体产生斥力。 假设q ，q 9 0 a l ，q o b 。分别代表物体、目标点和障碍物在运动空间中的位置。 d ( q ，q g o a i ) = iq g o a l q l l 代表物体q 与目标点q 9 0 a l 的距离：d ( q ，q o b 。) 2 iq o b s q | 代表物 哈尔滨工程大学硕士学位论文 体q 与障碍物q o b 。的的距离。则斥力公式为： 磉力= 雠力d 2 ( q o b , 一q ) ( 2 1 ) 式中：d ( q o b , - - q ) 丸 引力公式为： f 引力2 k 引力幸d ( g g f ，g ) ( 2 2 ) 式中：磉力斥力系数 k 引力引力系数 丸考虑斥力的最大距离，只有在小于氏的范围才考虑斥 力 最终的合力公式为： 咯力= 嚷力+ 乓i 力 ( 2 3 ) 合力的方向决定物体的运动方向。目标点和障碍物对物体产生的力分析 如图2 3 所示： 图2 3 势场力分析图 人工势场法计算简单、实时性好、算法复杂性低、算法动态响应快、静 态安全性好。用人工势场法进行路径规划时不仅考虑了物体的避障和轨迹规 划，而且也考虑了物体的运动性能，使物体运动更加自然，规划出来的路径 一般比较平滑并且安全。但它属于一种局部寻优方法，只着眼于得到一条能 够避障的可行路径，并不保证路径的全局最优，而且它对简单环境很有效， 1 6 哈尔滨工程大学硕士学位论文 但对于复杂的多障碍物环境，不合理的势场数学方程容易产生局部极值点， 即在某点的势场合力为零，就会出现在该点停止而不能到达目标点，或者是 在相近的障碍物群中不能识别路径。 2 2 1 4 遗传算法 遗传算法是目前路径规划研究中应用较多的一种方法，它是由 j o h n h o l a n d 在6 0 年代提出的一种以自然遗传机制和自然选择等生物进化理 论为基础的随机化搜索算法，无论是单物体的静态环境还是多物体的动态环 境，遗传算法都取得了良好的路径规划结果，它是一种多点搜索算法，因而 是一种求解全局最优解的较好方法。 利用遗传算法进行路径规划通常和栅格澍m 3 习结合使用，首先用栅格法对 环境进行建模，用编号标注每个栅格。然后用遗传算法进行路径规划，用十 进制栅格编号表示路径节点，用栅格序列表示一条染色体。染色体的长度由 物体走过的栅格数决定；初始解群为随机生成的从初始点到目标点的任意一 条可行路径集合，具体产生的方法和与栅格法搜索最优路径方法类似；适应 度函数可由路径长度、路径平滑度等目标函数确定，定义了初始群体和适应 度函数后，通过交叉、变异等遗传算子生成新个体，通过对新个体的评估产 生子代，不断进化，直到得到问题的最优解或达到算法终止条件而停止。 遗传算法具有优良的全局寻优能力，能够找到全局最优解，而且将遗传 算法与已有的其它的路径规划方法( 栅格法) 相结合来解决路径规划问题，能 够大大提高路径规划问题的求解质量和求解效率。但是遗传算法比较繁琐， 它的求解过程是个迭代循环的过程，而且每次迭代中都有很多算子，同时染 色体的编码设计和适应度函数设计是算法成功与否的关键因素，如果这两个 地方设计不好，往往求不出问题的最优解。 2 2 1 5 感知一动作的应激式方法 这类方法不是建立在推理和外界建模的基础上，而是建立在行为主义的 思想上，认为智能活动是在“感知。运动 模式p q 下进行的，其代表为b u g 算法系列。b u g 算法是最早提出的解决未知环境下机器人路径规划问题的方 法之一，它的算法思想p ：如图2 4 所示。 1 7 哈尔滨工程大学硕士学位论文 g 图2 4b u g 算法下的机器人路径规划示意图 阴影部分为静态障碍，将机器人起始点s 与目标点g 的连线视为机器人 运动的主线( m 1 i n e ) ，机器人从起始点位置出发，首先沿着主线运动，当环境 中有障碍物被探测到与机器人前进路线发生冲突，即机器人奔向目标g 的直 线路径段被阻断，机器人h 点处开始沿此障碍边界运动，直到机器人再次回 到主线( l 点) 并且其与终点的距离较前一次脱离主线时与目标点距离有所减 少时，机器人继续沿主线向目标点移动。 b u g 算法流程： s t e p 0