A PDE Based Approach to Path Finding in Three Dimensions: Solving a Path Finding Problem for an Unmanned Aerial Vehicle
This thesis presents a general three-dimensional method for pathfinding, based
on 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 a
fluid flow problem, we construct an artificial permeability based on the hazard-
values, and we use this to calculate streamlines that constitute the potential paths
from a starting point to the target. We investigate the different parameters
and ways to manipulate the problem to yield sufficiently flyable streamlines.
The method is geared towards finding a terrain-following, flyable path for an
unmanned aerial vehicle(UAV) through a hostile terrain. In special, we consider
the potential for a program implementation to run on-board the UAV during
mission flight. For this application, the available memory and processor resources
can be restricted. This sets strict requirements on the pathfinding algorithm.
Particularly fast solvers exist for solving PDEs discretized using finite differences
on regular grids. We implement a multigrid method for the resulting linear set
of equations, with optimal memory usage, linear complexity and a potential for
Place, publisher, year, edition, pages
Institutt for matematiske fag , 2014. , 91 p.
IdentifiersURN: urn:nbn:no:ntnu:diva-26202Local ID: ntnudaim:11348OAI: oai:DiVA.org:ntnu-26202DiVA: diva2:745623
Rønquist, Einar, ProfessorPaulsen, Kristin