A novel path planning algorithm based on twofold interpolations

Most grid-based path planners use discrete state transitions that artificially constrain a robot´s motion to a small set of possible headings to increments of 45 degrees. Consequently, even ldquooptimalrdquo grid-based path planning algorithms produce unnatural and suboptimal paths. In order to handle the problem, we present a twofold-interpolation-based path planning algorithm called T* for producing low-cost paths through uniform resolution grids. First, it starts at the goal node and propagates through four adjacent nodes, assigning monotonically increasing values to nodes using FMM (fast marching method) interpolation. Consequently, we obtain a goal-propagation map that is zero at the goal node and monotonically increasing along wavefront propagation from the goal node. Subsequently, it begins from robot´s position and uses linear interpolation to generate near-optimal paths which eliminate unnecessary turnings. The experimental results demonstrate the performance of our approach.