💻 computer science

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

This paper introduces LA-BHH, a landscape-aware bandit hyper-heuristic that dynamically learns an online operator-selection policy using contextual features and LinUCB to significantly improve UAV multi-site inspection routing performance compared to existing baselines.

Original authors: Junhao Wei, Yanxiao Li, Yifu Zhao, Qibin He, Haochen Li, Dexing Yao, Baili Lu, Zhenhong Peng, Yapeng Wang, Sio-Kei Im, Xu Yang

Published 2026-05-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Junhao Wei, Yanxiao Li, Yifu Zhao, Qibin He, Haochen Li, Dexing Yao, Baili Lu, Zhenhong Peng, Yapeng Wang, Sio-Kei Im, Xu Yang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the pilot of a drone tasked with inspecting a list of locations—maybe rooftops on a campus, power lines in a park, or sensors in a farm. You have a map with all the spots marked, but the order in which you visit them matters immensely. If you visit them in a messy, zigzag pattern, you waste battery and time. If you visit them in a smart, smooth loop, you finish quickly and efficiently.

This paper introduces a new "smart pilot" named LA-BHH that helps drones figure out the best order to visit these spots.

The Problem: Too Many Ways to Rearrange

Think of the drone's route like a string of beads. To make the string shorter (more efficient), you can try different tricks:

2-opt: Cut a loop in the string and flip it over to untangle a knot.
Swap: Exchange the positions of two beads.
Relocate: Take one bead and move it to a different spot in the line.
Or-opt: Move a small group of beads together to a new spot.

In the past, drone planners had to pick one of these tricks and stick with it, or pick them randomly. But sometimes, "flipping a loop" works great in an open field, while "swapping beads" works better in a crowded city. A fixed rule doesn't know the difference.

The Solution: A "Smart Coach" (LA-BHH)

The authors created a system called LA-BHH (Landscape-Aware Bandit Hyper-Heuristic). You can think of this as a smart coach standing next to the drone, watching the map and the drone's progress in real-time.

Reading the Room (Landscape Awareness): Before the drone even starts, the coach looks at the map. Is it a wide-open field? A tight cluster of buildings? A long straight road? The coach notes these "landscape features."
Watching the Game (Online Learning): As the drone tries to rearrange its route, the coach watches what happens.
- If the drone tries a "Swap" and the route gets shorter, the coach gives that move a high score.
- If the drone tries a "Swap" and the route gets worse, the coach lowers its score.
Making the Call (The Bandit Strategy): The coach uses a mathematical trick (called a "Bandit") to decide which move to try next. It balances exploration (trying new things to see if they work) and exploitation (using the moves that have worked best so far).
The "Stuck" Sensor: If the drone keeps trying moves but the route isn't getting any better (it's stuck), the coach has a special rule: "Okay, we're stuck. Let's try the '2-opt' move, which is really good at untangling knots." This helps the drone break out of a rut.

What Happened in the Experiments?

The researchers tested this smart coach against other methods using 45 different map scenarios (some open, some crowded, some grid-like).

The Results: The LA-BHH coach was the clear winner. It found routes that were significantly shorter than those found by:
- Just picking the nearest neighbor (the "lazy" approach).
- Randomly guessing which move to make.
- Using a standard, non-smart rulebook.
The Improvement: Compared to the next-best smart method, LA-BHH improved the final route quality by about 17.6%. Compared to the "lazy" approach, it improved by a massive 68.2%.
Speed: It did this without needing a supercomputer or a massive training period. It learned everything during the single flight, making it fast and practical.

The Takeaway

The paper shows that you don't need a giant, complex AI to solve drone routing. Instead, you need a lightweight, adaptable coach that:

Looks at the shape of the map.
Watches what works in real-time.
Knows when to switch tactics if the drone gets stuck.

This makes the drone smarter, faster, and more efficient at inspecting sites, whether it's checking a power line or patrolling a factory. The paper concludes that this "learn-as-you-go" approach is a practical and powerful way to handle complex routing tasks.

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

1. Problem Definition

The paper addresses the UAV multi-site inspection routing problem, abstracted as a Euclidean Traveling Salesman Problem (TSP). In this context, a UAV must visit a set of assigned sites and return to a depot within a limited flight window. The core decision variable is the visiting order of these sites, assuming that lower-level concerns (e.g., altitude control, collision avoidance, service times) are handled separately by other planners.

The challenge lies in the fact that different routing landscapes (e.g., uniform, clustered, corridor-like, grid-like, mixed-density) and different stages of the search process require different optimization strategies. Classical heuristics often rely on fixed schedules or random operator selection, which can lead to inefficiencies such as overusing an operator that has ceased to provide improvements or wasting evaluations on moves unsuitable for the current search state.

