Multiresolution Path Planning Via Sector Decompositions Compatible to On-Board Sensor Data

Abstract

In this paper we present a hybrid local-global path planning scheme for the problem of operating a moving agent inside an unknown environment in a collision-free manner. The path planning algorithm 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. We use a multi-resolution cell decomposition of the environment in order to solve the path-planning problem using the wavelet transform 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. Simulations are presented to test the efficiency of the algorithm using a non trivial scenario.