💻 computer science

Robust Fleet Sizing for Multi-UAV Inspection Missions under Synchronized Replacement Demand

This paper addresses the mission-level reliability failure of existing fleet-sizing methods under synchronized UAV replacement demands by deriving a closed-form rule that adds a specific buffer of spare drones to guarantee success even when all active units deplete simultaneously.

Original authors: Vishal Ramesh, Antony Thomas

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vishal Ramesh, Antony Thomas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive construction site. You have a team of 10 robotic drones (let's call them "Worker Drones") that need to inspect a huge area. They are fast, smart, and great at their job, but they have a fatal flaw: they run on batteries that die quickly.

Once a Worker Drone's battery is low, it has to fly back to the charging station, swap its battery, and get ready to fly again. This whole process takes time. While it's charging, it can't work.

To keep the construction site running 24/7, you need a pool of Spare Drones sitting at the base, ready to fly out and take over the moment a Worker Drone returns for a charge.

The Problem: The "All-at-Once" Crash

Most engineers used to think about this problem like a busy coffee shop.

The Old Way (The Coffee Shop Model): They assumed that drones would get tired at random times, just like customers arriving at a coffee shop. Some arrive at 9:00 AM, some at 9:15, some at 9:30. Because the arrivals are random and spread out, you only need a few extra baristas (spare drones) to handle the occasional rush. They used a famous math formula (called Erlang-B) to calculate exactly how many spares you need to keep the line moving 99% of the time.
The Reality (The School Bus Model): The authors of this paper discovered that drones don't act like random coffee customers. They act like school buses.
- You send 10 buses out at 8:00 AM.
- They all drive the same distance.
- They all run out of gas at exactly 8:45 AM.
- They all pull into the gas station at the exact same time.
- They all need to get back on the road at the exact same time.

This is called Synchronized Demand.

Because the drones are sent out to do similar jobs, they all get tired at the same time. When they all return to the base together, they create a massive "wave" of demand. If you only have enough spares for the average day (like the Coffee Shop model), you will have 10 drones waiting to fly, but only 2 spares available. The mission stops. The construction site halts.

The Solution: The "Safety Buffer" Rule

The authors came up with a simple, foolproof rule to calculate exactly how many spare drones you need to guarantee the mission never stops, even if every single drone gets tired at the exact same moment.

Their formula is:
Total Spares Needed = (Number of Workers) × (Time to Charge + 1)

Let's break it down with an analogy:
Imagine you have 10 workers (m=10).
It takes 3 hours to recharge a battery, and they work for 1 hour before needing a charge. So, the "Recovery Ratio" is 3.

The Old Math (Coffee Shop): Might say, "You need about 46 spares." It assumes the workers will be tired at slightly different times.
The New Math (School Bus): Says, "You need 50 spares."

Why the extra 4?
Think of the charging station as a pipeline.

You need enough spares to fill the pipeline while the first batch is charging (3 hours of work).
BUT, you also need a safety buffer of extra drones sitting on the runway, fully charged, ready to launch immediately when the first batch of 10 workers comes back.

If you don't have that extra buffer, the moment the first 10 workers land, the pipeline is full, and there are no drones left to take their place. The mission fails. The new rule says: "Always keep one full team of spares on standby, just in case everyone gets tired at once."

What Happened When They Tested It?

The researchers ran 1,000 computer simulations to see who was right.

The "Coffee Shop" Method (Old Way): In the hardest scenarios, it failed 30% of the time. The mission would crash because the spare pool ran dry during a synchronized wave.
The "School Bus" Method (New Way): It succeeded 99.8% of the time.

The best part? The new method only required 4 extra drones (a small increase in cost) to turn a 70% success rate into a near-perfect 99.8% success rate.

The Takeaway

If you are managing a fleet of robots, drones, or even delivery trucks with limited battery life:

Don't trust "average" math. If your vehicles do similar tasks, they will get tired at the same time.
Plan for the worst-case wave. Assume everyone will need a break at the exact same second.
Add a small buffer. A tiny bit of extra capacity (just a few extra units) prevents total system failure.

This paper is essentially telling us: "Don't build your fleet based on how things usually go; build it for the day everything goes wrong at the exact same time."

1. Problem Statement

The paper addresses the critical challenge of determining the minimum number of spare UAVs required to ensure uninterrupted operation in finite-horizon multi-UAV inspection missions.

Context: In missions like infrastructure inspection or environmental monitoring, a team of $m$ active UAVs must service a set of sites. Due to battery limitations, active UAVs must periodically return to a base for recharging and be replaced by spares from a shared pool.
The Failure Mode: Existing fleet-sizing methods fail in this context because they rely on two flawed assumptions:
1. Steady-State Operation: Assuming indefinite cycling, which ignores the transient nature of finite missions.
2. Statistical Independence: Treating replacement requests as independent random events (e.g., using Erlang-B models).
The Core Issue: In reality, energy-aware routing assigns similar workloads to UAVs, causing them to deplete batteries at similar rates. This leads to synchronized replacement bursts (temporal clustering of requests). Even if the average spare capacity is sufficient, these bursts can exhaust the spare pool simultaneously, causing mission failure. The paper identifies this "synchronized demand" as a structural failure mode that standard probabilistic models cannot capture.

2. Methodology

The authors propose a deterministic, worst-case approach to fleet sizing rather than a probabilistic one.

A. System Model

Parameters:
- $m$ : Number of active UAVs.
- $T_{active}$ : Maximum active flight time per battery cycle.
- $T_{recovery}$ : Total time for return, recharge, and relaunch.
- $R = T_{recovery} / T_{active}$ : The recovery-to-active time ratio.
Objective: Find the minimum spare count $k$ such that no replacement request is blocked over the entire mission horizon, regardless of synchronization.

B. Theoretical Derivation

The authors derive a closed-form sufficient condition based on worst-case phase alignment (where all UAVs deplete simultaneously):

Concurrent Recovery Bound: Under worst-case alignment, up to $m \lceil R \rceil$ UAVs can be in the recovery pipeline simultaneously.
The Boundary-Burst Mechanism: At time $t = \lceil R \rceil T_{active}$ , the pipeline is full ( $m \lceil R \rceil$ spares in use), and a new wave of $m$ active UAVs simultaneously requests replacement.
The Solution: To serve this incoming wave, the system needs the $m \lceil R \rceil$ spares to fill the pipeline plus an additional $m$ flight-ready spares to handle the new demand.
Proposed Rule:
$k = m(\lceil R \rceil + 1)$
This formula adds a buffer of $m$ spares to the standard duty-cycle requirement ( $m \lceil R \rceil$ ).

C. Validation Framework

Simulation: Monte Carlo simulations across 5 scenarios ( $m \in [2, 10]$ , $R \in [0.87, 3.39]$ ) with 1,000 trials each.
Variables: Tested against wind variability (Coefficient of Variation up to 0.30) and clustered site distributions.
Comparison: The proposed rule was compared against:
- Naive: $k = m$
- Duty-Cycle: $k = m \lceil R \rceil$
- Erlang-B: Sizing based on per-request blocking probability ( $\epsilon = 0.01$ ).
Metric: Mission success rate (all sites inspected, zero spare exhaustion) with Wilson 95% lower confidence bounds.

3. Key Contributions

Identification of Synchronized Demand: The paper formally identifies that energy-aware routing in finite missions creates deterministic, correlated replacement bursts, rendering independence-based queueing models (like Erlang-B) insufficient for mission-level reliability.
Closed-Form Sizing Rule: Derivation of the rule $k = m(\lceil R \rceil + 1)$ $k = m (⌈ R ⌉ + 1)$ . This rule is:
- Analytical: Requires no simulation or distributional assumptions.
- Robust: Guarantees feasibility under worst-case synchronization.
- Simple: Computed in constant time from mission parameters.
Reliability Analysis: Demonstration that per-request blocking guarantees (e.g., 99% success per handover) do not translate to mission-level reliability. For a mission with $H$ handovers, the success probability drops to $(1-\epsilon)^H$ , which can be negligible even for small $\epsilon$ .

4. Experimental Results

The simulations revealed stark differences in performance between the proposed method and existing baselines:

Scenario S5 (Most Demanding): $m=10$ $m = 10$ , $R=3.39$ $R = 3.39$ .
- Erlang-B: Suggested $k=46$ spares. Achieved only 69.9% mission success (Wilson lower bound 67.0%).
- Duty-Cycle: Suggested $k=40$ spares. Achieved 0.2% success.
- Proposed Rule: Suggested $k=50$ spares. Achieved 99.8% success (Wilson lower bound 99.3%).
Cost of Robustness: The proposed rule required only 4 additional UAVs (from 46 to 50) compared to Erlang-B to bridge the reliability gap from ~70% to ~99.8%.
Failure Concentration: Analysis showed that failures in baseline methods were not random; 95% of Erlang-B failures and 100% of Duty-Cycle failures occurred within the top 10% of 5-minute demand windows (synchronized bursts).
Robustness: The proposed rule maintained >99% success even with high wind variability (CV = 0.30), whereas Erlang-B performance remained stagnant at ~70%.

5. Significance and Implications

Paradigm Shift: The paper argues that for finite-horizon missions, fleet sizing must move from probabilistic guarantees (per-request) to deterministic sufficiency (mission-level).
Operational Impact: The proposed rule provides a simple, computable metric for mission planners. It ensures that the "price of robustness" (a small number of extra drones) is paid to avoid catastrophic mission failure.
Limitations & Future Work: The current model assumes homogeneous UAVs and unlimited charging capacity. Future work could extend this to heterogeneous fleets, limited charging infrastructure, and adaptive routing that might desynchronize demand.

In conclusion, the paper demonstrates that ignoring the synchronization of battery depletion leads to severe under-provisioning of spare fleets. The proposed additive buffer rule ( $k = m(\lceil R \rceil + 1)$ ) offers a mathematically rigorous, simulation-free solution to guarantee mission success in battery-constrained multi-UAV operations.