路径规划技术的发展与展望

路径规划技术的发展与展望报告人：董诗宇日期：2020.11.27二、路径规划技术的发展历史三、路径规划技术的现状四、路径规划技术的发展趋势五、路径规划应用及其意义目录一、路径规划研究概述大工至善·大学至真路径规划研究概述CHAPTER

ONE第一章近年来，移动规划技术在先进科技的辅助下不断升级，渗透这项技术于移动机器人设备，优选适合的路径规划方案，这对路径规划技术良好发展有重要意义。本章摘要路径规划研究概述一、路径规划的定义：路径规划是指导航中物体从起点移动到终点时在地图上做出路线选择行为。一般情况下，路径规划主要功能是搜索起止点之间的最优路径。注意，路径规划并不一定寻找最短路径，路径规划有一套系统的衡量指标——时间最短、距离最短或者时间/距离综合等等。二、路径的评价标准：最短路径、最快路径、最少拐弯路径等。路径规划研究概述三、路径规划技术分类：a.静态结构化环境下的路径规划，比如说slam把图做好了之后，在已有的图上进行路径规划，已知地图进行全局规划。b.动态已知环境下的路径规划，比如说地图已知了，但是地图中有一些可以移动的障碍物，这些障碍物在一定时间内它的信息是未知的。c.动态不确定环境下的路径规划，环境是未知的，它要求机器人自己去生成一条路径，然后主动去探索环境。路径规划研究概述路径规划研究概述四、路径规划算法分类：第一种分类方式：路径规划研究概述四、路径规划算法分类：第二种分类方式：路径规划研究概述五、路径规划步骤：a.环境建模。环境建模是路径规划的重要环节，目的是建立一个便于计算机进行路径规划所使用的环境模型，即将实际的物理空间抽象成算法能够处理的抽象空间，实现相互间的映射。b.路径搜索。路径搜索阶段是在环境模型的基础上应用相应算法寻找一条行走路径，使预定的性能函数获得最优值。c.路径平滑。通过相应算法搜索出的路径并不一定是一条运动体可以行走的可行路径，需要作进一步处理与平滑才能使其成为一条实际可行的路径。路径规划研究概述环境建模delaunay三角剖分栅格图拓扑图路径规划研究概述路径搜索三角地图下的路径拓扑地图下的路径栅格地图下的路径路径规划研究概述软约束优化样条曲线优化节点优化路径平滑路径规划技术的发展历史路径规划相关领域研究最早于20世纪60年代提出，当时主要是将路径规划技术应用在机器人避障行动控制的应用中。后来，随着研究的不断深入，更多需要应用到路径规划技术的领域不断涌现，路径规划算法也就逐渐扩展到其他领域的研究中。

本章摘要CHAPTER

