Capability-Speed-Coupled Mission Planning for Heterogeneous UAV Swarms

Abstract

Heterogeneous UAV mission planning faces a structural tension: multi-capability platforms offer operational versatility but carry heavier payloads and fly slower than single-role UAVs. Prior formulations address parts of this setting, but the joint treatment of capability-speed coupling, a path-planning interface, and soft deadline penalties remains limited. We introduce the Heterogeneous Multi-Type Sortie Task Planning with Time Windows (HMTSPTW) problem, which models a binary capability matrix, payload-informed normalized type speeds, a 3D path-planning interface, task precedence, and soft deadline penalties in a single formulation. We propose an Improved Discrete Particle Swarm Optimization (IDPSO) algorithm with a self-organizing inheritance schedule and capability-aware Variable Neighborhood Descent (VND). Across 1,200 optimizer trials spanning six scales (5–20 targets), IDPSO completes all required sorties in all 12 tested scale-window configurations; the heterogeneous PSO baseline implementation loses task-completion reliability from 10 targets onward, and a three-run no-time-window GA check reports comparable costs, with IDPSO lower at T15–T20. Ablation reveals a scale-dependent pattern: VND dominates at 5 targets (98.8%), whereas the inheritance schedule dominates from 8 to 20 targets (93–98%).