Complexity-Aware Path Planning for Online UAV-Based 3D Reconstruction

open_access
Open Access
Author:
Rhoads, Alexandria
Area of Honors:
Aerospace Engineering
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Junyi Geng, Thesis Supervisor
Sven Schmitz, Thesis Honors Advisor
Keywords:
A*
UAV
Path Planning
3D Reconstruction
Heuristic
Trajectory
Algorithm
Voxel occupancy
Abstract:
Three-dimensional reconstruction from UAV imagery is a powerful tool for inspection, mapping, and documentation, but current approaches have a significant inefficiency built into them. Because standard trajectory planners treat every part of an environment the same way, the UAV ends up collecting dense imagery everywhere — over flat walls and open ground just as much as over the corners, edges, and structural features that actually drive reconstruction quality. The result is a massive dataset, most of which contributes little to the final model, and that dataset has to be processed offline before anything useful can be extracted from it. The core argument of this thesis is that a smarter trajectory can change this. If the UAV spends more of its flight time around geometrically complex regions—the parts of an environment where surface detail, occlusions, and structural variation make accurate reconstruction genuinely difficult — and moves more quickly through simple areas, it collects a smaller total dataset that is disproportionately made up of the imagery that actually matters. Less data means less post-processing, and the data that does get collected is the data the reconstruction algorithm needs most. To achieve this, two complementary path planners are developed, both built on the A* search framework. The first is a β-weighted formulation that blends a complexity reward directly into the planning cost, with a tunable parameter controlling how strongly the UAV is drawn toward complex regions. This approach works and is easy to use, but it cannot guarantee that the path it finds is the best possible one for any given flight budget. The main contribution of this thesis addresses that limitation. The problem is recast as a constrained maximization: find the path that collects the most geometric complexity while staying within a hard limit on total flight distance. This formulation is equivalent in structure to the orienteering problem from combinatorial optimization. Solving it exactly requires an effective admissible heuristic, and designing that heuristic is the central technical challenge. The result is the ellipse heuristic: at any point during planning, a cell can only be visited on a feasible continuation of the current path if the total distance to travel to that point and continue to the goal is less than the remaining flight budget. This condition defines an ellipse with foci at the current position and the goal. Restricting the heuristic’s optimistic complexity estimate to cells inside this ellipse produces a bound that is provably tighter than any geometry-blind alternative. Formal proofs of admissibility, consistency, and dominance over the global baseline are provided. The planner is tested on synthetic environments designed to isolate different aspects of the algorithm’s behavior, and then integrated with real sensor data from a recorded UAV inspection flight. The high-fidelity simulation uses voxel occupancy and complexity maps extracted from a ROS bag, allowing a direct comparison between the trajectory the algorithm would have planned and the one the UAV actually flew. The algorithm also handles dynamic environments through a replanning extension that correctly tracks remaining flight budget across replanning events. In every case, the planned paths satisfy the single-visit constraint exactly and route meaningfully through the high-complexity regions that the original inspection trajectory ignored.