ONE第二章大工至善·大学至真路径规划技术的发展历史经过相当长时间的研究，路径规划领域取得了不错的理论成果，涌现出许多优秀的算法，有学者将这些算法划分为传统规划算法和智能规划算法。传统规划算法包括模拟退火法、Dijkstra算法、A*算法、Floyd算法、人工势场法等。智能规划算法包括神经网络算法、遗传算法、禁忌搜索算法、粒子群算法、蚁群算法等。路径规划技术的发展历史路径规划技术的发展历史路径规划技术的发展历史人工势场法路径规划技术的发展历史缺陷：1、当目标点距离较远的话，引力将变得特别大，相对较小的斥力下，物体路径可能会碰到障碍物2、当目标点附近有障碍物时，斥力将非常大，引力相对较小，物体很难到达目标点3、在某个点，引力斥力刚好相等，方向相反，物体容易陷入局部最优解或震荡路径规划技术的发展历史PRM、RRTPRM是一种基于图搜索的方法，它将连续空间转换成离散空间，再利用A*等搜索算法在路线图上寻找路径，以提高搜索效率。RRT算法从某个点出发一边搜索，一边抽样并建图，以一个初始点作为根节点，通过随机采样增加叶子节点的方式，生成一个随机扩展树，直到叶子节点包含了目标点或进入了目标区域。路径规划技术的发展历史完备性：如果在起点和终点间如果存在可走的路径，那么一定可以找到这条路径。概率完备性：如果在起点和终点间如果存在可走的路径，通过随机采样的方式最终可以找到这条路径。最优性：指规划得到的路径在某个评价指标上是最优的，一般指规划的路径最短。缺陷：当采样点太少，或者分布不合理时，PRM算法是不完备的，但是随着采用点的增加，也可以达到完备。所以PRM是概率完备且不最优的。RRT与PRM类似，是概率完备且不最优的，由于生长缺乏方向性，其实是一种“碰运气”式的搜索。RRT树的分支填充了所有空间直至找到目标点。这样的搜索会消耗大量的时间。路径规划技术的发展历史Dijkstra、A*基本思想：1、指定起点s(即从顶点s开始计算)。2、引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。3、初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。…重复该操作，直到遍历完所有顶点。g(n)是节点n距离起点的代价。h(n)是节点n距离终点的预计代价路径规划技术的发展历史缺陷：OPEN表(S表)需要保存大量的节点信息，不仅存储量大是一个问题，而且在查找F值最小的节点时，需要查询的节点也非常多，当然就非常耗时。再加上如果地图庞大，路径比较复杂，路径搜索过程则可能要计算成千上万的节点，计算量非常巨大。路径规划技术的发展历史蚁群算法：基本思路：蚂蚁们在行走的过程中会不断释放信息素，标识自己的行走路径。随着时间的推移，有若干只蚂蚁找到了食物，此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的，因此在单位时间内，短路径上的蚂蚁数量比长路径上的蚂蚁数量要多，从而蚂蚁留下的信息素浓度也就越高。这为后面的蚂蚁们提供了强有力的方向指引，越来越多的蚂蚁聚集到最短的路径上去。路径规划技术的发展历史缺陷：1、收敛速度慢。蚁群算法中信息素初值相同，选择下一个节点时倾向于随机选择。需要较长时间才能发挥正反馈的作用，导致算法初期收敛速度较慢。2、局部最优问题。在信息素更新时，蚁群算法在较优解经过的路径上留下更多的信息激素，引导整个系统向最优解的方向进化。如果算法开始得到的较优解为次优解，那么正反馈会使次优解很快占据优势，使算法陷入局部最优，且难以跳出局部最优。3、优化能力问题。蚁群算法中参数众多并且具有一定的关联性，参数选择更多是依赖经验和试错，不恰当的初始参数会减弱算法的寻优能力。4、种群多样性与收敛速度的矛盾。种群多样性对应于候选解在问题空间的分布。个体分布越均匀，种群多样性就越好，得到全局最优解的概率就越大，但是寻优时间就越长；个体分布越集中，种群多样性就越差，不利于发挥算法的探索能力。路径规划技术的发展历史粒子群优化算法：每个粒子在搜索空间中单独的搜寻最优解，并将其记为当前个体极值，并将个体极值与整个粒子群里的其他粒子共享，找到最优的那个个体极值作为整个粒子群的当前全局最优解，粒子群中的所有粒子根据自己找到的当前个体极值和整个粒子群共享的当前全局最优解来调整自己的速度和位置。路径规划技术的发展历史缺陷：1、算法可能会早熟收敛，也就是粒子群在没有找到全局最优信息之前就陷入停顿状态，飞翔的动力不够，粒子群丧失了多样性2、算法搜索性能对参数具有一定的依赖性。对于特定的优化问题，如果用户经验不足，参数调整的确是个棘手的问题。参数值的大小直接影响到算法是否收敛以及求解结果的精度。3、算法局部搜索能力较差，搜索精度不够高。路径规划技术的发展历史遗传算法：遗传算法模拟一个人工种群的进化过程，通过选择(Selection)、交叉(Crossover)以及变异(Mutation)等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到近似最优的状态。路径规划技术的发展历史缺陷：1、遗传算法在进行编码时容易出现不规范不准确的问题。2、由于单一的遗传算法编码不能全面将优化问题的约束表示出来，因此需要考虑对不可行解采用阈值，进而增加了工作量和求解时间。3、遗传算法效率通常低于其他传统的优化方法。4、遗传算法容易出现过早收敛的问题。路径规划技术的现状CHAPTER

