Fair Shares of Flight Energy: Weighted Chore Division for 3D Multi-Drone Inspection

When several organizations pool drones to inspect a shared structure, such as a crane, a bridge, or a building facade, someone has to decide which drone visits which inspection point. Each operator has agreed to carry a stated fraction of the work, perhaps in proportion to what it paid in or the size of its fleet. The usual tools for this split are vehicle-routing heuristics and clustering. Both minimize total cost, and neither promises any operator that it will not be stuck with more than its share. Fair-division theory makes exactly that kind of promise. Weighted fair division splits indivisible items among agents with unequal entitlements, and when the items are chores (things that cost effort), there is an algorithm that guarantees each agent's burden is at most its share once any single chore is removed. That theory, however, assumes each chore has a fixed cost that adds up across a bundle. In 3D flight this assumption fails. What a waypoint costs depends on which other waypoints share the same tour and in what order the drone visits them. Climbing costs much more than descending, and every drone pays a fixed overhead to take off and climb to the work site.

This note proposes treating 3D inspection waypoints as weighted indivisible chores whose costs are each drone's own optimized 3D energy tour. It makes three contributions. The first is a measurement of how much proportional fairness is lost because tour costs are not additive. The second is a "route-aware" version of a known chore-division algorithm that bids using marginal 3D insertion energy. The third is an empirical test of whether formal guarantees beat the obvious alternative of capacity-scaled min-max routing. The central observation is simple and, as far as the file shows, unexamined. With route costs, the sum of the drones' tour costs exceeds the cost of a single tour through all waypoints by roughly one depot-to-site overhead per drone. Exact weighted proportionality is therefore generally impossible, and the size of the gap is set by the vertical geometry.

Core Claim

Let $M$ be the set of inspection waypoints, $w_i$ the entitlement of drone (or operator) $i$ with $\sum_i w_i = 1$, and $C_i(S)$ the minimum energy that drone $i$ needs to take off from its depot, visit every waypoint in $S$ in 3D, and return. Drone $i$ computes $C_i(S)$ with its own asymmetric energy model. The proportionality-up-to-any-chore notion of Almost (Weighted) Proportional Allocations for Indivisible Chores asks that

$$C_i(A_i \setminus \{c\}) \le w_i \, C_i(M) \quad \text{for every } i \text{ and every } c \in A_i,$$

where $A_i$ is the set of waypoints given to drone $i$. That paper proves such an allocation always exists for additive chore costs and computes it with a Bid-and-Take procedure. In that procedure, active agents repeatedly claim the chore they find cheapest and drop out once they reach their threshold. Tour costs $C_i$ are monotone and roughly subadditive, not additive. For identical drones sharing one depot, the sum of the drones' tour costs can never fall below the single-tour cost $C(M)$, and it typically exceeds it by about $(n-1)$ times the climb-and-return overhead $h$. This holds because any one tour through all points is no longer than the drones' tours stitched together.

Our claim is that the right guarantee is an approximate one, $C_i(A_i \setminus \{c\}) \le \alpha \, w_i C_i(M) + \beta_i$. Here $\alpha$ is a multiplicative slack, $\beta_i$ is an additive overhead term tied to drone $i$'s depot-to-site climb, and both are determined by two quantities: the ratio of climb to descent energy and the ratio of overhead to total mission energy. We further claim that a route-aware Bid-and-Take, in which each active drone bids its marginal 3D insertion energy into its current tour, reaches this guarantee with near-minimal $\alpha$ at an energy premium (the price of fairness) of a few percent over the best unfair plan. The new element is not "fairness for drones," which prior work handles with symmetric indices. It is the identification of a geometric obstruction to weighted proportionality and an algorithm calibrated to that obstruction.

Where This Sits

The 3D side supplies the cost model. Multi-UAV Path Planning Considering Multiple Energy Consumptions via an Improved Bee Foraging Learning Particle Swarm Optimization Algorithm decomposes energy into steady flight, acceleration, deceleration, climbing, and turning, and plans multi-UAV tours on a 3D-lifted Augerat benchmark. We reuse its energy model and its planner as the oracle that computes $C_i$, but that work assigns points to minimize total cruising time with no notion of per-agent share. Optimal Cruise Airspeed for Hybrid-Electric and Electric Aircraft motivates pricing tours in operating cost rather than geometric distance. We borrow that idea to make $C_i$ comparable across heterogeneous vehicles, which matters because $w_i C_i(M)$ is a subjective share measured in each drone's own energy.

The fair-division side supplies the method and also limits what it can do. Weighted Envy-freeness in Indivisible Item Allocation shows that envy-cycle elimination breaks under weights and that weaker envy notions can fail to exist beyond additive valuations. That is a warning that our non-additive costs may defeat envy-based targets, and it is why we aim at proportionality, not envy-freeness. Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations with Subsidy bounds the total subsidy needed for weighted proportionality of additive chores at $n/3 - 1/6$. We use that result as a comparison point for whether energy credits, such as recharge slots, can close our overhead gap.

The closest connecting work motivates the gap without filling it. AAV-Assisted Joint Mobile Edge Computing and Data Collection via Matching-Enabled Deep Reinforcement Learning separates discrete assignment, done with stable matching, from continuous control at a fixed 100 m altitude. Multi-UAV Trajectory Design for Fair and Secure Communication uses K-means clustering and Jain's index in 2D. Fresh, Fair and Energy-Efficient Content Provision in a Private and Cache-Enabled UAV Network enforces symmetric fairness through virtual queues at constant altitude and names 3D as future work. None of the three uses unequal entitlements, indivisible task guarantees, or vertical costs. Cooperative Aerial Robot Inspection Challenge provides the application motivation: heterogeneous teams inspecting thin 3D structures run into workload imbalance and allocation failures.

