Change search
ReferencesLink to record
Permanent link

Direct link
A PDE Based Approach to Path Finding in Three Dimensions: Solving a Path Finding Problem for an Unmanned Aerial Vehicle
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Mathematical Sciences.
2014 (English)MasteroppgaveStudent thesis
Abstract [en]

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 PDE’s 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 parallelization.

Place, publisher, year, edition, pages
Institutt for matematiske fag , 2014. , 91 p.
URN: urn:nbn:no:ntnu:diva-26202Local ID: ntnudaim:11348OAI: diva2:745623
Available from: 2014-09-10 Created: 2014-09-10 Last updated: 2014-09-10Bibliographically approved

Open Access in DiVA

fulltext(7983 kB)493 downloads
File information
File name FULLTEXT01.pdfFile size 7983 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(489 kB)0 downloads
File information
File name COVER01.pdfFile size 489 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Mathematical Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 493 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 151 hits
ReferencesLink to record
Permanent link

Direct link