Beyond quadtrees: Cell decompositions for path planning using wavelet transforms

Path planning techniques based on hierarchical multiresolution cell decompositions are suitable for online implementation due to their simplicity and speed of implementation. We present an efficient multiresolution cell decomposition scheme based on the Haar wavelet transform. The decomposition approximates the environment using high resolution close to the agent and coarse resolution elsewhere. We demonstrate an algorithm to extract the adjacency and transition cost relations of the cells directly from the wavelet transform coefficients.