科学网 › 标签 › 移动机器人

标签: 移动机器人

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

移动传感器（移动机器人）路径规划方法总结（二）: zswm27 2011-7-4 14:32; 根据对环境信息掌握的程度将其分为 2 种：基于环境先验完全信息的全局路径规划，又称静态或离线规划；基于传感器信息的局部路径规划，又称动态或在线路径规划。二. 局部路径规划 1. 传统方法 1). 人工势场法人工势场法是 Khatib 提出的一种虚拟力法。其基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力，目标点产生引力，引力和斥力周围由一定的算法产生相应的势，机器人在势场中受到抽象力作用，抽象力使得机器人绕过障碍物。该法结构简单，便于低层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广泛应用，其不足在于存在局部最优解，容易产生死锁现象，因而可能使移动机器人在到达目标点之前就停留在局部最优点。主要的缺陷： 1) 陷阱区域 2) 在相近的障碍物之间不能发现路径。 3) 在障碍物前振荡。 4) 在狭窄通道中摆动。针对这些缺陷，提出了一些改进办法。针对人工势场法存在“机器人在到达目标位置前由于陷入局部极小点而无法到达目标位置”的问题，解决的方法有：重新定义势函数，使之没有或有更少的局部极小点；利用搜索算法跳出局部极小点。还可以利用模拟退火算法使势函数跳出局部极小点，到达机器人的目标位置。 2). 模糊逻辑算法模糊逻辑算法基于对驾驶员的工作过程观察研究得出。驾驶员避碰动作并非对环境信息精确计算完成的，而是根据模糊的环境信息，通过查表得到规划出的信息，完成局部路径规划。优点是克服了势场法易产生的局部极小问题，对处理未知环境下的规划问题显示出很大优越性，对于解决用通常的定量方法来说是很复杂的问题或当外界只能提供定性近似的、不确定信息数据时非常有效。假设检测的是障碍物与机器人的距离和障碍物的运动信息，输出机器人速度变化和转角变化。模糊控制算法有诸多优点，但也有固有缺陷：人的经验不一定完备；输入量增多时，推理规则或模糊表会急剧膨胀。由于模糊隶属度函数的设计、模糊控制规则的制定主要靠人的经验和试凑，总结模糊控制规则时比较困难，而且，控制规则一旦确定，在线调整困难，无法很好地适应情况的变化。因此，如何得到最优的隶属度函数、控制规则以及对控制规则进行在线调整是该方法最大的问题。 3). 模拟退火算法模拟退火算法由 Kirkpatrick S 于 1983 年提出，源于物理退火过程。基本思想是利用随机优化问题求解过程与统计力学中热平衡问题的相似性，通过设定初温、初态和降温率控制温度的不断下降，结合概率突跳特性，利用解空间的邻域结构进行随机搜索。模拟退火算法用于路径规划可避免局部极值，但其理论收敛条件过于苛刻，在实际应用中往往无法满足。在有限计算量条件下的收敛性能依赖于自身参数，这使得参数设定成为算法应用过程中的一个关键环节。 2. 智能仿生算法 1). 神经网络法路径规划是感知空间到行为空间的一种映射。映射关系可用不同方法实现，很难用精确数学方程表示，但采用神经网络易于表示。将传感器数据作为网络输入，由人给定相应场合下期望运动方向角增量作为网络输出，由多个选定位姿下的一组数据构成原始样本集，经过剔除重复或冲突样本等加工处理，得到最终样本集。将神经网络和模糊数学结合也可实现移动机器人局部路径规划。先对机器人传感器信息进行模糊处理，总结人的经验形成模糊规则。再把模糊规则作用于样本，对神经网络进行训练。通过学习典型样本，把规则融会贯通，整体体现出一定智能。实际中允许输入值偏离学习样本，只要输入接近一个学习样本的输入模式，则输出也就接近该样本输出模式。该性质使得神经网络可以模仿人脑在丢失部分信息时仍具有对事物正确的辨识力。 2). 遗传算法遗传算法以自然遗传机制和自然选择等生物进化理论为基础，构造了一类随机化搜索算法。利用选择、交叉和变异编制控制机构的计算程序，在某种程度上对生物进化过程作数学方式的模拟。只要求适应度函数为正，不要求可导或连续，同时作为并行算法，其隐并行性适用于全局搜索。多数优化算法都是单点搜索，易于陷入局部最优，而遗传算法却是一种多点搜索算法，故更有可能搜索到全局最优解。遗传算法的整体搜索策略和优化计算不依赖于梯度信息，解决了一些其它优化算法无法解决的问题。遗传算法运算速度不快，进化众多的规划要占据较大存储空间和运算时间，优点是克服了势场法的局部极小值问题，计算量不大，易做到边规划边跟踪，适用于时变未知环境的路径规划，实时性较好。遗传算法运用于移动机器人路径规划的研究近来取得了许多成果，其基本思想：将路径个体表达为路径中一系列中途点，并转换为二进制串。首先初始化路径群体，然后进行遗传操作，如选择、交叉、复制、变异。经过若干代进化以后，停止进化，输出当前最优个体，其过程如以下算法所示。开始随机初始化群体 P(0) 计算群体 P(0) 中个体的适应度 t ： =0 while( 不满足终止准则 )do { 由 P(t) 通过遗传操作形成新的种群 P(t+1) ；计算 P(t+1) 中个体的适应度， t ： =t+1 ； } 3). 蚁群算法蚁群优化算法是由意大利学者 Dorigo 等人在 2O 世纪 9O 年代从蚁群觅食行为受到启发，通过模拟自然界蚂蚁寻径的行为，提出的一种全新的模拟进化算法。蚁群优化算法在并行运行环境 ( 如网格环境 ) 下可以同步寻优，加快了寻优速度。另外，它是一种通用性强的算法，稍加修改便可用于其他优化问题。但计算量较大，搜索时间较长，易于陷入局部最优解。 4). 粒子群算法粒子群算法是由 Kennedy 博士和 Eberhart 博士于 1995 年从鸟类的捕食行为中受到启发提出的一种基于群体的智能随机优化算法。粒子群算法具有收敛速度快、算法简单、容易编程实现和鲁棒性强等特点，但是，粒子群算法也有一些缺陷，一是容易陷入局部极值点，导致得不到全局最优解；二是粒子群算法本身的参数设置，若参数选择不当，会导致寻优过程中粒子的多样性迅速消失，造成算法“早熟收敛”。 3. 启发式搜索方法启发式方法的最初代表是 A* 算法，其新发展是 D* 和 Focussed D* 。这 2 种由 Stentz A 提出的增量式图搜索算法的产生。 D* 算法可以理解为动态的最短路径算法，而 Focussed D* 算法则利用 A* 算法的主要优点即使用启发式估价函数， 2 种方法都能根据机器人在移动中探测到的环境信息快速修正和规划出最优路径，减少了局部规划的时间，对于在线的实时路径规划有很好的效果。此外，还出现了一些基于 A* 的改进算法，它们一般都是通过修改 A* 算法中的估价函数和图搜索方向来实现的，可以较大地提高路径规划的速度，具有一定的复杂环境自适应能力。 4. 基于滚动窗口的算法基于滚动窗口的算法是基于预测控制理论的一种次优方法，其基本思想是依靠机器人实时探测到的局部信息，以滚动的方式进行在线规划。在滚动的每一步，根据探测到的局部信息，用启发式方法生成优化子目标，在当前滚动窗口内进行局部路径规划，然后，实施当前策略，随着滚动窗口的推进，不断取得新的环境信息，从而在滚动中实现优化与反馈的结合。在未知环境下，基于滚动窗口的机器人路径优化算法能够保证安全地避开障碍物，具有计算量小、反应迅速、可操作性强等特点，对动态未知环境有一定的适应性。 5. 基于行为的路径规划算法基于行为的路径规划最具代表性的是 1986 年 Brooks 的包容式体系结构，其基本思想是把移动机器人所要完成的任务分解成一些基本的、简单的行为单元，机器人根据行为的优先级，结合本身的任务综合做出反应。在基于行为的机器人控制系统中，不同的行为要完成不同的目标，多个行为之间往往产生冲突，因此，涉及到行为协调问题。 Tyrrell 等人将行为协调机制的实现方法分为两类：仲裁机制和命令融合机制。仲裁机制在同一时间允许一个行为实施控制，下一时间又转向另一个行为。它能够解决在同一时间由于多重行为而使执行器产生冲突的弊端，该方法具有行为模式简单灵活，实时性、鲁棒性强等优点。但当有多种行为模式时，系统做出正确判断的概率会降低。而命令融合机制允许多个行为都对机器人的最终控制产生作用，这种机制适用于解决典型的多行为问题。该机制在环境未知或发生变化的情况下，能够快速、准确地规划机器人路径。但当障碍物数目增加时，该方法的计算量会增大，影响规划结果。 6. 基于再励学习的路径规划算法基于再励学习的路径规划算法是一种未知环境下的实时规划方法。它来源于行为心理学，其基本思想是采用了动物学习心理的“试错法”原理，强调在与环境的交互中利用评价性反馈信号进行学习，为实现具有自学习能力的智能系统提供了有效手段。由于再励学习通过与环境的直接交互进行学习，不需要环境模型和先验知识，也不需要样本训练数据，而且，能够方便地在线实现，因此，比较适用于未知环境模型的不确定系统。 7. 多传感器信息融合移动机器人在动态环境中进行路径规划所需的信息都是从传感器获得，单一传感器难以保证输入信息的准确性与可靠性，多传感器所获得的信息具有冗余性、互补性、实时性和低代价性，且可快速并行分析现场环境。目前的方法有：采用概率方法表示信息的加权平均法、贝叶斯估计法、多贝叶斯法、卡尔曼滤波法、统计决策理论法、仿效生物神经网络的信息处理方法、人工神经网络法等。; 个人分类: 学习之路|15934 次阅读|0 个评论

