An Extension of Dynamic Programming Algorithm in Robotic Path Planning

Abstract

DP (Dynamic Programming) algorithm based on distance-propagating is a very good approach to real-time collision avoidance in robotic path planning. But the problem with DP is the waste of step number of walking in tracking process. For the A* (A Star) algorithm, there are commonly three heuristic, and usually three ways (4-adjacency, 8-adjacency and 16-adjacency) to get the adjacencies. After The comparison and analysis of three ways in three heuristic, we find that the 16-adjacency is more suited to the DP algorithm. The 16-adjacency can expand the search area and then the extended DP algorithm will improve the search speed. Based on this, we extend DP algorithm called Extended DP. We can guarantee its completeness and optimality. On the experimental side, we demonstrate several simulations to illustrate its effectiveness.