Why a Drone's Route Must Be Optimized on the Ground, Not in the Air #7
Mission-analyzer
started this conversation in
General
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
The Problem: A Low-Cost Autopilot Doesn't Know What's Below It
The flight controller of a budget UAV — whether it's the popular ArduPilot stack or one of its counterparts — in the overwhelming majority of cases carries no digital elevation model (DEM) on board. To it, a mission is simply a sequence of points with coordinates and an altitude: either absolute (AMSL) or relative to the takeoff point. Between two neighboring waypoints, the autopilot linearly interpolates altitude and flies a straight line in three-dimensional space, with no "awareness" whatsoever of what the ground is doing underneath that line.
This works fine over flat terrain. But the moment a hill, a ravine, or a sharp elevation change appears along the way, the linear interpolation between two individually-safe points can run straight through the terrain — or, conversely, push the aircraft to an unjustifiably high altitude where there was no need for it.
Professional survey and mapping drones have long solved this problem: they carry their own digital elevation model right in the flight planner, and terrain following is a standard feature — see, for example, the implementation overview in UgCS (geoconnexion.com) or in Delair's products, which directly use open SRTM data for exactly this purpose (delair.aero). But that's the privilege of expensive platforms. A mass-market, low-cost autopilot simply doesn't have this capability — not in memory, not in compute, and not in the firmware architecture itself.
Which means the task of "lay out a route such that the autopilot, knowing nothing about the terrain, still stays a safe distance from it" has to be solved before takeoff — on the ground, in the mission planner, by adjusting the sequence of points and their altitudes in advance for the specific terrain under the specific route.
What Exactly Needs to Be Guaranteed in Advance
Solving this on the ground means holding several requirements at once, and they constantly pull in different directions:
The problem is that all of these requirements compete for one and the same resource — the number of waypoints — which is finite and small on an autopilot. On budget boards built around Pixhawk/Cube Black, the practical ceiling is on the order of a few hundred points, running directly into EEPROM/FRAM capacity; this comes up regularly in open ArduPilot community discussions, up to and including proposals to store the mission on an SD card precisely because of this limit (discuss.ardupilot.org; see also the storage-format discussion at github.com/ArduPilot/ardupilot#2391). In other words, a waypoint is not a free resource to be spent generously on every little thing. Every new point is a withdrawal from a shared budget, and the algorithm has to manage that budget deliberately, not just "add a point whenever something doesn't check out."
In our implementation none of these limits are hard-coded directly; they're moved into two separate, independently configurable profiles. The aircraft profile describes what's physically determined by the specific airframe — above all, the maximum climb and descent angle. The route type describes what depends on the specific mission and region: the target altitude over controlled versus occupied territory, the altitude right at the moment of crossing the demarcation line, the allowed angle specifically for the border-crossing maneuver (which can differ from the general angle limit), and the point budget itself allocated to altitude optimization. This separation lets you swap out a single airframe or a single mission without touching the rest of the settings.
Our Scheme
What we ended up with is two sequential but connected stages of offline optimization: first by coordinates (avoiding no-fly zones), then by altitude (terrain, angles, point budget).
flowchart TD A[Mission: waypoints + SRTM terrain +<br/>no-fly zones + aircraft profile] --> B subgraph S1["Stage 1 — coordinates"] B[No-fly zone avoidance:<br/>tangent graph + Dijkstra] end B --> C subgraph S2["Stage 2 — altitude (loop with feedback)"] C[Phase 0<br/>critical clearance violations] --> D D[Phase 1<br/>climb/descent angle control<br/>+ pinched-point resolution] --> E E{Phase 2:<br/>clearance OK?} E -- no --> F[Raise altitude within angle limit,<br/>otherwise — new point] --> D E -- yes --> G{Point budget<br/>remaining?} G -- yes --> H[Phase 3<br/>splitting long edges,<br/>hugging the terrain] --> D G -- no --> I[Border crossing<br/>as a separate block] end I --> J[Finished mission]Stage 1 — Coordinate Optimization: No-Fly Zone Avoidance
Each settlement (or other no-fly zone) is represented as a circle with a safety radius around it. A straight line between two waypoints that clips such a circle has to be replaced with the shortest detour — and here we use the classic combination for this problem: a graph built from the common tangent lines between every geometrically relevant pair of obstacles (a tangent/visibility graph), plus a shortest-path search over that graph using Dijkstra's algorithm — the very same algorithm Edsger Dijkstra described back in 1959 in a short two-page note [1].
This is a well-established approach, studied for decades in computational geometry and robotics — from the classic construction of a visibility graph [2] to its simplified, faster variants that use common tangents instead of the full graph over every obstacle vertex [3, 4]. For circular obstacles (and a settlement is naturally modeled as a circle) there's also dedicated work specifically on avoidance via tangents to circles [5].
A practical nuance that usually doesn't show up in textbook treatments: if tangents are computed between every pair of obstacles indiscriminately, the graph bloats needlessly — edges appear between geometrically distant obstacles that could never plausibly sit on the same reasonable path, and on the circle that actually does lie on the path, this produces extra, nearly-coincident tangent points. In our case this is filtered by a relevance threshold (based on the distance between circles), and if a path still can't be found after filtering, there's an automatic fallback to the full, unfiltered graph — so correctness of the detour is never sacrificed for geometric tidiness.
This is also the right place to explain why coordinates and altitude are computed separately, one after the other, rather than as a single combined three-dimensional optimization. This isn't our own invention but established practice: splitting a trajectory into a horizontal (lateral) and a vertical profile and computing them independently, one after the other, is a standard technique in aircraft trajectory planning, reflected among other places in aviation-automation patent practice [6], and "first a two-dimensional trajectory in the plane, then altitude" is explicitly described as the conventional approach in current UAV trajectory research [7], as well as in dedicated recent work on flight-path planning for a scouting UAV, where after computing XY waypoints as a separate first step, "these waypoints were then used to optimize the flight altitude" [8]. The reasoning behind the split is simple: the horizontal problem (go around obstacles by the shortest path) and the vertical one (terrain, angles, point budget) are, by nature, different optimization problems with different constraints, and solving them independently is easier to control and debug than one coupled three-dimensional model.
Stage 2 — Altitude Optimization: Terrain, Angles, Budget
Once the route has gone around all no-fly zones horizontally, the second stage fits the altitude along the entire route. This is organized as several sequential, specialized passes, each aimed at its own specific job:
Phase 0 — eliminating critical violations. First, in a single pass, every spot where the terrain physically sits above the flight path (negative clearance) is removed — these are the most dangerous cases, and they need to be closed before any angle work starts, otherwise a sharp local "spike" wrecks the neighboring segments.
Phase 1 — climb/descent angle control. Every violation of the angle limit is eliminated completely, down to zero, by shifting existing points along the route, without adding new ones. A separate case is handled when a point ends up "pinched" between two competing angle requirements on both sides at once (wherever you shift it, the neighboring edge breaks) — in that case, instead of a horizontal shift, the point's own altitude is adjusted, chosen so that it satisfies the limit on both sides simultaneously.
The angle limit itself isn't an arbitrary number — it's a direct consequence of the airframe's available vertical and horizontal speed. If Vᵥ is the available rate of climb or descent (m/s) and Vₕ is the horizontal speed (m/s), then the maximum sustainably-held flight path angle γ follows from a simple ratio of speeds:
This is a direct consequence of decomposing the velocity vector into vertical and horizontal components — the same angle aerodynamics calls the flight path angle. In practice this means the angle limit for an aircraft profile doesn't need to be eyeballed: given the airframe's rated climb rate and cruise speed, γ is computed once with this formula and entered into the aircraft profile as a constant.
Phase 2 — eliminating insufficient clearance. Wherever the terrain runs too close to the trajectory, priority goes to raising the altitude of the nearest existing points (within limits that won't violate the angle constraint), and only if that isn't enough is a new point added. This is a direct application of the "a waypoint is a resource" principle: the cheap fix (raise something that already exists) is always preferred over the expensive one (add another point).
Phase 3 — tight terrain hugging. As long as point budget remains, the longest remaining segments are split in half, and the new point's altitude is interpolated along the existing profile, corrected for the actual terrain right at that spot. This forces the route to "hug" dips and folds in the terrain instead of flying one straight line for dozens of kilometers — which is exactly where unjustified excess altitude tends to pile up unnoticed without explicit splitting.
Border crossing. This is carved out into a separate, geometrically isolated block: if the target altitude differs noticeably on either side of the border, the start and end points of the climb/descent maneuver itself are computed separately, with their own allowed angle (configurable independently from the general one, since it can differ for a specific airframe) — so the crossing itself never gets tangled up with the ordinary obstacle-avoidance or clearance-control logic.
All phases run in a shared loop with feedback: if Phase 2 or 3 changed anything, Phase 1 runs again — a new point might have accidentally created a local angle violation right where the terrain changes sharply at the insertion point.
How This Relates to Mission Planning as a Whole
Everything described above solves the problem for an already-given set of waypoints — that is, the en-route portion of the mission. But in a broader framing, UAV mission planning is typically broken down into several segments, including the flight to the task area and the task area segment itself — this kind of segmented representation of a mission from takeoff is explicitly described in work on UAV trajectory control [9, 10].
Our optimization scheme doesn't replace this breakdown — it works within it: it takes an already-given sequence of points, set by the pilot or the planner, and makes it physically flyable given the real terrain. The landing segment deserves particular attention here: the target altitude there typically doesn't descend gradually but follows its own approach-specific logic, which is exactly why, in our implementation, the last few edges of the route before the landing point are deliberately excluded from the overall clearance and angle optimization — the landing approach is a separate segment of the trajectory with its own specific requirements, and it can't be measured with the same yardstick as the en-route portion of the flight.
In other words, the full task of mission planning is broader than what our scheme solves — it also covers choosing the waypoints themselves, the parameters of the task-area segment, and the logic of the approach itself. Our part is to guarantee that the route already chosen is physically safe and fits within the airframe's flight limits, while spending the strictly limited resource of waypoint count economically.
Results on a Real Route
The scheme was tested on a real mission of ~623 km and 30 waypoints — the source file and the results of both optimization stages are in the root of the project repository:
example_mission.waypoints(as is),coords_optimized.waypoints(after no-fly zone avoidance), andfull_optimized.waypoints(after full optimization, including altitude).One number here deserves a separate explanation — angle violations increasing from 3 to 24 right after coordinate optimization. This isn't a bug; it's a direct consequence of the no-fly-zone avoidance stage working only with horizontal geometry: every detour adds short arc edges around the obstacle, and the altitude at these new points is taken by linear interpolation of the existing profile — with no regard for the fact that on a short detour-arc segment, that interpolation can produce an unacceptably steep angle. This is exactly why altitude optimization isn't an optional nice-to-have but a mandatory second stage: without it, the result of the first stage is less flight-ready than even the unoptimized original mission. After it, only one of the 24 violations remains (2.0° — effectively right at the limit boundary, not a real overshoot), while the route length barely changes at all (634.1 → 634.0 km); the point count, meanwhile, is the direct price of terrain detail, discussed separately below.
A Separate Tool: Clearance Distribution
To visually assess what's happening with clearance (the altitude margin above terrain) across the entire route at once, rather than at individual points, the repository includes a separate script,
clearance_distribution.py. It's deliberately not built into the main planner: it takes any mission file as input, samples clearance at the same step (25 m) the optimization algorithm itself uses, and builds a distribution — a histogram of how many route points fly at what altitude margin. Two mission files can be loaded at once ("Mission 1" and "Mission 2") — both distributions are drawn on the same coordinate grid, which immediately shows the integral before/after picture: not just the minimum and median (given as numbers in the legend), but the shape of the whole distribution — for instance, whether a characteristic narrow peak around the target AGL appears after optimization instead of a wide, blurry "tail" of excess margin.What's Next
The scheme evolved iteratively: some of the decisions (for example, splitting "terrain hugging" and "climbing" into separate phases, or batch-processing every found violation in a single pass instead of one at a time) didn't appear on the first attempt — they were a direct response to specific problems found in practice: races between phases, cases where a point ends up pinched, and similar issues. Further development will likely move toward a more precise estimate of the "payoff" from each added point — not just clearing a violation, but evaluating where investing the remaining point budget gives the greatest effect.
References
All reactions