Navigation and exploration

Notes on the decision layers of an autonomous drone: given a pose estimate and a map (the subject of VIO and SLAM), how the vehicle decides where to go and how to get there safely. Companion to the earlier system-design notes, which chose an architecture; this one surveys the field the way the VIO/SLAM notebook does.

Core take: once a goal is chosen, flying to it is mature engineering; choosing the goal is the open problem. Finding a route through a mapped building, turning it into a smooth trajectory, and not hitting things on the way are solved problems with healthy open implementations. What remains genuinely open — and where an indoor-capture product differentiates — is deciding where the drone should go next. That decision comes in two distinct flavors: exploration (observe all the space) and capture planning (photograph all the surfaces, well). They look similar, optimize different quantities, and only the first has mature public solutions.

A second theme runs through everything below: no single planner can be both globally smart and instantly reactive, so the work is split into layers. Each layer solves a coarser version of the problem over a longer horizon, less often; the layer below fills in the detail faster. Most of the design judgment in a navigation stack is deciding what each layer is allowed to ignore.

The stack

Every deployed system decomposes the same way, whatever the vehicle:

Layer Question Rate Horizon
Mission / goal selection what is worth visiting next? 0.1–1 Hz mission
Global planner which route through known space? 0.5–5 Hz whole map
Local planner / trajectory optimizer which dynamically feasible curve for the next few seconds? 5–30 Hz 2–10 m
Tracking controller which attitude/thrust right now? 100–500 Hz one step
Flight controller which motor commands? 1 kHz none

Two structural facts about this table:

  • Commands flow down, failures flow up. Each layer hands the one below a reference to follow — a route, a trajectory, an attitude — and receives back failure signals: blocked, infeasible, degraded. A stack is healthy when each failure is handled at the lowest layer able to absorb it: a newly seen obstacle should bend the local trajectory, not wake the mission planner.
  • The layers assume different world models. The global planner reads the full (drifting, occasionally corrected) map; the local planner trusts only the recent, high-confidence neighborhood; the controller assumes free space entirely. This is why map jump-on-loop-closure semantics (REP-105 map vs odom frames, covered in VIO and SLAM) are a planning-layer concern: layers above the local planner may see jumps, layers below must never.

For a quadrotor specifically, one property makes the whole stack tractable: differential flatness. A quadrotor’s full 12-dimensional state and its motor inputs can be recovered algebraically from just the position trajectory and yaw, plus their derivatives. Planners therefore never simulate the vehicle: they draw smooth curves in x, y, z, yaw, and checking that a curve is flyable reduces to bounding its derivatives (velocity, acceleration, jerk). A car offers no such shortcut — its no-sideways-motion constraint must be honored by the planner itself — which is why drone trajectory optimization is in some ways simpler than parking.

Global planning: routes through known space

Input: the map (occupancy or ESDF — Euclidean signed distance field, per-voxel distance to the nearest obstacle) and a goal. Output: a collision-free path, geometric only — no dynamics yet. Two families:

Search-based — discretize space, run graph search:

  • A* on a grid/octree: optimal, complete, the default indoors where maps are volumetric anyway. JPS (Jump Point Search) exploits grid symmetry to run an order of magnitude faster with identical results; standard in drone stacks.
  • D* Lite / incremental variants repair the previous solution when the map changes instead of replanning from scratch — historically important, less critical now that full A* on a house-sized map takes milliseconds.

Sampling-based — throw random configurations, connect feasible ones:

  • RRT (rapidly-exploring random tree) and descendants — RRT* (asymptotically optimal), Informed RRT*, BIT* (batch informed trees); PRM (probabilistic roadmap) when many queries hit one static map. OMPL packages the whole family.
  • Sampling planners earn their keep in high-dimensional configuration spaces (a 7-joint arm) or spaces too large to discretize. A drone searching 3D positions in a building-sized voxel map is neither: grid search is simpler, faster to reason about, and effectively optimal there. Sampling planners still show up in drone stacks (the VOXL SDK’s voxl-mapper plans with a vendored RRT*) — more by lineage than by necessity.

One level of abstraction up sits topological planning: extract a sparse graph — rooms as nodes, doorways as edges — from the metric map, and route on that instead of on voxels. It is cheap at building scale, it is where semantic labels (“kitchen”, “hallway”) naturally attach, and a multi-room capture mission ends up needing exactly this graph anyway to order its work.

