Hierarchical Path Planning for Ground Vehicles
Master thesis
Permanent lenke
http://hdl.handle.net/11250/2352561Utgivelsesdato
2015Metadata
Vis full innførselSamlinger
Sammendrag
Path planning for autonomous terrain vehicles is performed with terrain data of differentlevels of detail. Some of the data are prior knowledge with coarse resolution, while someare sensed data of the surroundings with finer resolutions. The vehicle always needs apath in the most detailed terrain available to be able to traverse the terrain. Performingcomplete 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 aretoo large for practical computations.
Performing path planning using the coarse terrain data can provide a basis for performingpath 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 hierarchicalpath 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 thecoarsest data being the highest level, and the finest data being the lowest level in thehierarchy. In the hierarchy, path planning is performed in the highest level, and the resultis used to reduce the data of the lower levels before performing path planning.Experiments using real terrain data are performed for comparing the hierarchical pathplanning to conventional path planning, both with respect to computational efficiency andalso optimality and similarity between the paths. Additional experiments are performedfor investigating possible improvements to the method presented.
The results show that hierarchical path planning can improve computation efficiency atthe expense of optimality of the paths. In the experiments, as much as 5 times increasein 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 doesoccur. The optimality is also dependent on the parameters chosen, and there is a trade-offbetween computational efficiency and optimality.