PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum-Based k-Coverage Optimization for UAV-Aided Search and Rescue Missions

Halim Lee, Suhui Jeong, Na Young Kim, Jiwon Seo

arXiv:2609.01930v1eess.SY

TL;DR

Large-scale SAR requires efficient waypoint selection to provide threefold coverage across complex terrains. This paper formulates the task as an extended k-coverage QUBO and evaluates QAOA on simulation and IBM’s Eagle processor, achieving over 95% 3-coverage in real-hardware experiments while characterizing current limitations.

  • Problem

    Large-scale disasters scatter missing persons across vast, complex terrains, making rapid and efficient SAR searches challenging.

  • Method

    The paper formulates UAV waypoint selection as extended k-coverage, derives an exact-penalty QUBO, and evaluates it with QAOA on simulation and IBM’s 127-qubit Eagle processor.

  • Results

    QAOA recovered known minimum-cardinality solutions in tested noise-free instances and achieved over 95% 3-coverage across real-hardware experiments.

  • Takeaways & Limitations

    The study establishes a solver-independent QUBO formulation for RF-based SAR waypoint selection and characterizes its implementation on current gate-based quantum hardware.

  • Takeaways & Limitations

    The controlled static single-UAV setting does not establish quantum advantage, while tested hardware accommodates approximately 40 candidate waypoints.

Abstract

from arXiv · show

In large-scale disaster scenarios, rapid localization of missing persons is a critical challenge for search-and-rescue (SAR) operations. Unmanned aerial vehicles (UAVs) equipped with radio frequency (RF) receivers can support RF-based localization by collecting signals emitted from mobile devices at spatially distributed sensing locations. This paper addresses the resulting waypoint-selection problem: determining a minimum set of UAV waypoints that provides at least threefold coverage of every potential target location. We formulate this task as an extended k-coverage problem that independently defines the UAV-navigable and target regions, and derive an exact-penalty quadratic unconstrained binary optimization (QUBO) formulation with a sufficient penalty condition that preserves feasibility and minimum waypoint cardinality. The QUBO is mapped to an Ising-form cost Hamiltonian and evaluated using the quantum approximate optimization algorithm (QAOA) on both a noise-free simulator and IBM's 127-qubit Eagle processor. On the tested simulator instances, QAOA recovers the known minimum-cardinality solutions. Across the rectangular hardware test cases, the mean 3-coverage ratio exceeded 95%. In the campus-scale evaluation, ten hardware executions achieved 99.3% mean 3-coverage with a 90% feasible-run rate, while the shortest feasible flight path was up to 37.0% shorter than those of the deterministic grid-based baselines. Additional comparisons with classical optimization and learning-based baselines are provided, together with computational and quantum-resource analyses for larger generated instances. These results establish an exact QUBO representation for RF-based SAR waypoint selection and characterize its implementation on current gate-based quantum hardware.

I. INTRODUCTION

RF-equipped UAVs can support localization of disaster victims, but SAR waypoint planning must balance sufficient spatial measurements against flight cost. This work formulates the task as an extended k-coverage problem and develops an exact-penalty QUBO evaluated with QAOA and classical baselines.

  • Motivation: Large-scale disasters scatter missing persons across complex terrains, creating demand for autonomous, scalable, real-time SAR strategies.The paper cites 393 natural-hazard disasters in 2024, affecting 167.2 million people.
  • Motivation: RF signals from mobile devices offer an alternative sensing modality for individuals who may be difficult to detect with cameras, thermal imaging, or radar.UAVs can collect Wi-Fi probe requests or cellular uplink signals at spatially distinct waypoints.
  • Problem: Waypoint planning seeks the minimum set of spatially distributed UAV locations that provides sufficient coverage for localization while limiting flight path and mission duration.Insufficient coverage may yield too few measurements, whereas each additional waypoint increases travel cost.
  • Problem: The waypoint-selection problem is NP-hard, although exact classical optimization remains effective at the tested quantum-hardware instance sizes.The campus-scale exact ILP solution is reported to run in well under a second.
  • Contributions: The paper separates UAV-navigable and target regions in an extended k-coverage formulation, allowing waypoints inside or outside the target region.The formulation reduces to conventional k-coverage when the two regions coincide.
  • Contributions: An exact-penalty QUBO uses logarithmic-size slack encoding and guarantees feasibility and minimum waypoint cardinality when λ > |W|.The resulting QUBO is mapped to an Ising Hamiltonian and solved with QAOA on a simulator and IBM’s 127-qubit processor.
  • Evaluation: The evaluation combines real-hardware experiments with classical exact, heuristic, metaheuristic, and learning-based baselines plus computational and quantum-resource analyses.The paper positions the work as a formulation and implementation study rather than only a quantum-algorithm comparison.

