Feasibility Ceilings Before Learning: Sizing and Timing Bounds for Drone-Mesh Interception

Summary

A mesh of interceptors defending a fixed site must spread over the predicted arrival point of an approaching object.

Abstract Summary

A mesh of interceptors defending a fixed site must spread over the predicted arrival point of an approaching object. This is a recurring task in multi-agent robotics: N agents, each covering a disc of radius r, spread over a probability density so that a point drawn from it falls within some agent's disc. We give closed forms for the quantities that bound performance before any policy is chosen, and validate each by Monte Carlo. The uncertainty of a point predicted by extrapolating a noisy linear track follows from least-squares variance propagation plus a delta-method term for the uncertain arrival time, agreeing with simulation to within 1.8%. The coverage probability of a packed mesh admits a closed form accurate to 0.007 absolute, with a volumetric analogue. A naive area ratio misses a ceiling: while agents stay at least 2r apart, no mesh exceeds 90.69% coverage in the plane or 74.05% in a volume. This ceiling belongs to the separation constraint, not to the problem - permitting overlap substitutes Kershner's thinnest-covering density and removes it, the better regime above a crossover at p=0.80. Hexagonal packing is optimal among five arrangements; the centroidal-Voronoi configuration coverage control supplies reaches only half its coverage at small budgets. The Gaussian assumption is conservative under heavy tails and anisotropy but fragile under bias: a one-sigma aim-point offset costs 14 points of coverage. A repositioning team must also choose a commit time, and the admissible window can be empty. Against the applicable ceiling, analytic placement attains 85% of what the configuration permits while centralised PPO averages 15% over three trainer seeds, with a paired bootstrap against a null policy containing zero at every seed. We argue such ceilings should be computed before any learning experiment and quoted alongside every result.

Key Points

A mesh of interceptors defending a fixed site must spread over the predicted arrival point of an approaching object.
This is a recurring task in multi-agent robotics: N agents, each covering a disc of radius r, spread over a probability density so that a point drawn from it falls within some agent's disc.
We give closed forms for the quantities that bound performance before any policy is chosen, and validate each by Monte Carlo.
The uncertainty of a point predicted by extrapolating a noisy linear track follows from least-squares variance propagation plus a delta-method term for the uncertain arrival time, agreeing with simulation to within 1.8%.
The coverage probability of a packed mesh admits a closed form accurate to 0.007 absolute, with a volumetric analogue.

Problem Formulation

A point of interest travels on a straight line and will cross a fixed plane $x=x_{p}$ at an unknown in-plane location $\mathbf{c}\in\mathbb{R}^{2}$. A sensor supplies $n$ position fixes at times $t_{1},\dots,t_{n}$, each corrupted by independent Gaussian noise of per-axis standard deviation $\sigma_{s}$. $N$ agents occupy the plane.

Each covers a disc of radius $r$; $r$ is treated throughout as a fixed input parameter of the platform, not a design variable.

Problem Formulation — Feasibility Ceilings Before Learning: Sizing and Timing Bounds for Drone-Mesh Interception — Fig. 1: (a) Closed-form $R$ against Monte Carlo RMS radial error across the grid of Table I ; the dashed line is $y=x$. (b) Growth of the uncertainty with lead time $t_{c}$; dotted curves are the hand-tuned heuristic, whose error grows with $t_{c}$.

Prediction Uncertainty

Fit per-axis ordinary least-squares lines $p_{k}(t)=a_{k}+b_{k}t$ for $k\in\{x,y,z\}$ and solve $p_{x}(t)=x_{p}$ for the crossing time $t_{c}$. With $\bar{t}$ the mean fix time and $S=\sum_{i}(t_{i}-\bar{t})^{2}$, the standard OLS results are The fitted value at an arbitrary time $\tau$ therefore has variance The crossing time is itself an estimate.

Coverage Laws

A natural way to size the mesh is an area ratio: to cover the disc of radius $m\sigma$ with non-overlapping discs of radius $r$, take $N\approx(m\sigma)^{2}/r^{2}$. This is optimistic, because it assumes the discs tile the plane perfectly. They cannot: the densest packing of equal circles covers only $\eta_{2}=\pi/\sqrt{12}$ of the plane [ 6 ] .