移动传感器（移动机器人）路径规划方法总结（一）: zswm27 2011-7-4 14:25; 根据对环境信息掌握的程度将其分为 2 种：基于环境先验完全信息的全局路径规划，又称静态或离线规划；基于传感器信息的局部路径规划，又称动态或在线路径规划。一. 全局路径规划其主要方法有：可视图法，自由空间法，最优控制法，栅格法，拓扑法，神经网络法等。 1). 可视图法可视图法视移动机器人为一点，将机器人、目标点和多边形障碍物的各顶点进行组合连接，并保证这些直线均不与障碍物相交，这就形成了一张图，称为可视图。由于任意两直线的顶点都是可见的，从起点沿着这些直线到达目标点的所有路径均是运动物体的无碰路径。搜索最优路径的问题就转化为从起点到目标点经过这些可视直线的最短距离问题。运用优化算法，可删除一些不必要的连线以简化可视图，缩短搜索时间。该法能够求得最短路径，但假设忽略移动机器人的尺寸大小，使得机器人通过障碍物顶点时离障碍物太近甚至接触，并且搜索时间长。切线图法和 Voronoi 图法对可视图法进行了改造。切线图用障碍物的切线表示弧，因此是从起始点到目标点的最短路径的图，即移动机器人必须几乎接近障碍物行走。其缺点是如果控制过程中产生位置误差，移动机器人碰撞的可能性会很高。 Voronoi 图法用尽可能远离障碍物和墙壁的路径表示弧。由此，从起始节点到目标节点的路径将会增长，但采用这种控制方式时，即使产生位置误差，移动机器人也不会碰到障碍物。 2). 拓扑法将规划空间分割成具有拓扑特征子空间，根据彼此连通性建立拓扑网络，在网络上寻找起始点到目标点的拓扑路径，最终由拓扑路径求出几何路径。拓扑法基本思想是降维法，即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。优点在于利用拓扑特征大大缩小了搜索空间。算法复杂性仅依赖于障碍物数目，理论上是完备的。而且拓扑法通常不需要机器人的准确位置，对于位置误差也就有了更好的鲁棒性；缺点是建立拓扑网络的过程相当复杂，特别在增加障碍物时如何有效地修正已经存在的拓扑网是有待解决的问题。 3). 栅格法将移动机器人工作环境分解成一系列具有二值信息的网格单元，多采用四叉树或八叉树表示，并通过优化算法完成路径搜索。该法以栅格为单位记录环境信息，有障碍物的地方累积值比较高，移动机器人就会采用优化算法避开。环境被量化成具有一定分辨率的栅格，栅格大小直接影响环境信息存储量大小和规划时间长短。栅格划分大了，环境信息存储量小，规划时间短，但分辨率下降，在密集环境下发现路径的能力减弱；栅格划分小了，环境分辨率高，在密集环境下发现路径的能力强，但环境信息存储量大，规划时间长。栅格法是由 w ． E ． Howden 在 1968 年提出的。栅格法将机器人工作环境分解成一系列具有二值信息的网格单元，工作空间中障碍物的位置和大小一致，并且在机器人运动过程中，障碍物的位置和大小不发生变化。用尺寸相同的栅格对机器人的二维工作空间进行划分，栅格的大小以机器人自身的尺寸为准。若某个栅格范围内不含任何障碍物，则称此栅格为自由栅格；反之，称为障碍栅格。自由空间和障碍物均可表示为栅格块的集成。栅格的标识方法有两种：直角坐标法和序号法。多采用四叉树或八叉树表示工作环境，并通过优化算法完成路径搜索。该方法以栅格为单位记录环境信息，栅格粒度越小，障碍物的表示越精确，但同时会占用大量的存储空问，算法的搜索范围将按指数增加。栅格的粒度太大，规划的路径会很不精确。所以栅格粒度的大小的确定，是栅格法的主要问题。 4). 自由空间自由空间应用于移动机器人路径规划，采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间，并将自由空间表示为连通图，通过搜索连通图来进行路径规划。自由空间的构造方法是：从障碍物的一个顶点开始，依次作其它顶点的链接线，删除不必要的链接线，使得链接线与障碍物边界所围成的每一个自由空间都是面积最大的凸多边形：连接各链接线的中点形成的网络图即为机器人可自由运动的路线。其优点是比较灵活，起始点和目标点的改变不会造成连通图的重构，缺点是复杂程度与障碍物的多少成正比，且有时无法获得最短路径用栅格法建模受到了空间分辨率和内存容量的矛盾限制。而自由空间法建模，解决了这一矛盾。但自由空间法的分割需构造想象边界，想象边界本身具有任意性，于是导致路径的不确定性。 5). 最优控制法在确定的空间里，二维平面上的一条边界可由方程来描述。那么，机器人在运动过程中，从起点到终点的众多路径里，有障碍物的路径是不允许机器人通过的。这些路径可以作为约束条件，由数学表达式表示。非完整移动机器人通过适当的变换，可将其转化为链式形式。因此，通过选择适当的控制量就可以驱使机器人从一个位置运动到另一个位置。 6). 神经网络法可视图法缺乏灵活性，且不适用于圆形障碍物的路径规划问题。神经网络法用于全局路径规划可以解决以上问题。; 个人分类: 学习之路|23149 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 移动机器人

相关帖子

相关日志

关闭安全验证