2015-机器人技术-第5讲-路径规划和避障

第五讲路径规划与避障  熊蓉  控制系智能系统与控制研究所参考书目• Roland  Siegwart  and  Illah  R.  Nourbakhsh.    Introduc8on  to  Autonomous  Mobile  Robots.  The  MIT  Press,  2004.  • Where  am  I  ?    (在哪里?)  • Where  am  I  going  ?    (到哪里?)  • How  do  I  get  there  ?  (怎么去?)自主移动的三个关键问题?自定位目标规划导航规划环境地图地图表示未知环境地图构建自主移动必须具备的四要素• 环境模型/地图（预先已知或者自主构建）• 感知和分析环境• 确定自己在环境中的位置• 规划并执行移动自主移动的一般软件体系结构⺫⽬目标规划导航规划信息处理感知运动控制执⾏行测量数据局部观测/地图位置  全局地图参考点运动轨迹驱动指令感知控制任务指令知识、数据库环境⾃自定位地图构建导航规划• 导航规划：在给定环境的全局或局部知识以及一个或者一系列目标位置的条件下，使机器人能够根据知识和传感器感知信息高效可靠地到达目标位置• 导航方式：路径导航自主导航路径导航• 在路径上连续敷设电缆、反射条带等引导标记，或采⽤用电波、光等连续引导信号，或设置磁铁、路标等断续的引导标记• 优点：简单• 缺点– 将机器⼈人的移动⾃自由度限制在⼀一维– 降低了机器⼈人环境适应的能⼒力– 预设路标定⽆无法适应灵活多变的作业要求– 给机器⼈人的应⽤用增加了额外的硬件开销7自主导航的主要问题• 路径规划：根据所给定的地图和目标位置，规划一条使机器人到达目标位置的路径（只考虑工作空间的几何约束，不考虑机器人的运动学模型和约束）• 避障：根据所得到的实时传感器测量信息，调整路径/轨迹以避免发生碰撞• 轨迹生成：根据机器人的运动学模型和约束，寻找适当的控制命令，将可行路径转化为可行轨迹。路径规划和避障规划路径规划根据所给定的地图和目标位置，规划一条使机器人到达目标位置的路径避障规划根据所得到的实时传感器测量信息，调整轨迹以避免发生碰撞面向长期目标的战略方法解决当前问题的战术方法互补对立路径规划和轨迹规划• 路径不包含时间轴，轨迹包含时间轴• 路径规划只考虑工作空间的几何约束，不考虑机器人的运动学模型和约束。• 轨迹规划则需要根据机器人的运动学模型和约束，寻找适当的控制命令，将可行路径转化为可行轨迹，使机器人鲁棒地跟随期望路径。路径规划姿态空间(Configura8on  space)• 将工作空间降为二维物理空间  • 两个重要假设：  – 机器人是一个点，障碍物按机器人半径进行膨胀  – 机器人是完整的，忽略非完整约束对姿态的限制  姿态空间• 一个机器人所有可能的姿态集合  • 障碍物空间：不可行的姿态集合  – 在该空间中，机器人会与障碍物发生碰撞  • 自由空间：可行的姿态集合  – 在该空间中，机器人将无碰地安全移动路径规划：在自由姿态空间中为机器人寻找一条路径，使其从初始姿态发展到目标姿态路径规划方法• 路径规划方法应确保完备性，即当存在一条从初始姿态到目标姿态的路径时，系统总能够到达目标姿态  • 达到近似完备性的方法：将姿态空间离散化，构成分辨率完备的路径规划算法不同的空间离散策略1.行车图法：在自由空间中构建连通网络2.单元分解法：区分空闲单元和被占单元3.势场法：对空间施加虚拟力行车图路径规划• 基本思想：基于障碍物几何形状分解姿态空间，将自由空间的连通性用一维曲线的网格表示，在加入起始点和目标点后，在该一维无向连通图中寻找一条无碰路径  • 构建行车图的典型方法：可视图（Visibilitygraph）Voronoidiagram可视图法• 可视图由所有连接可见顶点对的边组成  – 可见指顶点之间无障碍物– 初始位置和目标位置也作为顶点可视图法• 优点：  – 非常简单，特别是当环境表示用多边形描述物体时  – 基于可视图的路径规划可得到在路径长度上最优的解  • 缺点：  – 所得路径过于靠近障碍物，不够安全。  – 常用的解决方法：以远远大于机器人半径的尺寸扩大障碍物，或者在路径规划后修改所得路径，使其与障碍物保持一定的距离    Voronoi  diagram• 基本思想：取障碍物之间的中间点，以最大化机器人和障碍物之间的距离  Voronoi  diagram• 构建方法：  – 对于自由空间中的每一点，计算它到最近障碍物的距离；  – 类似于画直方图，在垂直于二维空间平面的轴上用高度表示该点到障碍物的距离；  – 当某个点到两个或多个障碍  物距离相等时，其距离点处  出现尖峰，Voronoi  diagram  就由连接这些尖峰点的边组  成。Voronoi  diagram• 优点：安全性高  • 缺点：计算复杂、路径长度较可视图法长、不适用于短距离定位传感器单元分解路径规划• 基本思想  – 首先，将姿态空间中的自由空间地分为若干的小区域，每一个区域作为一个单元，以单元为顶点、以单元之间的相邻关系为边构成一张连通图；– 其次，在连通图中寻找包含初始姿态和目标姿态的单元，搜索连接初始单元和目标单元的路径；– 最后，根据所得路径的单元序列生成单元内部的路径• 主要方法– 精确单元分解– 近似单元分解精确单元分解• 单元边界严格基于环境几何形状分解，所得单元完全空闲  精确单元分解• 优点：– 机器人不需要考虑它在每个空闲单元中的具体位置，只需要考虑如何从一个单元移动到相邻的空闲单元– 单元数与环境大小无关• 缺点：– 计算效率极大地依赖于环境中物体的复杂度近似单元分解• 栅格表示法，将环境分解成若干个大小相同的栅格  – 并不是每个单元都是完全被占或者完全空闲的，因此分解后的单元集合是对实际地图的一种近似  近似单元分解• 优点  – 非常简单，与环境的疏密和物体形状的复杂度无关  • 缺点：  – 对存储空间有要求可变大小的近似单元分解四叉树表示法：递归地把环境分为4个大小相等的子区域。直到每个区域中所包含的基本元素全为0或全为1。人工势场法• 基本思想：  – 目标点对机器人产生吸引力  – 障碍物对机器人产生排斥力  – 所有力的合成构成机器人的控制律  5.35-3rFtF5-45-55-612r1Fr2rFF5-35-7Fr2FtFFr12FtF42人工势场法• 步骤1：构建人工势场(Ar8ficial  Poten8al  Field)  – 目标点：吸引势场  28ArtificialPotentialFieldsIntroductionArobotshouldbedesignedandcontrolledtonavi-gateandtraversewithoutcollidingtotheobstacleslocatedarounditselfwhichmaybestaticordynamic.Artificialpotentialfields(apf)isareactiveapproachinwhichtrajectoriesarenotplannedexplicitly.In-stead,agent’sinteractionswithitsenvironmentaresuperposedoremergedtomaketherobotflexiblycopewiththechangingenvironment.Althoughtheideabehindusingapfinpathplanningseemseasy,problemssuchaslocalminimaandoscilliatorymove-mentsmakesitdiculttofindapathconnectingtwo-endpositions.BasicArtificialPotentialFieldConceptsAPFmainlyconsistsofforcevectors,causedbytheobstaclesortargetpositions,whichmaybelinearortangentialandtheymayhavecharacteristicsofre-pulsive,attractiveorrandomdependingonthestateoftheagentwithrespecttoitsenvironment.Anex-ampleofapotentialfieldforcefunctionisasfollows;U=K⇥expxxo↵+yyoDirectionofthepotentialfieldforcecanbefoundbytakingit’sgradient;d(U)d(x)=K⇥(2⇥(xxo)↵)⇥expxxo↵+yyo⇥d(x)d(U)d(y)=K⇥(2⇥(yyo))⇥expxxo↵+yyo⇥d(y)Followingfigures,takenfrom[1],indicatesdi↵erentsortofpotentialfields.Figure1:AttractivelinearapfFigure2:RepulsivelinearapfFigure3:OnedirectiontangentialpotentialfieldsKadirFiratUyanik122||||()(2||)||addaattaadadaKdUKddd⎧−−≤=⎨−−−⎩xxxxxxxxxadaKdxx为系数为被评估点为目标点为距离阈值人工势场法• 步骤1：构建人工势场(Ar8ficial  Poten8al  Field)  – 目标点：吸引势场– 障碍物：推斥势场ArtificialPotentialFieldsIntroductionArobotshouldbedesignedandcontrolledtonavi-gateandtraversewithoutcollidingtotheobstacleslocatedarounditselfwhichmaybestaticordynamic.Artificialpotentialfields(apf)isareactiveapproachinwhichtrajectoriesarenotplannedexplicitly.In-stead,agent’sinteractionswithitsenvironmentaresuperposedoremergedtomaketherobotflexiblycopewiththechangingenvironment.Althoughtheideabehindusingapfinpathplanningseemseasy,problemssuchaslocalminimaandoscilliatorymove-mentsmakesitdiculttofindapathconnectingtwo-endpositions.BasicArtificialPotentialFieldConceptsAPFmainlyconsistsofforcevectors,causedbytheobstaclesortargetpositions,whichmaybelinearortangentialandtheymayhavecharacteristicsofre-pulsive,attractiveorrandomdependingonthestateoftheagentwithrespecttoitsenvironment.Anex-ampleofapotentialfieldforcefunctionisasfollows;U=K⇥expxxo↵+yyoDirectionofthepotentialfieldforcecanbefoundbytakingit’sgradient;d(U)d(x)=