geohashim

terrain-follow

A checker and planner for drone missions over hills. For every leg it proves a lower bound on the clearance above the terrain, counting the error in the elevation data, in the vehicle's altitude and in how far off the line it may fly. A leg it can't prove is refused, and plan raises the mission until every leg is proven.

Ground stations give mission altitudes relative to home by default, so "60 m" means 60 m above the take-off point. Where the ground rises along the way, that is a line drawn into the hillside, and a multicopter without a rangefinder flies it there. Checking the terrain under the waypoints, or every so many metres along the line, can miss the high point between samples, the ridge beside the line, and the few metres the elevation data itself is wrong by.

View on GitHub How the bound works

Plays the seven stages below in order, about 60 seconds. Scroll or press Esc to stop.

Language
Python 3.11 or newer, no dependencies
Tests
237 passing with pytest, on Python 3.11, 3.12 and 3.13
Bound
The exact maximum of the elevation surface over each 5 m piece's corridor
Budget
30 m clearance after 4 m DEM, 5 m altitude and 10 m cross-track error, by default
Missions
QGroundControl .plan files, or CSV
Flown
PX4 v1.15.4 software-in-the-loop with Gazebo Classic, over the same terrain
License
MIT; the elevation clip is Copernicus data
terrain-follow check examples/delivery.plan --dem data/zurich-cop30.asc DEM data/zurich-cop30.asc: 180 x 288 posts about 31 x 21 m apart, elevation 399-729 m

Real runs of terrain-follow 0.1.0, output verbatim. delivery.plan is the repo's example: a 3.7 km delivery from PX4's default simulator home in Zurich, at 60 m above home. The elevation data is the repo's clip of the Copernicus GLO-30 DEM. terrain-frame.plan in the last tab is Illustrative input: the same mission with one waypoint switched to QGroundControl's terrain frame.

1Read the mission the way PX4 flies it

A mission file is a list of items, and the checker needs the path the vehicle actually flies through them. terrain-follow reads QGroundControl .plan files and a small CSV, and models what each item means to a PX4 multicopter.

  • Takeoff climbs straight up, a waypoint is a straight line in three dimensions, and a landing descends straight down. RTL climbs to 60 m above home if it is lower, then flies home level.
  • Relative altitudes become AMSL with the plan's home altitude, --home-alt, or the DEM at home. Items that don't move the vehicle, like a speed change, pass through.
  • Terrain-relative frames are refused, because their real altitude depends on the terrain data the ground station had. So are survey items, and a landing that isn't straight below the last waypoint.

A leg it can't model is a leg it can't prove. It names the item and the reason instead of guessing.