Research Program

The theory part has three steps. We first prove a lower bound showing that for any $n$ there are 3D instances in which every allocation violates exact weighted proportionality by at least the depot overhead. We then characterize how the climb/descent asymmetry ratio inflates $\alpha$ when costs are asymmetric shortest-path tours. Finally, we analyze route-aware Bid-and-Take: drones active in a weighted order bid the marginal insertion energy of each remaining waypoint into their current tour, take the cheapest one, and drop out once their tour cost reaches $w_i C_i(M)$. The target is a guarantee of the form above, with $\alpha$ bounded by the approximation factor of the insertion heuristic under a triangle inequality on asymmetric 3D costs. If a clean bound cannot be proven, we will report the empirical $\alpha$ distribution and state the bound as a conjecture.

The systems part wraps the allocator around a per-drone 3D planner, IBFLPSO-style with 2-opt as in Qi et al. The planner computes $C_i(M)$ once per drone and then computes marginal insertion costs incrementally. We also add an optional energy-credit stage that pays residual violations, so that we can measure how far the realized subsidy falls from the additive-case bound of Wu and Zhou.

Baselines

The naive reference point is the standard engineering pipeline. Weighted K-means splits waypoints into clusters sized in proportion to $w_i$, and each drone then plans its own cluster with the same 3D planner. This is what Multi-UAV Trajectory Design for Fair and Secure Communication does in 2D, and it is the default a practitioner would reach for. We beat it if we lower the worst-case ratio $\max_i C_i(A_i)/(w_i C_i(M))$ and the rate of approximate-proportionality violations at equal or lower total energy.

The strongest competitor is weighted min-max routing. It minimizes $\max_i C_i(A_i)/w_i$ directly with the same IBFLPSO/2-opt planner and the same wall-clock budget. Because it optimizes a weighted burden objective, it is the baseline most likely to match us. It differs in two ways: it scales by a common yardstick rather than each drone's own $C_i(M)$, and it gives no per-agent guarantee. We call our method better only if it gets strictly fewer violations of the approximate-proportionality condition across instances with heterogeneous drones and pays no more than a small total-energy premium, which we pre-register as 5%. For the planner itself, Qi et al. report on the 51-point 3D Augerat benchmark that IBFLPSO cuts cruising time by 54.64% relative to PSO and by 25.78% relative to GA. We found no reported result on Lacuna for fairness metrics or min-max weighted routing on this benchmark, so all fairness numbers will be produced by us.

The first ablation is additive Bid-and-Take using fixed per-waypoint costs, namely depot round-trip energy. This is the algorithm of Almost (Weighted) Proportional Allocations for Indivisible Chores applied verbatim, and it isolates the route-aware marginal bid. The second ablation flattens all altitudes to a single plane while keeping everything else fixed, which isolates the contribution of vertical asymmetry. All methods share instances, energy models, planner, and compute budget.

Why not just…?

Why not just run capacity-weighted min-max routing? This is the real threat. If it achieves the same worst-case ratio, the contribution shrinks to a proof and a diagnosis of the overhead gap. The head-to-head comparison above decides the question. We expect the two methods to diverge mainly on heterogeneous fleets, such as a mix of fixed-wing and multirotor vehicles. There, a common yardstick misjudges each drone's subjective share, because the same waypoint set costs drones very different amounts. If the methods do not diverge, we will report that result.

Why not just add Jain's index or a max-min penalty to a multi-agent reinforcement learning reward? Jain's index measures equality and ignores entitlements. Folding discrete assignment into continuous reinforcement learning is what AAV-Assisted Joint Mobile Edge Computing and Data Collection found necessary to decouple for stability. We will include a reward-shaped variant only as a secondary check, since it offers no per-agent bound.

Why not just plan at a fixed altitude? Deng et al. (UAV-enabled Computing Power Networks) report gains of up to 247% from dynamic over static configurations once altitude is optimized. More importantly here, flattening removes the climb asymmetry that inflates $\alpha$. The 2D ablation shows directly whether 3D changes which allocation is fair, and not merely its total cost.

Proposed Experiments

We run four instance families. The first is the modified Augerat benchmark of Qi et al., with coordinates scaled by 50, altitudes drawn from 0 to 150 m, and 30, 40, 50, and 51 points. The second places viewpoint sets on Crane-, MBS-, and Hangar-like 3D structures modeled after CARIC. Because Lacuna lists no standalone CARIC codebase, we rebuild these geometries in Gazebo with RotorS. The third uses heterogeneous fleets of two to eight drones with entitlements drawn from uniform and skewed distributions. The fourth spot-checks executability: fixed-wing tours are flown in VVC-Gym to confirm that planned energies survive 6-degree-of-freedom dynamics.

The metrics are the worst-case proportionality ratio; the empirical $\alpha$ and the per-drone overhead term $\beta_i$; the fraction of instances meeting approximate proportionality; total energy relative to the best unfair plan; battery feasibility; and the residual energy credit needed, compared with $n/3 - 1/6$.

Three checks are decisive. The first test is whether the measured gap to exact proportionality grows with depot overhead and climb asymmetry as the lower bound predicts. Finding that it does not would falsify the core geometric claim. Second, route-aware bidding must beat additive Bid-and-Take on the worst-case ratio. Third, the comparison against weighted min-max routing on heterogeneous fleets settles whether the guarantee buys anything operationally.