上一篇讲了启发式函数的设计。今天讲A的几个重要变体——它们在实际工程中用得比原版A还多面试也经常考。标准A*保证最优解但有时候最优不是最重要的——快才是。比如移动机器人实时避障你给它0.5秒算路径它需要的是一条能走的没碰撞的路不是绝对最短的路。这些变体就是在最优性和速度之间做不同的权衡。一、Weighted A*——牺牲最优性换速度Weighted A*是最简单的变体把启发式乘以一个权重w 1。f(n) g(n) w * h(n) # w 1w越大搜索越贪心——越倾向于朝终点方向走。极端情况下w无穷大退化成贪心最佳优先搜索只看h(n)。有界次优性Weighted A*找到的路径代价不超过最优路径的w倍。这是它的理论保证也是工程上敢用的原因。# Weighted A* 示例 def weighted_astar(graph, start, goal, heuristic, w2.0): open_set [(0, start)] g_score {start: 0} came_from {} while open_set: f, current heapq.heappop(open_set) if current goal: return reconstruct_path(came_from, current) for neighbor, cost in graph[current]: tentative_g g_score[current] cost if tentative_g g_score.get(neighbor, float(inf)): came_from[neighbor] current g_score[neighbor] tentative_g f_score tentative_g w * heuristic(neighbor, goal) heapq.heappush(open_set, (f_score, neighbor)) return None工程上w通常取1.5-5.0。w2是个不错的起点——速度快一倍路径长度增加不超过100%。实际测试中w2通常路径只增加10-30%但搜索时间减少50%以上。二、ARA*——动态调整权重ARAAnytime Repairing A的思路很巧妙先用大的w快速找到一个可行解然后逐步减小w在已有解的基础上改进。# ARA* 伪代码 w 5.0 # 初始权重 while w 1.0: path weighted_astar(graph, start, goal, h, w) if time_exceeded(): break w - 0.5 # 逐步减小权重 # 返回当前最好的路径ARA*的特点anytime算法——任何时候中断都能返回一个可行解解的质量随时间逐步提高适合有时间限制的场景比如给你2秒尽量找到最好的路径ARA的每一轮迭代叫做一个inflation——用当前权重w跑一遍Weighted A然后减小w再跑。每轮迭代都利用上一轮的结果不用从头搜索。这使得ARA比多次独立跑Weighted A效率高很多。工程上ARA用得相对少一些——大多数场景要么需要最优解用A要么需要快速可行解用Weighted A。ARA适合那种时间充裕但想尽量优化的场景比如离线路径优化。三、D和DLite——动态环境增量搜索标准A*有个大问题环境一变就得从头搜索。在动态环境中比如移动机器人遇到新障碍物这太浪费了。D* Lite解决了这个问题。核心思想增量搜索——环境变化后只更新受影响的部分不用从头来。D* Lite的工作方式从终点反向搜索到起点和A*方向相反。为什么反向因为机器人移动时起点在变终点不变。反向搜索只需要一次正向移动时增量更新。机器人沿路径移动时如果发现新障碍物传感器检测到只更新局部地图中受影响的节点基于更新后的地图增量修改搜索树——只重新计算不一致的节点增量搜索的核心概念是每个节点维护两个值g(s)当前估计的最短距离和rhs(s)一步lookahead的最短距离。当g(s) ! rhs(s)时节点是不一致的需要重新计算。环境变化只影响变化点附近的节点所以增量更新很快。# D* Lite的核心概念 # 每个节点维护两个值 # g(s): 当前估计的最短距离 # rhs(s): 一步 lookahead 的最短距离 # rhs(s) min(cost(s, s_next) g[s_next]) for all successors # 当 g(s) ! rhs(s) 时节点不一致需要更新 def is_consistent(s): return g[s] rhs[s] def update_vertex(s): rhs[s] min(cost(s, s_next) g[s_next] for s_next in successors(s)) if g[s] ! rhs[s]: add_to_queue(s)D* Lite的优势环境变化后重新规划的时间远小于从头搜索在变化不大的环境中增量更新只需修改很少的节点是自动驾驶和移动机器人最常用的全局规划算法之一理论完备——有最优性和复杂度的严格证明四、工程选型场景推荐算法原因静态环境需要最优解A*保证最优静态环境速度优先Weighted A*快有次优保证有时间限制越算越好ARA*anytime特性动态环境频繁变化D* Lite增量更新动态环境变化很大重新跑A*D* Lite优势不明显之前做移动机器人的项目用的是D* Lite。仓库环境里偶尔会有人临时放的货物箱传感器检测到新障碍物后D* Lite只需要更新障碍物周围的十几个节点而重新跑A*要搜索几千个节点。差距非常明显。五、面试实战QWeighted A*的次优保证是什么意思A找到的路径代价 w * 最优代价。比如w2最优路径长度100Weighted A*找到的路径长度不超过200。QDLite和A的主要区别是什么** AA每次环境变化都从头搜索。DLite从终点反向搜索环境变化后增量更新。在变化不大的动态环境中D* Lite比A*快很多。Q什么时候该用DLite而不是重新跑A** A当环境变化很小时比如只有一两个格子变了D* Lite的增量更新很快。当环境变化很大时比如一半地图都变了D* Lite的增量更新可能比重新搜索还慢。经验法则变化量小于10%用D* Lite大于10%重新搜索。QARA*的anytime特性是什么意思Aanytime算法在任何时刻中断都能返回一个可行解。ARA*先用大权重快速找到解然后逐步改进。如果时间到了就返回当前最好的解。这个特性在嵌入式系统中很有用——中断信号来了就停不会算到一半什么都没有。小结A的变体在最优性和速度之间做不同的权衡。Weighted A最简单——乘以权重就行工程上最常用。ARA是anytime算法——越算越好适合离线优化。DLite适合动态环境——增量更新避免重复搜索是移动机器人导航的标配。工程上根据场景选择静态环境用A或Weighted A动态环境用D* Lite有时间限制用ARA。大多数实际项目用Weighted A或D* Lite就够了。下一篇讲D* Lite算法——动态环境中的增量路径规划展开讲具体细节和实现。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第210篇 启发式函数设计——曼哈顿/欧几里得/对角线距离的选型下一篇预告第212篇 D* Lite算法——动态环境中的增量路径规划有任何问题欢迎评论区留言我会尽量回复。 第211篇 A算法变体——Weighted A/ARA*/D*的工程应用
上一篇讲了启发式函数的设计。今天讲A的几个重要变体——它们在实际工程中用得比原版A还多面试也经常考。标准A*保证最优解但有时候最优不是最重要的——快才是。比如移动机器人实时避障你给它0.5秒算路径它需要的是一条能走的没碰撞的路不是绝对最短的路。这些变体就是在最优性和速度之间做不同的权衡。一、Weighted A*——牺牲最优性换速度Weighted A*是最简单的变体把启发式乘以一个权重w 1。f(n) g(n) w * h(n) # w 1w越大搜索越贪心——越倾向于朝终点方向走。极端情况下w无穷大退化成贪心最佳优先搜索只看h(n)。有界次优性Weighted A*找到的路径代价不超过最优路径的w倍。这是它的理论保证也是工程上敢用的原因。# Weighted A* 示例 def weighted_astar(graph, start, goal, heuristic, w2.0): open_set [(0, start)] g_score {start: 0} came_from {} while open_set: f, current heapq.heappop(open_set) if current goal: return reconstruct_path(came_from, current) for neighbor, cost in graph[current]: tentative_g g_score[current] cost if tentative_g g_score.get(neighbor, float(inf)): came_from[neighbor] current g_score[neighbor] tentative_g f_score tentative_g w * heuristic(neighbor, goal) heapq.heappush(open_set, (f_score, neighbor)) return None工程上w通常取1.5-5.0。w2是个不错的起点——速度快一倍路径长度增加不超过100%。实际测试中w2通常路径只增加10-30%但搜索时间减少50%以上。二、ARA*——动态调整权重ARAAnytime Repairing A的思路很巧妙先用大的w快速找到一个可行解然后逐步减小w在已有解的基础上改进。# ARA* 伪代码 w 5.0 # 初始权重 while w 1.0: path weighted_astar(graph, start, goal, h, w) if time_exceeded(): break w - 0.5 # 逐步减小权重 # 返回当前最好的路径ARA*的特点anytime算法——任何时候中断都能返回一个可行解解的质量随时间逐步提高适合有时间限制的场景比如给你2秒尽量找到最好的路径ARA的每一轮迭代叫做一个inflation——用当前权重w跑一遍Weighted A然后减小w再跑。每轮迭代都利用上一轮的结果不用从头搜索。这使得ARA比多次独立跑Weighted A效率高很多。工程上ARA用得相对少一些——大多数场景要么需要最优解用A要么需要快速可行解用Weighted A。ARA适合那种时间充裕但想尽量优化的场景比如离线路径优化。三、D和DLite——动态环境增量搜索标准A*有个大问题环境一变就得从头搜索。在动态环境中比如移动机器人遇到新障碍物这太浪费了。D* Lite解决了这个问题。核心思想增量搜索——环境变化后只更新受影响的部分不用从头来。D* Lite的工作方式从终点反向搜索到起点和A*方向相反。为什么反向因为机器人移动时起点在变终点不变。反向搜索只需要一次正向移动时增量更新。机器人沿路径移动时如果发现新障碍物传感器检测到只更新局部地图中受影响的节点基于更新后的地图增量修改搜索树——只重新计算不一致的节点增量搜索的核心概念是每个节点维护两个值g(s)当前估计的最短距离和rhs(s)一步lookahead的最短距离。当g(s) ! rhs(s)时节点是不一致的需要重新计算。环境变化只影响变化点附近的节点所以增量更新很快。# D* Lite的核心概念 # 每个节点维护两个值 # g(s): 当前估计的最短距离 # rhs(s): 一步 lookahead 的最短距离 # rhs(s) min(cost(s, s_next) g[s_next]) for all successors # 当 g(s) ! rhs(s) 时节点不一致需要更新 def is_consistent(s): return g[s] rhs[s] def update_vertex(s): rhs[s] min(cost(s, s_next) g[s_next] for s_next in successors(s)) if g[s] ! rhs[s]: add_to_queue(s)D* Lite的优势环境变化后重新规划的时间远小于从头搜索在变化不大的环境中增量更新只需修改很少的节点是自动驾驶和移动机器人最常用的全局规划算法之一理论完备——有最优性和复杂度的严格证明四、工程选型场景推荐算法原因静态环境需要最优解A*保证最优静态环境速度优先Weighted A*快有次优保证有时间限制越算越好ARA*anytime特性动态环境频繁变化D* Lite增量更新动态环境变化很大重新跑A*D* Lite优势不明显之前做移动机器人的项目用的是D* Lite。仓库环境里偶尔会有人临时放的货物箱传感器检测到新障碍物后D* Lite只需要更新障碍物周围的十几个节点而重新跑A*要搜索几千个节点。差距非常明显。五、面试实战QWeighted A*的次优保证是什么意思A找到的路径代价 w * 最优代价。比如w2最优路径长度100Weighted A*找到的路径长度不超过200。QDLite和A的主要区别是什么** AA每次环境变化都从头搜索。DLite从终点反向搜索环境变化后增量更新。在变化不大的动态环境中D* Lite比A*快很多。Q什么时候该用DLite而不是重新跑A** A当环境变化很小时比如只有一两个格子变了D* Lite的增量更新很快。当环境变化很大时比如一半地图都变了D* Lite的增量更新可能比重新搜索还慢。经验法则变化量小于10%用D* Lite大于10%重新搜索。QARA*的anytime特性是什么意思Aanytime算法在任何时刻中断都能返回一个可行解。ARA*先用大权重快速找到解然后逐步改进。如果时间到了就返回当前最好的解。这个特性在嵌入式系统中很有用——中断信号来了就停不会算到一半什么都没有。小结A的变体在最优性和速度之间做不同的权衡。Weighted A最简单——乘以权重就行工程上最常用。ARA是anytime算法——越算越好适合离线优化。DLite适合动态环境——增量更新避免重复搜索是移动机器人导航的标配。工程上根据场景选择静态环境用A或Weighted A动态环境用D* Lite有时间限制用ARA。大多数实际项目用Weighted A或D* Lite就够了。下一篇讲D* Lite算法——动态环境中的增量路径规划展开讲具体细节和实现。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第210篇 启发式函数设计——曼哈顿/欧几里得/对角线距离的选型下一篇预告第212篇 D* Lite算法——动态环境中的增量路径规划有任何问题欢迎评论区留言我会尽量回复。