2. Methodology: LA-BHH

The authors propose LA-BHH (Landscape-Aware Bandit Hyper-Heuristic), a compact online controller designed to learn an operator-selection policy during a single optimization run without offline training.

Hyper-Heuristic Framework: LA-BHH operates at a high level, selecting from a portfolio of four low-level operators (arms):
1. 2-opt: Reverses a tour segment to remove edge crossings.
2. Swap: Exchanges two inspection sites.
3. Relocate: Moves one site to a different position.
4. Or-opt-2: Relocates a block of two sites.
Contextual Bandit Controller: The selection mechanism utilizes a LinUCB (Linear Upper Confidence Bound) algorithm.
- Context Vector ( $z_t$ ): The controller conditions its decisions on a feature vector comprising:
  - Static Landscape Descriptors: Normalized problem size, mean nearest-neighbor distance, dispersion, coordinate anisotropy, radial dispersion, and MST weight per node.
  - Dynamic Search-State Features: Budget progress, current/best tour length relative to the initial, recent improvement, acceptance rate, and stagnation indicators.
- Learning Signal: The reward ( $r_t$ ) is the clipped relative improvement in tour length produced by the selected operator. This reward updates the ridge-regression statistics ( $A_a, b_a$ ) for the chosen arm, allowing the controller to adapt its credit assignment in real-time.
Stagnation-Aware Repair: A specific design feature biases the selection toward 2-opt moves when the search detects stagnation (a lack of improvement over a short window). This leverages the known efficacy of 2-opt for Euclidean repair without introducing new move types.
Acceptance Strategy: The method employs a greedy best-improvement rule. While annealing-style acceptance was tested as an ablation, it was found to degrade performance on these specific Euclidean instances by disrupting strong nearest-neighbor structures.

3. Key Contributions

Online Learning for Routing: The paper demonstrates that a compact online controller can effectively learn to select operators based on both static instance characteristics and dynamic search progress, eliminating the need for large offline datasets or complex neural architectures.
Contextual Credit Assignment: It explicitly combines static landscape descriptors with online search-state features to guide operator selection, showing that this context is superior to non-contextual bandit selection (UCB-HH) or random selection.
Stagnation Handling: The integration of a stagnation-aware gate that dynamically biases the controller toward 2-opt repair moves is identified as a critical component for maintaining search progress.
Ablation Analysis: The study systematically isolates the contributions of specific components (context, static features, dynamic features, specific operators), clarifying that the performance gains stem from the interaction between 2-opt repair, contextual credit assignment, and stagnation-aware state use.

4. Experimental Results

The method was evaluated on 45 generated Euclidean TSP instances across five landscape families (uniform, clustered, corridor, grid-jitter, mixed-density) and three instance sizes (50, 100, 200 sites).

Performance Metrics: LA-BHH achieved the best mean final gap (0.0223) and convergence AUC (0.0389) among all compared methods.
Comparative Gains:
- Reduced final gap by 17.6% compared to non-contextual UCB-HH.
- Reduced final gap by 22.6% compared to Random-HH.
- Reduced final gap by 68.2% compared to Nearest-Neighbor (NN) construction.
Robustness: LA-BHH consistently outperformed classical baselines (including Simulated Annealing, Genetic Algorithms, and Iterated Local Search) across all landscape families, demonstrating stability in diverse deployment scenarios.
Operator Usage: Analysis showed that while 2-opt was the dominant operator (especially during stagnation), the learned controller effectively utilized swap, relocate, and Or-opt-2 to correct local ordering errors that 2-opt alone could not address.

5. Significance and Claims

The paper positions LA-BHH as a practical case study for Learning-Assisted Algorithm Design (LEAD) in the domain of routing. Its significance is framed around several modest but practical claims:

Interpretability and Efficiency: Unlike large offline models, LA-BHH is a lightweight, inspectable controller that learns during a single run, making it suitable for scenarios where only a small number of related instances are available.
Complementary Role: The authors explicitly state that LA-BHH is not intended to replace state-of-the-art TSP solvers (like LKH). Instead, it serves as a routing-ordering layer that decides which reusable search operator to apply under a fixed budget.
Scalability: The method is computationally efficient (CPU-only, $O(Tn)$ complexity) and scales well from 50 to 200 sites, maintaining competitiveness where classical local-search baselines become less reliable.
Future Applicability: The authors suggest the framework can be extended to real-world UAV inspection by replacing Euclidean distances with shortest-path distances on traversability graphs and handling obstacles via lower-level planners, though they note that current experiments rely on controlled generated instances rather than field-collected data.