Obstacle-aware multi-UAV scheduling for plant-protection operations using an enhanced walrus optimizer

Technical Summary: Obstacle-Aware Multi-UAV Scheduling for Plant-Protection Operations Using an Enhanced Walrus Optimizer

Problem Statement
The paper addresses the challenge of scheduling cooperative plant-protection Unmanned Aerial Vehicles (UAVs) in orchard environments characterized by complex terrain and obstacles. Unlike traditional coverage path planning, this study focuses on targeted treatment of discrete disease patches or nutrient-deficiency sites. The core problem is a single-depot, multi-UAV, multi-sortie scheduling task constrained by:

• Endurance and Payload: Limited battery range and pesticide capacity requiring repeated returns to a central depot.
• Obstacle Avoidance: The presence of trees, buildings, and no-fly zones that render Euclidean (straight-line) distances inaccurate for route planning.
• Workload Balance: The need to distribute tasks evenly among a homogeneous fleet to prevent overloading specific UAVs.
• 3D Feasibility: The requirement to generate executable routes that respect terrain clearance, climb-angle limits, and specific working altitudes above the canopy.

Existing methods often evaluate schedules using straight-line distances, which can lead to infeasible or inefficient routes when obstacles are introduced. Furthermore, few studies simultaneously optimize task assignment, visit order, and route realization under these specific 2.5-dimensional constraints.

Methodology
The authors propose a two-stage framework combining a deterministic route realization layer with a metaheuristic scheduling optimizer.

1. Scheduling Model:

   • Objective: A multi-objective function minimizing aggregate travel distance, maximum cumulative per-UAV distance (makespan), and the standard deviation of inter-UAV route lengths (workload balance).
   • Edge Costs: Instead of Euclidean distance, edge costs ($c_{ij}$) are derived from A* search on a static occupancy graph. This ensures that the scheduling algorithm accounts for horizontal detours around obstacles and no-fly zones.
   • Constraints: The model enforces payload limits, maximum sortie length, and single-depot return constraints. A decoder constructs sorties by packing tasks until capacity or range limits are reached.

2. Route Realization (2.5-Dimensional):

   • Horizontal: A* reconstructs collision-free paths between tasks based on the schedule.
   • Vertical: A 2.5D altitude model assigns elevation profiles. The UAV maintains a cruise height ($H_c$) above terrain, descends smoothly to a working altitude ($H_{min}$) above the tree canopy at task sites, and adheres to a maximum climb angle ($20^\circ$).
   • Feasibility Check: The realized 3D spatial distance is calculated post-scheduling and verified against the UAV's endurance limit.

3. Enhanced Walrus Optimizer (CRWO):
   To solve the NP-hard combinatorial scheduling problem, the authors enhance the standard Walrus Optimizer (WO) with three specific strategies:

   • Random Differential Mutation: Uses the difference between the historical best solution and random individuals to direct perturbation, balancing exploration and exploitation.
   • Lens-Imaging Opposition-Based Learning: Generates symmetric candidate solutions across the search space to escape local optima.
   • Discrete Neighbourhood Search: Applied to elite solutions to refine task reassignments and visit priorities.
   • Encoding: A dual-random-key representation encodes both task-to-UAV assignment and visit priority, allowing continuous optimization operators to solve discrete problems.

Key Contributions

• Obstacle-Aware Formulation: The paper formulates a scheduling model where edge costs are precomputed via A* rather than Euclidean distance, ensuring that the optimization objective aligns with executable route costs.
• CRWO Algorithm: The development of an enhanced metaheuristic (CRWO) specifically tailored for high-dimensional, constrained multi-UAV scheduling, demonstrating superior performance over standard WO, PSO, GWO, and others.
• 2.5D Realization Framework: A sequential approach that decouples the 2D scheduling search from 3D route realization, ensuring that generated schedules satisfy terrain clearance and climb-angle constraints without complicating the search space with full 3D dynamics.
• Comprehensive Evaluation: A rigorous benchmarking against eight algorithms across low, medium, and high obstacle densities, including ablation studies to isolate the contribution of specific CRWO components.

Experimental Results
Experiments were conducted on an 800m × 800m orchard map with 50 tasks and 6 UAVs.

• Performance vs. Baselines: In the medium-obstacle scenario, CRWO outperformed the strongest baseline (PSO) by reducing the mean objective value by 3.71%, the maximum cumulative per-UAV spatial distance by 3.70%, and the inter-UAV route-length standard deviation by 47.62%.
• Workload Balance: CRWO consistently achieved the lowest workload variation (standard deviation) across all obstacle densities, indicating superior fleet utilization.
• Feasibility: All realized sorties satisfied endurance, obstacle avoidance, terrain clearance (minimum 5.52m), and climb-angle ($\le 20^\circ$) constraints.
• A vs. Euclidean:* Using A* edge costs did not significantly reduce total aggregate distance compared to Euclidean scheduling but significantly improved workload balance (reducing route-length standard deviation from 50.43m to 23.11m in paired runs).
• Ablation: The study confirmed that the combination of differential mutation, opposition learning, and discrete neighborhood search was necessary to achieve the final performance; removing any component degraded results.

Significance and Claims
The paper claims that CRWO offers a practical scheduling method for static, single-depot plant-protection operations where obstacle avoidance and fleet balance are critical. The authors emphasize that the method is a "balanced scheduler" rather than a pure shortest-path algorithm; its primary value lies in distributing the workload evenly and ensuring safety constraints are met without requiring complex 3D coupling during the optimization phase.

The authors maintain a modest scope, acknowledging that the current framework is limited to static maps, deterministic demands, and homogeneous fleets. They explicitly state that the method does not guarantee a global optimum and that future work is required to address dynamic reassignment, heterogeneous fleets, and uncertainty in flight conditions. The study concludes that while the aggregate distance gains are marginal, the significant improvements in workload balance and safety compliance make CRWO a viable solution for targeted orchard protection.