Anytime, Dynamic Planning in High-dimensional Search Spaces

Abstract

We present a sampling-based path planning and replanning algorithm that produces anytime solutions. Our algorithm tunes the quality of its result based on available search time by generating a series of solutions, each guaranteed to be better than the previous ones by a user-defined improvement bound. When updated information regarding the underlying search space is received, the algorithm efficiently repairs its previous solution. The result is an approach that provides low-cost solutions to high-dimensional search problems involving partially-known or dynamic environments. We discuss theoretical properties of the algorithm, provide experimental results on a simulated multirobot planning scenario, and present an implementation on a team of outdoor mobile robots.