Hierarchical Path Planning for Ground Vehicles

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.