III. QUANTUM ALGORITHM FOR UAV WAYPOINT OPTIMIZATION

The framework discretizes the search environment into a triangular lattice, distinguishes navigable waypoints from possible target locations, and selects a minimum waypoint subset achieving k-coverage. The resulting extended problem generalizes conventional k-coverage and is solved through QUBO-based QAOA.

  • Framework: The workflow has three phases: mission setup, quantum optimization, and field execution for UAV planning and RF-based localization.Mission setup produces W and G; quantum optimization selects the waypoint subset.
  • Extended k-coverage problem: The localization setting uses k = 3 because two spatial coordinates and one additional modality-dependent scalar motivate three spatially distinct measurements.The paper notes that practical localization also depends on sensing geometry, noise, and model validity.
  • Extended k-coverage problem: The search area A is divided into a UAV-navigable region U and a target region T, which may overlap but need not coincide.U represents accessible ground projections, while T contains possible missing-person locations.
  • Discretization: UAV ground coverage is analyzed in two dimensions using the projected radius r = √(l^2 − h^2), determined by communication range l and altitude h.This geometric projection connects the three-dimensional flight setting to the planar optimization model.
  • Discretization: A triangular lattice with spacing δ generates indexed grid points that can serve as candidate waypoints, target locations, or both.Each point has a sequential index and axial coordinates for optimization and geometry.
  • Extended k-coverage problem: W contains grid points in U, whereas G contains grid points in T, including target points located in inaccessible areas such as buildings.Candidate UAV waypoints can therefore lie above or around structures while targets remain inside them.
  • Extended k-coverage problem: The extended k-coverage problem selects a minimal O ⊆ W so every target point in G lies within radius r of at least k distinct selected waypoints.When U = T, the formulation reduces exactly to conventional k-coverage and remains NP-hard.

B. QUBO formulation

The QUBO formulation encodes waypoint minimization and coverage requirements using binary decisions, waypoint coverage sets, and per-target covering-neighbor sets. It assumes every target has at least k eligible covering waypoints before construction.

  • B. QUBO formulation: The QUBO reformulation defines a binary decision vector, represents coverage with sets, and converts the constrained problem into an unconstrained quadratic objective.These are the three stated construction steps.
  • 1) Objective Function:: Each binary variable x_i indicates whether candidate waypoint p_i is selected, and minimizing Σx_i minimizes the total waypoint count.The decision vector has dimension |W|.
  • 1) Objective Function:: For each waypoint p_i, the coverage set C_i contains target grid points in G within distance r.The set representation restricts coverage to target points inside the waypoint’s radius.
  • 2) Coverage Constraint:: For each target p_j, the index set N_j identifies candidate waypoints that can cover that target.Coverage eligibility is determined by the distance relation used to construct C_i.
  • 2) Coverage Constraint:: The model requires every target point to be covered by at least k selected waypoints and excludes instances with |N_j| < k.Such instances are infeasible before QUBO construction.
  • 2) Coverage Constraint:: Figure 3 depicts UAV measurement waypoints, target locations, separate U and T regions, and radius-based coverage sets C_i.Its panels connect the physical RF-localization setting to the grid-based optimization representation.

3) QUBO Model:

The constrained coverage problem is converted to QUBO by introducing binary-encoded slack variables for coverage surplus and penalizing violations. A sufficient common penalty condition provides exactness, after which the QUBO is mapped to an Ising Hamiltonian for QAOA.

  • 3) QUBO Model:: Nonnegative slack variables s_j convert each minimum-coverage inequality into an equality by representing surplus coverage.The slack variables are jointly optimized with waypoint decisions.
  • 3) QUBO Model:: Each s_j is binary encoded over its feasible range, whose maximum is n_j − k with n_j = |N_j|.The encoding is designed to fit the QUBO’s binary-variable structure.
  • 3) QUBO Model:: The minimum number of slack bits is B_j = ⌈log2(n_j − k + 1)⌉.This logarithmic encoding represents the required surplus range.
  • 3) QUBO Model:: The QUBO penalty discourages infeasible coverage configurations while optimizing the binary waypoint-selection vector.The penalty is applied to violations of the k-coverage requirement.
  • 3) QUBO Model:: For the canonical uniform-penalty QUBO, λ > |W| guarantees that every global minimizer is feasible and has minimum waypoint cardinality.The paper provides a formal proof in Proposition 2 of the supplementary material.
  • 3) QUBO Model:: Experimental QUBOs used Qiskit’s automatic penalty selection, so the common-λ exactness condition applies specifically to the canonical formulation and controlled sensitivity study.Different conversion stages may receive different automatically selected coefficients.
  • 3) QUBO Model:: The binary variables map to Pauli-Z operators, and the resulting cost Hamiltonian combines mapped cardinality and quadratic coverage-penalty terms.Identity-proportional terms are dropped as global energy offsets.
  • 3) QUBO Model:: The total qubit count is n = |W| + ΣB_j, and the standard X-mixer is used in the depth-p QAOA ansatz.The Hamiltonian and mixer define the QAOA circuit used for optimization.

IV. SIMULATOR-BASED FEASIBILITY AND OPTIMALITY VALIDATION

Noise-free simulator experiments evaluated eight varied SAR waypoint scenarios under a 34-qubit resource limit. QAOA returned feasible minimum-cardinality solutions for 3-coverage in every scenario.

  • Simulation configuration: The simulator used QAOA depth p = 2 and 1024 shots per objective-function evaluation in the baseline configuration.COBYLA performed the classical optimization stage with an objective-function evaluation budget of one per run.
  • Resource constraints: Simulator instances were limited to at most 34 qubits because available GPU memory constrained state-vector simulation.Larger target areas or finer grids increase decision and slack variables, quickly exceeding the available qubit budget.
  • Test scenarios: The eight scenarios varied in convexity, grid density, and whether candidate waypoints lay within or beyond target-region boundaries.The communication radius was fixed at r = 35 m across scenarios.
  • Simulator evaluation: In every scenario, QAOA selected a feasible waypoint set providing at least threefold coverage of every target grid point.The evaluation covered eight geometrically and spatially varied scenarios.
  • Simulator evaluation: In every scenario, the selected waypoint count matched the known minimum required for 3-coverage.This established optimality under ideal, noise-free simulation conditions.
  • Robustness analysis: For scenario (g), stronger noise reduced feasible and globally minimum-cardinality sample fractions, while tested penalty values above λcrit = 0.5 retained feasible minimum-cardinality best-of-sample solutions.Shot-count changes mainly reduced run-to-run dispersion, and sensitivity effects appeared primarily in sampled distributions rather than retained solution quality.

V. EVALUATION ON REAL QUANTUM HARDWARE

The evaluation tests QAOA for RF-based SAR waypoint selection on IBM’s Eagle processor, measuring coverage, mission efficiency, and waypoint-selection quality. Hardware experiments maintain high 3-coverage, while path and solver comparisons expose trade-offs with deterministic, classical, and learning-based methods.

  • A. Coverage satisfaction: Ten Eagle-processor executions achieved over 95% 3-coverage across rectangular scenarios despite hardware noise.The scenarios contained 8–23 target grid points and 18–39 candidate waypoints.
  • A. Coverage satisfaction: The rectangular hardware experiments used target regions from 100 m × 87 m to 250 m × 130 m, discretized with triangular lattices and boundary-margin points.The largest example had |W| = 39 candidate waypoints and |G| = 22 target grid points.
  • B. Mission efficiency versus SAR deployment methods: The framework explicitly selects a minimal subset from a finer triangular lattice, unlike baselines that use constructed geometric grids directly as waypoint sets.The study used δ = 55 m for the proposed lattice under available-qubit constraints.
  • B. Mission efficiency versus SAR deployment methods: The proposed QAOA reduced total path length by 22.5% versus LocalizerBee and 37.0% versus Yuan et al., while selecting fewer waypoints.Against PPO-RL, QAOA selected 18 versus 11 waypoints and produced a 1323.83 m versus 1129.36 m path.
  • C. Waypoint-selection quality against classical solvers: At the tested scale, ILP found the optimal seven-waypoint solution in 0.04 s, whereas QAOA returned an 18-waypoint feasible solution in approximately 30.5 s.Greedy, QUBO-SA, and QUBO-GA each returned eight-waypoint feasible solutions.
  • C. Waypoint-selection quality against classical solvers: In cross-domain comparison, QAOA achieved a 90% feasible rate and 99.3% mean 3-coverage, versus 60% and 97.1% for PPO-RL.The comparison reflects different paradigms: training-free per-instance optimization versus a policy trained on other environments.

