Efficient computation of level sets for path planning
Bin Xu, Daniel J. Stilwell, Andrew J. Kurdila · 2009
We propose an efficient method for updating a path that was computed using level-set methods. Our approach is suitable for autonomous vehicles navigating in a static environment for which an a priori map of the environment is inaccurate. When the autonomous vehicle detects a new obstacle, our algorithm replans an optimal route without recomputing the entire path. Computational costs when planning paths with level set methods are due to creation of the level set. Once the level set has been computed, the optimal path is simply gradient descent down the level set. Our approach is based on formal analysis of how the level set changes when a new obstacle is detected. We show that in many practical cases, only a small portion of the level set needs to be re-computed when a new obstacle is detected. Simulation examples are presented to validate the effectiveness of the proposed method.