💻 computer science

Landscape-Aware Bandit Hyper-Heuristics for Online Operator Selection in UAV Inspection Routing

本文介绍了 LA-BHH，这是一种感知景观的赌博机超启发式算法，它利用上下文特征和 LinUCB 动态学习在线算子选择策略，从而显著优于现有基线方法，提升无人机多站点巡检路径规划性能。

原作者： Junhao Wei, Yanxiao Li, Yifu Zhao, Qibin He, Haochen Li, Dexing Yao, Baili Lu, Zhenhong Peng, Yapeng Wang, Sio-Kei Im, Xu Yang

发布于 2026-05-15

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Junhao Wei, Yanxiao Li, Yifu Zhao, Qibin He, Haochen Li, Dexing Yao, Baili Lu, Zhenhong Peng, Yapeng Wang, Sio-Kei Im, Xu Yang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一架无人机的飞行员，任务是对一系列地点进行检查——也许是校园的屋顶、公园的电线，或是农场的传感器。你有一张标有所有地点的地图，但访问它们的顺序至关重要。如果你以杂乱无章、 zigzag 式的模式访问它们，就会浪费电池和时间。如果你以智能、平滑的环路访问它们，就能快速高效地完成。

本文介绍了一种名为LA-BHH的新型“智能飞行员”，它能帮助无人机确定访问这些地点的最佳顺序。

问题：重组方式过多

将无人机的航线想象成一串珠子。为了让这串珠子更短（更高效），你可以尝试不同的技巧：

2-opt：切断串中的一段环路并将其翻转，以解开绳结。
交换（Swap）：交换两颗珠子的位置。
重定位（Relocate）：取出一颗珠子并将其移动到队列中的不同位置。
Or-opt：将一小组珠子一起移动到新位置。

过去，无人机规划者必须选择其中一种技巧并坚持使用，或者随机选择。但有时，“翻转环路”在开阔地带效果极佳，而“交换珠子”在拥挤的城市中效果更好。固定规则无法区分这些差异。

解决方案：“智能教练”（LA-BHH）

作者创建了一个名为LA-BHH（景观感知老虎机超启发式）的系统。你可以将其想象为一位站在无人机旁的智能教练，实时观察地图和无人机的进展。

洞察环境（景观感知）：在无人机甚至开始行动之前，教练就会查看地图。是开阔的田野？是密集的建筑群？还是长长的直路？教练会记录这些“景观特征”。
观察比赛（在线学习）：随着无人机尝试重组其航线，教练会观察结果。
- 如果无人机尝试“交换”且航线变短，教练会给该动作打高分。
- 如果无人机尝试“交换”且航线变差，教练会降低其得分。
做出决策（老虎机策略）：教练使用一种数学技巧（称为“老虎机”）来决定下一步尝试哪种动作。它在探索（尝试新事物以观察其效果）和利用（使用迄今为止最有效的动作）之间取得平衡。
“卡住”传感器：如果无人机不断尝试动作但航线没有任何改善（即陷入停滞），教练有一条特殊规则：“好吧，我们卡住了。让我们尝试'2-opt'动作，它在解开绳结方面非常有效。”这有助于无人机摆脱困境。

实验中发生了什么？

研究人员使用 45 种不同的地图场景（有些开阔，有些拥挤，有些呈网格状）测试了这位智能教练与其他方法。

结果：LA-BHH 教练是当之无愧的赢家。它找到的航线明显短于以下方法找到的航线：
- 仅选择最近邻（“懒惰”方法）。
- 随机猜测下一步动作。
- 使用标准的、非智能的规则手册。
改进幅度：与次优的智能方法相比，LA-BHH 将最终航线质量提高了约17.6%。与“懒惰”方法相比，其改进幅度高达68.2%。
速度：它无需超级计算机或漫长的训练期即可完成。它在单次飞行过程中学习一切，因此既快速又实用。

结论

该论文表明，解决无人机路径规划问题并不需要庞大复杂的 AI。相反，你需要一位轻量级、适应性强的教练，它能够：

观察地图的形状。
实时观察什么方法有效。
知道在无人机陷入困境时何时切换策略。

这使得无人机在检查场地时更智能、更快速、更高效，无论是检查电线还是巡逻工厂。论文总结道，这种“边做边学”的方法是处理复杂路径规划任务的一种实用且强大的方式。

技术摘要：面向无人机巡检路径在线算子选择的景观感知老虎机超启发式方法

1. 问题定义

本文解决了无人机多站点巡检路径问题，将其抽象为欧几里得旅行商问题（TSP）。在此背景下，无人机必须在有限的飞行窗口内访问一组指定的站点并返回基地。核心决策变量是这些站点的访问顺序，假设底层问题（如高度控制、避障、服务时间等）由其他规划器单独处理。

