文档介绍：关于移动机器人路径规划
第一页，本课件共有19页
体系结构
基于功能的分层式体系结构
功能：感知->建模->规划->行动
基于(传感器)行为的反应式体系结构
如Brooks包容式体系结构
机器人行为控制器构造优化方法
基于模糊逻辑及神经网络的监督学****br/>基于传感器信息的局部运动规划
(前两种)混合式
Brooks R, Robis A. Layered Control System for a Mobile Robot. IEEE Trans on Robotics & Automation. 1986, 2(1):14-23
第二页，本课件共有19页
路径规划
以C表示机器人的位形空间，以F表示无碰撞的自由位形空间。给定机器人初始位形qinit和目标位形qgoal，在F中寻找一条连接这两点的连续曲线，满足某些性能指标，如路径最短、行走时间最短、工作代价最小等。
路径规划主要包括环境、路径搜索和路径平滑环节
第三页，本课件共有19页
环境建模
从现实物理空间到算法处理抽象空间的映射表示
常用建模表示方法：
栅格法
类似于矩阵，栅格数据表示有无障碍物
易创建和维护，但分辩率和数据量互相制约
几何法
利用几何特征表示
需要对感知信息作额外处理
图
将前面两种方法结果用拓扑法连接成一个图
第四页，本课件共有19页
路径搜索
路径表达：
以环境模型中的结点序列组成或由直线段序列组成
路径平滑：依据机器人运动学或动力学约束形成机器人可跟踪执行的运动轨迹
如果考虑机器人运动学约束，则路径轨迹的一阶导数应连续
如果考虑动力学约束，则路径轨迹的二阶导数应连续
第五页，本课件共有19页
路径规划
基于地图的全局路径规划
环境已知的离线全局路径规划
环境未知的在线规划
基于进化算法
基于广义预测控制
基于传感器的局部路径规划
增量式构造当前可视区域路径图的规划方法
基于近似单元分解的局部路径规划方法
基于微分平坦系统理论的运动规划方法
第六页，本课件共有19页
路径规划方法分类
传统经典算法
基于图的方法
基于栅格的方法
势场法
数学编程法
智能方法
模糊方法
神经网络方法
遗传算法
第七页，本课件共有19页
基于图的方法
通过起始点和目标点以及障碍物顶点在内的一系列点构造可视图，连接这些点，使某点与其周围的可视点（即中间无障碍物）相连，然后机器人沿着这些点在图中搜索路径。
全局图法
可视图法、Voronoi图法、Silhouette法、基于启发式搜索的Q-M图法
全局搜索，路径完备，但计算量大，难实现
基于随机路图的方法
PRM（Probabilistic Roadmap Method）
易于实现，速度效率高，但仅具有概率完备性
第八页，本课件共有19页
基于栅格的方法
将区域划分成栅格，搜索连通栅格表示路径。优点：易于建模、存储、处理、更新与分析
Dijkstra算法：通过枚举求解两点间距离最短
A*算法：通过代价评估加快搜索
梯度法：由起点到目标点距离下降最大梯度方向搜索，不能保证全局最短，可能陷入局部最小点
距离变换法：逆向的梯度法，保证全局最短，但搜索效率随栅格和障碍物数目增加急骤下降
四叉树法：不能最优甚至次优、损失大量可行自由空间
第九页，本课件共有19页
势场法
目标产生引力、障碍物产生斥力，合力控制机器人运动
适用于静态环境或动态环境
存在振荡和局部最小值
方法：
人工势场法
虚拟力场法
电场法
结合模拟退火的人工势场法
第十页，本课件共有19页