Compute is a non-issue at this layer: milliseconds per solve on one core at house scale. In fact the whole planning stack is cheap — the only decision-side layer with real compute weight is goal selection above it, where estimating what a candidate view would reveal means ray-casting the map thousands of times.

Local planning and trajectory optimization

The geometric path is not flyable: it has corners and no notion of time. The local layer converts it into a smooth, dynamically feasible, collision-free trajectory over the next few seconds, replanned continuously. The lineage that leads to the current defaults:

  • Minimum-snap polynomials (Mellinger & Kumar 2011) — the founding result: with differential flatness, encode the trajectory as piecewise polynomials and minimize snap (4th derivative of position, a proxy for control effort); the optimization is a small QP (quadratic program). Everything since is about adding obstacles and time allocation.
  • Safe flight corridors — carve a chain of overlapping convex regions (boxes or polyhedra) out of free space around the path, then constrain the trajectory inside them. Convex constraints keep the optimization fast and make safety auditable: trajectory inside corridor, corridor inside known-free space, done. FASTER (MIT) is the reference for doing this with a hard safety guarantee — it always maintains a committed backup trajectory ending in a stop inside known-free space.
  • B-spline / gradient methods — represent the trajectory as a B-spline and push control points away from obstacles by descending the ESDF gradient. Fast-Planner (HKUST) is the classic kinodynamic-search-plus-B-spline pipeline; EGO-Planner (ZJU) made it ESDF-free — computing gradients only along the trajectory — cheap enough for a 20 g computer, and EGO-Swarm extended it to decentralized multi-drone.
  • MINCO / GCOPTER (ZJU) — the current state of the art in trajectory representation: minimum control effort polynomials with waypoints and segment times jointly optimized through a clever sparse parameterization, corridors handled by diffeomorphic mapping. Most 2023+ academic planners build on it.
  • MPC (model predictive control) — re-solve a short-horizon optimal control problem every cycle. The natural home for dynamic obstacles and aggressive tracking; heavier per-cycle, and the flat-output planners above cover most static-world needs without it.

Two concerns cut across all of these methods. Time allocation: deciding how many seconds each trajectory segment gets. Allocate too generously and the flight is slow; too tightly and the segment demands infeasible accelerations. Naive planners fix durations by heuristic and suffer either way; MINCO optimizes durations jointly with geometry, which is much of why it wins. Perception awareness: the trajectory determines what the camera sees, and the estimator (VIO) needs to see somewhere useful. In practice this means scheduling yaw so the camera faces the direction of travel (new obstacles) or feature-rich structure (tracking quality), rather than letting yaw be an afterthought.

Compute: the entire local layer is CPU-light by design — EGO-class planners report sub-millisecond replans, corridor QPs take single-digit milliseconds. Like VIO, this layer is never why you buy a bigger computer; budget well under one core at 10–30 Hz replanning.

Safety: the layers under the planner

Obstacle avoidance is not one mechanism but a hierarchy of increasingly dumb, increasingly trustworthy fallbacks — designed so that each catches the failures of the smarter layer above:

  1. The planner itself — trajectories constrained to known-free space with an inflation margin (obstacle cells grown by vehicle radius plus stopping distance plus pose uncertainty — the derivation our collision-margin lesson works through). The subtle rule for unknown space: unknown is not free. A safe planner only commits to trajectories it can stop within space already observed to be free — FASTER’s committed-backup formalizes this.
  2. Reactive avoidance — a fast loop consuming raw depth or a local ESDF, bending or braking the current trajectory when something appears where the map said nothing was. Dynamic obstacles (people, pets — guaranteed in an occupied house) live here: velocity-obstacle methods or simply generous margins plus braking, since houses leave no room for elegant evasion.
  3. Autopilot-level guards — PX4/ArduPilot collision prevention: rangefinder or DISTANCE_SENSOR-fed speed limiting and hard stops near obstacles, working even when everything above is dead. ModalAI’s VOA (Voxl Obstacle Avoidance) in voxl-vision-hub is this tier.
  4. Failsafes — offboard-link-loss, geofence, battery: land or hold. Not avoidance, but the reason a planner bug is an abort, not a crash.

The architectural principle from the system-design notes bears repeating here because the literature quietly assumes it: layers 2–4 must run on the vehicle. A planner on a ground station may command; nothing off-board may be load-bearing for not hitting the wall.

Exploration: choosing where to look next