Six missions, read as legs or refused

    
            
    
            
    delivery.plan is the repo's example. The other five are Illustrative input, written for this page as small edits of it. The item list is a summary of each file; the output is what terrain-follow check printed, with its three header lines left out where there is a table.
    
          
    
        
    
      
    
    
    

    
    
      
    
        
    
          
    2Take the exact maximum, not samples
    
          
    Between elevation posts, the terrain is the bilinear interpolation of the four posts around it. A bilinear patch is linear along each axis, so over a rectangle inside one cell its maximum is at one of the rectangle's corners. Clip the corridor's box to every cell it touches, evaluate the corners, and the largest is the exact maximum of the surface over the box.
    
          
      
            
    • No samples, so nothing between samples to miss: not a peak between posts, and not a ridge just beside the line.
      • 
            
    • The corridor is everywhere within --horizontal-error (10 m) of the piece. Metres become degrees with the WGS84 radii at that latitude, rounded up by 0.1% so a corridor never shrinks.
      • 
            
    • The real ground may be up to --dem-error above the surface: 4 m is the Copernicus GLO-30 specification at LE90.
      • 
          
    
        
    
        
    
          
    
            
    
              
    One 5 m piece of the refused leg
    
              
    
                
                
                
                
              
    
            
    
            
    
            
    
            
    Real posts from data/zurich-cop30.asc, 21 m apart east to west and 31 m north to south, around piece 461 of 487 on leg 3 to 4, 2.3 km into the leg. The box, the corners and their values come from the repo's own DEM class, run in a scratch script. The box holds no post at all, so the nearest-post mutant falls back to the closest one.
    
          
    
        
    
      
    
    
    

    
    
      
    
        
    
          
    3Count every error, then take the smallest
    
          
    Each leg is cut into pieces no longer than 5 m. On a piece the planned altitude is at least the lower of its two ends, the vehicle may be 5 m below that, and the ground may be 4 m above the surface's maximum over the corridor. The leg's proven clearance is the smallest of these over its pieces.
    
          
    clearance >= min(altitude at the ends) - max(DEM over the box) - dem_error - alt_error
    
          
      
            
    • On the refused leg the bound is 9.5 m below the plain centre-line clearance: 9 m of errors, and half a metre of higher ground within 10 m of the line.
      • 
            
    • Below the required 30 m, the leg is refused. The checker also says where the line itself enters the terrain: 842 m into leg 3 to 4, which is 2.15 km along the path.
      • 
          
    
        
    
        
    
          
    
            
    
              
    The delivery as planned, 60 m above home
    
              
    
                
                
                
                
                
              
    
            
    
            
    
            
    
            
    
            
    Every point is from check(keep_profile=True) on delivery.plan, the profile the CLI draws with terrain-follow profile, taken every 10 m. Proven and centre-line figures are the CLI's.
    
          
    
        
    
      
    
    
    

    
    
      
    
        
    
          
    4Try to break the bound
    
          
    A sound bound is never above the true minimum clearance. terrain-follow mutants makes random cases, a small rough DEM with hills and noise, a leg over it and a random budget, and compares the bound with a brute-force search that samples the corridor every metre along and on a grid across. Sampling can only miss low points, so a correct checker is never above it.
    
          
      
            
    • Six plausible ways of computing "the clearance" each overstate it somewhere, and are caught, five of them on the first seed.
      • 
            
    • The bound sits 1.5 m below dense sampling on average. That is the price of being sound, and a test keeps it under 5 m so the bound can't go vacuous.
      • 
            
    • pytest runs the property on 150 fixed seeds, and under Hypothesis with any piece length from 0.5 to 20 m. CI also runs 1,000 seeds on every push.
      • 
          
    
        
    
        
    
          
    
            
    
              
    Cases where each variant claims more clearance than there is
    
              
            
    
            
    
              
    
            
    
            
    terrain-follow mutants --seeds 1000, the command CI runs, output read straight off the table: overstated cases out of 1,000, and the first seed that caught each one.
    
          
    
        
    
      
    
    
    

    
    
      
    
        
    
          
    5Refuse what it can't prove
    
          
    This is the line. A mission goes on only if every leg is proven to clear the terrain by the required margin. Anything short of that exits 1 and names the leg. The budget is a set of flags, so whoever flies the mission states it.
    
          
      
            
    • Exit 0 is proven, 1 refused, 2 bad input. A leg whose corridor leaves the DEM is refused as "cannot be checked".
      • 
            
    • A tighter budget can only lower the bound, so the same mission can go from proven to refused.
      • 
            
    • The defaults are a stated budget, not a measurement of anyone's aircraft. At LE90, one post in ten may be off by more than 4 m.
      • 
          
    
          
    The bound holds for the DEM plus the errors you state. A mast, a crane or trees that grew since 2015 aren't in the DEM, and no margin fixes that.
    
        
    
        
    
          
    
            
    
              
    The planned mission under four budgets
    
              
    
                
                
                
                
                
              
    
            
    
            
    
              
    
            
    
            
    Real runs of terrain-follow check examples/delivery-planned.plan --dem data/zurich-cop30.asc with each flag, header lines left out; the exit code is the shell's. The first is the default budget.
    
          
    
        
    
      
    
    
    

    
    
      
    ClearedAbove this line terrain-follow reads the mission and proves each leg against the terrain. Below it, only a mission whose every leg is proven goes on, and it is flown.
    
    
    
    
  
    

  
    
    
    
      
    
        
    
          
    6Raise the mission until every leg is proven
    
          
    terrain-follow plan keeps the horizontal path exactly as planned. Only altitudes change, and only upwards. The result is written with AMSL altitudes and checked again, leg by leg, by the same checker.
    
          
      
            
    • Each 5 m piece gets a floor: the exact maximum over its corridor widened by one more piece length, plus the errors and the 30 m.
      • 
            
    • Climbs move earlier and descents later until none is steeper than 0.15 m per metre flown. At 12 m/s that is a 1.8 m/s climb, inside PX4's default 3 m/s.
      • 
            
    • From each kept point it takes the farthest point a straight line can reach while staying on or above the profile, if that costs at most --slack of extra altitude. A landing gets a waypoint straight above it.
      • 
          
    
          
    The extra piece length is what makes the final check pass by construction: any piece the checker cuts lies inside the widened box of every planner piece it touches. The check still runs.
    
        
    
        
    
          
    
            
    
              
    Planned, at three settings of --slack
    
              
    
                
                
                
                
              
    
            
    
            
    
            
    
            
    
            
    Waypoints are from the .plan files terrain-follow plan wrote with each setting; 15 m gives the repo's examples/delivery-planned.plan byte for byte. The dashed line is the corridor maximum plus 39 m, as the CLI's profile draws it.
    
          
    
        
    
      
    
    
    

    
    
      
    
        
    
          
    7Fly both in PX4 SITL
    
          
    Both missions are flown in PX4 v1.15.4 software-in-the-loop with Gazebo Classic, over a world built from the same DEM. Every post is a vertex of the ground mesh, placed with the projection Gazebo's GPS simulator uses, so the vehicle's GPS reports a post's own coordinates over it. PX4 flies each .plan as uploaded.
    
          
      
            
    • Everything is measured from the vehicle's own position estimate against the DEM, by sitl/analyze.py.
      • 
            
    • CI flies both missions on every push and fails if any of the README's claims stops holding: the original hits the hillside, the planned one lands at the drop point with at least 30 m measured clearance, within the 10 m and 5 m budgets.
      • 
          
    
          
    
        
    
        
    
          
    
            
    
              
    Two flights, measured from telemetry
    
              
    
                
                
                
              
    
            
    
            
    
            
    
            
    
            
    
          
    
        
    
      
    
    
    

    
    
      
    
        
    
          
    Measured, not assumed
    
          
    What the checker predicted, set against both missions flown in PX4 SITL on this machine, and what the checks cost. The README's own run, from the same commit, gave the same contact point and the same lowest clearance.
    
        
    
        
    
          
    
            
    Where the line meets the hill
    
            
    The checker said the original line enters the terrain 842 m into its second leg, 2.15 km along the path. In SITL the vehicle made contact at 2.14 km.
    
            
    Predicted 2.15 kmContact 2.14 km
    
          
    
          
    
            
    Proven, then flown
    
            
    The planned mission was proven to keep at least 30.1 m. Flown, its lowest clearance over the DEM was higher, because SITL spends little of the 9 m error budget.
    
            
    
              
    Proven30.1 m
    
              
    Measured39.7 m
    
            
    
            
    The simulated ground is the DEM, so the DEM error is zero, and PX4 stayed within 2.21 m of the line sideways and 0.36 m below it.
    
          
    
          
    
            
    Fast enough for every push
    
            
    On this machine with Python 3.12, while other jobs kept it busy:
    
            
    237 tests 6.2 s1,000 seeds 11.5 s
    
            
    The README says about 10 s and 11.8 s. Each seed checks the bound and six mutants against a brute-force search of the corridor.
    
          
    
        
    
      
    
    
    

    
    
      
    
        
    
          
    237 tests, most of them the property
    
          
    Counted with pytest -q: 237 passed on Python 3.11, 3.12 and 3.13. 190 of them are two properties run over many inputs: soundness on 150 seeds, and the exact box maximum on 40 random grids.
    
        
    
        
    
          
    
            
            
      
          
      
          
      
            
      Weighted toward the claim
      
            
        
              
      • Soundness: never above the brute-force minimum on 150 seeds, and on 60 Hypothesis examples with any piece length from 0.5 to 20 m; every mutant caught in 120 cases; the bound within 5 m of sampling on average.
        • 
              
      • The surface: the box maximum is never below a 61 by 61 sample of the box on 40 random grids, a peak beside the line counts, and no-data posts and boxes leaving the grid are refused.
        • 
              
      • The planner: the example raised until proven, altitudes only ever raised, nine combinations of gradient and clearance, and fewer waypoints with more slack.
        • 
              
      • Missions: terrain frames and survey items refused, RTL climbing to its altitude, a landing away from the last waypoint left unproven, CSV and .plan round trips.
        • 
              
      • The CLI: exit codes, and a tighter budget flipping the planned mission to refused.
        • 
            
      
            
      CI also runs ruff, mypy, 1,000 mutant seeds, a check that the planned example and the README profile match what the code makes, and the SITL flights. Run 38665143703 on cd490b4 passed every job; the SITL job took 13 minutes.
      
          
      
        
      
      
      
    
      

    
      
      
      
        
      
          
      
            
      Deliberately missing
      
            
      
              
      Obstacles the DEM doesn't have
      Copernicus data is from 2011 to 2015. Masts, cranes, power lines and grown trees aren't in it, and a DEM that misses a mast can't be corrected by a margin.
      
              
      Terrain-relative altitudes
      QGroundControl's terrain frames depend on the terrain data the ground station had. Those items are refused.
      
              
      Takeoff and landing
      The climb leaves the ground and the final descent ends on it, on purpose. Neither is a leg to prove.
      
              
      Fixed-wing flight
      No turn radius, loiter circles or fixed-wing climb limits; corners are covered only by the cross-track budget.
      
              
      A geoid
      Altitudes are compared as given. A receiver on another geoid model can differ by a metre or so, which belongs in --alt-error.
      
              
      Real hardware
      The flights are SITL only, over a mesh made from the same DEM.
      
            
      
          
      
          
      
            
      Run it
      
            
      git clone https://github.com/ahmed-hashim-pro/terrain-follow && cd terrain-follow
python3 -m venv .venv && . .venv/bin/activate
pip install -e '.[dev]'

terrain-follow check examples/delivery.plan --dem data/zurich-cop30.asc
terrain-follow plan  examples/delivery.plan --dem data/zurich-cop30.asc -o safe.plan
terrain-follow check safe.plan --dem data/zurich-cop30.asc
terrain-follow mutants --seeds 300

# The suite, then the SITL flights (Docker, about 5 GB).
pytest -q
make sitl
      
            
      Python 3.11 or newer and nothing else at run time. Any DEM in geographic coordinates that GDAL can read works, clipped to an ESRI ASCII grid.