移动机器人的自主导航控制一、研究的背景移动机器人是一个集环境感知、动态决策与规划、行为控制与执行等多功能于一体的综合系统。
它集中了传感器技术、计算机技术、机械工程、电子工程、自动化控制工程以及人工智能等多学科的研究成果,是目前科学技术发展最活跃的领域之一。
随着机器人性能不断地完善,移动机器人的应用范围大为扩展,不仅在工业、农业、国防、医疗、服务等行业中得到广泛的应用,而且在排雷、搜捕、救援、辐射和空间领域等有害与危险场合都得到很好的应用。
因此,移动机器人技术已经得到世界各国的普遍关注。
在自主式移动机器人相关技术的研究中,导航技术是其研究核心,同时也是移动机器人实现智能化及完全自主的关键技术。
导航是指移动机器人通过传感器感知环境信息和自身状态,实现在有障碍的环境中面向目标的自主运动。
导航主要解决以下三方面的问题:(l)通过移动机器人的传感器系统获取环境信息;(2)用一定的算法对所获信息进行处理并构建环境地图;(3)根据地图实现移动机器人的路径规划及运动控制。
二、相关技术移动机器人定位是指确定机器人在工作环境中相对于全局坐标的位置,是移动机器人导航的基本环节。
定位方法根据机器人工作环境的复杂性、配备传感器种类和数量等方面的不同而采用多种方法。
主要方法有惯性定位、标记定位、GPS定位、基于地图的定位等,它们都不同程度地适用于各种不同的环境,括室内和室外环境,结构化环境与非结构化环境。
惯性定位是在移动机器人的车轮上装有光电编码器,通过对车轮转动的记录来粗略地确定移动机器人位置。
该方法虽然简单,但是由于车轮与地面存在打滑现象,生的累积误差随路径的增加而增大,导致定位误差的逐渐累积,从而引起更大的差。
标记定位法是在移动机器人工作的环境里人为地设置一些坐标已知的标记,超声波发射器、激光反射板等,通过机器人的传感器系统对标记的探测来确定机器人在全局地图中的位置坐标。
三角测量法是标记定位中常用的方法,机器人在同一点探测到三个陆标,并通过三角几何运算,由此可确定机器人在工作环境中的坐标。
标记定位是移动机器人定位中普遍采用的方法,其可获得较高的定位精度且计量小,但是在实际应用中需要对环境作一些改造,添加相应的标记,不太符合真正意义的自主导航。
GPS定位是利用环绕地球的24颗卫星,准确计算使用者所在位置的庞大卫星网定位系统。
GPS定位技术应用已经非常广泛,除了最初的军事领域外,在民用方面也得到了广泛的应用,但是因为在移动导航中,移动GPS接收机定位精度受到卫星信号状况和道路环境的影响,同时还受到时钟误差、传播误差、接收机噪声等诸多因素的影响,因此,单纯利用GPS定位精度比较低、可靠性不高,所以在机器人的导航应用中通常还辅以磁罗盘、光码盘与GPS数据进行融合,提高导航精度。
另外,GPS定位系统也不适用于室内或者水下机器人的导航中以及对于位置精度要求较高的机器人系统。
基于环境地图模型匹配定位是指移动机器人通过自身的传感器系统,探测周围环境,利用感知到的局部环境信息和一定的算法进行局部地图构建,并将建立的局部地图与其内部事先存储的全局地图进行匹配,从而实现定位。
这种定位方法常用于移动机器人的全局定位。
2.2移动机器人的地图构建由于路径规划和许多定位方法都是基于环境地图,所以构建并维护一个环境地图也是自主导航中的一个重要内容。
机器人利用对环境的感知信息对现实世界进行建模,自动地构建一个地图。
典型的地图表示方法有概率栅格地图、拓扑地图和几何特征地图三种。
2.2.1栅格地图栅格地图是在机器人系统中得到广泛应用的一种地图描述方法。
首先由Elfes 和Moravec依据“occuPancygridmaPPing’’算法提出的18一9],在机器人的路径规划、导航、避障控制、位姿估计中均得到了广泛应用,并成为一种通用的移动机器人地图描述方法。
栅格地图是一种表示静态环境的方法,用每一个栅格被占据的概率值来表示环境信息,栅格地图很容易创建和维护,即使使用精确度不高的声纳传感器也可以创建栅格地图来表示环境信息,但是栅格地图最大的缺点就是精确度不高,信息存储量高。
在环境规模比较大或者对环境划分比较详细的情况下,栅格地图的维护所占用的内存和CPU资源迅速增长,使得计算机的实时处理变得很困难。
2.2.2拓扑地图拓扑地图由Brooks,Mataric等学者提出110一川。
在表示环境地图时,它并没有一个明显的尺度概念,而是选用一些特定的地点来描述环境信息。
拓扑地图通常表示为一个图表,图中的节点表示一个特定地点,连接节点的弧用来表示特定地点之间的路径信息。
拓扑地图对于结构化的环境是一个很有效的表示方法,这里有更多的特定地点。
相反,在非结构化环境中,地点的识别将变得非常复杂。
如果仅仅以拓扑信息进行机器人定位,机器人将很快迷失方向和位置。
另外,为了更好地表示环境模型,出现了混合拓扑和尺度地图的表示方法,通过加入尺度信息来补偿拓扑信息。
这样的地图表示方法具有拓扑地图的高效性,尺度地图的一致性和精确性。
2.2.3几何特征地图几何特征地图【’2]由一组环境特征组成,每一个路标特征用一个几何原型来近似。
这种地图只局限于表示可参数化的环境路标特征或者可建模的对象,如点、线、面。
由于以几何位置关系来表示环境地图,所以为了保证地图的一致性,要求各观测位置是相对精确的。
对于结构化的办公室环境,用一些几何模型来表示环境空间是可行的。
用线段来拟合室内的墙面,用点来拟合墙角、桌子角等。
对于室外道路环境,可以用点特征来表示道路两侧的大树位置。
几何特征地图中特征的提取需要对感知信息做额外的处理,且需要大量的感知数据才能得到结果。
1.2.3移动机器人路径规划技术不论采用何种导航方式,智能移动机器人主要完成路径规划、定位和避障等任务。
路径规划是自主式移动机器人导航的基本环节之一。
它是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无障路径。
根据机器人对环境信息掌握的程度不同,可分为两种类型:环境信息完全可知的全局路径规划和环境信息完全未知或部分未知,通过传感器在线地对机器人的工作环境进行探测,以获取障碍物的位置、形状和尺寸等信息的局部路径规划。
2.3.1全局路径规划全局路径规划的主要方法有:可视图法【’3一’4]、栅格法11今’5]和拓扑法[l“]等。
所谓图,就是用弧连接节点的数据结构,节点代表机器人的位置,弧代表移动机器人在两个位置间的移动线路。
可视图法将机器人、目标点和多边形障碍物的各顶点视为节点。
并将机器人、目标点和多边形障碍物的各顶点进行组合连接,连接的直线视为弧,机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是可视的。
因此,可视图法可将最优路径搜索问题转化为在这些直线中搜索从起始点到目标点的最短距离问题,是全局路径规划中一种经典的方法。
其常用的有Thngeni图法和Voronoi图法。
可视图法虽然给复杂的路径规划问题提出了一种可行的方法,但本身也存在其灵活性和实时性不高的问题。
由于传统的丁hngeni图法要求移动物体沿着障碍物的边缘移动,所以当物体可以旋转时,最短路径非常容易受到物体模型的影响而不精确。
而voronoi图法可有效的解决Thngeni图法在三维空间中的缺陷。
几ngeni 图,如图1.1所示,用障碍物的切线表示弧,因此是从起始点到目标点的最短路径的图。
图1.2用尽可能远离障碍物和墙壁的路径表示弧。
因此从起始节点到目标节点的路径将会增长,但可以有效的提高机器人移动过程中的安全系数。
此外,如果环境中障碍物过多,可视图法的复杂性迅速增加,为了提高系统的实时性,可以采用优化算法删除一些不必要的连线,如DynamicVisibihtyGr即h方法和T-Veetors[”一’8]方法等。
栅格法是移动机器人以构建好的全局栅格地图做为先验信息,按照一定的约束算法而规划出一条从起始点到目标点的最优路径。
由于该方法是基于栅格地图的,因此路径规划的实时性和精确性往往受到栅格地图的制约。
若栅格过小,分辨率虽高,但抗干扰性差,由于存储的信息量大,处理时间长而导致实时性较差;栅格越大,其抗干扰性越强,实时性好,但存在分辨率低,路径规划不精确的缺点。
所以如何选择合适的栅格,保证路径规划的实时性和准确性是其研究的主要问题。
拓扑法是基于拓扑地图实现路径规划的一种方法。
拓扑法基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。
优点在于利用拓扑特征大大缩小了搜索空间。
算法复杂性仅依赖于障碍物数目,理论上是完备的。
缺点是建立拓扑网络的过程相当复杂,特别在增加障碍物时如何有效地修正己经存在的拓扑网是有待解决的问题。
2.3.2局部路径规划技术局部路径规划的主要方法有:人工势场法11”l、模糊逻辑算法120一2’]、遗传算法[22一24]等。
人工势场法是由肠atib提出的一种虚拟力法,其基本思想是建立一种虚拟力,将机器人在未知环境中的运动视为在人工虚拟力场中的运动,即目标对被规划对象存在吸引力,而障碍物对其有排斥力,引力与斥力的合力作为机器人运动的加速力,从而计算机器人的位置和控制机器人的运动方向。
势场法结构简单,便于低层的实时控制。
但它存在陷阱区域以及在相近的障碍物群中不能识别路径等缺点。
模糊逻辑算法是通过对驾驶员的工作过程观察研究得出的。
驾驶员的避碰动作并不是对环境信息的精确计算来完成的,而是根据比较模糊的环境信息,靠经验来决策采取什么样的操作。
模糊逻辑算法基于实时传感器的信息,参考人的驾驶经验,通过查表得到规划出的信息,完成局部路径规划。
该法克服了势场法易产生局部极小的问题。
而且计算量小,易做到边规划边跟踪,适用于时变未知环境下的路径规划,实时性较好。
遗传算法是Holfand教授于1962年首先提出的。
遗传算法是一种基于自然选择和基因遗传学原理的搜索算法。
遗传算法借鉴物种进化的思想,将欲求解的问题进行编码,每一个可能解均被表示成字符串的形式,初始化随机产生一个种群的候选群,种群规模固定为N,用合理的适应度函数对种群进行性能评估,并在此基础上进行繁殖、交叉和变异遗传操作。
适应度函数类似于自然选择的某种力量,繁殖、交叉和变异这三个遗传算子则分别模拟了自然界生物的繁衍、交配和基因突变。
多数优化算法都是单点搜索算法,很容易陷入局部最优,而遗传算法却是一种多点搜索算法,因而更有可能搜索到全局最优解。
在复杂环境下,遗传算法也存在导致进化缓慢、易产生非法个体及进化效率不高的问题。
对于移动机器人而言,导航能力是其最重要的功能之一,机器人首先要求避免危险情况如碰撞等,将机器人停留于安全的操作环境下;其次需具备完成到环境中某一特定位置执行特定任务的能力。
通常移动机器人导航问题可总结为“在哪里?”、“去哪里?”、“怎么去?”三个问题。