移动机器人的自主导航

移动机器人的自主导航一、讨论的背景二、移动机器人是一个集环境感知、动态决策与规划、行为掌握与执行等多功能于一体的综合系统。它集中了传感器技术、计算机技术、机械工程、电子工程、自动化掌握工程以及人工智能等多学科的讨论成果，是目前科学技术进展最活跃的领域之一。随着机器人性能不断地完善，移动机器人的应用范围大为扩展，不仅在工业、农业、国防、医疗、服务等行业中得到广泛的应用，而且在排雷、搜捕、救援、辐射和空间领域等有害与危急场合都得到很好的应用。因此，移动机器人技术已经得到世界各国的普遍关注。三、在自主式移动机器人相关技术的讨论中，导航技术是其讨论核心，同时也是移动机器人实现智能化及完全自主的关键技术。导航是指移动机器人通过传感器感知环境信息和自身状态，实现在有障碍的环境中面对目标的自主运动。导航主要解决以下三方面的问题：(1)通过移动机器人的传感器系统猎取环境信息;(2)用肯定的算法对所获信息进行处理并构建环境地图;(3)依据地图实现移动机器人的路径规划及运动掌握。四、相关技术五、移动机器人定位是指确定机器人在工作环境中相对于全局坐标的位置是移动机器人导航的基本环节。定位方法依据机器人工作环境的简单性、配备传感器种类和数量等方面的不同而采纳多种方法。主要方法有惯性定位、标记定位、GPS定位、基于地图的定位等，它们都不同程度地适用于各种不同的环境，括室内和室外环境，结构化环境与非结构化环境。度之间达到一种平衡。相对于其他定位方法，基于采样表示MCL方法的优点如下:①与卡尔曼滤波器方法相比，可以表示多模分布，并可实现机器人的全局定位;②与基于栅格的马尔可夫定位方法相比，能以相当高的频率集成测量数据;③与固定尺寸栅格单元的马尔可夫定位方法相比，具有更高的定位精度，缘由在于采样中对应的状态表示没有被离散化;④易于实施。然而粒子滤波器算法也存在不足，其缘由在于估量的随机性。例如，假如采样集的尺寸较小机器人可能仅由于MCL没能够生成正确位置的一个采样而导致失去对其位置的跟踪。算法也不适用于机器人绑架问题，由于一旦机器人处于绑架状态，则可能在机器人新位姿四周没有合适的采样。因此，当传感器不足够精确时，上述基本的MCL算法性能会急速下降。极端状况下，常规MCL算法在传感器信息无噪声干扰时也会失败。为避开和削减常规MCL算法的缺陷，讨论人员提出了多种改进方案，如混合McL算法、实时粒子滤波器方、帮助粒子滤波器等。三十、(3)路径规划三十一、不论采纳何种导航方式，智能移动机器人主要完成路径规划、定位和避障等任务。路径规划是自主式移动机器人导航的基本环节之一。它是依据某一性能指标搜寻一条从起始状态到目标状态的最优或近似最优的无碰路径。依据机器人对环境信息知道的程度不同，可分为两种类型:环境信息完全知道的全局路径规划和环境信息完全未知或部分未知，通过传感器在线地对机器人的工作环境进行探测，以猎取障碍物的位置、外形和尺寸等信息的局部路径规划。全局路径规划包括环境建模和路径搜寻策略两个子问题。依据不同的地图模型，路径规划可分为两类:基于图结构的路径规划、基于波阵面的路径规划。对于图结构的路径规划，通常依靠于环境结构的拓扑图表示，如可视图法(v-GraPh)、自由空间法(FreespaeeAPproaeh)和四叉树法等(Grids)等。在该类以拓扑地图表示的路径规划中，通常可直接采纳基于图的最优路径计算方法猎取路径信息，如A*算法、D*算法。可视图法以机器人为一点，将机器人、目标点和多边形障碍物的各顶点进行组合连接，要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线，均不能穿越障碍物，即直线是可视的。搜寻最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。广义Voronoi图法和切线图法对可视图法进行了改进，其中Voronni图的基本思想是产生与全部边界点等距的线，而这些线的走向是沿着走廊或开口的中间，沿该线运动不会与任何障碍物冲突。切线图用障碍物的切线表示弧，因此是从起点到目标点的最短路径的图，即机器人必需几乎接近障碍物行走。自由空间法应用于机器人路径规划，采纳预先定义的如广义锥形和凸多边形等基本外形构造自由空间，并将自由空间表示为连通图，通过搜寻连通图来进行路径规划。该法比较敏捷，起始点和目标点的转变不会造成连通图的重构，但算法的简单程度与障碍物的多少成正比，且不是任何状况下都能获得最短路径。四叉树或八叉树表示通常是将标准栅格地图转化为图的形式，并通过优化算法完成路径搜寻。波阵面传播型规划器(WaVe-frontTransform)很适合栅格类型地图的规划处理。其基本原理是:波阵面把结构空间视为一种导热物质，假如存在一个路径，热从起始节点向目标节点传导，热量将最终达到目标节点，同时全部栅格单元到目标的最优路径都可以计算出来，该算法与势场原理相像，让路径自身来表示机器人应当怎么做。该类算法讨论比较丰富，在论文的节有具体叙述。局部路径规划的主要方法有:人工势场法(ArtifieialPotentialField)、遗传算法(GenetieAlgorithm)和模糊规律算法(FuzzyLogieAlgorithm)等。人工势场法将机器人在环境中的运动视为一种虚拟的人工受力场中的运动。障碍物对机器人产生斥力，目标点产生引力，引力和斥力的合力作为机器人的加速力，来掌握机器人的运动方向和计算机器人的位置。该法结构简洁，便于低层的实时掌握，在实时避障和平滑的轨迹掌握方面，得到了广泛的应用，但对存在局部最优解的问题，简洁产生死锁现象(DeadLock),因而可能使机器人在到达目标点之前就停留在局部最优点。多数优化算法都是单点搜寻算法，很简洁陷入局部最优，而遗传算法却是一种多点搜寻算法，因而更有可能搜寻到全局最优解。由于遗传算法的整体搜寻策略和优化计算不依靠于梯度信息，所以解决了路径规划处理中一些其它优化算法无法解决的问题。但遗传算法运算速度不快，进化众多的规划要占据较大的存储空间和运算时间。基于实时传感信息的模糊规律算法参考人的驾驶阅历，通过查表得到规划信息，实现局部路径规划,可克服势场法易产生的局部微小问题，适用于时变未知环境下的路径规划，实时性较好。三十二、（4）同步地图创建与自定位三十三、移动机器人地图创建需要机器人位姿和基于当前位姿的外界环境信息。因此地图创建过程就是机器人对所在环境进行遍历，并将遍历过程中猎取的环境信息不断融合累积的过程。地图创建最简洁的方法为增进式方案，它包含2个部分:首先采用当前地图估量机器人位置，然后当机器人猎取新的信息时对当前估量位置四周区域进行局部地图更新。然而在未知环境下的实时地图创建中，增进式地图创建方案明显不能满意需要。由于机器人运动存在累积误差，仅依靠运动掌握信息不能确定机器人位姿，需依据地图中的外部环境信息不断进行校正定位;而地图构建过程又依靠于精确的位姿信息，两过程相互冲突与依靠，必需同时考虑，即要求实现同步地图创建和定位。作为移动机器人讨论的核心问题，近20年来SLAM讨论吸引了全世界范围内大批讨论人员的参加，并已经取得系列重要讨论成果。方法主要可分为:基于Kalman滤波器的跟踪方法;基于EM算法的全局优化方法;基于Partiolefilters的SLAM算法;此外,讨论人员也提出了基于上述算法的混合方案,以及基于其他计算智能方法的SLAM方案。上述讨论为SLAM问题奠定了基本理论框架和讨论基础，但是仍旧存在很多难题。1六、惯性定位是在移动机器人的车轮上装有光电编码器通过对车轮转动的纪录来粗略地确定移动机器人位置。该方法虽然简洁，但是由于车轮与地面存在打滑现象，生的累积误差随路径的增加而增大，导致定位误差的渐渐累积，从而引起更大的差。七、标记定位法是在移动机器人工作的环境里人为地设置一些坐标已知的标记，八、超声波放射器、激光反射板等,通过机器人的传感器系统对标记的探测来确定机器人在全局地图中的位置坐标。三角测量法是标记定位中常用的方法，机器人在同一点探测到三个陆标，并通过三角几何运算，由此可确定机器人在工作环境中的坐标。标记定位是移动机器人定位中普遍采纳的方法，其可获得较高的定位精度且计量小，但是在实际应用中需要对环境作一些改造，添加相应的标记，不太符合真正意义的自主导航。九、GPS定位是采用环绕地球的24颗卫星，精确计算使用者所在位置的浩大卫星网定位系统。GPS定位技术应用已经特别广泛，除了最初的军事领域外，在民用方面也得到了广泛的应用，但是由于在移动导航中，移动GPS接收机定位精度受到卫星信号状况和道路环境的影响，同时还受到时钟误差、传播误差、接收机噪声等诸多因素的影响，因此，单纯采用GPS定位精度比较低、牢靠性不高，所以在机器人的导航应用中通常还辅以磁罗盘、光码盘与GPS数据进行融合，提高导航精度。此外，GPS定位系统也不适用于室内或者水下机器人的导航中以及对于位置精度要求较高的机器人系统。基于环境地图模型匹配定位是指移动机器人通过自身的传感器系统，探测四周环境，采用感知到的局部环境信息和肯定的算法进行局部地图构建，并将建立的局部地图与其内部事先存储的全局地图进行匹配，从而实现定位。这种定位方法常用于移动机器人的全局定位。十、2.2移动机器人的地图构建十一、由于路径规划和很多定位方法都是基于环境地图，所以构建并维护一个环境地图也是自主导航中的一个重要内容。机器人采用对环境的感知信息对现实世界进行建模,自动地构建一个地图。典型的地图表示方法有概率栅格地图、拓扑地图和几何特征地图三种。十二、栅格地图十三、栅格地图是在机器人系统中得到广泛应用的一种地图描述方法。首先由Elfes十四、和Moravec依据"occuPancygridmaPPing''算法提出的，在机器人的路径规划、导航、避障掌握、位姿估量中均得到了广泛应用，并成为一种通用的移动机器人地图描述方法。栅格地图是一种表示静态环境的方法，用每一个栅格被占据的概率值来表示环境信息，栅格地图很简洁创建和维护，即使使用精确度不高的声纳传感器也可以创建栅格地图来表示环境信息，但是栅格地图最大的缺点就是精确度不高，信息存储量高。在环境规模比较大或者对环境划分比较具体的状况下，栅格地图的维护所占用的内存和CPU资源快速增长，使得计算机的实时处理变得很困难。十五、拓扑地图十六、拓扑地图由Brooks;Mataric等学者提出110—川。在表示环境地图时，它并没有一个明显的尺度概念，而是选用一些特定的地点来描述环境信息。拓扑地图通常表示为一个图表，图中的节点表示一个特定地点，连接节点的弧用来表示特定地点之间的路径信息。拓扑地图对于结构化的环境是一个很有效的表示方法，这里有更多的特定地点。相反，在非结构化环境中，地点的识别将变得特别简单。假如仅仅以拓扑信息进行机器人定位，机器人将很快迷失方向和位置。此外，为了更好地表示环境模型，消失了混合拓扑和尺度地图的表示方法，通过加入尺度信息来补偿拓扑信息。这样的地图表示方法具有拓扑地图的高效性，尺度地图的全都性和精确性。十七、几何特征地图十八、几何特征地图由一组环境特征组成，每一个路标特征用一个几何原型来近似。这种地图只局限于表示可参数化的环境路标特征或者可建模的对象，如点、线、面。由于以几何位置关系来表示环境地图，所以为了保证地图的全都性，要求各观测位置是相对精确的。对于结构化的办公室环境，用一些几何模型来表示环境空间是可行的。用线段来拟合室内的墙面，用点来拟合墙角、桌子角等。对于室外道路环境，可以用点特征来表示道路两侧的大树位置。几何特征地图中特征的提取需要对感知信息做额外的处理，且需要大量的感知数据才能得到结果。十九、移动机器人路径规划技术二十、不论采纳何种导航方式，智能移动机器人主要完成路径规划、定位和避障等任务。路径规划是自主式移动机器人导航的基本环节之一。它是依据某一性能指标搜寻一条从起始状态到目标状态的最优或近似最优的无障路径。依据机器人对环境信息把握的程度不同，可分为两种类型:环境信息完全可知的全局路径规划和环境信息完全未知或部分未知，通过传感器在线地对机器人的工作环境进行探测，以猎取障碍物的位置、外形和尺寸等信息的局部路径规划。二十一、全局路径规划二十二、全局路径规划的主要方法有:可视图法、栅格法今和拓扑法等。所谓图，就是用弧连接节点的数据结构，节点代表机器人的位置，弧代表移动机器人在两个位置间的移动线路。可视图法将机器人、目标点和多边形障碍物的各顶点视为节点。并将机器人、目标点和多边形障碍物的各顶点进行组合连接，连接的直线视为弧，机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是可视的。因此，可视图法可将最优路径搜寻问题转化为在这些直线中搜寻从起始点到目标点的最短距离问题是全局路径规划中一种经典的方法。其常用的有Thngeni图法和Voronoi图法。可视图法虽然给简单的路径规划问题提出了一种可行的方法，但本身也存在其敏捷性和实时性不高的问题。由于传统的丁hngeni图法要求移动物体沿着障碍物的边缘移动，所以当物体可以旋转时，最短路径特别简洁受到物体模型的影响而不精确。而voronoi图法可有效的解决Thngeni图法在三维空间中的缺陷。几ngeni图，二十三、如图1.1所示，用障碍物的切线表示弧，因此是从起始点到目标点的最短路径的图。二十四、图1.2用完可能远离障碍物和墙壁的路径表示弧。因此从起始节点到目标节点的路径将会增长，但可以有效的提高机器人移动过程中的平安系数。此外，假如环境中障碍物过多，可视图法的简单性快速增加，为了提高系统的实时性，可以采纳优化算法删除一些不必要的连线，如DynamicVisibihtyGr即h方法和T-Veetors方法等。栅格法是移动机器人以构建好的全局栅格地图做为先验信息，依据肯定的约束算法而规划出一条从起始点到目标点的最优路径。由于该方法是基于栅格地图的，因此路径规划的实时性和精确性往往受到栅格地图的制约。若栅格过小，辨别率虽高，但抗干扰性差，由于存储的信息量大，处理时间长而导致实时性较差;栅格越大，其抗干扰性越强，实时性好，但存在辨别率低，路径规划不精确的缺点。所以如何选择合适的栅格，保证路径规划的实时性和精确性是其讨论的主要问题。拓扑法是基于拓扑地图实现路径规划的一种方法。拓扑法基本思想是降维法，即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。优点在于采用拓扑特征大大缩小了搜寻空间。算法简单性仅依靠于障碍物数目，理论上是完备的。缺点是建立拓扑网络的过程相当简单，特殊在增加障碍物时如何有效地修正己经存在的拓扑网是有待解决的问题。二十五、局部路径规划技术局部路径规划的主要方法有:人工势场法、模糊规律算法、遗传算法等。人工势场法是由肠atib提出的一种虚拟力法其基本思想是建立一种虚拟力，将机器人在未知环境中的运动视为在人工虚拟力场中的运动，即目标对被规划对象存在吸引力，而障碍物对其有排斥力，引力与斥力的合力作为机器人运动的加速力，从而计算机器人的位置和掌握机器人的运动方向。势场法结构简洁，便于低层的实时掌握。但它存在陷阱区域以及在相近的障碍物群中不能识别路径等缺点。模糊规律算法是通过对驾驶员的工作过程观看讨论得出的。驾驶员的避碰动作并不是对环境信息的精确计算来完成的，而是依据比较模糊的环境信息，靠阅历来决策实行什么样的操作。模糊规律算法基于实时传感器的信息，参考人的驾驶阅历，通过查表得到规划出的信息，完成局部路径规划。该法克服了势场法易产生局部微小的问题。而且计算量小，易做到边规划边跟踪，适用于时变未知环境下的路径规划，实时性较好。二十六、遗传算法是Holfand教授于1962年首先提出的。遗传算法是一种基于自然选二十七、择和基因遗传学原理的搜寻算法。遗传算法借鉴物种进化的思想，将欲求解的问题进行编码，每一个可能解均被表示成字符串的形式，初始化随机产生一个种群的候选群，种群规模固定为N,用合理的适应度函数对种群进行性能评估，并在此基础上进行繁殖、交叉和变异遗传操作。适应度函数类似于自然选择的某种力气，繁殖、交叉和变异这三个遗传算子则分别模拟了自然界生物的繁衍、交配和基因突变。多数优化算法都是单点搜寻算法，很简洁陷入局部最优，而遗传算法却是一种多点搜寻算法，因而更有可能搜寻到全局最优解。在简单环境下，遗传算法也存在导致进化缓慢、易产生非法个体及进化效率不高的问题。对于移动机器人而言，导航力量是其最重要的功能之一，机器人首先要求避开危急状况如碰撞等，将机器人停留于平安的操作环境下;其次需具备完成到环境中某一特定位置执行特定任务的力量。通常移动机器人导航问题可总结为"在哪里?"、"去哪里?"、"怎么去?"三个问题。为解决上述三个问题，通常涉及以下三方面讨论:①地图创建和地图识别解释，即用有效表示模型，将移动机器人环境遍历过程中猎取的环境信息储存记忆;②自定位(self-focalization),确定移动机器人在地图中当前位置信息;③路径规划(PathPlanning)，给定当前位置和目标信息，选择最优运动掌握序列驱动机器人到达目标位置。地图表示模型和地图创建机器人地图可以分为两大类:几何地图和拓扑地图。几何地图又可分为栅格地图和特征地图。栅格地图将空间环境地图划分为若干规章方格，依据传感器猎取的环境信息，采纳有效的传感器几何模型确定当前栅格区域是否被占用。由于测距传感器几何模型不精确问题和环境的干扰影响，人们先后提出了基于声纳和激光信息融合的栅格概率计算模型、MuRIE栅格模型、基于反馈神经网络模型的栅格概率计算方法、改进型模糊自调整栅格地图模型、前向传感器模型，削减传感器存在的镜面反射、测量数据冗余、随机性误差等影响。Ribo.M等分析了Bayesian概率模型、D—S证据理论、模糊集三种栅格地图更新模型的优缺点。特征地图由一系列包含位置信息的特征组成【，刀。特征地图创建主要包括特征检测、特征匹配和更新三个方面。特征的选择特别广泛，多面体、平面体、直线、角点、目标边缘等均可作为地图特征，如Ayache等采纳三目立体摄像机猎取环境中的直线段信息，Leonard等提出Ren模型提取固定特征，Ipv.Lip等采纳EAFc算法从原始声纳测量数据中提取线段特征，Tardos等用Hough变换实现特征的提取。多传感器融合是提高特征检测力量的重要手段，Castellanos等对激光和摄像机数据在特征级进行融合;wijk等用三角融合测量方法TBF提取点目标口］,choset等［551提出ATM模型实现点特征的精确提取。特征地图的匹配和更新模型常见的有kalman模型、粒子滤波器等，详见论文第六章。二十八、拓扑地图由环境中特征位置或区域组成的节点及其连接关系组成[']。拓扑地二十九、图节点的定义和识别是首要问题，它可以由操作人员直接定义或由机器人系统自动生成。第一种定义方法是人为预定节点标志，通常选择走廊、门、墙和角点等来完成空间环境的定义。其次是特定位置法，即依据特定位置的环境信息定义节点。KuiPers等通过采纳爬山法查找局部唯一特征点，采用外部传感器感知的环境信息定义节点。Kortenkamp等提出用入口(gateway)作为节点标志等。第三种节点定义为，传感器测量值相像的区域，如Nehmzow等直接依据栅格直方图信息进行节点定义f64—66],Ulrich等基于图像信息进行节点识别和定义。拓扑地图中节点之间的关系可以分为:①邻接关系,即可从一个节点直接到另一节点163,67];②相对几何关系，即依据机器人内部传感器如里程计和方向盘信息，确定节点之间的相对几何位置。③肯定位置关系，即每个节点被指定全局位置坐标。④隐含连接，节点之间的关系由包含有通用路标的节点推想获得。依据连接关系信息，移动机器人可从一个节点区域运动到另一节点区域，从而更有利于高级任务处理如导航和规划等。拓扑地图的创建有两种方式，一种是直接依据传感器信息和机器人运动模型创建，另一种是从几何地图(特殊是栅格地图)提取节点和连接关系，如常见的广义voronoi图法和四叉树法(2)自定位(self-loealization)GPS全球定位系统有效解决了"我在哪里"的问题，然而该定位系统对于室内机器人或者微型机器人而言，其定位精度难以达到要求，而且GPS系统在室内或者障碍物密集区域也受到很大限制，因此需要讨论其他的定位方案。定位问题有3种形式:①局部跟踪:假如机器人的初始姿势已知，则定位就一个跟踪问题，跟踪问题可以通过有界的不确定性加以描述;②全局定位，其中机器人初始位置完全未知，必需在全局不确定条件下进行机器人定位;③绑架问题，即机器人在运动操作过程中，被人为搬运至任意位置区域下的定位问题，该种状况通常用于测试极端条件下定位方法的鲁棒性。目前，常用的定位方法有基于Kalman滤波器的跟踪定位模型、Markov概率定位模型、基于粒子滤波器的蒙特卡罗定位模型等。卡尔曼滤波器是定位定位算法中最主要手段之一，它用高斯分布表示后验概率。为解打算位过程中测量模型的非线性问题，人们提出了扩展Kalman模型。当机器人移动时，位置估量