移动机器人路径规划.ppt

移动机器人路径规划技术 体系结构 基于功能的分层式体系结构功能 感知 建模 规划 行动基于 传感器 行为的反应式体系结构如Brooks包容式体系结构机器人行为控制器构造优化方法基于模糊逻辑及神经网络的监督学习基于传感器信息的局部运动规划 前两种 混合式 BrooksR RobisA LayeredControlSystemforaMobileRobot IEEETransonRobotics Automation 1986 2 1 14 23 路径规划 以C表示机器人的位形空间 以F表示无碰撞的自由位形空间 给定机器人初始位形qinit和目标位形qgoal 在F中寻找一条连接这两点的连续曲线 满足某些性能指标 如路径最短 行走时间最短 工作代价最小等 路径规划主要包括环境 路径搜索和路径平滑环节 环境建模 从现实物理空间到算法处理抽象空间的映射表示常用建模表示方法 栅格法类似于矩阵 栅格数据表示有无障碍物易创建和维护 但分辩率和数据量互相制约几何法利用几何特征表示需要对感知信息作额外处理图将前面两种方法结果用拓扑法连接成一个图 路径搜索 路径表达 以环境模型中的结点序列组成或由直线段序列组成路径平滑 依据机器人运动学或动力学约束形成机器人可跟踪执行的运动轨迹如果考虑机器人运动学约束 则路径轨迹的一阶导数应连续如果考虑动力学约束 则路径轨迹的二阶导数应连续 路径规划 基于地图的全局路径规划环境已知的离线全局路径规划环境未知的在线规划基于进化算法基于广义预测控制基于传感器的局部路径规划增量式构造当前可视区域路径图的规划方法基于近似单元分解的局部路径规划方法基于微分平坦系统理论的运动规划方法 路径规划方法分类 传统经典算法基于图的方法基于栅格的方法势场法数学编程法智能方法模糊方法神经网络方法遗传算法 基于图的方法 通过起始点和目标点以及障碍物顶点在内的一系列点构造可视图 连接这些点 使某点与其周围的可视点 即中间无障碍物 相连 然后机器人沿着这些点在图中搜索路径 全局图法可视图法 Voronoi图法 Silhouette法 基于启发式搜索的Q M图法全局搜索 路径完备 但计算量大 难实现基于随机路图的方法PRM ProbabilisticRoadmapMethod 易于实现 速度效率高 但仅具有概率完备性 基于栅格的方法 将区域划分成栅格 搜索连通栅格表示路径 优点 易于建模 存储 处理 更新与分析Dijkstra算法 通过枚举求解两点间距离最短A 算法 通过代价评估加快搜索梯度法 由起点到目标点距离下降最大梯度方向搜索 不能保证全局最短 可能陷入局部最小点距离变换法 逆向的梯度法 保证全局最短 但搜索效率随栅格和障碍物数目增加急骤下降四叉树法 不能最优甚至次优 损失大量可行自由空间 势场法 目标产生引力 障碍物产生斥力 合力控制机器人运动适用于静态环境或动态环境存在振荡和局部最小值方法 人工势场法虚拟力场法电场法结合模拟退火的人工势场法 数学编程法 用一组不等式来表示机器人的避碰约束 机器人运动起点和终点分别用一个函数的起始条件和终止条件表示 同时设定一个最优评价函数 从而将路径规划问题转化为一个纯数学的最优求解问题 基于模糊逻辑的方法 模糊逻辑 构造二维隶属度函数 模糊综合评价该方法在环境未知或发生变化的情况下 能够快速而准确地规划机器人路径 对于要求较少规划时间的机器人是一种良好的导航方法 缺点是当障碍物数目增加时 该方法的计算量会很大 影响规划结果 基于神经网络的方法 利用神经网络进行路径规划缺点 运算时间长 在运动空间数据不完备时可能发生不收敛或路径不可行问题 基于遗传算法的路径规划 遗传算法是计算数学中用于解决最优化的搜索算法 是进化算法的一种 遗传算法通常实现为一种计算机模拟 对于一个最优化问题 一定数量的候选解 称为个体 的抽象表示 称为染色体 的种群向更好的解进化 传统上 解用二进制表示 即0和1的串 但也可以用其他表示方法 进化从完全随机个体的种群开始 之后一代一代发生 在每一代中 整个种群的适应度被评价 从当前种群中随机地选择多个个体 基于它们的适应度 通过自然选择和突变产生新的生命种群 该种群在算法的下一次迭代中成为当前种群 衍生算法 退火遗传算法 改进遗传算子等 其它智能机器人路径规划方法 蚂蚁算法 一种全局优化算法 模仿蚂蚁搜索食物的行为 是一种通用型随机优化方法 基于电路地图的路径规划方法 将环境建模成电路图 规划路径与电流相似 即路径的长度以电路中某条通路中串联电阻的多少来反映 路径的宽度以电路中某个方向上的支路数目即并联电阻多少来反映 根据欧姆定律和电的基本性质 在电路中电阻最小的支路上电流最大 而串联电阻少且并联电阻多的支路即最大电流通路 优点 在规划最短路径的同时考虑了路径宽度 运动控制 基于路径规划的移动机器人路径跟踪控制非完整控制系统的镇定方法非连续定常镇定化时变镇定化基于传感器 执行器直接映射的运动控制模糊逻辑方法 神经网络法 要求先验知识 基于动态规划的增强 故障诊断 现有故障检测方法可分为基于知识 基于解析模型和基于信号处理3种诊断决策方法 阈值法模糊逻辑贝叶斯分类故障假设检验 机器学习 机器学习为复杂未知环境中的信息提取 环境理解 任务规划和行为决策提供了有效的解决途径增强学习理论和算法进化学习算法统计学习 支持向量机 SVM 理论和算法