dc.description.abstract | Path planning for autonomous terrain vehicles is performed with terrain data of different
levels of detail. Some of the data are prior knowledge with coarse resolution, while some
are sensed data of the surroundings with finer resolutions. The vehicle always needs a
path in the most detailed terrain available to be able to traverse the terrain. Performing
complete path planning using the most detailed terrain data is often not possible as de-
tailed terrain data only becomes available as the vehicle moves, or that the data sets are
too large for practical computations.
Performing path planning using the coarse terrain data can provide a basis for performing
path planning using the higher detail terrain, which can improve performance of calcula-
tions. The combination of the path planning in different terrain is a type of hierarchical
path planning.
In this report, a method for hierarchical path planning using terrain data is presented.
Using terrain data in different resolutions, a hierarchy of terrain data is created, with the
coarsest data being the highest level, and the finest data being the lowest level in the
hierarchy. In the hierarchy, path planning is performed in the highest level, and the result
is used to reduce the data of the lower levels before performing path planning.
Experiments using real terrain data are performed for comparing the hierarchical path
planning to conventional path planning, both with respect to computational efficiency and
also optimality and similarity between the paths. Additional experiments are performed
for investigating possible improvements to the method presented.
The results show that hierarchical path planning can improve computation efficiency at
the expense of optimality of the paths. In the experiments, as much as 5 times increase
in computation efficiency were achieved on average, depending on the parameters cho-
sen. The hierarchical paths are in most cases close to optimal, but large deviations does
occur. The optimality is also dependent on the parameters chosen, and there is a trade-off
between computational efficiency and optimality. | |