（计算机系统结构专业论文）未知环境下多机器人动态路径规划策略研究.pdf

摘要 摘要 移动机器人是机器人学中的重要分支，对它的研究属于多学科相互交叉，相互 渗透的前沿课题，因此具有很大的理论价值和广阔的应用前景。 机器人导航代表一种高层智能。在避开障碍物的同时，引导机器人走向目标。自 主式导航就是按照预先给出的任务命令，根据已知的环境信息做出路径规划，并在 行进过程中，不断感知周围的环境信息，自主地做出各种决策，并随时调整自身位 姿，引导自身安全行驶或跟踪已知路径达到目标位置。路径规划是移动机器人导航 技术中不可缺少的重要组成部分，它反映了机器人在运动过程中与周围环境的交互 能力，是移动机器人完成任务的基础和安全保障。它研究在有障碍物的工作环境中， 如何为机器人寻找从起点到目标点的运动路径，使机器人在运动中能安全、无碰撞 地通过所有的障碍物。当机器人硬件系统的精度在短期内不能得到解决的情况下， 对路径规划算法的研究显得尤为重要。 本文构建和研究了一种基于行为的自主移动机器人导航决策系统，该系统以多 机器人觅食过程为研究对象，主要包含三部分的内容：一是目标随机分配的搜索导 航策略研究；二是动态任务分配策略研究；三是确定目标的多机器人导航策略研究。 与以往的基于行为的控制方法所不同的是，行为之间的切换是依据一定的情感因子 来决定的。这样，行为的协调机制能够根据当前的情感状态来确定采用合作型或竞 争型的协调，从而能充分利用两者的优点，以提高移动机器人在未知环境中导航的 自适应性，同时确保产生光滑的运动轨迹。并且本文增加了增强学习方法，使得机 器人根据以往的避障经验，可以熟练的完成后面的避障行为。 通过具体的算法仿真，证明本方法在目标随机分配的搜索导航，动态任务分配， 以及目标明确的机器人导航中都有很好的表现。 关键词：移动机器人；导航决策；避障；动态任务分配；增强学习 广东工业大学硕士学位论文 a b s t r a c t m o b i l er o b o ti sa ni m p o r t a n tb r a n c hi nr o b o t i c sr e s e a r c h t h er e s e a r c h e so fi ta r e c r o s s c u t t i n g ，c u t t i n g - e d g ei s s u e so fm u t u a lp e n e t r a t i o n , 8 0t h et h e o r yh a sg r e a tv a l u ea n d b r o a da p p l i c a t i o np r o s p e c t s r o b o tn a v i g a t i o ni sah i g h - l e v e li n t e l l i g e n c eb e h a v i o r a tt h es a m et i m et oa v o i d o b s t a c l e si nt h eg u i d et h er o b o tt o w a r dt h eg o a l a u t o n o m o u sn a v i g a t i o ni s g i v e ni n a c c o r d a n c ew i t ht h et a s ko f p r e o r d e r s ，a c c o r d i n gt ot h ee n v i r o n m e n t a li n f o r m a t i o nm a d e b yt h ep a t hp l a n n i n ga l g o r i t h m , a n di nt h ep r o c e s so fm o v i n g ，t h er o b o th a st oc o n s t a n t l y p e r c e i v et h ee n v i r o n m e n ta r o u n dt om a k ei t so w nd e c i s i o n , a n da ta n yt i m et oa d j u s tt h e i r o w n p o s i t i o na n dp o s t u r et og u i d ei t so w ns e c u r i t yp a t ho ft r a v e lo rt r a c kak n o w nt a r g e t l o c a t i o n p a t hp l a n n i n gf o rm o b i l er o b o tn a v i g a t i o nt e c h n o l o g yi sa ni n d i s p e n s a b l ep a r t ， w h i c hr e f l e c t st h ei n t e r a c t i v i t yb e t w e e nt h er o b o ta n dt h ee n v i r o n m e n ti nt h em o v i n g p r o c e s s ，a n di tf o c u s e so nh o wt of i n dt h ep a t hf o rt h er o b o tf r o mt h es t a r t i n gp o i n tt ot h e t a r g e tp o 妯tw i t ho b s t a c l e si nt h ew o r ke n v i r o n m e n ts ot h a tt h em o v e m e n to fr o b o tc a nb e s a f e ，c o l l i s i o n - f r e et h r o u g ha l lt h eo b s t a c l e s w h e nt h ea c c u r a c yo ft h er o b o th a r d w a r e s y s t e m sc a nn o ta c h i e v ep r e c i s e l y , t h ep a t hp h n n i n ga l g o r i t h mf o rt h es t u d yi sp a r t i c u l a r l y i m p o r t a n t i nt h i sp a p e r , ab e h a v i o rb a s e da u t o n o m o u sm o b i l er o b o t n a v i g a t i o nd e c i s i o n - m a k i n g s y s t e mh a sb e e nb u i l t t h er e s e a r c hf o c u so nm u l t i - r o b o tf e e d i n gp r o c e s s ，t h em a i n c o n t e n t si n c l u d et h r e ep a r t s ：f i r s t ，r o b o tn a v i g a t i o nw i t ht a r g e t sr a n d o m l ya s s i g n e di nt h e u n k n o w ne n v i r o n m e n t ；s e c o n d ，d y n a m i ct a s ka l l o c a t i o ns t r a t e g yf o rr e s e a r c h ；t h et h i r di s t a r g e t e ds t r a t e g yo fm u l t i - r o b o tn a v i g a t i o ni nu n k n o w ne n v i r o n m e n t c o m p a r i n gw i t ht h e p r e v i o u sm e t h o d s ，t h es w i t c hb e t w e e na c t si sb a s e do nac e r t a i nd e g r e eo fe m o t i o n a l f a c t o r si nt h ed e c i s i o n t h i sc o o r d i n a t i o nm e c h a n i s mc a na c ti na c c o r d a n c ew i t ht h e c u r r e n te m o t i o n a ls t a t et od e t e r m i n et h eu s eo fc o o p e r a t i v eo rc o m p e t i t i v ec o - o r d i n a t i o n , s ot h a ti tc a nt a k ef u l la d v a n t a g eo ft h es t r o n gp o i n t so fb o t hi no r d e rt oi m p r o v em o b i l e r o b o tn a v i g a t i o ni nu n k n o w ne n v i r o n m e n t ，a tt h es a m et i m ee n s u r et h es m o o t ht r a j e c t o r y i nt h i sp a p e r , r e i n f o r c e m e n tl e a r n i n gh a sb e e nu s e d , m a k i n gt h er o b o tt oa v o i do b s t a c l e sa c c o r d i n gt o a b s t r a c t p r e v i o u se x p e r i m e n t s t h es i m u l a t i o nr e s u l t ss h o wt h a tt h em e t h o dh a v eag o o dp e r f o r m a n c ei nt h en a v i g a t i o nw h i c h t a r g e t sh a v eb e e nr a n d o m l ya l l o c a t e d , d y n a m i ct a s ka l l o c a t i o na sw e l l 鹊i nt a r g e t e dr o b o tn a v i g a t i o n k e yw o r d s ：m o b i l er o b o t ；r o b o tn a v i g a t i o n ；o b s t a c l ea v o i d a n c e ；d y n a m i ct a s ka l l o c a t i o n ； r e i n f o r c e m e n tl e a r n i n g i i i 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作过的同志对本研究所做的任何贡 献均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 6 l 指导教师签字 第一章绪论 第一章绪论 1 1 课题研究背景及意义 本课题由广东省自然科学基金( n o 0 5 0 0 1 8 0 1 ) 支持。主要研究轮式机器人 在动态未知的环境中如何实现路径规划策略。 众所周知，智能移动机器人【l 】是一类能够通过传感器感知环境和自身状态， 实现在有障碍物的环境中面向目标自主移动，从而完成一定作业功能的机器人系 统。在移动机器人的相关技术研究中，避障控制【2 】一直以来都是路径规划中的难 点与核心，根据机器人对环境信息知道的程度不同，可分为两种类型：环境信息 完全知道的全局路径规划和环境信息完全未知或部分未知的局部路径规划。对于 已知环境下的避碰问题，已经提出了许多有效的解决方法，但是与在已知环境中 相比，机器人在环境完全未知或部分未知情况下实现避障更加困难。 因此本课题的目的就是研究在充满障碍物的环境中，轮式机器人根据自身携 带的传感器获得的局部信息【3 】，能够及时地、有效地、平稳地、安全地避开障碍 物，规划出合理的路径。更进一步的，当有多个机器人在环境中工作时，每个轮 式机器人如何根据其它机器人的运动情况和周围环境信息，动态的规划自己的路 径。 1 2 移动机器人导航的主要研究内容 移动机器人的导航就是按照预先给出的任务命令，根据已知的环境信息做出 全局路径规划，并在行进过程中，不断感知周围的局部环境信息【4 】，自主地做出 正确决策，并随时调整自身位姿，引导自身安全行驶或跟踪已知路径达到目标位 置。移动机器人要实现导航 5 1 涉及到的基本行为有：自身位姿和周围环境的感知 与识别、路径规划、路径跟踪、障碍回避等。由于工作环境的复杂性、自身状态 的不确定性和单一传感器只能获得环境特征的部分信息段的局限性，仅仅依靠一 种传感器难以完成对外部环境的感知。为完成在复杂、动态及不确定性环境下的 广东工业大学硕士学位论文 导航，机器人通常装有用于导航需要的多种传感器，通常用到视觉、超声波、红 外线、光敏、雷达等传感器来完整、准确地探测环境特征。 目前，移动机器人正朝着具有自组织、自学习、自适应的智能化方向发展， 导航能力的高低是移动机器人智能化水平的重要体现。随着移动机器人的应用领 域日益广泛，对移动机器人导航研究不断提出新的课题，使移动机器人的导航研 究不断深入和发展。 在移动机器人的导航过程中，有时它所处的环境是完全知道的，而且是属于 一种静态过程；而在许多情况下，机器人并不预先知道其作业环境【6 】，需要机器 人具有在未知环境中自主导航和建立环境模型的能力。近年来，自主式移动机器 人( a u t o n o m o u sm o b i l er o b o t ) 具有高度的自规划、自组织、自适应能力，在无需 人干预、无需对环境做任何规定和改变的条件下，有目的地移动和完成相应的任 务。在自主式移动机器人相关技术的研究中，导航技术是其研究核心，导航是指 移动机器人通过传感器感知环境和自身状态，实现在有障碍物的环境中面向目标 的自主运动，导航主要解决以下方面的问题： 1 、通过一定的检测手段获取移动机器人在空间中的位置、方向以及所处环 境的信息； 2 、用一定的算法对所获信息进行处理并建立环境模型； 3 、寻找一条最优或近似最优的无碰路径，实现移动机器人安全移动的路径 规划； 4 、控制机器人沿着规划好的路径运动，直至到达目的地为止。 目前，对移动机器人导航技术的研究己取得了大量的成果，但还有很多关键 理论和技术问题有待解决和完善。 未知环境中移动机器人的自主导航问题一直是机器人学中非常具有挑战性 的课题t ，】。为了能够安全而自主地进行导航，机器人需要能够感知周围的环境， 然后实时地规划出一条无碰撞的路径、控制自身的速度和方向、最终到达目的地， 从而安全地完成导航和相应的任务，移动机器人必须能够获取周围环境的信息， 因此，导航控制设计的首要问题是机器人如何探测前进道路上的障碍物以避免发 生碰撞，为此对于移动机器人常常会采用各种传感器或传感器组进行探测。在实 际应用中经常使用的传感器包括视觉c c d 、激光扫描仪、红外传感器和超声传感 器等。其中，超声传感器由于价格低廉而成为移动机器人上普遍采用的环境探测 2 第一章绪论 传感器。 1 2 1 移动机器人导航与定位方式 移动机器人的导航方式有：基于环境信息的环境地图模型匹配导航、基于各 种导航信号的路标导航、视觉导航、气味导航等。 环境地图模型匹配导航是机器人通过自身的各种传感器探测周围环境，利用 感知到的局部环境信息进行局部的地图构造，并与其内部事先存储的完整地图进 行匹配。如果两模型相互匹配，机器人可确定自身的位置，并根据预先规划的一 条全局路线，采用路径跟踪和避障技术，从而实现导航，几年前国外的科学家就 开始从事这项技术的研究，如英国伦敦大学的a r n e 机器人就采用的这种方法。 路标导航是事先将环境中的一些特殊景物作为路标，机器人在知道这些路标 在环境中的坐标、形状等特征的前提下，通过对路标的探测来确定自身的位置， 同时将全局路线分解成为路标与路标间的片段，不断地对路标探测来完成导航。 根据路标的不同，可分为人工路标导航和自然路标导航。人工路标导航是机器人 通过对人为放置的特殊标志的识别实现导航，虽然比较容易实现，但它人为地改 变了机器人工作的环境；自然路标导航不改变工作环境，是机器人通过对工作环 境中的自然特征的识别完成导航，但路标探测的稳定性和鲁棒性是研究的主要问 题。 视觉导航主要完成障碍物和路标的探测及识别，国内外应用最多的是在机器 人上安装车载摄像机的基于局部视觉的导航方式。从视觉图像中识别道路是影响 移动机器人导航性能的一个最重要因素。对于一般的图像边沿抽取而言，已有了 许多方法，例如，局部数据的梯度法和二阶微分法。在视觉导航中边缘锐化、特 征提取等图像处理方法的计算量大，移动机器人是在运动中对图像进行处理，实 时性差始终是一个非常棘手的问题，解决该问题的关键在于设计一种快速图象处 理方法。为了满足速度的要求，基于统计计算的预值法被应用于机器人的导航， 但在实际应用中发现，它抑制噪声的能力差，特别是预值的选取极大地依赖于环 境，要想获得理想的结果，仅在一幅图像中的不同区域就要设置不同的预值。 基于传感器数据导航：一般机器人都安装了一些视觉传感器或非视觉传感 器、如超声传感器、红外传感器、接触传感器等，利用这些传感器亦可以实现机 器人导航。移动机器人导航的关键是用来探测障碍物的传感器的性能，任何类型 广东工业大学硕士学位论文 的传感器都有各自的优点和不足，选用时需要仔细地考虑。 1 、超声波传感器利用物体界面上超声反射、散射检测物体的存在与否。超 声波在空气中传播时如果遇到其它媒介，则因两种媒质的声阻抗不同而产生反射。 因此，向空气中的被测物体发射超声波，检测反射波并进行分析。每个超声波传 感器的射线宽度大约为2 3 6 0 ，通过使用1 6 个传感器，能迅速获得3 6 0 。的全景。 不利的是，超声波传感器工作于发收方式，为了减少交调失真，必须使每个传感 器单独发射射线，超声波传感器由于信息处理简单、快速和低的价格，被各种移 动机器人广泛应用。但它具有一定的局限性，表现在探测波束角过大，方向性差， 往往只能获得目标的距离信息，不能准确地提供目标的边界信息，单一传感器的 稳定性不理想等。在实际应用中，往往采用其它传感器来补偿，或采用多传感器 融合技术提高检测精度等。 2 、雷达发射一束波长介于3 0 c m 和l m m 之间的电磁波，波碰到障碍物被反射 回来，通过测定量波的多普勒频移和波的传播时间就能得到障碍物的有关信息。 微波雷达的最大优点是其性能不受昼夜的影响。即使在恶劣的天气状况下，也能 得到可靠的探测数据，显示出比其它传感器更强的适应性和优越性。 3 、红外线传感器同声纳传感器相似，红外线传感器工作处于发射接收状态。 这些传感器由同一发射源发射红外线，并用两个光检测器测量反射回来的光量。 由于这些仪器测量光的差异，它们受环境的影响非常大，物体的颜色、方向、周 围的光线都能导致测量误差，但由于发射光线是光而不是声音，可以在相当短的 时间里获得较多的红外线传感器测量值。 4 、c c d 图像传感器在一片硅衬底上配置光敏元和电荷转移器件，通过电荷 的依次转移，将多个象素的信息分时、顺序地取出来。这种传感器有一维的线型 图像传感器和二维的面型图像传感器。二维面型图像传感器需要进行水平，垂直 方向扫描，有帧转移方式和线问转移方式。c c d 型驱动电路较复杂，但输出信号 基准高，信号处理较简单，灵敏度高。c c d 图像传感器的应用已遍及航天、遥感、 工业生产检测或监视、医疗卫生等领域。在工业机器人领域也得到了特别广泛的 应用( 用来组成摄像装置) 。 。 气味导航是通过装配在机器人的化学传感器感知气味的浓度，根据气味的浓 度和气流的方向来控制机器人的运动。由于气味传感器具有灵敏度高、响应速度 快以及鲁棒性好等优点，但该技术实用性很差，还处在实验研究阶段。 4 第一章绪论 作为移动机器人导航的最基本环节，定位是确定机器人在二维工作环境中相 对于全局坐标的位姿。定位方法根据机器人工作环境复杂性、配备传感器的种类 和数量等不同有多种方法。主要方法有：惯性定位、路标定位和声音定位等。 惯性定位是在移动机器人的车轮上装有光电编码器，通过对车轮转动的记录 来粗略地确定位置和姿态，该方法简单，但缺点是存在累积误差。 路标定位是在移动机器人工作的环境里，人为地设置一些坐标已知的路标， 通过对路标的探测来确定自身的位姿，它可获得较高的计算精度且计算量小。 声音定位用于物体超出视野之外或光线很暗时，视觉导航和定位失效的情况 下，基于声音的无方向性和时间分辨率高等优点，采用最大似然法、时空梯度法 和m u s i c 法等方法实现机器人的定位。 1 2 2 路径规划 路径规划是移动机器人导航中最重要的任务之一，它是按照某一性能指标搜 索一条从起始状态到目标状态的最优或近似最优的无碰路径。路径规划可以分为 三种类型：一种是基于环境先验完全信息的路径规划；另一种是基于传感器信息 的不确定环境的路径规划；第三种是基于行为的路径规划方法。 1 、基于环境先验完全信息的路径规划 该方法也被称为全局路径规划，能够处理已知环境下的移动机器人路径规 划，当环境发生变化时，如出现未知障碍物时，该方法就无能为力了。这种方法 主要包括可视图法、栅格法和拓扑法等以下几种方法： 可视图法( v i s i b i l i t yg r a p h ) 是将机器人视为一点，把机器人、目标点和多边形 障碍物的各个顶点进行连接，要求机器人和障碍物各顶点之间，目标点和障碍物 各顶点之间以及各障碍物顶点与顶点之间的连线，都不能穿越障碍物，这样就形 成了一张图，称之为可视图。由于任意两直线的顶点都是可视的，显然移动机器 人从起点沿着这些连线到达目标点的所有路径均是无碰路径。搜索最优路径的问 题就转化为从起始点到目标点经过这些可视直线的最短距离问题。运用优化算法， 可删除一些不必要的连线以简化可视图，缩短搜索时间。该法能够求得最短路径， 但假设机器人的尺寸大小忽略不计，使得机器人通过障碍物顶点时离障碍物太近 甚至接触并且搜索时间长，对于n 条连线的搜索时间为o ( n 2 ) 。 栅格法( g r i d s ) 是将移动机器人工作环境分解成一系列具有二值信息的网格单 广东工业大学硕士学位论文 元，多采用二维笛卡儿矩阵栅格表示工作环境，每一个矩形栅格都有一个累积值 c v ，表示在此方位中存在障碍物的可信度。c v 值越高，表征存在障碍物的可能 性越高。用栅格法表示格子环境模型中存在障碍物的可能性的方法起源于美国 c m u 大学，通过优化算法在单元中搜索最优路径。由于该方法以栅格为单位记录 环境信息，环境被量化成具有一定分辨率的栅格，因此栅格的大小直接影响着环 境信息存储量的大小以及路径搜索的时间。栅格划分大了，环境信息存储量小， 规划时间短，但分辨率下降，在密集环境下发现路径的能力减弱；栅格划分小了， 环境分辨率高，在密集环境下发现路径的能力强，但环境信息存储量大，规划时 间长，可以采用改进的栅格法弥补栅格法的不足。路径搜索策略主要有：a 算法、 d 幸最优算法等。因此在实际应用上受到一定的限制。 拓扑法是根据环境信息和运动物体的几何特点，将组成空间划分成若干具有 拓扑特征一致的自由空间，然后根据彼此间的连通性建立拓扑网，从该网中搜索 一条拓扑路径，该方法的优点在于因为利用了拓扑特征而大大缩小了搜索空间， 其算法复杂性只与障碍物的数目有关，在理论上是完备的。但建立拓扑网的过程 是相当复杂而费时的，特别是当增加或减少障碍物时，如何有效地修正已经存在 的拓扑网络以及如何提高图形搜索速度是目前亟待解决的问题。但是针对一种环 境，拓扑网只需建立一次，因而在其上进行最短路径规划就可期望获得较高的效 率。 2 、基于传感器信息的局部路径规划 局部路径规划的主要方法有：人工势场法( a r t i f i c i a lp o t e n t i a lf i e l d ) 、遗传算 法( g e n e t i ca l g o r i t h m ) 和模糊逻辑算法( f u z z yl o g i ca l g o r i t h m ) 等【8 】。 人工势场法( a r t i f i c i a lp o t e n t i a lf i e l d ) 其基本思想是把移动机器人在已知全局环 境中的运动看作一种虚拟的人工受力场中的运动。目标点对机器人产生引力作用， 障碍物对机器人产斥力作用，引力和斥力的合力控制机器人的运动。这种方法结 构简单，易于实现，便于低层的实时控制，在实时避障和平滑的轨迹控制方面， 得到了广泛的应用，但是这种方法也存在着一些缺点：如存在陷阱区，在相近的 障碍物前不能发现路径，在障碍物前产生振荡以及在狭窄通道中摆动等缺点。针 对人工势场法的缺陷，国内外许多专家学者不断寻找新的途径，以克服该方法所 存在的弊端。 j h o l l a n d 在6 0 年代初提出了遗传算法，以自然遗传机制和自然选择等生物进 6 第一章绪论 化理论为基础，构造了一类随机搜索算法。它利用选择、交叉和变异来构造控制 机构的计算程序，在某种程度上对生物进化过程做数学形式的模拟。它不要求适 应度函数是可导或连续的，而只要求适应度函数为正，同时作为并行算法，它的 并行性适用于全局搜索。多数优化算法都是单点搜索算法，很容易陷入局部最优， 而遗传算法却是一种多点搜索算法，因而更有可能搜索到全局最优解。由于遗传 算法的整体搜索策略和优化计算不依赖于梯度信息，所以解决了一些其它优化算 法无法解决的问题。但遗传算法运算速度不快，进化众多的规划时要占据较大的 存储空间和运算时间。 基于实时传感信息的模糊逻辑算法，参考人的驾驶经验，通过查表得到规划 信息，实现局部路径规划。该方法克服了势场法易产生的局部极小问题，适用于 时变的未知环境下的路径规划【，】，实时性较好。 3 、基于行为的路径规划方法 最具有代表性的是美国m i t 的r b r o o k s 的包容式体系结构。所谓基于行为的 研究方法【l o 】是把移动机器人所要完成的任务分解成一些基本的、简单的行为单元， 这些单元彼此协调工作。每个单元有自己的感知器和执行器，二者紧耦合在一起， 构成感知动作行为，机器人根据行为的优先级及结合本身的任务综合作出反应。 该方法的主要优点在于每个行为的功能较简单，因此可以通过简单的传感器及其 快速信息处理过程获得良好的运行效果。但这种方法主要考虑机器人的行为，而 对机器人所要解决的问题以及所面临的环境没有任何的描述，只是通过在实际的 运行环境中机器人行为的选择，达到最终的目标。如何构造和优化机器人行为控 制器是成功与否的关键，主要方法包括：基于传感器信息的局部运动规划方法和 基于模糊逻辑及神经网络的监督学习方法等。 不论采用何种导航方式，智能移动机器人主要完成路径规划、定位和避障等 任务。路径规划是研究自主移动机器人技术的一个活跃课题，路径规划是自主式 移动机器人导航的基本环节之一。 1 2 3 运动控制 运动控制【l l 】是研究自主移动机器人技术较为活跃的课题之一。自主移动机器 人按照存储在其内部的地图信息，或根据外部环境所提供的引导信号( i l p 通过对环 境的实时探测所获得的信息) 规划出一条路径后，它还必须能够沿着该路径在没有 7 广东工业大学硕士学位论文 人工干预的情况下，采用跟踪控制和避障技术移动到预定目标点，实现机器人导 航。跟踪控制是移动机器人运动控制的一个重要问题，分为轨迹跟踪控制和路径 跟踪控制两种。在轨迹跟踪控制中，移动机器人要求跟踪的期望轨迹是以时间关 系曲线图给出的，而在路径跟踪控制中，期望轨迹是由几何参数( 如路径的弧长) 来描述的。当要求机器人必须在一个特定的时间内到达一个特定的目标点时，轨 迹跟踪控制是必需的；当要求机器人以一个期望的速度跟踪一条由几何参数给出 的路径时，路径跟踪控制是合适的。已有的轨迹跟踪方法在数学上很精致，并且 得到许多有意义的结果，但对于设计跟踪控制器来说，并不是最好的方法。事实 上，在传统的自动化应用中，常常采用基于几何路径跟踪概念的方法，控制器的 设计更与人的直觉接近，并且简单、易于实现。 1 3 国内外研究现状 1 3 1 国外研究概况 国外移动机器人的研究起步较早，早在6 0 年代，就已经开始了关于移动机器 人的研究，作为机器人研究中非常重要的路径规划与导航策略，随着具体的机器 人应用方向而得以研究。 路径规划算法这一概念提出的最早时间是在二十世纪七十年代。1 9 7 9 年， t l o z a n o p e r e z 和m a w e s l e y 提出了在几何多面体障碍物间进行路径规划的算法， 之后将算法的应用范围扩展到配置空间( c o n f i g u r a t i o ns p a c e ) 。该算法可以产生 非常精确的优化路径和解决十分困难的问题，特别是在混乱的任务环境，同时它 也考虑到非同构这样的限制。但是此算法的缺点是非常耗时，并且环境模型的更 新对于导航算法的影响很大。 此后，机器人路径规划得到广泛的重视，很多大学都开展了相关的研究，提 出了大量的算法，多数成功的算法都能很好的解决图形搜索的问题。例如， e m j o s s o n 在1 9 9 7 年提出的“真实的数字地图中车辆的最佳路径搜索算法 ，用来 解决在数字化的地图中车辆如何寻找最优的行走路线。此外有研究者提出当数据 只包含几何图形时，可以使用称为“线相交 方法来实现路径规划。任务空间中 几何图形内部不允许穿越，并且没有分布障碍物的区域对于机器人的运动速度和 第一章绪论 其它参数不造成影响。1 9 9 7 年s m w o o d c o c k 在“游戏中的人工智能 一文中提 出了权重图法，此种方法将搜索空间划分为许多的离散区域，每个区域称为一个 栅格，机器人从特定的一个栅格移动到其临近的栅格是受到限制的。此外定义了 一个称为权重函数的方程来计算临近栅格之间的连接值。使用权重图这一概念的 还有非常出名的a 算法，以及其改进算法d 幸。1 9 9 6 年1 2 月美国发射了“火星探 路者”探测器，并用所携带的“索杰纳 火星车对火星进行了实地考察，获得了 很大的成功。索杰纳所采用路径规划方法就是d + 算法，它使索杰纳能在火星表面 自如而谨慎地行走，且能自主判断出前进道路上的障碍物，并通过实时重规划来 做出后面行动的决策，真正做到了“三思而后行 。 近年来国外的路径规划研究除了使用前文提到的可视图法、自由空间法、栅 格法之外，主要着重于环境信息未知和对于已有算法的优化改进。例如d o n g h u nk m 和s e i i c h i s h i n 在“一种新的人工势场法的函数组成以及在局部路径规 划中的应用 一文中提出势力场的概念，将目标定义为对于机器人吸引力，障碍 物定义为排斥力，机器人在这两种力的共同作用下根据一定的算法确定行走的路 线。b e a t r i z a g a r r o 等人使用动态变化的蚁群算法来解决路径规划问题，并使用遗 传算法对于蚁群算法中的参数进行优化，取得了很好的效果。t r w a n 等人在“未 知环境下的实时路径规划”中，根据a 算法提出了一种新的称为动态探测点的方 法来研究未知环境中的路径规划问题，此算法允许机器人根据自身的视觉范围来 调整最优的系统结点，使得机器人可以很好的运行在动态的未知环境中，并且计 算速率非常有效。 1 3 2 国内研究概况 国内对于移动机器人的研究，起步要晚些，从上个世纪八十年代中后期才开 始的，但是有几所大学在机器人方面的研究表现优秀，如哈工大、清华大学和华 南理工大学等。同时有很多学者都在专注于机器人路径规划的研究。 上文提到k o e i n g s 等提出了增量式的d 算法，该方法利用启发式策略搜索一 条从目标点指向机器人当前位置的路径，并在机器人向目标运动过程中根据局部 环境的更新信息来实时重规划路径，由此得出一条最优路径。在国内，张纯刚等 提出了基于滚动窗口的规划方法，也取得了较好的效果。也有学者认为d 宰算法已 经在环境信息部分未知或动态环境下移动机器人路径规划中成功应用，针对原d 宰 9 广东工业大学硕士学位论文 算法精度不高的问题，提出对该算法加以改进。首先采用栅格法对工作空间建模， 然后改进原d 算法，使其对邻近1 6 个方向上的栅格单元进行同时搜索，得到优化 的路径，使机器人角度变化的最小增量降低到兀8 ，从而使机器人在角度上的离 散精度得到了提高，因此机器人路径规划更加灵活，减少了不必要的路径代价。并 在m o b o t s i m 环境中进行算法的仿真，实验结果表明，在同等规模的栅格地图中， 该算法规划的路径质量更高。 梁轲等在“移动机器人在未知狭窄环境中的路径规划 中提到由于人工势场 法很容易产生反复、徘徊等现象，因此结合了几何信息和参考方向来纠正人工势 场法这些缺陷，实现在障碍物体积比较庞大，自由空间相对狭窄的未知环境中有 目的的平滑的路径规划。开且提出一种能够适应复杂环境的避障策略，取得了很 好的实验效果。 近年来，自主式水下机器人由于其在海底资源探测上的优势而受到各国的关 注( 如中俄研制的“c r 一0 1 ”6 0 0 0 m 自治水下机器人) ，但因为水下环境十分复杂( 能 见度差、定位困难等) ，导致一般的规划方法都难以奏效，而水下环境的拥挤程 度相对较低、机器人工作在同一区域的可能性较大这一特征恰好有利于基于事例 的规划方法的应用，因此该方法被广泛的用于解决水下机器人的路径规划问题， 试验证明其效果也较为理想。 刘瑜等根据基于行为的方法成功地研制出两代自主智能吸尘机器人样机，在 智能家庭等商业领域受到了青睐。并且将基于行为的思想引入机器人的作业规划 中，提高了规划的效率和对环境的适应度，具有良好的应用前景。 需要特别提及的是蔡自兴教授于2 0 0 9 年1 月出版了未知环境中移动机器人 导航控制理论与方法一书，此书以未知环境中的移动机器人导航为研究内容， 详细的介绍了机器人的体系结构、环境建模与定位，机器人导航策略，机器学习 理论及应用等知识，意在推动认知科学、模式识别、非线性控制等学科的前沿问 题的研究，对提高探测移动机器人导航控制系统的技术水平，促进移动探测技术 的发展，具有重要的科学意义。 1 0 第一章绪论 1 4 论文的研究内容与组织结构 1 4 1 本文的主要研究内容与创新点 本文以多机器人觅食( 搜寻任务) 为研究对象，研究了动态未知环境下多机 器人的路径规划问题，概括来说主要研究内容包括： 1 、未知环境下的目标随机分配的机器人搜索导航策略； 2 、机器人如何利用先前的避障经验快速的决策本次避障行为的增强学习功 能； 3 、多机器人动态任务分配算法； 4 、未知环境下目标明确的多机器人导航策略； 5 、使用仿真软件验证算法的可行性； 与已有的路径规划策略相比，本文的创新之处主要包括以下两点： 1 、在算法方面使用基于情感法的控制策略进行机器人路径规划导航，能有效 地提高机器人在未知环境中的自主导航能力； 2 、增加机器人自学习功能，当遇到与之前相似的路况时，可以根据先验知识 快速导航。 1 4 2 论文的组织结构 本文主要由下面几个章节组成，第二章主要介绍系统研究的相关理论基础。 第三章主要介绍系统总体设计结构。第四章为系统软件平台设计及数据融合，主 要介绍软件仿真平台，及传感器的数据融合算法。第五章介绍未知环境下目标随 机分配的导航策略。研究在环境信息未知，目标随机分配的情况下，机器人如何 规划路径。第六章介绍未知环境下目标明确的多机器人导航策略。研究目标明确 的情况下机器人如何生成导航策略，以及简单的讨论了机器人动态任务分配。 广东工业大学硕士学位论文 第二章系统研究的相关理论基础 2 1 神经网络 2 1 1 人工神经元模型 一个典型的人工神经元模型如图2 一l 所示。 z 图2 1 神经元模型 f i g 2 1n e u r o nc e l lm o d e l 其中x i ( j = 1 ，2 ，n ) 为神经元i 的输入信号，w i j 为突触强度或连接权。 i l l 是由输入信号线性组合后的输出，是神经元i 的净输入。口i 为神经元的阈值或 称为偏差用b i 表示，v i 为经偏差调整后的值，也称神经元的局部感应区。 = w o x j ( 2 1 ) j m = 甜f + 岛 ( 2 2 ) f ( g ) 是传递函数，y i 是神经元i 的输出。 弗- s ( y _ + 岛) ( 2 3 ) j 传递函数f ( g ) 可取不同的函数，但常用的基本传递函数有以下三种： 1 、阈值函数( t h r e s h o l df u n c t i o n ) 1 2 第二章系统研究的相关理论基础 他，= 忙三或巾，= 辨一 1 , x 删o 巾，一基 3 、s i g m o i d 函数( s i g m o i df u n c t i o n ) f ( v ) = 百而1 ( 2 4 ) ( 2 5 ) ( 2 6 ) 式中参数a 可控制其斜率。s i g m o i d 函数也称为s 型函数。它是人工神经网 络中最常用的传递函数。 2 1 2 人工神经网络结构 1 、单层前向网络 所谓单层前向网络是指拥有的计算节点( 神经元) 是“单层 的，如图2 2 所示。这里表示原节点个数的“输入层 看作一层神经元，因为该“输入层”不 具有执行计算的功能。 源节点输入层神经元输出层 图2 2 单层前向网络 f i g 2 2s i n g l el a y e rf n n 2 、多层前向网络 多层前向网络含有一个或更多的隐含层，其中计算节点被相应的称为隐含神 经元或隐含单元，如图2 3 所示。 1 3 广东工业大学硕士学位论文 源节点输入层 神经元隐禽层神经元输出层 图2 - 3 多层前向网络 f i g 2 3m u l t i - l a y e r sf n n 网络输入层中的每个源节点的激励模式( 输入向量) 单元组成了应用于第 二层( 如第一隐层) 中神经元( 计算节点) 的输入信号，第二层输出信号成为第 三层的输入，其余层类似。网络每一层的神经元只含有作为它们输入前一层的输 出信号，网络输出层( 终止层) 神经元的输出信号组成了对网络输入层( 起始层) 源节点的激励模式的全部响应。即信号从输入层输入，经隐层传给输出层，由输 出层输出信号。 2 2 强化学习 2 2 1 强化学习原理 强化学习( r e i n f o r c e m e n tl e a r n i n g ) 把学习看作试探评价过程，可用图2 4 描述。a g e n t 选择一个动作用于环境，环境接受该动作后状态发生变化，同时产 生一个强化信号( 奖励或惩罚) 反馈给a g e n t ，a g e n t 根据强化信号和环境当前状态 再选择下一个动作，选择的原则是使受到正强化( 奖) 的动作的概率增大。选择的 动作不仅影响立即强化值，而且影响环境下一时刻的状态及最终的强化值。 强化学习不同于连接主义学习中的监督学习，主要表现在教师信号上，强化 学习中，由环境提供的强化信号是a g e n t 对所产生动作的好坏作一种评价( 通常 为标量信号) ，而不是告诉a g e n t 如何去产生正确的动作。由于外部环境提供了 很少的信息，a g e n t 必须靠自身的经历进行学习。通过这种方式，a g e n t 在行为评 价的环境中获得知识，改进行为方案以适应环境。 1 4 第二章系统研究的相关理论基础 图2 - 4 强化学习原理 f i g 2 - 4p r i n c i p l eo fr e i n f o r c e m e n tl e a r n i n g 强化学习系统学习的目标是动态地调整参数，以达到强化信号最大。若已知 强化信号r 与a g e n t 产生的动作a 的o r o a 梯度信息，则可直接使用监督学习算 法。因为强化信号r 与a g e n t 产生的动作a 一般没有明确的函数形式描述，所以 梯度信息o r a a 无法得到。因此，在强化学习系统中，需要某种随机单元，通过 使用这种随机单元，a g e n t 在可能动作空间中进行搜索并发现正确的动作。 2 3 人工情感 很久之前，人们就注意到了情绪对于认知和智能的作用，即情绪与认知、情 绪与智能的关系。1 9 8 1 年就有人研究人工情感问题，但是直到1 9 9 0 年以后才开 始逐渐引起人们的注意，特别是近年来人工情感的研究越来越受到人们的重视。 人工情感( a r t i f i c i a le m o t i o n ) 是利用信息科学的手段对人类情感过程进 行模拟、识别和理解，使机器能够产生人类情感，并与人类进行自然和谐地人机 交互的研究领域。目前对人工情感的研究主要有两个相关领域：情感计算 ( a f f e c t i v ec o m p u t i n g ) 和感性工学( k a n s e ie n g i n e e r i n g ) 。人工情感的研究 内容包括：心理统一模型建模、情感建模、情感的形式化、表情识别和合成、语 音情绪识别、视线追踪、情感姿势识别、意识的机器实现、人工情感的机器表达、 情感与心理信号自动测量和人类心理数字化。 2 3 1 情感计算 使得计算机具有情感能力这一概念首先是由麻省理工学院教授m i n s k y ( 人工 智能创始人