ONE第三章分为路径规划算法现状和路径规划应用现状。算法研究一般从算法的本身改进入手或者结合多种路径规划算法形成融合算法。路径规划的应用领域非常广泛，可简单的划分为离散域路径规划和连续域路径规划。

本章摘要路径规划技术的现状算法现状一、算法本身的改进RRTRRTConnectRRT算法倾向于拓展到开放的未探索区域，只要时间足够，迭代次数足够多，没有不会被探索到的区域。RRT*基于RRT搜索空间的盲目性，节点拓展环节缺乏记忆性的缺点，为了提高空间内的搜索速。在RRT算法的基础上加上了两棵树双向搜索的引导策略，并且在生长方式的基础上加上了贪婪策略加快了搜索速度，并且减少了空白区域的无用搜索，节省了搜索时间。渐进最优的RRT*算法，该算法在原有的RRT算法上，改进了父节点选择的方式，采用代价函数来选取拓展节点领域内最小代价的节点为父节点，同时，每次迭代后都会重新连接现有树上的节点，减少不必要的搜索，和没必要的储存，从而保证计算的复杂度和渐进最优解。路径规划技术的现状算法现状RRTRRTConnectRRT*路径规划技术的现状算法现状1.产生一个随机点xrand。2.在树上找到与xrand最近的节点xnearest。3.连接xrand与xnearest。4.以xrand为中心，ri为半径，在树上搜索节点。5.找出潜在的父节点集合Xpotential_parent，其目的是要更新xrand，看看有没有比它更好的父节点。6.从某一个潜在的父节点xpotential_parent开始考虑。7.计算出xparent作为父节点时的代价。8.先不进行碰撞检测，而是将xpotential_parent与xchild（也就是xrand）连接起来。9.计算出这条路径的代价。10.将新的这条路径的代价与原路径的代价作比较，如果新的这条路径的代价更小则进行碰撞检测，如果新的这条路径代价更大则换为下一个潜在的父节点。路径规划技术的现状算法现状11.碰撞检测失败，该潜在父节点不作为新的父节点。12.开始考虑下一个潜在父节点。13.将潜在父节点和xchild连接起来14.计算出这条路径的代价。15.将新的这条路径的代价与原路径的代价作比较，如果新的这条路径的代价更小则进行碰撞检测，如果新的这条路径代价更大则换为下一个潜在的父节点。16.碰撞检测通过。17.在树中将之前的边删掉。18.在树中将新的边添加进去，将xpotential_parent作为xparent。19.遍历所有的潜在父节点，得到更新后的树。路径规划技术的现状算法现状Dijkstra每次迭代时选择的下一个节点是当前节点最近的子节点，在每一次迭代过程中，都要对起始节点到所有遍历到的点之间的最短路径进行更新A*启发式搜索即在搜索过程中建立启发式搜索规则，以此来衡量实时搜索位置和目标位置的距离关系，使搜索方向优先朝向目标点所处位置的方向，最终达到提高搜索效率的效果。D*D*算法是一种反向增量式搜索算法，反向即算法从目标点开始向起点逐步搜索；增量式搜索，即算法在搜索过程中会计算每一个节点的距离度量信息H(x)LPA*、D*Lite搜索起始点为所设起点，按照Key值的大小作为搜索前进的原则，迭代到目标点为下一搜索点时完成规划；处于动态环境时，在当前搜索期间二次利用先前搜索得到的g值，以便重新规划路径。D*lite与LPA*的主要区别在于搜索方向的不同路径规划技术的现状算法现状启发式搜索是利用启发函数来对搜索进行指导，在每次搜索时将搜索方向导向目标点，从而实现高效的搜索，启发式搜索是一种“智能”搜索，典型的算法例如A*算法、遗传算法等。增量搜索是对以前的搜索结果信息进行再利用来实现高效搜索，大大减少搜索范围和时间，典型的例如LPA*、D*Lite算法等。搜索方向的正反多与是否能处理动态规划有关；启发式搜索带来的时效能的提高，避免全局盲目搜寻；增量式搜索则代表着迭代信息的二次利用，多用于提高算法效率。路径规划技术的现状算法现状二、多种算法的融合目前比较完整的路径规划模块包括全局路径规划和局部路径规划，但局部规划器有效范围太小，则机器人任然遵循全局路径，不能及时躲避障碍物；而大范围将导致太大的运动原语，这样的路径灵活性严重限制，很难找到接近全球运动路径的运动原语。因此发展出了新的三层级路径规划模块。路径规划技术的现状算法现状路径规划技术的现状算法现状路径规划技术的现状应用现状(离散域)基于GIS的路径规划问题，以路口为节点，道路信息为路径信息，构造路径信息拓扑网络，再利用路径搜索算法进行最短路径寻优规划路由问题是通信技术领域的重点，主要功能是使数据信息顺利的从源节点传到目标节点，也属于在网络拓扑结构搜索最优路径的问题路径规划技术的现状应用现状(离散域)虚拟装配路径规划、旅行商问题和各种车辆问题和物流问题都属于离散域内的遍历式最优路径问题，实现以最短的路径从起点出发，遍历所有子目标节点后回到起点。路径规划技术的现状应用现状(连续域)机械臂自主移动路径规划、无人机航迹规划、巡航导弹航迹规划等都属于静态环境下的全局路径规划问题，解决在安全范围内避开障碍物到达目标的最短路径问题路径规划技术的现状应用现状(连续域)连续域内的遍历式路径规划应用主要包括清洁机器人、草坪修剪机、扫雷机器人、搜救机器人等，目标是实现机器人用最短路径覆盖工作区域每个角落，要求最大覆盖率和最小重复率。路径规划技术的发展趋势CHAPTER

