Self-Adjusting Roadmaps: A Fast Sampling-Based Path Planning Algorithm for Navigation in Unknown Environments

Despite the outstanding performances of sampling-based motion planning algorithms in different planning problems, they fail to operate in the presence of unknown obstacles. Even in few recent versions of these planners which has been upgraded to deal with unknown situations, the generated results are computationally expensive which creates a major problem in online implementations. Since the basic idea of randomized navigation algorithms is to utilize a pre-constructed structure of the obstacle map, the sampling procedure and the graph structure need to improve in order to deal with uncertainty in the planning space. In this paper, a self-adjusting probabilistic roadmap algorithm is proposed which deals with unknown obstacles quickly. This algorithm stores the generated samples in a grid structure based on their position in the corresponding configuration space which makes it computationally affordable to check them against collision later. It also enables the path planner to include safety as a decision factor during the actual navigation. Next, only the occupied grid cells by the undetected obstacles and their corresponding samples will be checked and the roadmap responses to the changes in the environment as soon as they occur. Furthermore, the size of the graph is maintained, and the occupied nodes are pushed away from the obstacle rather than being removed from the set of samples. Several simulation and comparative studies show the effectiveness of the proposed algorithm. The planner has been also successfully implemented on a differential drive robotic platform in two navigation missions in unknown environments.