CS Paper Radar

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

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

eess.SY ·submitted 2026-09-01 22:58 UTC · v1
published

Abstract

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.

Comment
Accepted for publication in the IEEE Internet of Things Journal
DOI
10.1109/JIOT.2026.3729685

Closest papers

Nearest neighbours by meaning across the whole index.

Joint UAV Activation and Placement for Post-Disaster Wireless Restoration via a Hybrid Quantum-Inspired Evolutionary Framework

cs.NE ·2026-09-07 ·Fatima Azzahraa Amarcha, Lahcen Hassine, Rachid Saadane, Mohamed Rahouti, Rachid Ahl Laamara +2 more
published similarity 0.71
Abstract

In post-disaster environments, the failure of terrestrial communication infrastructure necessitates the rapid deployment of unmanned aerial vehicles (UAVs) as aerial base stations to restore wireless connectivity. This paper addresses the joint UAV activation-and-placement problem in continuous space, with the objective of minimizing the number of deployed UAVs while satisfying coverage and minimum-separation constraints. To solve this problem, we propose a Hybrid K-means Quantum-Inspired Evolutionary Algorithm (HKQEA) that combines K-means-guided initialization, a calibrated penalty-based feasibility objective, non-elitist evolutionary search, and a quantum-inspired learning update. Experimental results over 50 independent runs show that HKQEA attains a best fully feasible solution with 8 UAVs, while achieving average values of 98.94\% for coverage, 99.94\% for non-overlap, and 99.68\% for minimum-distance satisfaction. Comparative evaluation against standard Non-dominated Sorting Genetic Algorithm II (NSGA-II), Particle Swarm Optimization algorithm (PSO) and an elitist variant of HKQEA further shows that the proposed method provides a more favorable balance among exploration, convergence behavior, and reliable feasibility preservation in constrained deployment problems. An illustrative procurement-level cost analysis also indicates that reducing the fleet from 10 UAVs to 8 can yield a 20\% reduction in hardware count, corresponding to a simplified savings ratio of 25\% for the studied deployment setting. These results demonstrate the potential of the proposed framework for resource-efficient post-disaster communication restoration.

0.29

Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing

cs.ET quant-ph ·2026-10-14 ·Silvie Illésová, Vojtěch Novák, Martin Beseda
similarity 0.64
Abstract

Drone-delivery planning combines routing decisions with operational constraints such as payload capacity and limited onboard energy, resulting in combinatorial optimization problems that can become costly to encode directly in binary form. This work investigates a hybrid quantum--classical approach in which candidate drone missions are generated and evaluated classically before constructing a quadratic unconstrained binary optimization (QUBO) model for mission selection. Payload- and energy-infeasible missions are removed during preprocessing, while the reduced QUBO is solved using exact enumeration, simulated annealing (SA), and the Quantum Approximate Optimization Algorithm (QAOA), with mixed-integer linear programming (MILP) used as a classical reference. Experiments on controlled synthetic delivery instances evaluate solution quality, the effect of preprocessing, and computational scaling. Exact QUBO optimization reproduces the MILP optimum on the evaluated small instances, while SA achieves $100\%$ feasibility with a median optimality gap of $0\%$. Combined payload-and-energy preprocessing reduces the mean number of QUBO variables by $29.60\%$ and quadratic interactions by $49.20\%$, while reducing mean SA runtime by $31.26\%$. In contrast, the evaluated shallow statevector-based QAOA configuration achieves lower feasibility and is restricted to small QUBO instances. These results indicate that, in the considered setting, the main practical benefit of the hybrid architecture comes from classical feasibility preprocessing that reduces the binary search space before QUBO-based optimization.

0.09

Quantum Annealing for Resource Allocation in Next-Generation Wireless Communication Networks: A QUBO Modeling Guide

cs.IT ·2026-10-09 ·Nguyen Xuan Tung, Le Tung Giang, Mai Dinh Cong, Pham Dang Anh Duc, Nguyen Hoang Viet +2 more
published similarity 0.64
Abstract · 16 pages, 5 figures, and 7 tables. Accepted by OJ-COMS