The first of the two goal-selection problems. Exploration is goal selection when the map is incomplete: repeatedly pick the motion that reveals the most unknown space, until nothing reachable remains unknown. Every method is built from the same three ingredients — generate candidate goals, estimate the gain of each, order the visits — and methods differ mainly in which ingredient they invest in:

Frontier-based (Yamauchi 1997, still the backbone): a frontier is a boundary cell between observed-free and unknown. Cluster frontiers, pick one (nearest, biggest, cheapest), go, repeat. Complete by construction — no frontiers left means nothing reachable remains unseen — and greedy by nature, which costs travel distance.

Sampling / next-best-view: sample candidate viewpoints, score each by expected information gain (unknown voxels visible from there, weighted by sensor model), pick the best. The receding-horizon variant (NBVP, ETH 2016) grows an RRT of viewpoints, executes only the first edge of the best branch, and regrows — handling the fact that the map changes underfoot. Gain evaluation (ray-casting from every candidate) is the expensive step and the reason this layer, unlike planning, can eat a core.

Hierarchical hybrids — the current state of the art. Greedy frontier chasing wastes travel (it ping-pongs across the building as the “nearest” frontier flips); deep view-tree lookahead pays exponentially for foresight. Modern planners escape the dilemma by splitting the problem by scale — global visit order computed cheaply over the whole map, motion optimized expensively only nearby:

  • FUEL (HKUST 2021) maintains incremental frontier information and solves a TSP (traveling salesman problem) over frontier clusters for global tour order, then optimizes an aggressive local trajectory toward the next one. The quantitative reference for fast single-drone exploration.
  • TARE (CMU 2021) — coarse global coverage tour over a sparse representation, fine trajectory only inside a local horizon. Ground-robot-born, the other standard baseline.
  • The 2024–2026 crop refines the same recipe — better frontier structures, omnidirectional sensing, spatio-temporal candidate memory (FSMP, OPAL, STExplorer) — without changing the shape: frontiers + gain + tour.

Multi-robot extends the tour problem to task allocation (RACER, decentralized pairwise workload partition); relevant to us only as evidence the single-drone formulation is stable.

Caveats that matter in practice: published comparisons run in favorable sim worlds, and house interiors — doorway bottlenecks, mirrors, furniture clutter — degrade all of these systems. And “exploration complete” means every voxel got classified, not that every surface got photographed well — the gap the next section is about.

Capture planning: coverage of surfaces, not space

Exploration’s objective — no unknown voxels — is the wrong objective for reconstruction. A room can be fully explored while half its surfaces were seen exactly once: obliquely, from across the room, motion-blurred. Reconstruction needs every surface observed well — close enough, head-on enough, from several angles, with overlap between shots — and no exploration planner optimizes for that. The planning problem that does appears in the literature under several names:

  • Coverage path planning (CPP) — geometry known in advance, compute a sweep (lawnmower passes, orbits). The mature, boring case: bridge inspection, agriculture. Indoors it applies only after a first pass has produced geometry — which is exactly what a two-pass architecture exploits.
  • NBV for reconstruction — the online version: score candidate views by expected reconstruction gain (poorly observed surface area, grazing-angle penalties, revisit needs) instead of unknown-voxel count. The surface- quality ledger from the system-design notes — per-surface-patch view count, best angle, best distance, blur — is precisely the data structure this planner reads.
  • Active reconstruction in the radiance-field era (the lively 2024–2026 thread): when the online map is the photometric model — 3DGS (3D Gaussian Splatting) — view gain can be computed in the target representation itself, e.g. Fisher information over Gaussian parameters (AG-SLAM), Shannon mutual information (GauSS-MI), or rendering- completeness heuristics (ActiveSplat, ActiveGS, HGS-Planner). The promise over voxel-gain NBV: the planner optimizes what the final product actually is — rendered image quality — closing the loop that classical pipelines leave open between “covered” and “reconstructs well”. Compute today is desktop-GPU class, so on our architecture this planner lives PC-side, commanding the drone over the offboard link.

The two objectives map directly onto mission structure: explore first (fast, gain = unknown space), then capture (deliberate, gain = surface quality), then verify (re-render or re-project the model and hunt for holes). GLEAM-class learned exploration policies (the Week-1 GLEAM report) solve only the first phase. The capture phase on house interiors has no off-the-shelf solution — the same gap the landscape survey’s autonomy scorecard found when approaching from the product side.

Planning under uncertainty, and active SLAM