VI. COMPUTATIONAL RUNTIME AND COMPLEXITY

The section characterizes measured QAOA runtime and the growth of preprocessing, QUBO, Hamiltonian, and resource requirements. Runtime rises approximately linearly over the tested waypoint range, but the paper treats this as an empirical executability trend rather than an asymptotic advantage.

  • A. Measured runtime: QAOA execution time increased from 12.9 s to 30.5 s as candidate waypoints grew from 18 to 39.The measured trend was approximately linear over the tested rectangular instances.
  • A. Measured runtime: The reported runtime trend does not establish general asymptotic linear scaling because sampling, evaluations, routing, and compiled depth may vary with problem size.The paper interprets the measured increase as an empirical trend over |W| = 18–39.
  • A. Measured runtime: Runtime comparisons are practical reference values because methods ran on heterogeneous platforms and represented different computational stages.QAOA, classical optimization, deterministic construction, and PPO-RL include different execution or training assumptions.
  • B. Computational complexity: Triangular-lattice generation requires O(P) time, while direct waypoint–target coverage construction requires O(|W||G|) distance evaluations.QUBO construction additionally expands target-specific squared penalties using local interaction sizes.
  • B. Computational complexity: Under fixed-density conditions, the number of qubits and nonzero QUBO coefficients grows linearly with candidate waypoints when |G| = Θ(|W|).Sparse Hamiltonian construction requires O(n+M_Q) time and storage after QUBO-to-Ising transformation.
  • C. Quantum-resource analysis: The framework analyzes logical circuit width, nonzero QUBO coefficients, circuit depth, and optimization-resource growth for instances containing up to 1,992 candidate waypoints.These analyses are formulation-level resource estimates rather than demonstrations on hardware at that size.

A. Qubit estimation

The qubit estimate accounts for one decision variable per candidate waypoint and binary slack variables for each target’s coverage constraint. Circuit-depth estimates then depend on the aggregated ZZ-interaction graph and its maximum logical degree.

  • A. Qubit estimation: Each candidate waypoint uses one decision qubit, while each target point receives slack bits encoding coverage-constraint slackness.For target j, the slack count is B_j = ⌈log2(|N_j| − k + 1)⌉.
  • A. Qubit estimation: The total logical-qubit estimate combines |W| decision qubits with slack variables determined by target neighborhoods N_j.A practical upper bound uses N_max = max_j |N_j|.
  • B. Interaction structure: The cost Hamiltonian contains single-qubit Z terms and two-qubit ZZ interactions, with ZZ terms determining parallelization constraints.Single-qubit terms can be applied in parallel, whereas ZZ gates sharing a qubit cannot execute simultaneously.
  • B. Interaction structure: Coverage penalties generate decision–decision, slack–slack, and decision–slack ZZ interactions for each target neighborhood.After aggregation, repeated decision-qubit pairs become single distinct ZZ terms.
  • C. Circuit depth: Edge coloring schedules one cost layer in Δ⋆ or Δ⋆ + 1 parallel ZZ rounds, where Δ⋆ is the maximum logical interaction degree.The resulting ideal p-layer depth scales with this interaction degree.
  • C. Circuit depth: For the campus scenario, 39 decision and 59 slack variables produced 98 logical qubits, 1,556 distinct ZZ interactions, and Δ⋆ = 85.An 85-round edge coloring gives 255 logical ZZ-interaction rounds for p = 3.

C. Large-Scale Resource Scaling

