Fast Asymptotically Optimal Path Planning in Dynamic, Uncertain Environments

Abstract

This paper presents Fast Adaptive Tree (FAT), an asymptotically-optimal sampling-based path planner for dynamic and uncertain scenarios. Namely, the solution extracted converges to the optimal solution given the sensor information as the number of samples approaches infinity. The planner maintains an underlying graph, which increasingly approximates the search domain, and a dynamic spanning tree of the graph, which contains the shortest path from the start to the goal state. The planner quickly responds to the availability of new information about the environments or the robot movements by minimally repairing the spanning tree over the navigation. The simulation results show that the proposed path planner achieves higher efficiency of replanning than several state-of-the-art path planners without sacrificing solution quality.