挑战在于，不同的路径景观（例如：均匀分布、聚类分布、走廊状、网格状、混合密度）以及搜索过程的不同阶段需要不同的优化策略。经典启发式方法通常依赖固定调度或随机算子选择，这可能导致效率低下，例如过度使用已不再提供改进的算子，或在不适合当前搜索状态的移动上浪费评估次数。

2. 方法论：LA-BHH

作者提出了LA-BHH（景观感知老虎机超启发式），这是一种紧凑的在线控制器，旨在单次优化运行中学习算子选择策略，无需离线训练。

超启发式框架：LA-BHH 在高层运行，从一个包含四个底层算子（臂）的组合中进行选择：
1. 2-opt：反转路径段以消除边交叉。
2. Swap（交换）：交换两个巡检站点。
3. Relocate（重定位）：将一个站点移动到不同位置。
4. Or-opt-2：移动一个包含两个站点的区块。
上下文老虎机控制器：选择机制利用LinUCB（线性置信上限）算法。
- 上下文向量（ $z_t$ ）：控制器的决策基于一个特征向量，该向量包含：
  - 静态景观描述符：归一化问题规模、平均最近邻距离、离散度、坐标各向异性、径向离散度以及每个节点的最小生成树（MST）权重。
  - 动态搜索状态特征：预算进度、相对于初始值的当前/最佳路径长度、近期改进量、接受率以及停滞指标。
- 学习信号：奖励（ $r_t$ ）是所选算子产生的路径长度的截断相对改进量。该奖励用于更新所选臂的岭回归统计量（ $A_a, b_a$ ），使控制器能够实时调整其信用分配。
停滞感知修复：一个特定的设计特征是在搜索检测到停滞（短时间内缺乏改进）时，将选择偏向于2-opt移动。这利用了 2-opt 在欧几里得修复中的已知有效性，而无需引入新的移动类型。
接受策略：该方法采用贪婪最佳改进规则。虽然退火式接受机制作为消融实验进行了测试，但发现它会破坏强最近邻结构，从而降低这些特定欧几里得实例的性能。

3. 主要贡献

路径规划的在线学习：本文证明，一个紧凑的在线控制器可以有效地根据静态实例特征和动态搜索进度学习算子选择，无需大型离线数据集或复杂的神经网络架构。
上下文信用分配：它明确地将静态景观描述符与在线搜索状态特征相结合以指导算子选择，表明这种上下文优于非上下文老虎机选择（UCB-HH）或随机选择。
停滞处理：集成一个停滞感知门控机制，动态地将控制器偏向 2-opt 修复移动，被确定为维持搜索进度的关键组件。
消融分析：该研究系统地分离了特定组件（上下文、静态特征、动态特征、特定算子）的贡献，阐明了性能提升源于 2-opt 修复、上下文信用分配和停滞感知状态使用之间的相互作用。

4. 实验结果

该方法在45 个生成的欧几里得 TSP 实例上进行了评估，涵盖五个景观族（均匀、聚类、走廊、网格抖动、混合密度）和三种实例规模（50、100、200 个站点）。

性能指标：LA-BHH 在所有比较方法中取得了最佳的平均最终间隙（0.0223）和收敛 AUC（0.0389）。
比较增益：
- 与非上下文 UCB-HH 相比，最终间隙降低了17.6%。
- 与 Random-HH 相比，最终间隙降低了22.6%。
- 与最近邻（NN）构建方法相比，最终间隙降低了68.2%。
鲁棒性：LA-BHH 在所有景观族中始终优于经典基线（包括模拟退火、遗传算法和迭代局部搜索），证明了其在多样化部署场景中的稳定性。
算子使用：分析显示，虽然 2-opt 是主导算子（特别是在停滞期间），但学习到的控制器有效地利用了 swap、relocate 和 Or-opt-2 来纠正 2-opt 单独无法解决的局部排序错误。

5. 意义与主张

本文将 LA-BHH 定位为路径规划领域学习辅助算法设计（LEAD）的一个实用案例研究。其意义围绕几个适度但实用的主张展开：

可解释性与效率：与大型离线模型不同，LA-BHH 是一个轻量级、可检查的控制器，它在单次运行中学习，因此适用于仅拥有少量相关实例的场景。
互补角色：作者明确指出，LA-BHH 并非旨在取代最先进的 TSP 求解器（如 LKH）。相反，它作为一个路径排序层，决定在固定预算下应用哪个可重用的搜索算子。
可扩展性：该方法计算高效（仅 CPU，$O(Tn)$ 复杂度），并且从 50 到 200 个站点的规模扩展性良好，在经典局部搜索基线变得不可靠的情况下仍能保持竞争力。
未来适用性：作者建议该框架可以通过将欧几里得距离替换为可通行图上的最短路径距离，并通过底层规划器处理障碍物，从而扩展到真实的无人机巡检任务，尽管他们指出当前的实验依赖于受控生成的实例，而非现场收集的数据。