Quantum annealing (QA) offers a physics-inspired approach for such subproblems by mapping them onto an Ising Hamiltonian, which is algebraically equivalent to a Quadratic Unconstrained Binary Optimization (QUBO) model executable on quantum annealers or hybrid solvers. However, their practical employment in wireless systems critically depends on the specific problem formulation, on the particular variable encoding, constraint handling, solver selection, hardware embedding, and fair benchmarking. This paper develops wireless-oriented QUBO modeling guidelines for QA-assisted resource allocation. We first present a beginner-friendly toy example in which a terrestrial-aerial resource-allocation problem with a fractional signal-to-interference-plus-noise ratio (SINR) maximization objective is reformulated into a two-bit QUBO via Boolean interpolation, converted into an Ising representation, and decoded back into a wireless scheduling decision. The same scheduling is applicable to UAV, aircraft, satellite, and terrestrial links in SAGIN systems. We then review the QA foundations and solver ecosystems, including binary quadratic, discrete quadratic, constrained quadratic, and hybrid models from the perspective of NG wireless optimization. Furthermore, we discuss both binary and discrete encoding, penalty-based constraint conversion, embedding overhead, solution decoding, and feasibility verification. A QUBO Compatibility Index is introduced as a lightweight diagnostic metric for assessing the associated QUBO formulation readiness, rather than a predictor of runtime or solution quality. Finally, a case study on max-min uplink power control in cell-free massive MIMO illustrates how a fairness-oriented wireless problem can be discretized, constrained, converted into the concept of a QUBO, and evaluated against classical baselines. A host of key challenges and future directions are also discussed.

0.23

Net-Zero Power UAVs: Facilitating Quantum HRLLC in Multi-Hop UAV Repeaters

eess.SY ·2026-10-16 ·Ali Ranjha, Georges Kaddoum, Halim Yanikomeroglu
publishedbenchmarkhot direction similarity 0.64
Abstract · 5 pages. Published in IEEE Wireless Communications Letters. This work was supported by the Postdoctoral Research Fellowship from the Fonds d…

In this paper, we propose a novel joint optimization framework for autonomous, quantum-enabled UAV repeater networks designed to support hyper-reliable low-latency communications (HRLLC) in challenging environments such as post-explosion chemical plant operations. The proposed system uses a symmetric dual-UAV architecture with three sequential quantum channels operating under strict energy harvesting (EH) constraints. We formulate a highly challenging non-convex mixed-integer non-linear programming (MINLP) problem. This model jointly determines qubit allocation, 2-D uncrewed aerial vehicle (UAV) spatial positioning (distance and altitude), and transmit powers to minimize the total decoding error. Crucially, our framework explicitly models real-world quantum physics, including decoherence, gate imperfections, and entanglement degradation. Since the objective function is demonstrably non-convex, to efficiently solve the MINLP, we propose a quantum-resource-optimized GA (QRO-GA). The results of our numerical simulations show that the QRO-GA yields better results than benchmark methods and it is highly efficient, with the convergence speed significantly increasing with the total qubit allocation. Convergence is achieved in as few as 5 iterations for higher qubit allocation. Moreover, the results reveal a critical U-shaped tradeoff, proving that an optimal latency distribution within a strict $80\ μ$s transmission window is strictly required to maintain HRLLC reliability. In addition, we find that the QRO-GA successfully optimizes the 2-D UAV positioning to minimize total decoding error. Finally, it balances consumed and harvested power to achieve net-zero power UAVs system.

0.40

Polyhedral RIS Architecture with Quantum-Assisted Facet Selection for Uniform Coverage

cs.IT eess.SY ·2026-10-23 ·Noha Hassan, Halim Yanikomeroglu
similarity 0.60
Abstract · This work has been submitted to the IEEE WCL for possible publication. Copyright may be transferred without notice, after which this version…

Reconfigurable intelligent surfaces (RISs) direct coverage toward moving user equipment (UE), but practical deployments involve discrete phase control, uncertain facet positions, and UE mobility, which require the problem to be re-solved continually. We consider these challenges for the chamfered hexagonal polyhedral RIS, which provides nearly uniform coverage. With both incidence and departure angles, we bound in closed form the gain loss of its best facet relative to the best possible reflecting facet, include the known b-bit quantization loss, and extend the bound to joint random mounting errors of all facets. For a precoded multi-user downlink, each facet-selection subproblem of the max-min rate design is shown to be an exact quadratic unconstrained binary optimization (QUBO) problem, suited to repeated time-constrained solving. The deployment of the base station in relation to the RIS allows the polyhedral surface to bring down the percentage of dead zones in vertical planar panels from 77% to 0.3% and increase the minimum rate by 34% relative to the STAR panel. The simulated annealing algorithm finds the optimum solution in 95% of the cases. The quantum approximation algorithm fails to do so.

