Enterprise AI Analysis

LORS Algorithm: A Multi-Stage Optimization Framework

The Launch Optimizer with Rescheduling and Swapping (LORS) algorithm is a comprehensive solution for the Team-PITH problem. It operates in several stages, building upon an initial solution and progressively refining it:

• Initial Solution: Utilizes a modified VRP solver and k-means clustering to establish initial UGV routes and drone assignments, while considering UGV energy limits.
• Launch Optimizer: Employs a Second-Order Cone (SOC) program to optimize drone launch and land locations, ensuring drones fully recharge and adhere to dynamic limitations. This step is crucial for efficient energy sharing.
• Update Subtour: Transforms each drone's sortie into a Traveling Salesman Problem (TSP) instance, solved by a polynomial-time TSP solver to optimize the sequence of PoI visits within each drone's flight.
• Action-Swap: A heuristic that improves solution quality by cycling through and swapping consecutive action pairs if doing so lowers the PAR, addressing potential "snagged" actions from the Launch Optimizer.

This multi-stage approach, combining various optimization techniques, allows LORS to find robust and efficient patrolling kernels.

Integrated Energy Models and Obstacle Avoidance

Effective collaboration relies on accurate modeling of energy consumption and transfer. The research incorporates detailed energy models for both UGVs and drones, accounting for speed-dependent power consumption. Crucially, a wireless energy transfer model for drone battery recharging on the UGV is included, recognizing that recharge time depends on the energy consumed by the drone. This ensures realistic constraints on mission duration and persistence.

Obstacle avoidance is handled by the Local-Planner() and LO-Obstacles() functions. The Local-Planner pushes actions out of obstacles and finds free-space paths, generating intermediate waypoints where necessary. The LO-Obstacles function refines timing and position using the SOC program with added constraints (square and action-to-action constraints) that prevent actions from re-entering obstacles, maintaining convexity for polynomial-time solvability.

The drone energy transfer model ensures that drones are fully recharged before subsequent sorties, explicitly accounting for the time required based on prior energy consumption. This level of detail is critical for indefinite patrolling missions.

Validation Through Simulation and Physical Prototype

The LORS algorithm's effectiveness was rigorously tested through extensive numerical simulations using four distinct datasets (IncN, IncO, IncMa, IncMg), simulating varying numbers of PoIs, obstacles, drones, and teams. Results consistently showed LORS outperforming baseline and ablation methods, reducing PAR by up to 37.7% and demonstrating robust performance across diverse scenarios.

A real-world case study based on a wind farm inspection scenario demonstrated the practical applicability. For 36 turbines (PoIs) and 15 obstacle areas, LORS computed a solution in 20.3 seconds with a PAR score of 33.1, aligning with simulation expectations. A physical prototype using a Clearpath™ Warthog UGV and custom drone further validated the problem setup, showing successful drone sorties and UGV ferrying operations, despite highlighting the need for future online replanning due to real-world deviations.