Source-linked AI summary
Conflict-Predictive Variable Horizons in Multi-Drone Distributed Model Predictive Control
Linda Mümken, Michael Schwung, Stefan Lier, Andreas Schwung
TL;DR
Fixed prediction horizons trade inexpensive but late reactions against earlier anticipation at a superlinearly growing per-step cost. The paper sets each drone’s horizon from predicted conflicts while leaving DMPC unchanged, and proves guarantees under a condition on the minimum horizon. In dense antipodal-swap simulations, it reduces computation relative to a long fixed horizon while maintaining separation where a short, similarly costly horizon does not.
Problem
Fixed horizons make drones choose between a short, inexpensive window that may react late and a long window whose per-step optimization cost grows superlinearly.
Source: §I · p. 1Method
Each drone predicts neighbor flight lines from observed positions, tests them with confidence funnels, and selects the smallest admissible horizon covering the farthest predicted conflict.
Source: §I · p. 1Results
On dense antipodal-swap benchmarks, the variable horizon reduces per-step and total computation versus a long fixed horizon and maintains separation where a short, similarly costly horizon fails.
Source: §VII · pp. 13–14Takeaways & Limitations
The guarantees extend from the linear model to asymptotic stability for the linearized quadrotor and practical stability for the full nonlinear model.
Source: §I · p. 1, B. Nonlinear Rigid-Body Quadrotor · p. 11The linear predictor loses accuracy against strongly maneuvering neighbors, and the nonlinear extension assumes a sufficiently high-bandwidth inner loop and small attitude error.
Source: §VII · p. 14
Abstract
from arXiv · showhide
In distributed model predictive control for multi-drone collision avoidance, a fixed prediction horizon forces a compromise: a short horizon is inexpensive but reacts late to approaching neighbors, whereas a long one anticipates conflicts at a per-step cost that grows superlinearly with its length. We propose a conflict-predictive variable horizon that each drone sets locally, leaving the distributed model predictive control itself unchanged. From a short history of observed positions, a drone extrapolates the flight lines of its neighbors, tests each against its own using confidence funnels that narrow with prediction range, and obtains each time to conflict in closed form. The horizon is then the smallest admissible value whose planning window covers the farthest predicted conflict. It collapses to its minimum in clear airspace and grows only when a conflict lies ahead. Provided this minimum meets a single computable feasibility bound, we prove that recursive feasibility and asymptotic stability are preserved for every horizon the policy can select. These guarantees hold for a linear model, and a cascaded inner loop reduces each quadrotor's translational dynamics to a perturbed double integrator, so they carry over to the linearized quadrotor model and, as practical stability, to the full nonlinear one. In simulation on dense antipodal-swap benchmarks, the variable horizon reduces both per-step solver cost and total computation well below those of a long fixed horizon, and it maintains separation in every run, which a short fixed horizon of comparable per-step cost does not.
I. Introduction
Fixed horizons impose a recurring cost for anticipation, while existing adaptive schemes do not couple predicted conflicts with guarantees independent of that prediction. The paper introduces a local conflict-predictive horizon policy and establishes its guarantees and quadrotor extensions.
I. Introduction
- A local conflict-predictive policy sizes each drone’s horizon to cover its farthest predicted conflict, while a lower-bound condition preserves feasibility and asymptotic stability for every admissible horizon.The distributed controller itself remains unchanged.Source: §I · pp. 1–2
- The guarantees extend to linearized quadrotor dynamics and, as practical stability, to the full nonlinear model.The analysis uses a perturbation argument for the nonlinear extension.Source: §I · pp. 1–2
A. Variable Prediction Horizons
- Earlier adaptive horizons are driven by the controlled system’s state, whereas this policy expands lookahead for predicted encounters and contracts it when airspace is clear.The related-work discussion also distinguishes event-triggered schemes, which govern when control is recomputed, from this policy’s choice of how far ahead to plan.Source: A. Variable Prediction Horizons · p. 2
- The lightweight linear predictor and confidence funnels keep prediction outside the safety argument, so misprediction affects anticipation rather than the stated feasibility and stability guarantees.The paper contrasts this design with forecasts that enter avoidance constraints directly.Source: A. Variable Prediction Horizons · p. 2
B. Distributed MPC for Collision Avoidance
- The work builds on adaptive safety-zone DMPC and shows that a uniformly bounded horizon-dependent residual lets its certificate survive every horizon in the admissible band.The framework combines a contraction argument, a physical-energy Lyapunov function, and asynchronous Gauss–Seidel iteration.Source: B. Distributed MPC for Collision… · p. 3
III. Conflict-Predictive Variable-Horizon Control
The control problem requires each drone to meet safety, stability, and efficiency objectives locally. The proposed scheme changes the horizon while retaining the underlying distributed MPC formulation.
III. Conflict-Predictive Variable-Horizon Control
- Each drone must maintain pairwise separation and airspace constraints, converge to its goal, and use the smallest admissible horizon that covers predicted conflicts.When no conflict is predicted, the horizon should equal Hmin.Source: §III · p. 3
- The horizon’s lower bound carries feasibility and stability, while conflict predictions select a value in [Hmin, Hmax] and cannot weaken those guarantees.Hmin is verified against the feasibility bound before deployment.Source: §III · p. 3
A. Preliminaries
- The underlying DMPC uses a double-integrator model, adaptive safety spheres, and pairwise separation constraints, with each drone optimizing locally through asynchronous ADMM–Gauss–Seidel iteration.The formulation and its fixed-horizon feasibility and stability guarantees were established in earlier work.Source: A. Preliminaries · p. 3, Adaptive safety zone · p. 4
B. Neighbor History and Linear Prediction
The controller estimates neighbor flight lines from position histories, tests them using time-varying confidence funnels, and identifies conflicts through a closed-form closest-approach calculation.
B. Neighbor History and Linear Prediction
- A first-order least-squares fit of recent observed positions estimates each neighbor’s position and constant-velocity flight line without requiring velocity measurements.The ego line uses its reference direction, and coordination relies on observed positions rather than transmitted plans or goals.Source: B. Neighbor History and Linear… · p. 4
C. Confidence Funnels
- Confidence funnels widen near the present and narrow with prediction time, matching a broad tolerance for imminent encounters with a tighter test for uncertain distant predictions.The funnel follows each predicted flight line from rmax toward the neighbor’s adaptive radius rf.Source: C. Confidence Funnels · p. 4, Figure 2 · p. 5
D. Conflict Detection
- A closed-form closest-approach test flags a predicted conflict when the miss distance falls within the funnel radius at that time.Because the funnel radius is always at least rf, any predicted gap within the neighbor’s current adaptive radius is flagged, even far ahead.Source: D. Conflict Detection · p. 5
E. Conflict-Driven Variable Horizon
The policy selects the smallest admissible planning horizon that covers the farthest predicted conflict. It returns Hmin when no neighbor is flagged.
E. Conflict-Driven Variable Horizon
- The conflict-driven policy covers every predicted conflict with the smallest admissible integer horizon, and returns Hmin when there are none.The horizon is clipped to the fixed admissible band [Hmin, Hmax].Source: E. Conflict-Driven Variable Horizon · p. 5
- Each control step fits flight lines, tests neighbors for conflict, resizes the solver and warm start to the selected horizon, then solves the unchanged local MPC and applies its first input.Per-step computational cost grows superlinearly with horizon length.Source: E. Conflict-Driven Variable Horizon · p. 6
- A conflict farther away in space yields a longer horizon and earlier anticipation, while a nearer conflict yields a shorter horizon and faster reaction.The policy’s lower clip at Hmin is the operative guarantee used in the stability analysis.Source: E. Conflict-Driven Variable Horizon · p. 6
F. Integration into the Distributed MPC
The variable horizon integrates into the existing DMPC by changing only the planning horizon; the underlying costs, constraints, and iteration scheme remain unchanged. Its minimum must satisfy the feasibility bound required for the guarantees.
F. Integration into the Distributed MPC
- The horizon is the scheme’s only controller-facing change; all DMPC costs, constraints, and iteration steps remain unchanged.With a constant horizon, the solver recovers the fixed-horizon controller exactly.Source: F. Integration into the Distributed MPC · p. 6
- At each step, the drone recomputes its horizon and resizes its local solver and ADMM state, padding or truncating warm starts as needed.This handling preserves solver efficiency across horizon changes.Source: F. Integration into the Distributed MPC · p. 6
- The minimum horizon must meet the underlying controller’s feasibility condition, and that bound is checked once from airspace and dynamics parameters.The condition constrains Hmin, not the time-varying horizon; consequently, every selected horizon preserves the underlying feasibility and stability guarantees.Source: F. Integration into the Distributed MPC · p. 6
IV. Feasibility and Stability of the Variable-Horizon DMPC
The variable-horizon analysis builds on fixed-horizon DMPC guarantees. It uses a physical-state Lyapunov certificate and a uniformly bounded finite-horizon residual to address changes in horizon length.
IV. Feasibility and Stability of the Variable-Horizon DMPC
- Horizon switches challenge standard MPC arguments because the optimal-value certificate changes with horizon length and shifted-solution feasibility assumes consecutive problems have equal lengths.The analysis instead uses a horizon-independent physical-state Lyapunov function and uniformly bounds the horizon-dependent residual over the admissible band.Source: §IV · p. 6
A. Fixed-Horizon DMPC Guarantees
- The horizon needed for per-step solver feasibility is bounded below under the stated drone-density condition.The bound is computable from the base radius, adaptation parameter, acceleration limit, and sampling time.Source: A. Fixed-Horizon DMPC Guarantees · p. 6
- Near the goal, inactive separation constraints and contracting adaptive radii reduce each local subproblem to an unconstrained LQR that drives the Lyapunov function downward.The sample-and-hold mismatch is a bounded O(∆t) perturbation that vanishes near equilibrium.Source: A. Fixed-Horizon DMPC Guarantees · p. 7
- At the distributed-iteration fixed point, each local DMPC feedback consists of nominal LQR feedback plus a finite-horizon residual and a coupling perturbation.The coupling perturbation is bounded by Cβ, and both terms vanish as the system approaches equilibrium.Source: A. Fixed-Horizon DMPC Guarantees · p. 7
B. A Perturbation Bound for the Adaptive DMPC
The stability argument treats departures from nominal LQR feedback as bounded perturbations. This yields practical stability, and asymptotic stability when the perturbations vanish near equilibrium.
B. A Perturbation Bound for the Adaptive DMPC
- The nominal Lyapunov descent tolerates bounded feedback perturbations, yielding practical asymptotic stability with an ultimate bound proportional to perturbation size.If the perturbation tends to zero as the state approaches equilibrium, the equilibrium is asymptotically stable.Source: B. A Perturbation Bound for the… · p. 7
- The perturbation argument recovers the fixed-horizon adaptive DMPC stability result as a special case.That result applies under the stated coupling condition.Source: B. A Perturbation Bound for the… · p. 7
- The realized DMPC feedback combines nominal LQR feedback with a finite-horizon residual and a coupling perturbation; both vanish near equilibrium.The coupling term is bounded by Cβ, with C depending on constraint geometry and β the distributed-update contraction rate.Source: B. A Perturbation Bound for the… · p. 7
C. Choice of the Horizon Bounds
The horizon is bounded between design constants: the minimum ensures feasibility, while the maximum limits the prediction window and peak computation. Under the stated assumptions, every selected horizon preserves feasibility and asymptotic stability.
C. Choice of the Horizon Bounds
- Hmax sets the conflict-prediction window and caps worst-case per-step computation, but it affects neither feasibility nor stability.Conflicts beyond that window are detected later; a larger Hmax enables earlier anticipation at higher peak cost.Source: C. Choice of the Horizon Bounds · pp. 7–8
D. Feasibility and Stability under the Variable Horizon
- When the horizon shrinks, truncating the shifted previous solution preserves feasibility; when it grows, per-step fixed-horizon feasibility supplies a feasible longer subproblem.The padded warm start initializes the solver but bears no feasibility burden.Source: D. Feasibility and Stability under the… · p. 8
- For every horizon sequence in [Hmin, Hmax] produced by the policy, the DMPC remains feasible at every step and is asymptotically stable under the stated α and β conditions.The guarantees require the minimum-horizon feasibility condition and the paper’s per-step fixed-horizon feasibility assumption.Source: D. Feasibility and Stability under the… · p. 8
- Stability holds across horizon switches because the physical-state Lyapunov function is horizon-independent and the feedback perturbation is uniformly bounded over the admissible horizon band.No dwell-time condition is needed; the perturbation contracts as the state approaches equilibrium.Source: D. Feasibility and Stability under the… · p. 8
E. Decoupling of Safety from Prediction Accuracy
The horizon predictor determines how much anticipation the controller uses, but feasibility and stability depend on the admissible horizon band, not on prediction accuracy. Cascaded control extends the guarantees to quadrotor models by treating their translational dynamics as perturbed double integrators.
E. Decoupling of Safety from Prediction Accuracy
- Feasibility and stability hold for any horizon policy within [Hmin, Hmax] under the stated assumptions, regardless of predictor, history length, or funnel parameters.Prediction quality affects efficiency and anticipation, not safety guarantees; separation margin is not guaranteed and a detector that misses conflicts can bring drones closer to contact.Source: E. Decoupling of Safety from… · p. 9
- A horizon H resolves up to κ(H) = ⌊H∆t/hmin⌋ sequential conflicts, so increasing it to cover a predicted encounter raises the conflict-resolution budget.A clear neighborhood retains H = Hmin and minimum per-step cost.Source: E. Decoupling of Safety from… · p. 9
V. Extension to Quadrotor Dynamics
- Cascaded inner–outer-loop control reduces quadrotor translation to a double integrator with a bounded inner-loop residual, allowing the horizon-uniform perturbation argument to carry over.The same analysis covers models whose additional effects perturb translation by a bounded residual.Source: §V · p. 9, A. Linearized Quadrotor with Cascaded… · p. 9
A. Linearized Quadrotor with Cascaded Control
- For the linearized quadrotor, the closed loop is asymptotically stable when the stated growth-rate, drone-count, and combined-perturbation conditions hold.The inner-loop residual, distributed coupling, and finite-horizon residual contribute additively to the perturbation bound.Source: A. Linearized Quadrotor with Cascaded… · pp. 9–10
B. Nonlinear Rigid-Body Quadrotor
The nonlinear quadrotor is handled by bounding the translational effects of attitude tracking and thrust/attitude inversion as a perturbation. Under the stated conditions, the adaptive DMPC retains recursive feasibility and practical asymptotic stability, with asymptotic stability when the inner-loop residual vanishes near equilibrium.
B. Nonlinear Rigid-Body Quadrotor
- Attitude-loop ISS and thrust-vector inversion let the nonlinear translational dynamics be written as a double integrator plus a residual from attitude tracking and thrust/attitude inversion mismatch.The residual has a steady-state bound tied to the commanded attitude rate.Source: B. Nonlinear Rigid-Body Quadrotor · p. 10
- Under Theorem V.3’s conditions, the nonlinear closed loop is practically asymptotically stable, converging to a neighborhood of radius O(∥ξnl∥∞).If the inner loop tracks asymptotically exactly, the stability is asymptotic.Source: B. Nonlinear Rigid-Body Quadrotor · p. 10
- The minimal rigid-body model omits higher-fidelity effects such as motor lag, aerodynamic drag, and gyroscopic rotor torques from its explicit dynamics.The analysis treats such effects as further bounded contributions to the nonlinear residual.Source: B. Nonlinear Rigid-Body Quadrotor · p. 10
- Under the respective linearized and nonlinear quadrotor conditions, the variable-horizon DMPC retains recursive feasibility and stability.Across model classes, the absorbed feedback perturbation is the quantity that changes; the critical density bound and variable-horizon results carry over.Source: B. Nonlinear Rigid-Body Quadrotor · p. 11
VI. Evaluation
The evaluation tests whether conflict-predictive variable horizons improve efficiency without compromising guarantees, and examines how closely drones approach the contact boundary. It compares short fixed, long fixed, and variable horizons under the same distributed controller.
VI. Evaluation
- The evaluation measures efficiency, preservation of guarantees, and proximity to the contact boundary for the conflict-predictive horizon.It includes benchmark setup, horizon-computation cost, separation, and the regime in which each effect dominates.Source: §VI · p. 11
- Three strategies are compared under the same distributed controller: fixed at Hmin, fixed at Hmax, and variable within [Hmin, Hmax].Source: §VI · p. 11
- The evaluation examines benchmark scenarios, the cost of computing the variable horizon, minimum pairwise separation over time, and the regimes where each effect dominates.Source: §VI · p. 11
A. Benchmark Setup
Across the benchmark, the variable horizon reduces total computation relative to the long fixed horizon and can outperform the short horizon in open scenarios, while tight scenarios make it costlier than the short baseline. Its per-step solver cost remains below the long-horizon cost.
A. Benchmark Setup
- The six antipodal-swap scenarios span 2, 4, or 8 drones in tight 53 m3 or open 203 m3 airspace, with 20 seeds per strategy and 360 runs total.The variable horizon ranged from Hmin = 4 to Hmax = 10, and Hmin exceeded the feasibility bound of 3 by one step.Source: A. Benchmark Setup · p. 11
- Open-airspace trajectories deviated mainly around the central crossing, whereas tight-airspace trajectories used detours for most of the flight.The antipodal swaps create a conflict-heavy mid-flight crossing preceded and followed by clear airspace.Source: A. Benchmark Setup · p. 11, Figure 3 · p. 12
B. Computational Cost
- Prediction costs 0.04 to 0.7 ms per step, two to four orders of magnitude below solver time and under 0.3% of the variable horizon’s per-step solver time.Long-horizon solver time ranged from about 0.1 s per step in two-drone scenarios to 10.7 s in the eight-drone open scenario, where it exhausted the 500 s budget within fifty steps.Source: B. Computational Cost · p. 12, Figure 4 · p. 12
- 4.5× to 8.6× lower per-step solver cost than the long horizon across scenarios, while the mean selected horizon stayed between 4.1 and 4.5 on.The eight-drone open-scenario long-horizon value is a lower bound because that strategy never passed the crossing.Source: B. Computational Cost · p. 12, Figure 4 · p. 12
- 2.0× to 2.7× lower total computation than the long fixed horizon in every scenario where it finishes; in the eight-drone open scenario, the long horizon exceeded budget in all 20 seeds while the variable horizon averaged 290 s.In open scenarios, it took 38 versus 98 s at four drones and completed missions in 220 versus 248 steps, with mean per-step solver time of 172 versus 393 ms; in tight scenarios it cost up to 2.7× more than the short horizon.Source: B. Computational Cost · p. 12
C. Separation and Safety
Across the benchmark regimes, the variable horizon is tractable and boundary-respecting, while its cost and separation trade-offs depend on the fixed-horizon baseline and airspace. The paper also reports guarantees for every selected horizon under a computable lower-bound condition, alongside limitations and an open question about neighbor coupling.
C. Separation and Safety
- Across 120 variable-horizon runs, minimum pairwise distance stays at or above the 0.8 m contact boundary; the short horizon breaches it in 2 of 20 eight-drone open runs, reaching 0.776 m.The long horizon also maintains the boundary wherever it completes; all strategies graze the boundary in tight scenarios.Source: C. Separation and Safety · p. 12
- In the four-drone open scenario, the variable horizon reaches a worst-case closest approach of 0.86 m and spends 3 mean-trace steps below 1.2 m, versus 32 for the short horizon.The long horizon stays farthest away, with a 1.07 m worst-case closest approach and no mean-trace step below 1.2 m; in the tight scenario, all strategies reach the boundary.Source: C. Separation and Safety · pp. 12–13, Figure 6 · p. 13
- The guarantees depend on per-step solver feasibility; the short horizon meets its feasibility bound with one step to spare, while lifting the variable horizon at predicted crossings avoids breaches.The paper attributes the short horizon’s isolated eight-drone breaches to conflicts the solver could no longer resolve within four steps.Source: C. Separation and Safety · p. 13
D. Operating Regime
- 2.0× to 2.7× faster in total than the long fixed horizon wherever it finishes, the variable horizon completes the eight-drone open swap and beats the short horizon in open scenarios.In tight scenarios, all strategies sit on the boundary and the short horizon is cheaper; the variable horizon is tractable and boundary-respecting across the benchmark matrix.Source: D. Operating Regime · p. 13
VII. Discussion and Conclusion
- Recursive feasibility and asymptotic stability are preserved for every horizon in the band under one computable lower-bound condition, with guarantees extending to linearized quadrotors and practical stability for the full nonlinear model.The discussion also describes the horizon as a budget allocated where conflicts are predicted, without weakening geometric density limits.Source: §VII · pp. 13–14
- The linear predictor loses accuracy against strongly maneuvering neighbors, evaluation is simulation-only, and whether variable horizons weaken coupling between neighboring subproblems remains unproved.The authors note that hardware experiments remain to be done and identify proving the proposed coupling link as an open question.Source: §VII · p. 14