Everything above quietly assumed the pose is right and the map is rigid. Over a whole-house mission neither holds (drift is structural), and there are two disciplined responses:

  • Inflate for uncertainty. Fold pose covariance into the obstacle margin — fly wider when less sure. Cheap, local, and the reason the margin derivation treats uncertainty as a first-class term. The subtle failure it guards against: a doorway that is passable at 5 cm pose error and a wall strike at 20 cm.
  • Plan to stay localized — active SLAM. Treat estimator health as part of the objective: prefer trajectories through feature-rich, well-mapped space; schedule deliberate revisits of mapped regions so loop closures fire before drift corrupts the map, not after; penalize candidate views whose approach crosses texture deserts. Formally this is belief-space planning over pose uncertainty; practically, deployed systems use heuristics — revisit intervals, localization-quality costmaps, perception-aware yaw. The AG-SLAM-style objectives above (gain minus localization risk) are the same idea in the 3DGS setting.

For a capture product the two pressures happen to align: capture already wants revisits (surfaces need views from multiple angles), and revisits are exactly what loop closure needs. Order the capture tour with the estimator in mind and drift correction comes nearly free. This is a real argument for one planner that owns both objectives, rather than an off-the-shelf exploration library with a capture pass bolted on top.

Learned navigation: what is real in 2026

The learned side, sorted by how deployed it actually is:

Learned modules inside classical stacks — real and shipping. Depth estimation, traversability prediction, semantic segmentation feeding costmaps, learned features keeping VIO alive on blank walls. Same pattern as in estimation: networks replace perception modules, solvers and safety layers stay classical.

End-to-end control policies — real in narrow regimes. The headline results are genuine: Swift beating human champions at drone racing (RL — reinforcement learning — trained in sim, Nature 2023) and Loquercio et al.’s zero-shot sim-to-real forest flight from depth images (Science Robotics 2021). Both exploit the same enablers — massive domain-randomized simulation and a low-dimensional input (depth, not RGB) — and both operate in regimes where a mistake costs a crashed research drone. No safety case exists yet for a learned policy as the only thing between a vehicle and a wall; fielded systems keep the classical safety hierarchy, with the learned policy proposing maneuvers and the classical layers keeping the authority to reject them.

Learned exploration policies — promising, so far sim-only. GLEAM (generalizable RL exploration over thousands of indoor scenes; evaluated locally, Week 1) and its kin learn the goal-selection layer: map in, next waypoint out. Goal selection is the sanest place in the stack to put a network — a bad output costs coverage efficiency, not a collision, because everything below it still enforces feasibility and safety. Whether map-conditioned policies transfer from sim to real buildings is the open question; today the evidence is entirely sim benchmarks (GLEAM-Bench’s coverage/AUC protocol).

Foundation-model navigation — the 2024–2026 research wave. Two threads: navigation foundation models trained across robot embodiments (ViNT, NoMaD — goal-image-conditioned, ground-robot-centric so far), and VLM/VLN (vision-language models / vision-and-language navigation) systems that put a language model in the goal-selection seat — scoring frontiers by semantic promise (“bedrooms are usually upstairs”), following instructions, or zero-shot commanding a drone (See, Point, Fly; the UAV VLN roadmap survey). For indoor capture the plausible near-term role is exactly this semantic prior — room recognition and mission structure — on top of a geometric stack that retains authority over feasibility and safety.

The stable division of labor, then: learning moves up the stack, not down. Perception first, goal selection now, trajectory generation rarely, the safety layers never.

Systems worth knowing by name

System Layer License Note
Nav2 full stack (ground) Apache-2.0 The ROS 2 reference navigation architecture (behavior trees over global/local planners). Read it for the structure; its planners are ground-robot 2D, not flight code
OMPL global planning BSD-3 The sampling-planner library (RRT*/PRM/BIT* and dozens more)
Fast-Planner local planning GPL-3.0 Classic kinodynamic search + B-spline pipeline
EGO-Planner / EGO-Swarm local planning GPL-3.0 ESDF-free gradient planner; the lightweight default; swarm variant decentralized
GCOPTER (MINCO) trajectory optimization MIT State-of-the-art trajectory representation; base of most 2023+ planners
FASTER local planning BSD-3 Hard safety via committed backup trajectories in known-free space
NBVP exploration BSD-3 The receding-horizon next-best-view original; a baseline now
FUEL exploration GPL-3.0 Incremental frontiers + TSP tour + aggressive local trajectories; the quantitative reference
TARE exploration BSD-like (custom) Hierarchical coarse-global/fine-local coverage; CMU, ground-born
RACER multi-robot exploration GPL-3.0 Decentralized workload partition over FUEL machinery
GLEAM learned exploration CC BY-NC 4.0 RL goal-selection policy generalizing across 1000+ indoor scenes; sim benchmark GLEAM-Bench
voxl-mapper / voxl-vision-hub mapping + local planning BSD-3 (ModalAI clause) voxblox + vendored RRT*/loco planners + VOA reactive tier on VOXL; no exploration layer
Isaac ROS / nvblox + planners mapping + planning NVIDIA proprietary, free GPU mapping feeding Nav2-style planning; Jetson-native path

