Low Altitude Pathfinding Service

Abstract

Pathfinding algorithms find a path from one node to another in a data structure known as a graph. They are heavily used in GPS devices. For GPS devices in cars, a graph is created from the world’s road networks, which can then be used to find a path from the user’s current location to their destination. To build an autonomous flying drone, it has to find it’s way around the world. Because they do not have to follow a road network, it may be possible to take a direct path. However, this ignores the terrain, and it may naively fly over a mountain, spending a lot of energy climbing to the required altitude. Airborne LIDAR scanning can create very high resolution surface maps. By converting these maps into a graph, we can use a pathfinding algorithm to find the path of least resistance. This allows the drone to fly around buildings and hills rather than above them. However, the problem with this is that these graphs become very large. For roads, they can be heavily simplified, but this is not the case for terrain. This means that pathfinding algorithms become extremely slow. To be as efficient as possible, the paths should be rounded out, which requires post-processing. The assignment given to us by Kongsberg Defence & Aerospace is to investigate whether a machine-learning based approach could work in this case. The hope is that a machine-learned approach can be run in a fraction of the time, and not require post-processing. To make investigation easier, we had to build a web service which allows us to run and compare the different implementations we came up with. In this report, we show how the service is built, and what the final result was. We explain the different machine-learning approaches we have experimented with. The chosen process model, using the principles of Kanban, is explained in detail. In the end, we show that the idea definitely has potential, and that further research in this field is warranted. We were unable to draw any meaningful conclusions as to the viability of this approach.