Under fixed-density area expansion, the QUBO representation and logical circuit width grow approximately linearly with candidate-waypoint count, but the largest generated instances exceed current hardware capacity. The study therefore distinguishes formulation-level resource scaling from executable QAOA performance and identifies modeling, hardware, and operational boundaries.

  • Resource scaling: Approximately linear scaling applies to both the binary-variable count n and nonzero QUBO coefficients M_Q as |W| increases under fixed-density geometric expansion.This scaling characterizes the QUBO representation and circuit width, not end-to-end QAOA runtime.
  • Resource scaling: 7,535 binary variables and 68,751 nonzero QUBO coefficients arise in the largest generated instance with 1,992 candidate waypoints and 1,863 target grid points.A monolithic implementation would require at least 7,535 qubits before additional hardware or fault-tolerance overhead.
  • Scope and limitations: The present evaluation uses a controlled, static, single-UAV SAR setting and does not establish quantum advantage over classical optimization.At the tested scale, classical exact and heuristic solvers achieve equal or better solution quality and generally shorter runtimes.
  • Scope and limitations: RF coverage is modeled using sufficiently accurate coverage relations and candidate-region knowledge, although disaster conditions can make coverage spatially nonuniform or stochastic.NLOS propagation, multipath, debris, interference, communication interruptions, and ranging uncertainty motivate reduced effective radii, redundancy, or site-specific models.
  • Hardware limits: Current IBM Eagle experiments accommodate approximately 40 candidate waypoints, while slack variables, QUBO interactions, circuit depth, and transpilation overhead increase with problem size.Restricted device connectivity further increases compiled circuit depth.
  • Future extensions: Multi-UAV coordination, dynamic targets, changing environmental information, and realistic energy or mobility constraints remain extensions requiring additional assignment, routing, or receding-horizon optimization.Online use depends on whether optimization latency remains sufficiently small relative to environmental change.

APPENDIX A NP-HARDNESS OF THE EXTENDED k-COVERAGE

The extended k-coverage problem is NP-hard because it strictly generalizes conventional k-coverage. The appendix also proves that, under a sufficient penalty condition, minimizing the QUBO is equivalent to minimizing waypoint cardinality over feasible solutions.

  • NP-hardness: The extended k-coverage problem is NP-hard because conventional k-coverage is recovered when the UAV-navigable and target regions coincide.Thus, the extended formulation strictly generalizes an NP-hard problem.
  • NP-hardness: Any exact algorithm for extended k-coverage would also solve conventional k-coverage as a special case.This follows directly from the reduction used to establish NP-hardness.
  • QUBO exactness: If λ > |W| and the slack encoding represents every feasible excess-coverage value, every global QUBO minimizer is feasible.Feasible assignments can achieve zero penalty under the stated encoding assumption.
  • QUBO exactness: For feasible assignments, minimizing the QUBO is equivalent to minimizing the original objective over the feasible set.The penalty terms can be eliminated for feasible solutions, leaving the cardinality objective.
  • QUBO exactness: Infeasible assignments incur a positive penalty because at least one violated coverage constraint cannot be satisfied by nonnegative binary slack variables.The violated constraint's squared residual is at least 1.
  • QUBO exactness: Consequently, global QUBO minimizers correspond exactly to minimum-cardinality feasible solutions of the extended k-coverage problem.The proof combines exclusion of infeasible minimizers with penalty elimination for feasible assignments.

PARAMETER SENSITIVITY

The appendix evaluates QAOA convergence, execution stability, calibration-derived noise, and distribution-level behavior under a fixed scenario and reference configuration. Best-of-shots outcomes remain optimal, while noise mainly redistributes sampled probability mass.

  • The reference configuration uses p = 2, 1024 shots per evaluation, COBYLA, and a one-evaluation budget.
  • 100% feasibility, 100.00% mean 3-coverage, five selected waypoints, and a 1.000 approximation ratio were invariant across tested configurations.These BoS metrics were reported with zero standard deviation.
  • 48 objective-function evaluations were sufficient for COBYLA to satisfy its stopping criterion under the tested convergence configuration.The recorded objective history was nonmonotonic because it included exploratory evaluations rather than only incumbent solutions.
  • Ten independent executions each returned a feasible globally optimal five-waypoint solution with 100% 3-coverage and approximation ratio 1.000.Different waypoint sets represented objective-equivalent global optima rather than changes in solution quality.
  • 100% mean 3-coverage and feasible rate persisted across all tested noise exposures, although Pfeas decreased from 10.45 ± 1.78% to 8.97 ± 1.06%.At η = 3, mean Popt was 2.95%, showing that optimal decisions remained represented in approximately 30 shots per execution.
  • The unchanged BoS results demonstrate robustness only for scenario (g) with 1024 shots, not general noise tolerance of QAOA.The fixed-circuit experiment does not capture additional error locations and duration in larger or deeper circuits.

D. Hyperparameter Sensitivity

