A Hierarchical On-Line Path Planning Scheme using Wavelets
MetadataShow full item record
The main objective of this thesis is to present a new path planning scheme for solving the shortest (collision-free) path problem for an agent (vehicle) operating in a partially known environment. We present two novel algorithms to solve the planning problem. For both of these approaches we assume that the agent has detailed knowledge of the environment and the obstacles only in the vicinity of its current position. Far away obstacles or the final destination are only partially known and may even change dynamically at each instant of time. The path planning scheme is based on information gathered on-line by the available on-board sensor devices. The solution minimizes the total length of the path with respect to a metric that includes actual path length, along with a risk-induced metric. In order to obtain an approximation of the whole configuration space at different levels of fidelity we use a wavelet approximation scheme. In the first proposed algorithm, the path-planning problem is solved using a multi-resolution cell decomposition of the environment obtained from the wavelet transform. In the second algorithm, we extend the results of the the first one by using the multiresolution representation of the environment in conjunction with a conformal mapping to polar coordinates. By performing the cell decomposition in polar coordinates, we can naturally incorporate sector-like cells that are adapted to the data representation collected by the on-board sensor devices.