（控制理论与控制工程专业论文）机器人路径规划中多信息融合技术研究.pdf

摘要 机器人路径规划是机器人导航系统的一个首要任务，这个任务能否顺利执行与机器人能否正 确地融合其多个传感器采集到的关丁环境各个方面的信息是密切相关的。以移动机器人为重点研 究对象，本文对这种密切的关系进行了详细的研究。 首先，为移动机器人的i ：作环境建立了一个基于多边形法的原始配置空间模型。该模型较其 他的机器人环境模型如栅格模型有着精度高的优点。而且该模型有非常成熟的几何理论做基础， 其可靠性有着严格的保证。环境中障碍物的形状复杂多样，分布没有规律性。这就要求在原始的 配置空间中进行路径规划时，需要同时考虑障碍物的大小、形状以及两个障碍物和多个障碍物之 间的最小距离，并将这些距离值与机器人的线径进行比较，以决定机器人的下一步该如何行走。 显然，这涉及到大量的定量运算。计算负荷较大。为此，本文提出了虚拟配置空间模硝t 给出了 随机生成虚拟配置空间的算法、流程和程序代码。针对目前丈多数移动机器人是圆形这一事实t 本文提出了光滑虚拟配置空间模型这一概念以及随机生成光滑虚拟空间的算法、流程以及程序代 码。在光滑虚拟空间中求解圆形移动机器人的无碰路径规划问题时，机器人完全可以当作一个质 点来处理。 其次运_ i i 基于忙尔曼滤波的信息融合准则，结合b a c k s t e p p i n g 积分思想和机器人的运动学 方程，给出了机器人跟踪任意给定轨迹的算法以及基丁本文所构造的两个机器人仿真平台的软件 实现。 仿真结果表明，机器人能够跟踪给定的期望轨迹，而且带信息融合的跟踪算法要优于没有信 息融合的跟踪算法。 最后，基于机器人1 ：作环境的先验信息。本文提出了两种搜索全局最佳路径的算法。本文所 构造的两个仿真平台上的仿真实验表明，第一个算法基本上能找到晟佳路径。但是由下其缺乏向 后搜索功能，有时候找到的路径并不是晟优的。第二个算法在第一个算法的基础上做了改进，理 论上总是可以找到最佳路径，仿真平台上的实验说明了这一点 关键词：机器人；路径规划；路径跟踪；信息融合：虚拟配置空间：卡尔曼滤波：积分b a c k s t e p p i n g n a b s t r a c t r o b o tp a t hp l a n n i n gi sac h i e ft a s kt h en a v i g a t i o ns y s t e mo ft h er o b o ti sc o n f r o n t e dw i t h t h e s u c c e s s f i t li m p l e m e n t a t i o no ft h i st a s kh a sm u c ht od ow i t ht h ef a c tt h a tt h er o b o ts u c c e e d si nc a r r y i n g o u ti n f o r m a t i o nf u s i o no nt h ed a t at h es e n s o r si n s t a l l e do nt h er o b o tc o l l e c ta b o u tt h ee n v i r o n m e n t m a i n l yf o c u s e do nt h em o b i l er o b o t , t h i sp a p e rd o e sp u n c t i l i o u sr e s e a r c ho nt h i sp a r t i c u l a r f i r s t l y , a l lo r i g i n a lc o n f i g u r a t i o ne n v i r o n m e n tm o d e l i ss e tu pt h ew o r ke n v i r o n m e n to f t h em o b i l e r o b o tb ym e a n so ft h ep o l y g o n a lm e t h o d c o m p a r e dt oo t h e rm o d e l s ，s u c ha st h ee v i d e n c eg r i dm o d e ， t h i sm o d e l i so fh i g hp r e c i s i o n a n dw h a t sm o r e t h i sm o d e li sb a s e do nm a t u r eg e o m e t r i c a lt h e o r y w h i c hg i v e ss t r i c tg u a r a n t e ef o rt h er e l i a b i l i t yo ft h i sm o d e l d u et ot h ec o m p l i c a t e ds h a p e so ft h e o b s t a e l e si nt h ee n v i r o n m e n ta n dt h ei r r e g u l a rd i s t r i b u t i o no ft h e m ，p a t hp l a n n i n gi nt h eo r i g i n a l c o n f i g u r a t i o ne n v i r o n m e n tr e q u i r e st h a tt h er o b o th a st os i m u l t a n e o u s l yo b s e r v ea n dm e a s u r et h es i z e s a n ds h a p e so f t h eo b s t a c l e sa n dt h em i n i m u md i s t a n c e sb e t w e e ne v e r yt w oo b s t a c l e sa n dc o m p a r et h e s e d i s t a n c e st ot h ed i a m e t e ro ft h er o b o t , i no r d e rt od e c i d eo nt h en e x ts t e p a p p a r e n t l y , t h i sp r a c t i c e i n v o l v e sl o r so fc o m p u t a t i o na n dc a u s e sah e a v yb u r d c o t os o l v et h i sp r o b l e m ，t h i sp a p e rp u t sf o r w a r d a l li m a g i n a r yc o n f i g u r a t i o ne n v i r o n m e n ta n dp r o v i d e st h ea l g o r i t h m s ，t h ef l o wc h a r t sa n dc o d e st o g e n e r a t es u c ha ne n v i r o n m e n t g i v e nt h ef a c tt h a tm o s tm o b i l er o b o t sa r eo fr o u n ds h a p e ，t h i sp a p e r p u t sf o r w a r dt h ec o n e e p to f as m o o t hi m a g i n a r ye o n f i g u r m i o ne n v i r o n m e n t a n dp r o v i d e st h ea l g o r i t h m s ， t h ef l o wc h a r t sa n dc o d e st og e n e r a t es u c ha ne n v i r o n m e n t w h e ni tc o m e st op a t hp l a n n i n gw i t h o b s t a c l ea v o i d a n c ei nt h i se n v i r o n m e n t , t h er o b o tc a nt h o r o u g h l yb er e g a r d e da sap a r t i c l e s e c o n d l y , c o m b i n i n gt h er u l e so fi n f o r m a t i o nf i i s i o nb a s e do nk a l m a nf i l t e r i n g ，t h em e t h o d o l o g y o fi n t e g r a lb a c k s t e p p i n ga n dt h ek i n e m a t i ce q u a t i o no ft h er o b o t , t h i sp a p e rp r o v i d e st h ea l g o r i t h m st o t r a c kag i v e na r b i t r a r yt r a j e c t o r ya n dr e a l i z e st h e s ea l g o r i t h m so nt h eb a s i so ft h et w os i m u l a t i o n p l a t f o r m sc o n s t r u c t e di nt h i sp a p e r t h es i m u l a t i o nr e s u l l ss h o wt h a tt h er o b o tc a nt r a c k t h eg i v e n a r b i t r a r yt r a j e c t o r yc o r r e c t l ya n dt h a tp a t ht r a c k i n gw i t hi n f o r m a t i o nf i l s i o n j sb e t t e rt h a tw i t h o u t i n f o r m a t i o nf u s i o n f i n a l l y , b a s e do nt h ep r i o r ii n f o r m a t i o na b o u tt h ew o r ke n v i r o n m e n to ft h er o b o t , t h ep a p e rp u t s f o r w a r dt w oa l g o r i t h m st os e a r c hf o rg l o b a l l yo p t i m a lp a t h t h es i m u l a t i o ne x p e r i m e n t sc o n d u c t e do n t h et w os i m u l a t i o np l a t f o r m ss h o wt h a tt h ef i r s ta l g o r i t h mc a nf i n dt h eo p t i m a lp a t hi nm o s tc a s e s o n a c c o u n to f l a c k i n gi nt h ef i t n c t i o n a l i t yo f s e a r c hb a c k w a r d t h ep a t hf o u n d e db yi ti sn o to p t i m a li ns o m e c a s e s 1 1 1 es e c o n da l g o r i t h mi st h ei m p r o v e dv e r s i o no ft h ef i r s to n e t h e o r e t i c a l l ys p e a k i n g ，i tc a n a l w a y sf i n dt h eo p t i m a l w h i c hi sv a l i d a t e db yt h es i m u l a t i o ne x p e d m e n t s k e yw o r d s ：r o b o t ；p a t hp l a n n i n g ；p a t ht r a c k i n g ；i n f o r m a t i o nf u s i o n ；i m a g i n a r yc o n f i g u r a t i o n e n v i r o n m e n t ；k a l m a nf i l t e r i n g ；i n t e g r a lb a e k s t e p p i n g i i i 学位论文独创性声明 本人所呈交的学位论文是我在指导教师的指导下进行的研究工作及取得的研 究成果据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发 表或撰写过的研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作 了明确说明并表示谢意 作者签名：瘥因玺日期：生= z 苎夕 学位论文使用授权声明 本人完全了解大庆石油学院有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文 的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 、i 学位论文作者签考夕参研处孬 导师签名： 日期：山7 蔓 。1 日期： 创新点摘要 i 为机器人的工作环境建立了一种基于多边形法的虚拟配置空间模型。并给出了生成这种模 型的算法、流程和程序代码。该虚拟配置空间模型可靠性和精度都很高，有效地克服了在原始工 作环境中进行路径规划的不便之处。 2 考虑到虚拟配置空间模型中的自由区域损失问题，本文提出了光滑虚拟配置空间模型的概 念，并给出了相应的流程、算法和程序代码。该模型对于圆形移动机器人有着特别的方便之处， 即在该模型下求解移动机器人的路径规划问题时，机器人完全可以当作一个质点来处理，而且不 会损失任何自由区域。这样就可以大大地提高区域覆盖问题的覆盖率。 3 在虚拟配置空间中，将机器人的路径寻优问题转换成一个图搜索问题。为该图建立了种 压缩式邻接矩阵，并提出了一种搜索该矩阵的苒法，该算法效率高，占川存储空间少。 4 使用v i s u a lc + + n e t 建立了两个移动机器入仿真平台，这些平台可以演示带多传感器的 任意路径跟踪算法，复杂环境f 路径寻找算法和障_ f i l 物规避算法。 5 本文所构建的移动机器人仿真平台需要处理大量复杂的计算机图形学问题。很多计算机图 形学大师已经为这些问题给出了完满的答案但是现实中很难寅接利用这些标准的答案。因此， 本文独立地为大多数的基本计算机图形学问题编制了解决方案，给出了其算法、流程以及基于c + + 的程序代码。 人庆石油学院硕l ，研究生学位论文 引言 在未知环境下进行路径规划是移动机器入的研究焦点，国内外众多学者和研究 机构对此做了大量的相关工作。1 9 9 3 年，卡内基梅隆大学的一个研究小组完成了 陆地机器人在未知动态环境下进行路径规划的理论研究，并在第二年完成了导航的相 关实验，这个研究小组也完成了自动驾驶小车跨越全美的实验，时速8 0 k m h 。未知 环境下自动导航的前提就是机器人能够感测到环境的相关信息。波士顿大学通过使用 立体视觉传感器和超声波传感器标记出了三维物理世界模型。俄亥俄州立大学使不同 大小的机器人协同工作，绘制出环境地图。加利福尼亚大学使用k o h o n e n 神经网络描 述机器人工作环境的自由空间。 常见的用于机器人路径规划的方法有： ( 1 ) 几何法：该法提取出环境的几何特性，并将这些特性数据映射为一个抽象的 有权图。这样原来的问题就转换成一个图搜索问题。 ( 2 ) 人工势场法：该法构造了一个虚拟的力场，该力场对机器入有引力作用，障 碍物对机器人有斥力作用，两个力的合力控制着机器人的运动。 ( 3 ) 栅格法：将环境地图划分成一个个的大小相等的栅格，各栅格均有两种状态， 即被障碍物占据或是没有被障碍物占据。在初始状态下，所有栅格的状态都是未知的。 ( 4 ) 人工智能法：近来，基于人工智能的规划方法获得了越来越广泛的应用。典 型的有：模糊逻辑法、神经网络法和遗传算法。 未知环境下的移动机器人自主路径规划的首要问题就是正确而可靠地感知机器 人的状态和环境信息，因此，导航系统是移动机器人的一个不可或缺的部分。移动机 器人的许多任务都建立在这个系统之上，如从房间中的一个位置移动到另一个位置、 在遥远行星上探索、水下巡游、外层空间的自由飞行等等。导航系统解决了机器人所 面对的很多重要闯题，其中三个主要的是：精确地感知和测量机器入的位霉和方向； 感知环境并获得环境信息，以便构建环境模型；与环境中的障碍物避免碰撞，安全地 到达目标。 传感器有位置传感器、距离传感器( 超声波传感器、红外传感器和激光传感器) 、 视觉传感器等，它们构成了导航系统，从不同的侧面感测和收集环境的不同信息，对 机器人起着不同的作用。随着科学技术的进步，现在所用的传感器己比s h a k e y 那个 时代所用的传感器远为精确和可靠，但是它们仍然不可能是完美的，将来也不会。例 如，距离传感器( 声纳、红外探测器或激光测距系统) 放在离障碍物或墙壁一定距离 的地方，它所测得的距离值将随时间的变化而有所不同。空气密度、湿度或温度的微 小变化都会对波束的速度有一定影响，从而影响到测量时间。简而言之，从概率上来 说，任何传感器收集到的数据都有可能出错或失真。因此，很有必要融合不同传感器 所获的信息，这个过程就叫做多传感器信息融合，也叫信息融合。现在有很多用于信 引言 息融合的方法，较为成熟的有：经典推理法、卡尔曼滤波法、证据推理法、聚类分析 法、参数模板法、物理模型法、熵法、质量因数法等等。近年来，智能计算方法在信 息融合领域获得了广泛的应用，例如。模糊集理论、神经网络理论、租糙集理论、小 波分析法和支持向量机。 以移动机器人为研究对象，本文运用基于卡尔曼滤波的信息融合准则，结合用于 时变状态反馈的b a c k s t e p p i n g 积分，成功地实现了机器人的路径跟踪和路径规划。 为了对本文所提出的方法进行仿真和验证，本文构建了两个基于v i s u a lc + + n e t 的移动机器人仿真平台，其中一个是采用o p e n g l 三维图形库的三维仿真平台，主要 实现了任意的路径跟踪，并有一定的真实立体感，另一个是采用醋f c 的二维仿真平台， 主要实现了随机环境的生成、最佳路径的寻找和跟踪。 2 大庆石油学院硕士研究生学位论文 1 概述 1 1 历史背景 很早以前，人们就想制造出可以执行人的命令的机器。例如，三国时代著名的思 想家和政治家诸葛亮制造出木牛流马，帮助运输粮草和辎重。古希腊诗人荷马曾提到 由希腊神h e p h a i s t o s 制造的机器仆人【1 1 。1 4 9 5 年，l e o n a r d od a v i n c i 曾设想制造机械 人。然而，直到2 0 世纪五六十年代( 这时已经发明了三极管和集成电路) ，才真正可 以考虑建造一个实际的机器人。在这2 0 年里，大多数机器人都是通过电控来执行一 组预定义命令的( 例如生产线上的机器人) 。直到1 9 6 7 年，才制造出可以根据给定目 标来决定其行为的机器人。 1 9 6 7 年，斯坦福研究学院在人工智能自动化移动机器人做出开创性的研制工作 1 2 1 。这个工作研制出一台叫做s h a k e y 的机器人，它上面装电视照相机、里程计和电 脑，可以执行运算功能。s h a k e y 可以通过使用一个关于其环境的世界模型、内测距 法、到地面和墙壁交界线的距离及角度来进行定位。距离和角度的观测值与环境地图 中预定义的值进行比较，它们之间的误差值可用来计算和更新s h a k e y 的位置和速度， 并驱动它走到目标点。因为2 0 世纪六十年代末期处理速度和传感器的限制，s h a k e y 需要l o 秒钟的时间才能对自己进行定位。在这l o 秒钟内，机器人没有移动，因此 它的位置纠正可以是准确的。s h a k e y 也能够进行一些基本的路径规划。它会选择拐 弯次数最少的路线( 不一定是距离最短的路线) ，以减少运算量。因为一些限制，如 运算速度、硬件性能、定位方法、规划方法等，s h a k e y 只能在某些环境中运行( 如 地面和墙壁间有可见边界线的光滑地面) ，在复杂的环境中找不到目标。但是，考虑 到s h a k e y 所处的时代，它在机器人领域已经表现出了极好的性能p l 。 2 0 世纪七十年代末期，著名的移动机器人之父h a n sm o r a v e c 首次将立体视觉用 于斯坦福小车的导航。尽管这个小车每1 0 一1 5 分钟只能移动一米，但是它能够通过 其立体视觉功能检测、记录和规划绕过障碍物的路径【钔。在2 0 世纪八十年代早期， h a n sm o r a v e c 将栅格法应用到一台名字叫做n e p t u n e 的机器人上。将立体视觉和声 纳搜集到的环境信息存储在栅格里面，给机器人提供它所在环境的环境地图。机器人 可以用环境地图来执行定位、路径规划和避障功能。当前，大多数机器人研究工作都 使用栅格法来进行导航。 1 2 当前进展 自1 9 6 7 年以来，移动机器入学已发展有一段时间了。目前研究人员使用众多不 同的健壮性方法来使机器人进行探索、定位、路径规划和避障等任务。另外，硬件计 算性能的提高和传感器的改进，使得许多机器人系统的性能有了很大改善。 第一章概述 现在，在未知环境下进行自主导航是移动机器人的研究焦点。1 9 9 3 年，卡内基 每 隆大学的一个研究小组完成了陆地机器人在未知动态环境下进行路径规划的理论研 究，并在第二年完成了导航的相关实验研究。这个研究小组也完成了自动驾驶小车跨 越全美的实验，时速8 0 k m h 。未知环境下自动导航的前提就是机器入能够感测到环 境的相关信息。波斯顿大学通过使用立体视觉传感器和超声波传感器标记出了三维物 理世界模型。俄亥俄州立大学使不同大小的机器人协同工作，绘制出环境地图。加利 福利亚大学使用k o h o n c n 神经网络描述机器人工作环境的自由空间，这种做法比较 特别。 未知环境下的自主导航，要求机器人有更强的避障能力。许多研究者常用人工势 场法、模糊控制法、神经网络法、遗传算法以及其他的人工智能方法，来达到目标。 然而，传统的搜索方法，如爬山法、光束搜索法、最佳优先搜索法、动态规划法等等， 仍然得到了广泛的应用，效果很好。 人工智能在机器人学中的应用尤其成为人们的研究焦点，许多学者在这方面做了 大量的工作。 然而，考虑到目前的技术，还远不能制造出一台完全自主的智能移动机器人。随 着全世界众多学者的努力，这个梦想在不久的将来必定会实现。 1 3 机器人路径规划和传惑器融合综述 移动机器人路径规划是机器人导航的重要问题之一，旨在发现一条从起始状态 ( 包含位置和姿态) 到目标状态( 包含位置和姿态) 的无碰路径。有时候，还要求这 条路径在某种标准的评价下是最优的，例如时问最短或是距离最短。 根据对环境了解的多少，路径规划可以分为两类：全局路径规划，这种情况下机 器人知道环境的所有信息：局部路径规划，这种情况下，机器人依赖于其上安装的众 多传感器所感测到的环境信息。从另外一个角度来看，全局路径规划可以看作是静态 路径规划，而局部路径规划可以看作是动态路径规划。在全局路径规划中，所有信息 ( 如障碍物的位置、形状等) 都需要事先提供给机器人，机器人据此计算出一系列关 键点( 称为顶点) ，将这些顶点连接起来，形成一条通至目标点的路径。在局部路径 规划中，机器人必须时刻感测环境，并根据其上装有的各个传感器所获的环境信息决 定下一步该如何行走。 移动机器人路径规划涉及到以下概念：配置空间、环境模型、传感器融合、路径 规划方法和搜索方法。 1 3 1 配置空间 配置空间是一些点的集合，每个点都代表了机器人的一个位姿( 位置和姿态) 【5 1 。 l o z a n o p c r e z 和w e s l e y 首次定义了配置空间 6 1 。在配置空间中，通过找至g 起始点和 4 大庆石油学院硕士研究生学位论文 目标点之间一系列连续的定位点来解决移动机器人的路径规划问题。二维配置空间的 自由度是3 ，即位置和姿态可以由三个参数唯一决定：x 坐标、y 坐标和机器人的速 度方向与x 轴正向的夹角。 1 3 2 环境模型 移动机器人工作环境的有效描述称为环境模型，所有的路径规划方法都是建立在 环境模型的基础上的。构建环境模型的过程就是将描述环境的原始数据转换成一个更 适合路径规划的内部模型，该过程的主要焦点就是如何描述环境中的障碍物。一个适 当的描述对在短时间内找到最佳路径是很有益处的。目前，描述环境的方法有栅格法、 单元树法、多边形法、人工智能法以及其他方法，其中栅格法是很常用的。图1 i 展 示了原始的工作环境以及相应的栅格模型。 ( a ) 原始环境( b j 栅格化的环境 图1 i 栅格法 栅格法将环境遐的空间划分成多个栅格，每一个都赋有一个值：0 或i 。0 表示 栅格是自由的，没有被任何障碍物占据：l 表示栅格被障碍物占据了。因为一些栅格 完全被障碍物占据，而一些只是部分被占据，所以每一个栅格可以被赋以一个0 到l 之间的值，丽不仅仅是0 或l 。这种情况下，可用概率p 来表示某个栅格的值；从另 一个角度来看，也可以说概率p 表明了一个栅格中有多少面积被障碍物占据了。例如， 0 表示了某个栅格中大概没有任何面积被障碍物占据，0 7 表示某个栅格中大概有7 0 的面积被障碍物占据，l 表示某个栅格大概完全被障碍物占据。如果p 是某个栅格 被障碍物占据的概率，那么1 一p 就是该栅格没有被障碍物占据的概率。这两个概率 的中间值0 5 表示某个栅格被障碍物占据的可能性和没有被障碍物占据的可能性是相 等的。当移动机器人被置于一个未知环境时，所有的栅格都被初始化为o 5 ，这也意 味着在初始状态下，所有的栅格都标记为未曾披机器人访问过。这条规则对于机器人 如何探索未知环境是非常重要的。 栅格法容易实施，而且能够描述不规则的障碍物，这就是为什么许多规划器使用 栅格法来描述环境。然而，栅格法的精度却不是很高。若要提高精度，就得减少栅格 第一章概述 的大小，这势必会极大地增加时间复杂度和空间复杂度。 另一个常见的环境模型是多边形模型。该模型精度很高，速度也快，相应的算法 建立在成熟的几何理论基础之上，可靠性极高。而且，当障碍物数量增加时，时间复 杂度和空间复杂度都可以接受。但是多边形模型的一个致命弱点就是它不能描述形状 复杂的不规则障碍物。 目前，研究人员倾向于使用基于人工智能的模型来描述移动机器人的工作环境。 这些模型及其相关算法已经成为研究焦点。 1 3 3 传感器融合 移动机器人局部自主路径规划的首要问题就是正确而可靠地感知机器人的状态 和环境信息，因此，导航系统是移动机器人的一个不可或缺的部分。移动机器人的许 多任务都建立在这个系统之上，如从房间中的一个位置移动到另一个位置、在遥远行 星上探索、水下巡游、外层空间的自由飞行等等。导航系统解决了机器人所面对的很 多重要问题，其中三个主要的为：感知和测量机器人的位置和方向；感知环境并获得 环境信息，以便构建环境模型；与环境中的障碍物避免碰撞，安全地到达目标。 传感器有位置传感器、距离传感器( 超声波传感器、红外传感器和激光传感器) 、 视觉传感器等，它们构成了导航系统，从不同的侧面感测和收集环境的不同信息，对 机器人起着不同的作用。随着科学技术的进步，现在所用的传感器已比s h a k e y 那个 时代所用的传感器远为精确和可靠，但是它们仍然不可能是完美的，将来也不会。例 如，距离传感器( 声纳、红外探测器或激光测距系统) 放在离障碍物或墙壁一定距离 的地方，它所测得的距离值将随时间的变化而有所不同。当声波( 或红外光束或激光 束) 与障碍物表面所成角度非常小的时候，情形更为糟糕。这是因为波束从障碍物表 面反射回来，可能射到另一个物体上，然后再反射到第三个物体上，如此反复，经过 一段时间之后才回到传感器，从而产生一个较大的滞后。更甚的是，如果障碍物的表 面不光滑，将会产生更加复杂的反射，也就会产生更大的滞后。由于距离传感器依赖 波束的飞行时间，使得机器人认为障碍物比实际距离要远一些，这种误判会导致碰撞。 相似的问题也存在于位置传感器和视觉传感器中。例如，空气密度、湿度或温度的微 小变化都会对波束的速度有一定影响，从而影响到测量时间。 简而言之，从概率上来说，任何传感器收集到的数据都有可能出错或失真。因此， 很有必要融合不同传感器所获得的信息。这个过程就叫做多传感器信息融合，也叫信 息融合，这可以通过概率论的方法来施行。例如，对于栅格模型。现在有很多方法可 以根据传感器的读数来更新各个栅格的概率值。这些方法有：d e m p s t e r - s h a f e r 证据理 论1 7 1 或是h i m m ( h i s t o g r a m m i ci nm o t i o nm a p p i n g ) 伸l ，等等。更新栅格概率值的常用 方法是贝叶斯准则的回归版本【9 1 0 】： 。f ，、尸( i 圩) ( h h l ) “ ( ，( 5 。f ) 尸( k i ) ) + ( p ( s 。l ) j p ( 日k 一。) ) 6 大庆石油学院顾t 研究生学位论文 e ( n l s , ) 是已知传感器的读数时，栅格被障碍物占据的概率。同样地，e ( s 1 h ) 是 已知传感器被障碍物占据时，传感器的读数是s 。的概率。曰是指栅格没有被障碍物 占据。所以 p ( h ) = l 一尸( 日) ，p ( h 1 一1 ) = l p ( 日i ，1 ) 其他较为成熟的信息融合方法有：经典推理法、卡尔曼滤波法、证据推理法、聚 类分析法、参数模板法、物理模型法、熵法、质量因数法等等。近年来，智能计算方 法在信息融合领域获得了广泛的应用【1 1 1 ，例如，模糊集理论、神经网络理论、粗糙集 理论、小波分析法和支持向量机，等等。 许多例子说明了多信息融合技术在移动机器人路径规划中的应用。文献 1 2 1 使用 里程表、激光测距仪和单视觉传感器，组成了导航系统，使用卡尔曼滤波方法对传感 器数据进行融合，以估计机器人的位置和姿态。文献【1 3 】使用模糊神经网络控制移动 机器人在一个未知环境下进行行走。 1 3 4 规划方法 已有许多方法来寻找移动机器人的一条无碰路径，常见的四种是：。 ( 1 ) 几何法1 1 4 】；该法提取出环境的几何特性，并将这些特性数据映射为一个抽象 的有权图。这样原来的问题就转换成一个图搜索问题。常见的几何法有：可见视图法 0 5 , 1 6 1 ；v o r o n o i 图法【1 刀和自由空间法【埽j 。这些方法在二维环境下工作地很好，但是在 三维环境下，它们的表现却乏善可陈。 ( 2 ) 人工势场法【伸1 ：该法构造了一个虚拟的力场，该力场对机器人有引力作用。 障碍物对机器人有斥力作用，两个力的合力控制着机器人的运动。该法的优点是机器 人能够迅速避开突然出现的障碍物。但是局部极点的存在可能会导致死区、振荡和寻 径失败。而且，凹障碍物的势函数是很难找到的。 ( 3 ) 栅格法【2 0 】：该法在前面已经分析过了。 ( 4 ) 人工智能法【2 1 】：近年来，基于人工智能的规划方法获得了越来越广泛的应用。 典型的有：模糊逻辑法1 2 甜。神经网络法f 2 硼，遗传算法 2 4 1 。这些方法有着很好的健壮性， 效果很好，尤其是对于复杂的环境。 1 3 5 搜索方法 建立移动机器人的环境模型和选择路径规划方法之后，下一步工作就是将路径规 划问题转化成一个搜索问题，在环境中搜出一条符合要求的路径。最基本的搜索方法 是深度优先法d f s ( d e p t hf i r s ts e a r c h ) 和广度优先法b f s ( b r e a d t h f i r s ts e a r c h ) 。图1 2 给出了常见的搜索技术及其分类 7 第一章概述 l e c m l o l o g l e $ ；凰= 。 本文的每一章都是可以成体系。 第二章提出了基于多边形法的虚拟配置空间概念，讨论了如何生成一个实际障碍 物的虚拟障碍物，并阐述了如何在虚拟配置空间中进行路径规划。考虑到虚拟配置空 间的一些局限性，针对圆形移动机器人，本文提出了光滑虚拟配置空间的概念。最后， 给出了生成光滑虚拟障碍物的方法。 第三章给出了随机生成一个障碍物、随机生成一个虚拟障碍物以及随机生成一个 光滑虚拟障碍物的算法、步骤和流程图。同时，也给出了随机生成虚拟配置空间和光 滑虚拟配置空间的算法、步骤和流程图。 第四章讨论了基于卡尔曼滤波的信息融合准则和适合于非线性时变系统的 b a c k s t e p p i n g 积分。之后，构建了第一个仿真平台，并利用该平台演示了带信息融合 和没有信息融合的机器人轨迹跟踪实验。然后，构建了第二个仿真平台，详细阐述并 演示了本文所提出的两种全局最佳路径搜索算法的路径寻找过程。 第五章阐述了本文所提出的一些计算机图形学算法，这些算法构成了第二章、第 三张和第四章内容的基础。 s 大庆石油学院硕卜研究生学位论文 2 虚拟配置空间的构建 2 1 移动机器人的环境模型 描述移动机器人环境模型的方法有：栅格法1 2 5 1 、拓扑法【2 6 l 、多边形法等等。本 文使用多边形法，即用多边形代表环境中障碍物。这些多边形可以相离或是相邻，但 是不能相交。为了简单起见，不考虑凹多边形，但是，这并不影响移动机器人路径规 划原理的阐述。不过，本文仍然给出了生成一个凹多边形的算法以及判断凹多边形之 间以及凹多边形与其他几何元素之间的位置关系的算法。用多边形法描述的环境如图 2 1 所示。考虑到很多因素，本文所构建的仿真平台只涉及到三角形、四边形、五边 形、六边形、七边形和八边形。边数更多的多边形可以由同样的原理和方法来处理， 因此本文不涉及它们。 图2 1 用多边形描述的机器人工作环境 用多边形法描述的机器人工作环境模型具有很高的精度和速度，而且避障算法建 立在成熟的凡何理论基础之上，可靠性很高。时间复杂度是o ( n 2 ) 。其中筇环境中障 碍物的个数；空闯复杂度是烈栉) ，其中，| 环境中障碍物的个数。因此，不会出现组合 爆炸问题。与之相比，用栅格法描述的环境模型精度较低，若要提高精度，就得减小 栅格的大小，这势必会极快地增加栅格总数，从而使空间复杂度急剧增加。这个问题 将会导致计算机程序缓存命中失败、内存不足和其他错误。当然，基于多边形法的环 境模型也有一些缺点，例如，它把实际环境理想化了，不能很好地描述具有复杂形状 的障碍物。然而，这些缺点并不妨碍机器人路径规划原理的阐述，也不妨碍本文所提 算法的有效性。 2 2 原始环境中的路径规划 路径规划要求机器入找出一条从起始点到目标点的无碰路径。有时候，还要求这 条路径在某种标准下是最优的。这些要求无论是对于整个机器人在杂乱的环境中移 9 第二章虚拟配置审问的构建 动，还是对于机械手在充满部件的工作车间里移动，都是成立的。图2 2 所示是一个 三角形机器人在多边形法描述的环境中的路径规划问题。该三角形机器人要从起始点 移动到目标点，且不与障碍物发生碰撞。问题的关键所在就是该机器人能否通过障碍 物之间的空隙。 图2 2 多边形描述的工作环境中的机器人路径规划 原始环境中的路径规划要求三角形机器人在移动时不与任何障碍物发生碰撞。因 为障碍物形状复杂，其间距离又未知，三角形机器人得时刻测量各对障碍物之间的最 小距离，并将这些距离值与它自身的线径相比教，否则，它就无法决定下一步如何行 走。然而，这种做法是很费时的。 2 3 虚拟配置空间中的路径规划 一个障碍物的虚拟障碍物定义为包围该障碍物的一个多边形。此后，在不会引起 误解的地方，障碍物也叫做多边形，虚拟障碍物也叫做虚拟多边形，虚拟障碍物的顶 点叫做虚拟顶点。图2 3 详细地阐述了如何生成一个五边形的虚拟多边形。三角形机 器人绕着五边形顺时针( 或是逆时针) 滑动，并总是保持刚好接触的状态。在机器人 绕行一周后，机器人左下顶点形成的轨迹( 图中租线所示) 就是五边形的虚拟多边形。 从图2 3 可以看出，虚拟多边形不再是一个五边形，而是一个八边形。事实上，不论 机器人顺时针绕行还是逆时针绕行，机器入左下顶点、右下顶点、上方顶点或是机器 人中的任何一点所形成的轨迹都可以看作是该五边形的虚拟多边形。一般说来，这些 虚拟多边形都是不一样的。也就是说，一个多边形的虚拟多边形决定于绕行方向以及 选择三角形机器人的哪一个点。但是，这种差别不会影响路径规划的解的存在性。 1 0 大庆石油学院硕 研究生学位论文 图2 4 虚拟配置空间中的路径规划 虚拟配置空间有很多优点。从图2 4 可以看出，在虚拟配置空间中求解路径规划 问题时，没有必要知道各对虚拟多边形之间的距离，而只需知道各虚拟多边形之间是 否相交即可。显然，这样可以减少计算量，使得处理起来更为便利。 2 4 虚拟配置空间中的最佳路径搜索 到目前为止，还不能确定一条可行路径是否是最佳路径或说最短路径( 时间最短 或距离最短) 。图2 4 中的最佳路径不一定是通过两个虚拟多边形之间的间隙。为了 判断一条路径是否最短，必须对虚拟配簧空间进行搜索。然而，搜索工作需要一个网 络才能进行。事实上，虚拟配置空间的搜索网络是很容易构造的。 假设机器人处在虚拟配置空间中的任一个位爱，并向目标点望去，结果只可能有 两种：能看到目标点或者看不到目标点。如果可以看到目标点，那么很容易可以知道 机器人与目标点之间的线段就是要求的最佳路径。如果看不到目标点，那么唯一有 意义的动作就是让机器人从其所在位置移动到另外一个可以看到目标点的虚拟顶点。 所有的动作就是：从起始点移动到一个虚拟顶点，从该虚拟顶点移动到另一个虚拟顶 点( 如果有必要的话) ，最后，从一个虚拟顶点移动到目标点。所以，起始点、 目标点、所有的虚拟顶点以及它们之间的边就构成了一个有权搜索网络，各边的长度 就是权值。该搜索网络也成为可见视图。 目前已经有多种方法用于搜索可见性视图，例如基本搜索法中的穷举法、d f $ 第二章虚拟配置宅间的构建 法和b f s 法，启发式搜索法中的爬山法、光束搜索法和最佳优先法，以及分枝限界 法、带低估的分枝限界法、动态规划法、带动态规划的分枝限界法和a 法，等等。 这些算法在功能和性能上都有所不同，适用于不同的任务。在移动机器人路径规划中， 分枝限界法、带低估的分枝限界法、动态规划法、带动态规划的分枝限界法和a 法 是比较常用的算法。 将动态规划法用于图2 4 所示的虚拟配置空间，结果如图2 5 所示，带箭头的实 线是最佳路径。 源点 图2 5 在虚拟配置空间中寻找最佳路径 2 5 虚拟配置空间的进一步讨论 节2 2 给出的方法求出了一个给定多边形的虚拟多边形，但是该法有些缺点，因 为结果与原多边形的形状、机器人的形状、机器人的绕行方向以及选择机器人的哪一 个点都是有关系的。一旦这些因素发生变化，结果将大不相同，将会导致环境中的不 同布局，对最佳路径的寻找有不利影响。从图2 6 可以知道，在左图中，选择机器人 的左下顶点，绕行方向为顺时针；在右图中，选择机器人的右下顶点，绕行方向为逆 时针。 图2 6 一个多边形的两个不同的虚拟多边形 左边的虚拟多边形与右边的大不一样，这会导致虚拟配置空间的分布也不一样。 现在的问题就是怎么修正它。 考虑到目前大多数移动机器人是圆形或是接近圆形，而且圆形是中心对称的几何 大庆矗油学院硕t ：g f 究生学位论文 图形，那么当它绕多边形行走一周后，由其圆心所形成的轨迹可以看成是虚拟多边形。 可以看到。该虚拟多边形与机器人的绕行方向是没有关系的。图2 7 和图2 8 给出了 简单而明晰的解释，粗实线所围区域就是虚拟多边形。实际边与对应虚拟边之间的距 离就是圆形移动机器人的半径。在图2 7 中，虚拟多边形是一个粗糙的虚拟多边形， 即两个楣邻的虚拟边直接相连。在图2 8 中，两个相邻的虚拟边之间用一个光滑的弧 连接，该弧的半径是机器人的半径。因此，图2 8 中的虚拟多边形不应该称为多边形， 但是为了方便，仍然这么称呼它。本文所构建的两个移动机器人仿真平台中，用的都 是圆形机器人。 图2 8 光滑虚拟多边形 显然，图2 8 所示的虚拟多边形最大程度地利用了所有空间，没有损失任何自由 空间。这也是大多数移动机器人采用圆形形状或接近圆形形状的原因之一。与光滑虚 拟多边形比较起来，粗糙虚拟多边形可能会损失一些自由空间，它的某个内角越小， 损失的自由空间就越多，这点可以从图2 9 看出来。 叠一叠 第一二章虚拟配置窄问的构建 图2 9 粗糙虚拟多边形会损失自由空间 然而，当考虑移动机器人路径规划的复杂度时，粗糙虚拟多边形算法的复杂度要 比光滑虚拟多边形的复杂度小一些。第三章分别给出了随机生成粗糙虚拟多边形和光 滑虚拟多边形的算法。第四章给出了多边形、粗糙虚拟多边形和光滑虚拟多边形的数 据结构，以便保存这两种虚拟多边形所构成的虚拟配置空间，并给出了搜索全局最佳 路径的算法。 l 毒 大庆石油学院硕上研究生学位论文 3 移动机器人仿真平台 3 1 生成原始环境 3 1 1 原始环境的多边形模型 第二章提到有很多方法可以用来为机器人的环境进行建模，其中多边形法精度 高，时间复杂度和空间复杂度都可以接受。在多边形模型中，一个多边形将空间分成 两部分：自由区域和有障区域。在用多边形法表示的原始环