0.26

Terrain-Aware Thompson Sampling for Multi-Drone Search and Rescue

cs.RO ·2026-11-10 ·Riana Gagnon Souleiman, Giovanni Beltrame
published similarity 0.58
Abstract · Accepted to the 18th International Symposium on Distributed Autonomous Robotic Systems (DARS 2026)

In this work, we propose a decentralized terrain-aware multi-drone Thompson Sampling algorithm tailored for search and rescue (SAR) applications. A probability distribution of locating a lost person is informed by terrain data, using established SAR models (displacement ring, elevation, watershed, dispersion angle, and track offset) derived from historical SAR case data on lost person behavior. Exploration is conducted by a team of drones using Thompson Sampling, where candidate actions are selected by drawing samples from this probability distribution, represented by a per-cell Gaussian posterior whose mean and variance are updated through Bayesian inference. This approach balances exploration of uncertain regions with exploitation of high-probability areas to locate a lost person. Observation uncertainty is incorporated through fractional forest coverage, which measures the percentage of an observation occluded by tree coverage and accounts for reduced detection performance in densely vegetated areas. Simulations using real SAR case data (YOSAR) evaluate the proposed method against a coverage planner and a probabilistic active search method in search regions of 1.5 and 3.8 square kilometers, with 5, 10, 15, and 20 agents flying at 50 km/hr. We demonstrate that our method achieves a success rate of approximately 87% within 60 to 247 seconds in the 1.5 square kilometer region, and success rates of approximately 75% to 91% within 161 to 466 seconds in the 3.8 square kilometer region, across different agent configurations.

0.36

GPU-Accelerated Quantum Annealing-Inspired UAV Path Planning for Smart Agriculture

cs.ET eess.SY ·2026-08-26 ·Maho Hirahara, Aohan Li
similarity 0.57
Abstract · 6 pages, 3 figures, conference

With the rapid advancement of smart agriculture, Unmanned Aerial Vehicles (UAVs) have become indispensable for efficient coverage and path planning in grid-mapped agricultural fields. However, optimizing UAV flight paths in large-scale environments remains a complex Nondeterministic Polynomial-time (NP)-hard problem. Traditional path planning methods are often constrained by local optima, limited scalability, and slow convergence, which significantly restrict their effectiveness in solving large-scale problems. To address these limitations, this paper proposes a novel optimization framework utilizing a Graphics Processing Unit (GPU)-parallelized Ising solver. Our method mimics the operational principles of quantum annealing on GPU hardware, enabling rapid search for the minimum-energy state of Ising models. Unlike physical quantum devices, which are often constrained by the number of qubits, our approach leverages the Fixstars Amplify (FA) platform to perform parallel annealing on highly parallelized GPUs. This enables the simultaneous evaluation of thousands of potential path candidates and vast state transitions. By leveraging large-scale parallel processing, this framework's core strength lies in minimizing computation time even as the problem scale increases. Simulation results demonstrate that our proposed method consistently identifies superior flight paths while maintaining stable computational performance compared with the genetic algorithm and simulated annealing method.

0.29

A two-stage approach to satellite constellation optimization: classical and QUBO formulations

eess.SY math.OC ·2026-10-01 ·Carlo Novara
similarity 0.57
Abstract · 17 pages, 1 figure, 1 table

The design of satellite constellations for Earth observation requires balancing spatial coverage, revisit time, cost, and operational complexity. This paper considers the problem of designing the orbits of a given number of Low Earth Orbit (LEO) or Very Low Earth Orbit (VLEO) satellites to maximize the spatial and temporal resolution achieved over a prescribed set of ground targets. This kind of problem is inherently nonconvex and possibly combinatorial, making its solution computationally demanding for large constellations and target sets. To address this challenge, we propose a two-stage optimization strategy that separates spatial-coverage design from temporal-resolution optimization, thereby reducing the complexity of the overall problem. Two variants of the method are developed. The first employs continuous decision variables during the spatial-optimization stage, whereas the second discretizes these variables and reformulates the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The latter formulation enables the use of efficient classical QUBO solvers and is directly compatible with quantum-annealing hardware. The proposed framework provides a scalable approach to the design of heterogeneous LEO and VLEO Earth-observation constellations and establishes a pathway for exploiting emerging quantum-optimization technologies in satellite mission design. Preliminary simulation results are presented to demonstrate the effectiveness of the strategy.

0.26