ONE第四章针对军事领域或智能控制领域出现的复杂问题，单一算法显然无法高效解决。这就需要多学科知识的交叉融合，将具有不同优势的算法有效结合成更加高效的复合型路径规划算法，这也是目前主流的研究方向。

本章摘要路径规划技术的发展趋势(1)局部路径规划与全局路径规划相结合全局路径规划一般是建立在已知环境信息的基础上，适应范围相对有限。局部路径规划能适应未知环境，但有时反应速度不快，对局部路径规划系统品质要求较高，因此，如果把两者结合即可达到更好的规划效果。路径规划技术的发展趋势DWA算法主要是在速度空间（v,w）中采样多组速度，并模拟这些速度在一定时间内的运动轨迹，再通过一个评价函数对这些轨迹打分，选取得分最高的最优路径，并把相应的速度控制指令发送给机器人。

路径规划技术的发展趋势(2)传统路径规划方法与新的智能方法相结合近年来，一些新的智能技术逐渐被引入到自主路径规划中来，也促使了各种方法的融合发展，例如：人工势场法与神经网络、模糊控制的结合，以及模糊控制与人工神经网络、遗传算法及行为控制之间的结合等。路径规划技术的发展趋势路径规划技术的发展趋势(3)多传感器信息融合用于局部路径规划移动机器人在动态环境中进行路径规划所需的信息都是从传感器获得，单一传感器难以保证输入信息的准确性与可靠性，多传感器所获得的信息具有冗余性、互补性、实时性，且可快速并行分析现场环境。路径规划技术的发展趋势(4)局部路径规划与动态环境路径规划相结合类似足球机器人比赛，需要考虑目标点情况。这类规划由于要考虑机器人及目标点状态，使得规划问题更为复杂，同时也赋予移动机器人更高的自主性以及智