Selection logic mirrors the estimation chapter: the planning and exploration layers are healthy open code (mind the GPL where it matters); the capture layer is not on this table because nothing shippable exists to put there.

Evaluating navigation and exploration

Metrics, by layer:

  • Trajectory quality: tracking error against the reference, jerk/snap (aggressiveness vs smoothness), time-to-goal, replan latency. Sim gives these against ground truth trivially — our B0.1 flight gate’s final-error and RMSE (root-mean-square error) numbers are this metric family in miniature.
  • Exploration: coverage ratio vs time (and its AUC — area under that curve, rewarding fast coverage, the headline GLEAM-Bench pair), path length per coverage, completion time, and completeness at termination.
  • Capture/reconstruction: surface completeness and accuracy (chamfer / point-to-plane distance against ground-truth geometry), fraction of surface meeting view-quality thresholds and — in the radiance-field thread — novel-view rendering quality (PSNR/SSIM — peak signal-to-noise ratio / structural similarity) of the final model. This last family is the one that actually corresponds to our product output.
  • Safety: collisions per mission, distribution of closest-approach margins, incursions into unknown space — reported almost nowhere in the literature, measurable for free in sim, and worth defining early and holding fixed as pass/fail gates.

Benchmark reality check: exploration papers evaluate in hand-picked sim worlds (MARSIM, Gazebo scenes, GLEAM-Bench’s ProcTHOR/HSSD/Gibson/MP3D splits); no field-standard physical benchmark exists. This makes the sim-first, frozen-metric, negative-control posture of our Isaac lesson plan not just convenient but the same evidence standard the field itself runs on — with the usual caveat that sim clutter is cleaner than a lived-in house.

Fit to the indoor capture project

  • Adopt, don’t write, everything below the goal. Global search, corridor or gradient local planning, and the safety hierarchy are commodity layers with multiple open implementations; on VOXL some of it (voxblox mapping, RRT* local planning, VOA) already ships. Writing our own trajectory optimizer would be recreational.
  • The product lives in the goal-selection layer, and it is two planners, not one. Exploration (space) has strong open baselines — FUEL/TARE-class classical, GLEAM-class learned — and should be selected, not invented. Capture (surface quality) has no off-the-shelf answer: the coverage-ledger NBV planner, its termination criterion (“this house is done”), and its interaction with estimator health are the parts a competitor cannot download.
  • The two-pass architecture keeps being right. Recon pass = exploration objective, onboard-safe, conservative; capture pass = coverage objective, PC-planned over the recon map, still onboard-guarded. The 3DGS-era active reconstruction results reinforce it: the heavy view-gain computation belongs off-board, and its output is goals, never trajectories.
  • Mission-level state is a first-class artifact. Frontier sets, the coverage ledger, tour order, revisit schedule — persistent, inspectable, resumable after battery swaps. The literature’s single-battery missions quietly skip this; a product cannot.
  • Near-term experimental path: B2’s occupancy/planning scaffold → frontier selection over it (B4’s photo-coverage metric as gain) → a small frozen exploration benchmark in Isaac/Pegasus scenes → swap in FUEL-style tour ordering and a GLEAM policy as comparisons on the same metric. That reproduces the field’s evaluation loop on our fixtures before any hardware flight.

References

Foundations:

Trajectory planning:

Exploration:

Active reconstruction and learned goal selection:

Learned flight:

Related notes: VIO and SLAM for the estimation layer below this one, system-design notes for the architecture decisions, the NVIDIA Isaac ecosystem and VOXL 2 Mini for what candidate platforms ship, and the flight compute landscape for who else is attacking the same problem.