Hyperparameter sensitivity examines QAOA depth and penalty selection, including the exactness boundary for scenario (g). Application-level quality is stable above the penalty threshold, while probability distributions can vary independently of retained BoS solutions.

  • 1) QAOA Layer Depth: At p ∈ {1, 2, 3}, every noise-free execution retained a globally optimal waypoint solution, so BoS quality saturated at p = 1.
  • 1) QAOA Layer Depth: Mean Popt increased from 3.12% at p = 1 to 4.42% at p = 3, without improving retained BoS quality.BoS already retained a global optimum in every execution at p = 1.
  • 1) QAOA Layer Depth: Increasing QAOA depth may alter Pfeas nonmonotonically because QAOA minimizes expected QUBO objective rather than Pfeas or Popt directly.Additional layers can also increase exposure to cumulative gate errors and decoherence on noisy hardware.
  • 2) Penalty Coefficient: The sufficient condition λ > |W| guarantees exactness, whereas scenario (g) has the tighter instance-specific threshold λcrit = 0.5.
  • 2) Penalty Coefficient: λ < 0.5 favors an infeasible four-waypoint assignment, λ = 0.5 permits a tie, and λ > 0.5 ensures strict instance-level exactness.At λ = 0.25, the observed feasible rate was 0% and mean 3-coverage was 33.33%; above the boundary, all ten executions were feasible.

3) Objective-Function Evaluation Budget:

The appendix studies evaluation budget, classical optimizer, shot count, and PPO-RL formulation details. BoS solutions remain optimal across tested budgets and optimizers, while probability estimates show budget- and sampling-dependent variability.

  • 3) Objective-Function Evaluation Budget: Every tested evaluation budget from 1 to 50 retained a globally optimal minimum-cardinality solution with full 3-coverage in every execution.
  • 3) Objective-Function Evaluation Budget: Mean Pfeas increased from 10.23% ± 2.03% at one evaluation to 19.74% ± 23.08% at 50 evaluations.The 9.51-percentage-point increase coincided with greater run-to-run dispersion.
  • COBYLA and SPSA produced nearly identical mean Popt values, 3.36 ± 0.78% and 3.35 ± 0.89%, respectively.SPSA had lower Pfeas dispersion, while COBYLA reached higher feasible-state concentration in some runs.
  • Across 256 to 4096 shots, mean Pfeas stayed between 10.16% and 10.32%, while Pfeas standard deviation decreased from 2.46 to 1.61 percentage points.Higher shot counts reduced finite-sampling variability with little change in mean output probabilities.
  • PPO-RL models waypoint selection as a finite-horizon sequential decision process in which the agent selects waypoints or issues STOP.
  • The PPO-RL state combines waypoint and target features, including coordinates, selection status, coverage gains, deficits, counts, and validity indicators.

B. Network Architecture, Hyperparameters, and Training

PPO-RL is trained under cross-domain and in-domain regimes using a shared sequential decision formulation, then assessed alongside classical baselines built from common coverage preprocessing. Cross-domain training reaches full feasibility and coverage while reducing waypoint count and path length on held-out instances.

  • B. Network Architecture, Hyperparameters, and Training: Cross-domain PPO-RL training uses 23 configurations from two campuses over 200,000 steps, with randomized grid spacing, communication range, and altitude.The Yonsei University International Campus evaluation scenario was geographically distinct and unseen during training.
  • B. Network Architecture, Hyperparameters, and Training: In-domain training includes the evaluation instance and therefore serves as an upper-bound reference rather than a held-out generalization result.
  • C. Training Convergence: By 200,000 steps, cross-domain validation reached 100% feasibility and 100% mean 3-coverage on held-out instances.Feasibility was already 96.7% at 10,000 steps.
  • C. Training Convergence: Mean selected waypoints decreased from 7.1 to approximately 3.3, while mean path length decreased from 330 m to approximately 131 m during training.The appendix relates the path-length reduction to the decreasing waypoint count.
  • APPENDIX E CLASSICAL BASELINE IMPLEMENTATIONS: All classical baselines use the same candidate waypoints, targets, and coverage sets, isolating differences to the optimization method.
  • APPENDIX E CLASSICAL BASELINE IMPLEMENTATIONS: The exact baseline solves the constrained waypoint problem as a binary integer linear program and uses its cardinality as the optimality reference.
Loading 2609.01930v1…