搜索
智能移动机器人路径规划优化方法研究一引言(Introduction移动机器人面对复杂的道路环境时,需要进行路径识别与决策。如何快速完成对复杂环境的分析,并作出正确决策,是移动机器人程序设计中的一个重要环节。机器人路径规划问题,可分为环境参数可知的路径规划和环境参数未知的路径规划。环境可知的路径规划即路径寻优问题,能实现快速避障以及全局路径最短等目的错误!未找到引用源。,全局路径规划方法采用可视图法、图搜索法、人工势场法等[1].环境未知的路径规划主要通过安装在机器人身上的众多传感器,利用传感器融合技术采集环境参数,对机器人的行动进行判断。人工神经网络的发展以及支持向量机的兴起,使得对环境参数的判断成为了系统辨识理论新的研究对象。环境可知的路径规划研究中,以往的研究方法集中在路径搜索问题上,如文献[2]研究的改进型遗传算法,文献[3]所提出的神经网络快速优化算法,都旨在从理论本身上消除或者减小该理论所带来的缺陷,从而保证算法的实现。达到优化机器人路径的优化,研究相对合理的优化方案。二选题背景及意义智能移动机器人(也称自引导车,英文简写为ALV或AGV,后面简称移动机器人是指室内、道路或室外环境中无需人工干预,可以自主完成行驶任务的车辆。移动机器人是机器人学中的一个重要分支,它集人工智能、智能控制信息处理、图像处理、监测与转换等专业技术为一体,跨计算机、自动控制、机械、电子等多学科,成为当前智能机器人研究的热点之一。移动机器人是生的计算机控制领域中的最年轻一代,并在1985年后成为此领域中的主角被广泛应用于社会生活的各方各面。移动机器人在移动过程中不可避免会遇到各式各样的障碍物,灵活、实时的躲开这些障碍物是衡量其性能的关键指标。具有避障功能的移动机器人拥有相当高的社会价值,被大量应用于航天、军事、制造业、医疗/交通等。路径规划技术是移动机器人领域中的核心问题之一,也是机器人学中研究人工智能问题的一个重要方面。我们希望未来的机器人能具有感知、规划和控制等高层能力。他们能从周围的环境中收集知识,构造一个关于环境的符号化的世界模型,并且利用这些模型来规划、执行由应用者下达的高层任务。其中的规划模块能生成大部分机器人要执行的命令,其目标是实现机器人的使用者在较高层次上给机器人下达一些较宏观的任务,由机器人系统自身来填充那些较低层的细节三复杂路径规划优化方法分析在对机器人路径规划研究过程中,笔者发现对于不同的路径规划,会得到相同的优化效果。规划路径的多点重合、多周迂回、部分路段重合等因素,增加了规划路径的复杂度,使通过神经网络或n次多项式拟合得到的全局优化结果很难接近真实值,甚至出现拟合曲线回归原点等崩溃现象。如何防止这些现象的发生,除了引言部分提到的,将智能算法与其他理论结合以外,还可以根据路径的特点,选择适当的坐标原点并做合理的坐标变换,让很难处理的复杂路径变得容易处理,这样,可以简化路径规划中得算法优化问题,从而降低了理论模型的计算量。四路径规划概述移动机器人路径规划是实现机器人智能的一个关键技术,移动机器人路径规划中设计的四个相关问题(1机器人如何从环境中获取周围的障碍物信息和其它相关信息;(2机器人如何根据内部及外部传感器来确定当前处于地图中什么位置;(3机器人如何根据其处于当前地图的位置和当前地图中信息确定行动略;(4如何产生合适的驱动信号使机器人运动在预定的轨迹上。为了解决这些问题,要对相应的四个技术进行研究:传感技术:智能机器人的传感器分为内部传感器和外部传感器,内部传感器提供的信息对机器人的自定位是非常必要的。外部传感器用以检测外部环境的信息,是建立环境的全局地图和得到用以局部避障的机器人附近障碍信息的依据。自定位技术:,由于智能机器人得到的传感信息是相当于机器人的局部坐标系的,而用于路径规划的地图才用全局坐标系。如果没有机器人的当前位置信息,也就没有局部坐标系在地图坐标系中的位置,从而无法进行运动的规划。运动控制:涉及机器人的结构、运动学和动力学性质。规划和决策:规划部分是智能机器人的智能部分,分为任务规划和运动规划,运动规划又分为路径规划和轨迹规划。移动机器人路径规划是实现机器人智能的一个关键技术,移动机器人路径规划中涉及的四个相关问题“”:(1机器人如何从环境中获取周围的障碍物信息和其它相关信息;(2机器人如何根据内部及外部传感器来确定当前处于地图中什么位置;(3机器人如何根据其处于当前地图的位置和当前地图中信息确定行动策略;(4如何产生合适的驱动信号使机器人运动在预定的轨迹上。五本文的主要研究内容本课题的核心任务就是对移动机器人路径规划问题的研究,研究的目的是利用计算机和通讯技术,向行驶在道路上的机器人提供信息,引导机器人避开障碍物,沿着最佳的路线到达目的地,即在路段交通状态实时动态变化的前提下,为机器人提供一条最优或者近似最优的路径解决方案。研究的意义就是利用蚁群算法来有效地解决移动机器人的路径规划问题,并在计算机仿真中得到比较满意的结果。目前蚁群算法的严格理论基础尚未奠定,国内外的相关研究还处于实验探索和初步应用阶段。蚁群算法在机器人路径规划中的研究还不是很多,尤其是将其应用于动态规划中更不多见。因此,本文首先提出了静态环境下基于蚁群算法的路径规划方法,考虑到移动机器人行驶过程中的实际路面情况,在静态路径规划方法的基础上提出了基于蚁群算法解决动态路径规划的方法,并在仿真实验中证实了该算法的可行性和实用性。六路径规划方法路径规划是移动机器人导航技术中不可缺少的重要组成部分,它要求机器人根据给予的指令及环境信息自主地决定路径,避开障碍物,按照某种优化指标,使系统在规定的时间内从起始点转移到目标点。机器人路径规划方法大致可以分为两类:传统方法和智能方法。1.传统路径规划方法(1自由空间法。为了简化问题,通常采用结构空间来描述机器人及其周围的环境。这种方法将机器人缩小成点,将其周围的障碍物及边界按比例相应地扩大,使机器人点能够在自由空间中移动到任意一点,而不与障碍物及边界发生碰撞。(2图搜索法。图搜索方法中的路径图由捕捉到的存在于机器人一维网络曲线(称为路径图自由空间中的节点组成。建立起来的路径图可以看作是一系列的标准路径。而路径的初始状态和目标状态同路径图中的点相对应,这样路径规划问题就演变为在这些点间搜索路径的问题。通过起始点和目标点及障碍物的顶点在内的一系列点来构造可视图。连接这些点,使某点与其周围的某可视点相连(即使相连接的两点间不存在障碍物或边界。然后机器人沿着这些点在图中搜索最优路径。(3栅格解耦法。栅格解耦法是目前研究最广泛的路径规划方法。该方法将机器人的工作空间解耦为多个简单的区域,一般称为栅格。由这些栅格构成了一个连通图,在这个连通图上搜索一条从起始栅格到目标栅格的路径,这条路径是用栅格的序号来表示的。栅格解耦法包括确切的和不确切的两种。确切的解耦法用来描述整个自由空间,这将使复杂环境的解耦速度变慢,其原因是许多复杂的多边形可能需要与障碍物的边界相匹配。这种方法可以保证只要起始点到目标点之间存在路径,就完全能搜索到这条路径,在不确切的解耦法中,所有的栅格都是预定的形状,为了研究方便假设全部为矩形。整个图被分割成多个较大的矩形,每个矩形之间都是连续的。如果大矩形内部包含障碍物或者边界,则又被分割成4个小矩形,对所有较大的栅格都进行这种划分,然后在划分的最后界限内形成的小栅格间重复执行程序,直到达到解的界限为止一条路径,如果该路径满足起点到目标点间无障碍物的要求则停止搜索。不确切的解耦方法比确切的解耦方法在数学计算上要简单的多,因此也比较容易实现。(4人工势场法。传统的人工势场法把移动机器人在环境中的运动视为一种在抽象的人造受力场中的运动,目标点对移动机器人产生“引力”,障碍物对移动机器人产生“斥力”,最后通过求合力来控制移动机器人的运动,但是,由于势场法把所有信息压缩为单个合力,这样就存在把有关障碍物分布的有价值的信息抛弃的缺陷,容易陷入局部最小值。大部分机器人路径规划中的全局规划都是基于上述几种方法进行的,但是以上这些传统方法在路径搜索效率及路径优化方面尚有待于进一步改善。而现在通常使用的搜索技术包括:梯度法、A+等图搜索方法、枚举法、随机搜索法等。这些方法中梯度法易陷入局部最小点,图搜索方法、枚举法不能用于高维的优化问题,而随机搜索法则计算效率太低。2智能路径规划方法近年来,随着遗传算法等智能方法的广泛应用,机器人路径规划方法也有了长足的进展,许多研究者把目光放在了基于智能方法的路径规划研究上。其中,应用较多的算法主要有模糊方法、神经网络和遗传算法。(1基于模糊逻辑的机器人路径规划模糊逻辑方法是在线规划中通常采用的一种规划方法,该方法根据不完整、模糊的环境信息,参考人的驾驶经验并利用模糊数学的理论,设计决策方案,以采取相应的操作。因此模糊控制算法的核心部分在于模糊决策表的建立。庄晓东等n”提出一种基于模糊概念的动态环境模型,参照物体的位置和运动信息构造二维隶属度函数:然后通过模糊综合评价对各个方向进行综合考察,得到搜索结果。该方法在移动障碍物和移动目标的环境中能有效地实现机器人避碰和导航。李彩虹等提出了一种在未知环境下移动机器人的模糊控制算法,并对此算法进行了推导与仿真,证明该算法鲁棒性强,可消除传统算法中存在的对移动机器人的定位精度敏感、对环境信息依赖性强等缺点,使移动机器人的行为表现出很好的一致性、连续性和稳定性。HartmutSurmann等提出一种未知环境下的高级机器人模糊导航方法,由8个不同的超声传感器来提供环境信息,然后利用基于模糊控制的导航器来计算这些信息,规划机器人路径。该方法在环境未知或发生变化的情况下能够快速而准确地规划机器人路径,对于要求有较少路径规划时间的机器人是一种很好的导航方法。但是其缺点是没有学习和自适应能力。它要求设计者能定义一系列有效的避障控制规则,但事实上环境非常复杂,突发事件也非常多,设计者不可能把所有的行为表示出来,且当障碍物数目增加时该方法的计算量会很大,影响规划结果。(2基于神经网络方法的机器人路径规划禹建丽等n”提出了一种基于神经网络的机器人路径规划算法,研究了在障碍物形状和位置已知情况下的机器人路径规划算法,其能量函数的定义利用了神经网络结构,根据路径点位于障碍物内外的不同位置选取不同的动态运动方程,规划出的路径达到了折线形的最短无碰路径,计算简单,收敛速度快。陈宗海等nm提出了一种在不确定环境中移动机器人的路径规划方法,将全局路径规划分解为局部路径规划的组合,为了提高规划的效率,在避障规划中采用了基于案例的学习方法,以ART-2神经网络实现案例的匹配学习和扩充,满足了规划的实时性要求。为了提高机器人路径规划的速度,禹建丽等在利用神经网络路径规划方法的基础上,又引进了线性再励的自适应变步长算法。这种方法实现了步长的自适应选择,使路径规划速度比原来的神经网络规划提高了10倍。但是神经网络也存在一些缺点,神经网络中的映射规则在网络中是隐含而无法直接理解的,因此想从神经网络内部去调整它的权值参数进而改进性能具有一定的难度。(3基于遗传算法的机器人路径规划遗传算法是目前机器人路径规划研究中应用较多的一种方法,无论是单机器人静态工作空间,还是多机器人动态工作空间,遗传算法及其派生算法都取得了良好的路径规划结果。孙树栋等“”用遗传算法完成了离散空间下机器人的路径规划,并获得了较好的仿真结果。但是,该路径规划是基于确定环境模型的,即工作空间中的障碍物位置是己知的、确定的。KazuoSugihara和JohnSmith在采用离散空间进行路径规划的同时,将问题更深入化,栅格序号采用二进制编码,统一确定其个体长度随机产生障碍物位置及数目,并在搜索到最优路径后,再在环境空间中随机插入障碍物,模拟环境变化,通过仿真结果验证了算法的有效性和可行性。但是,规划空间栅格法建模还存在缺陷,若栅格划分过粗,则规划精度较低:若栅格划分太细,则数据又会太大。周明等“”提出一种连续空间下基于遗传算法的机器人路径规划方法,该方法在规划空间利用链接图建模的基础上,先使用图论中成