Proceedings of the AAAI Symposium Series
A Feasibility-Aware HUBO/QUBO Benchmark for UAV Obstacle-Avoidance with Visibility Cost
Muhammad Ibrahim, Ali Mohammadi, Farrokh Janabi‐Sharifi, Ulrike Stege, Demetros Tareke, Prashanti Priya Angara
Abstract
Quantum-assisted UAV path planning has recently been studied using QAOA-style obstacle-avoidance formulations, but a low-energy binary sample is not necessarily a valid UAV trajectory. This paper presents a feasibility-aware evaluation protocol on one discrete 8 × 8, L = 20 UAV grid-planning instance with obstacle avoidance, a line-of-sight visibility cost, and a higher-order temporal buffer-risk term. The horizon L denotes discrete planning layers, not physical seconds. The model uses binary variables x_{t,v} indicating whether the UAV occupies cell v at time layer t and forms a HUBO objective with one-hot, start, motion, obstacle, visibility, terminal-goal, and sustained near-obstacle proximity terms. The instance has 1,280 original binary variables and 118,344 polynomial terms, including 4,392 cubic monomials. We compare A*, RRT-best, a QUAV-style QAOA candidate-path selector, native trajectory-level simulated annealing (SA), the classical neal BQM sampler after HUBO-to-QUBO reduction, and an exact CP-SAT baseline that minimizes the native HUBO soft objective over hard-feasible paths. The CP-SAT solver returns OPTIMAL and certifies that the best observed SA path is globally optimal for the enforced feasible-path objective, with implementation HUBO energy −20752.43, soft cost 247.57, path length 14, six turns, and 85% visibility. On the tested instance, the results show why feasibility-aware decoding, exact baselines, and quadratization effects matter; they do not establish quantum speedup or performance across an instance suite.