GENERATING AN ADAPTIVE PATH USING RRT SAMPLING AND POTENTIAL FUNCTIONS WITH DIRECTIONAL NEAREST NEIGHBORS

Abstract

Planning algorithms have attained omnipresent successes in several fields including robotics, animation, manufacturing, drug design, computational biology and aerospace applications. Path Planning is an essential component for autonomous robots. The problem involves searching the configuration space and constructing a desired collision-free path that connects two states (the start and the goal) for a robot to gradually navigate from one state to another. In global path planners, the complete path is computed prior to the robot set off. Sampling based planning like Rapidly Expanding Random Trees (RRT) and Probabilistic Road Maps (PRM) used for single or multi-query planning has gained popularity since it is probabilistic complete and scales well to complex configuration spaces. However, re-planning (re-calculating the complete path) is almost unavoidable as path execution is inherently uncertain since a robot will deviate from the path due to slippage and other uncertainties in the environment. Local path planners which only calculate the path direction at the current location partially alleviate this problem since they do not pre-calculate a complete path and are thus less affected by deviations. However, local path planners are either not complete or, if they use navigation functions, do not scale well to complex environments. To address this, this work presents an approach that combines the advantages of sampling-based global path planning with the benefit of a local, navigation function-based path planning on the generated sample space. This reduces the need for re-planning if the robot diverges from the original path by utilizing a harmonic function potential field computed over the RRT sample set and directional nearest neighbors. The proposed work derives the samples in the environment using a simple randomized algorithm and systematically sampled obstacles that are hit during random sampling of the space. It therefore avoids sampling of the complete space. Additionally, samples generated during one planning phase can be exploited further for new goals in the environment.