💻 computer science

Certified-Robust Multi-Objective UAV Routing for Military Resupply under Nonlinear Energy Dynamics: An Adaptive Physics-Informed Approach

This paper proposes Adaptive PINN, a physics-informed neural network framework with a certified repair layer, to solve a tri-objective robust military UAV routing problem that accounts for nonlinear battery depletion via Peukert's law and multiple sources of uncertainty.

Original authors: Karim Benalia, Karim Beddek, Melissa Mansouri, Brahim Oukacha

Published 2026-09-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Karim Benalia, Karim Beddek, Melissa Mansouri, Brahim Oukacha

Original paper licensed under CC BY 4.0 (https://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

In the high-stakes world of military logistics, getting supplies to remote outposts is a constant race against time, weather, and danger. For decades, planners have relied on unmanned aerial vehicles, or drones, to bridge these gaps, carrying medicine, fuel, and equipment to soldiers in the field. However, programming these machines to fly safely and efficiently is far more complex than simply drawing a line on a map. The air itself is unpredictable; wind and turbulence can stretch a flight time that was supposed to take twenty minutes into thirty, leaving a drone stranded. The ground below is equally treacherous, with the risk of enemy detection rising the longer a drone lingers in a contested zone. Perhaps most critically, the drone's own power source behaves in ways that defy simple logic. Unlike a car that burns fuel at a steady rate, a battery's ability to deliver energy changes depending on how hard it is working. If a drone flies faster or carries a heavier load, its battery drains disproportionately faster, a physical reality that standard computer models often ignore or oversimplify.

A team of researchers has tackled this tangled web of problems by creating a new way to plan drone missions that respects these physical limits while accounting for uncertainty. They developed a system that treats the drone's battery not as a simple tank of fuel, but as a living component governed by the laws of physics. By combining advanced mathematics with a type of artificial intelligence that "knows" these physical laws, they created a tool that can generate flight plans which are energy-aware, though not immediately guaranteed to be safe. The researchers found that by embedding the actual rules of battery chemistry directly into the planning software, they could produce routes that aim to avoid the dangerous scenario of a drone running out of power mid-flight, even when the weather turns bad or the mission takes longer than expected. However, the initial output from the AI is not always feasible; it requires a final verification step to ensure safety.

The core of this work is a new model for routing drones that balances three competing goals: finishing the mission quickly, minimizing the time spent in dangerous areas, and ensuring the drone has enough energy left to land safely. Traditional methods often treat energy as a fixed cost, like a toll fee, but the researchers showed that this approach fails when the drone's battery chemistry is taken into account. Real batteries lose their capacity faster when the drone works harder, a phenomenon known as the Peukert effect. To solve this, the team built a computer program that learns to predict the drone's path while simultaneously checking its energy levels against the actual laws of physics. They call this a physics-informed neural network. Instead of just guessing a route and hoping the math works out, the system is trained to understand that if a drone flies faster, it burns more energy, and it adjusts its plan accordingly.

What makes this approach particularly powerful is how it handles the unknown. In a real mission, a drone might encounter stronger winds or a more hostile environment than predicted. The new system uses a method called budgeted uncertainty, which assumes that things will go wrong, but only up to a certain limit. It plans for the worst-case scenario within that limit, ensuring that even if the wind is strong or the threat is high, the mission can still succeed. The researchers proved that their method could generate a wide variety of optimal plans, showing the trade-offs between speed, safety, and energy. For instance, a commander could choose a route that is slightly longer but much safer, or one that is faster but carries a higher risk, and the system would provide the exact numbers to support that decision.

To ensure that the computer's suggestions were not just theoretical but actually workable, the researchers added a "repair" step. Even the smartest computer can make a mistake, suggesting a route that overloads a drone's carrying capacity or leaves it with too little battery. The new system includes a fast, mathematical check that instantly verifies if a proposed route is safe. If the route is unsafe, the system attempts to automatically adjust it, moving supplies from one drone to another or changing the order of stops, until every constraint is met. However, this process is not infallible; if the system cannot find a feasible reassignment among the available options, it signals infeasibility, and the points assigned to the offending drone are flagged for manual replanning by human operators. This check is so efficient that it can be done in a fraction of a second, guaranteeing that the final plan is physically possible before it is ever sent to a drone, provided a solution exists within the reassignment scope.

The researchers tested their system using simulated missions with small groups of drones and supply points. They compared their results against the best possible solutions found by exhaustive computer searches, which take a very long time to run. On these small test cases, their system recovered nearly 86 percent of the best possible outcomes, capturing the most important trade-offs between the different goals. They also verified that their mathematical shortcut for calculating battery drain was accurate to the level of a standard computer's precision, proving that they did not need to run slow, complex simulations to know if a battery would last. While the system has not yet been tested on real drones in the field, the results suggest that it could revolutionize how military logistics are planned, moving away from rigid, linear assumptions to a more flexible, physics-aware approach that keeps both the machines and the people they serve safe.

The study also highlights what remains to be done. The current experiments used fixed speeds for the drones, meaning the system did not yet optimize how fast a drone should fly on each leg of its journey. In the future, the researchers plan to let the system decide the speed as well, which would allow for an even finer balance between speed and energy. They also intend to test the system against other advanced planning methods and eventually validate it with real-world flight data. For now, the work stands as a significant step forward, demonstrating that by teaching artificial intelligence to respect the physical laws of the world it operates in, we can create systems that are not only smarter but also more reliable in the face of uncertainty.

Technical Summary: Certified-Robust Multi-Objective UAV Routing for Military Resupply

Problem Statement
This paper addresses the scheduling of military Unmanned Aerial Vehicle (UAV) resupply missions under three coupled sources of uncertainty: flight-time variability, operational risk, and nonlinear battery-energy depletion. Unlike standard robust vehicle routing problems that often treat energy as a linear cost or a discrete penalty, this work models battery depletion as a physical state governed by Peukert's law. This law dictates that effective battery capacity decreases non-linearly as the discharge rate (driven by airspeed and payload) increases.

The problem is formulated as a tri-objective robust routing model that minimizes:

Mission Duration: The total time to complete resupply, accounting for flight-time uncertainty via a budgeted-uncertainty set (Bertsimas–Sim).
Cumulative Operational Risk: The worst-case exposure to hostile detection or interdiction, also modeled under a budgeted-uncertainty set.
Worst-Case Terminal Energy Shortfall: The maximum deficit between the required safety energy margin and the actual remaining battery energy upon mission completion.

The model is subject to hard constraints on payload capacity and the requirement that every resupply point be covered exactly once. Crucially, the energy safety margin is initially treated as a soft objective (to allow trade-offs) rather than a hard constraint, with feasibility guaranteed post-hoc.

Methodology
To solve this computationally challenging problem, the authors propose Adaptive Physics-Informed Neural Networks (Adaptive PINN), a framework designed to amortize the solution process across multiple instances and priority settings.

Architecture: The network consists of a shared "trunk" that encodes instance features (coordinates, threats, payloads, battery parameters) into embeddings. Two specialized heads branch from this trunk:
- Assignment Head: A $\lambda$ -conditioned head that predicts the routing distribution. It is derived from a continuous-time relaxation of the routing problem using Pontryagin's minimum principle, where the control policy is a softmax of a costate vector. This allows the network to output solutions for different objective weight vectors ( $\lambda$ ) in a single forward pass.
- Energy Head: Predicts the battery trajectory along the route implied by the assignment head. Unlike standard PINNs that solve differential equations, this head is trained to minimize the residual of the Peukert-law ordinary differential equation (ODE) while simultaneously minimizing the task loss.
Adaptive Training: The training process employs a Tchebycheff scalarization (inspired by MOEA/D) to decompose the multi-objective problem. Two key adaptive mechanisms are introduced:
- Neighborhood Weighting: Gradient signals are shared between neighboring weight vectors in the simplex to prevent hard instances from starving neighbors.
- Physics/Task Balance: The weight ( $w$ ) between the task loss (objective minimization) and the physics loss (Peukert residual) is dynamically adjusted during training based on the ratio of their gradient norms, ensuring neither term dominates prematurely.
Certified Repair: Since the neural network output is not guaranteed to satisfy hard constraints, a certified repair operator is applied post-prediction.
- Closed-Form Energy Recursion: A key theoretical contribution is the derivation of a closed-form solution for terminal battery state along any fixed route (Lemma 1). Despite the nonlinearity of Peukert's law, if the route and airspeed profile are fixed, the energy depletion integrates exactly in linear time without numerical ODE solvers.
- Greedy Restoration: Using this exact recursion, the repair operator checks payload and energy constraints in $O(n)$ time. If violated, it greedily reassigns points to other UAVs to strictly reduce the violation, guaranteeing termination in finite moves with a feasible plan.

Key Contributions

Robust Tri-Objective Model: A novel formulation integrating budgeted uncertainty for time/risk with a genuine nonlinear physical energy state (Peukert's law), moving beyond linear approximations.
Adaptive PINN Framework: A unified architecture that combines multi-objective decomposition, Pontryagin-derived control, and physics-informed learning, with adaptive weighting to balance task performance and physical consistency.
Certified Feasibility: A closed-form energy recursion that enables exact, linear-time feasibility checking and a greedy repair operator that guarantees worst-case feasibility restoration independent of the network's learning quality.
Validation: The paper validates the closed-form recursion against numerical integration (showing machine-precision accuracy) and benchmarks a decomposition-based local search (as a proxy for the trained network) against exact enumeration on small instances.

Results

Energy Recursion: The closed-form solution for terminal battery state was validated against 500 random routes using a high-precision numerical ODE solver. The maximum absolute error was $2.7 \times 10^{-12}$ , confirming the recursion is exact to machine precision.
Pareto Front Recovery: On small instances ( $n=7, m=2$ ), a decomposition-based search (using multi-restart local search as a stand-in for the trained network) recovered a Pareto front with a mean hypervolume ratio of 85.9% compared to the exact front obtained by exhaustive enumeration. The recovered front captured the most influential trade-offs, though it contained fewer points than the exact front.
Repair Efficiency: The repair operator successfully restored feasibility for infeasible candidate assignments in a number of moves well within the theoretical worst-case bound, demonstrating the tractability of the exact check.

Significance and Claims
The paper claims to bridge a modeling gap between robust operations research and physical battery dynamics. By treating energy depletion as a nonlinear differential equation rather than a linear cost, the model captures the genuine trade-offs between speed, payload, and endurance in military UAV operations.

The significance of the work lies in its amortized solving approach: instead of restarting an optimization from scratch for every new mission or priority setting, the Adaptive PINN learns a mapping from instance parameters to solutions. The certified repair layer ensures that this speed does not come at the cost of safety, as every returned schedule is mathematically guaranteed to satisfy payload and energy constraints.

Limitations and Future Work
The authors are modest regarding the current state of the trained network. The experiments validating the Pareto front used a local search proxy rather than the trained Adaptive PINN itself; the performance of the actual trained network at scale remains an open empirical question. Additionally, the current experiments hold airspeed fixed at a cruise value, simplifying the trade-off between speed and energy. Future work is identified as training the network at scale, comparing it against evolutionary baselines (like MOEA/D), optimizing airspeed as a continuous variable, and validating the energy dynamics against real-world flight-test data.

Technical Summary: Certified-Robust Multi-Objective UAV Routing for Military Resupply

More like this