Extraction of free-space structures for path planning purposes

Abstract: LKAB one of the world’s leading producers of upgraded iron ore products for
the steel industry, uses autonomous Laud-Haul-Dump (LHD) machines for
transportation of the iron ore at their underground mine located in Kiruna,
Sweden. These machines are an essential part in the flow of ore
transportation out of the mine and therefore the driving speed of these
machines is very important. Today the drive paths for these machines are
drawn by hand in computer software and this is a human-computer interaction
that LKAB wants to remove because of the time consumption and also for the
possibility to automatically generate faster and more optimized drive paths.

Research has been conducted at Luleå University of Technology concerning
optimization of drive paths for autonomous machines. This research resulted
in a software prototype that integrated map-handling and path generation for
the machines at LKAB. This prototype was based on a path generation algorithm
with the unfortunately limitation of that the polygon must be monotone, and
that is not the typical case for the drive paths that the machines are using.

This thesis will show an implementation of an extension of this prototype
that will improve the functionality so that polygons without constraints can
be used in the calculations of optimized drive paths. In order to achieve
this result triangulation of polygons and breadth first search has been
used.

Due to safety precautions a margin from the wall must exist on each side of
the drive path to prevent the machine from colliding with the walls, this
will affect the size of the polygon and the recalculation of the polygon is
described in this thesis. It will show how optimizations for the inner and
outer curves on the drive path will affect the final result of the
optimization.