Carrying the packing density through, $N$ touching discs of radius $r$ occupy a roughly circular region of area $N\pi r^{2}/\eta_{2}$, that is, out to radius $\rho=r\sqrt{N/\eta_{2}}$.

Coverage Laws — Feasibility Ceilings Before Learning: Sizing and Timing Bounds for Drone-Mesh Interception — Fig. 3: Planar and volumetric coverage laws. Dotted lines mark the packing ceilings $\eta_{2}=0.9069$ and $\eta_{3}=0.7405$.

Is Hexagonal Packing the Right Arrangement?

Equation ( 6 ) assumes a hexagonal arrangement, justified by Thue’s theorem. That theorem concerns covering the infinite plane, whereas our mesh covers a finite Gaussian with a finite budget. The assumption therefore deserves an empirical check, and the check is informative about the relation between this problem and classical coverage control.

Robustness of the Error Model

Equation ( 6 ) assumes an isotropic Gaussian error. Two departures are likely in practice. Heavy tails arise from occasional bad fixes, missed manoeuvres or track breaks. Anisotropy arises because crossing geometry rarely leaves the two in-plane axes equally determined. A third, bias, arises when the predictor is systematically off-centre rather than merely imprecise — which is what an unmodelled manoeuvre produces.

The Commit-Time Window

Sections IV and V price a mesh given $\sigma$. A team that must physically reposition faces a further constraint, because $\sigma$ is not exogenous: it depends on how early the team commits. Let $T$ be the commit time — the moment the team stops updating its aim point and flies to the formation. $T$ is squeezed from both sides. Commit late and the prediction is sharp but there is no time to fly.

Commit early and there is ample transit time but the arrival point must be extrapolated further. Two contributions enter $\sigma(T)$ in quadrature.

The Commit-Time Window — Feasibility Ceilings Before Learning: Sizing and Timing Bounds for Drone-Mesh Interception — Fig. 6: (a) The uncertainty budget against commit time: the sensor term is negligible beside unmodelled manoeuvre at every $T$. (b) Transit required against reach available; the two bounds on required transit bracket the answer, and neither admits a useful window.

Applying the Bounds

The results above are individually simple, and their value is in the order they are applied; we set out that order below. Step 1: price the prediction, including what the fit does not model. Compute $R$ from ( 5 ) for the intended cadence and lead time, then add the manoeuvre term of Section VIII in quadrature.

Section VIII is emphatic about the order of magnitude involved: a long track drives the sensor term to a metre or two while the manoeuvre term reaches hundreds, so a budget containing only the first is not conservative but simply wrong.

Implications for Learned Placement

The bounds above were derived after, not before, a sequence of reinforcement-learning experiments on this task in an accompanying prototype. We report those outcomes because the sequence itself is the argument. The geometry is the corrected one of Section X-C : $25$ agents, sector $\pm 35$ m, corridor $\pm 20$ m, $r=3$ m, mean $\sigma=4.57$ m, a $4$ s window.

All policies are evaluated through the identical environment code path over the same $100$ episode seeds, with percentile bootstrap intervals [ 33 ] over episodes.

Reproducibility

The prototype this work analyses — the prediction module, the hexagonal lattice generator, the placement environment and the training scripts — is openly available at https://github.com/DmytroBabarytskyi/drone-training , at commit 4924613 .

The eight experiment scripts, the figure generator and the JSON record of every run reported here are released alongside it, 1 1 1 See the repository’s README for the exact location of the experiment scripts and the archived policy checkpoints.

Declaration on Generative AI

During the preparation of this work, the author used Claude (Anthropic) in order to: search and screen the literature; write the code that produces Figures 1 – 6 from the recorded results; paraphrase and format the manuscript.

The research programme and its framing, the prototype and simulation environment that every experiment runs against, the reinforcement-learning study whose outcomes Section X reports are the author’s own.

Sources and Demonstrations

Figures are reproduced from Babarytskyi See the full paper for experimental details and the project page, when the paper links one, for demonstrations and videos.