A PDE Based Approach to Path Finding in Three Dimensions: Solving a Path Finding Problem for an Unmanned Aerial Vehicle

Abstract

This thesis presents a general three-dimensional method for pathfinding, basedon a partial differential equation. The method relies on a grid with hazard-values,describing the risk associated with every point in the domain. Analogous to afluid flow problem, we construct an artificial permeability based on the hazard-values, and we use this to calculate streamlines that constitute the potential pathsfrom a starting point to the target. We investigate the different parametersand ways to manipulate the problem to yield sufficiently flyable streamlines.The method is geared towards finding a terrain-following, flyable path for anunmanned aerial vehicle(UAV) through a hostile terrain. In special, we considerthe potential for a program implementation to run on-board the UAV duringmission flight. For this application, the available memory and processor resourcescan be restricted. This sets strict requirements on the pathfinding algorithm.Particularly fast solvers exist for solving PDE s discretized using finite differenceson regular grids. We implement a multigrid method for the resulting linear setof equations, with optimal memory usage, linear complexity and a potential forparallelization.