智能网联汽车决策规划技术算法原理与实践课件 8.基于 A 算法变种的动态规划算法

基于A*算法变种的动态规划算法目录/CONTENTS01A*算法变种概览02IncrementalA*算法原理03DynamicA*算法原理04DynamicA*与D*算法对比05应用场景与拓展06小结与思考A*算法变种概览01A*算法变种及其动态路径规划价值

01A*算法的局限A*算法在静态路径规划中表现出色，但在动态环境中，障碍物的变化会导致路径失效，需要重新规划。02变种算法的分类介绍了WeightedA*、ARA*、HierarchicalA*、ParallelA*、DynamicA*和IncrementalA*六种变种算法，每种算法针对不同的问题场景进行了优化。03重点变种算法DynamicA*和IncrementalA*因其在动态环境中的增量更新能力，被本章重点展开。动态环境挑战与算法选型思路动态环境的挑战动态障碍物的出现、消失或移动，使得传统A*算法的全局重算变得低效，增加了计算负担。算法选型的关键在动态环境中，算法选型的关键在于如何实现局部复用和增量修正，以提高路径规划的效率。IncrementalA*算法原理02IncrementalA*背景与动态更新机制算法起源IncrementalA*算法从1968年经典A*算法演化而来，旨在应对地图障碍物的持续变化。动态更新机制该算法通过检测障碍物的变化，仅对受影响的节点进行g值修正和重新入队，实现毫秒级的增量重规划。实时系统中的必要性在自动驾驶和机器人等实时系统中，IncrementalA*算法的实时更新能力至关重要。IncrementalA*实现步骤与伪代码初始化初始化起点代价为0，并将其添加到待探索节点列表中。循环搜索循环选取代价最小的节点进行扩展，动态更新邻节点的代价。动态更新在动态环境中，根据障碍物的变化，局部更新受影响的节点。路径回溯找到目标节点后，通过回溯父节点指针构建最终路径。10×10网格实例与运行结果实验设置在10×10网格地图上，起点为(0,0)，目标点为(9,9)，连续六次增删障碍物。运行结果算法每次均能在毫秒级重算出可行的最短路径，验证了增量更新的高效性。DynamicA*算法原理03DynamicA*提出背景与核心思想01算法背景DynamicA*作为A*算法的在线扩展，专为动态环境中的路径规划而设计。02核心思想通过保存前次搜索的g值与父指针，在环境变化时仅对受影响区域执行局部修正并重开搜索。03增量式更新策略采用增量式更新策略，对大规模地图的路径规划尤为重要。DynamicA*实现步骤与关键数据结构初始化创建环境的网格地图，定义起点和目标位置，将起点初始化为成本为0。主循环循环直到到达目标或开放列表为空，选择具有最低成本的节点进行扩展。节点扩展计算到达邻居的成本，并更新其总成本。路径重建到达目标节点后，使用父节点指针回溯构建路径。10×10网格实验与输出解读实验过程在同一10×10网格地图上，连续六次增删障碍物，观察算法的路径规划结果。结果分析路径坐标保持不变，算法仅在障碍物变动后局部修正，验证了其在线重规划能力。DynamicA*与D*算法对比04DynamicA*与D*算法差异总览搜索方向DynamicA*沿用起点至目标的正向搜索，而D*采用目标至起点的反向搜索。更新策略DynamicA*通过障碍差分驱动局部修正，D*通过传播rhs值实现一致修复。重用粒度DynamicA*重用子树代价，D*重用全空间rhs。实现复杂度DynamicA*实现接近A*，D*需维护rhs与key。优缺点归纳与选型建议DynamicA*的优缺点DynamicA*代码改动小、内存占用低，适合高频轻量变化，但对大规模突变需重新扩展较多节点。D*的优缺点D*反向传播可快速修正长距离变化，但rhs维护复杂、内存占用高。应用场景与拓展05智能网联汽车中的实时路径规划V2X感知在V2X感知突现障碍、临时施工、事故绕行中，车载单元以100ms周期调用增量算法。实时重规划复用上帧g值，实现30ms内重规划，避免急刹或二次停车。高精地图分区缓存结合高精地图分区缓存，可支持时速60km以下城市道路的安全跟车与车道保持。机器人、无人机及智慧交通拓展01AGV仓储AGV面对托盘搬动采用IncrementalA*实现秒级重算。02无人机配送无人机面对空中障碍物采用DynamicA*做三维增量航迹。03智慧信控信控平台融合DynamicA*为救护车动态绿波。小结与思考06核心知识点回顾IncrementalA*的关键特性IncrementalA*通过障碍差分实现毫秒级增量更新。DynamicA*的关键特性DynamicA*在正向搜索框架内复用g值完成在线重规划。算法选择依据两者与D*的搜索方向及更新粒度差异决定各自适用场景。习题与思考题引导填空题通过填空题检验增量更新、实时调整、快速重算三大关键词。思考题思考题要求对比IncrementalA*与传统