An Efficient Dynamic System for Real-Time Robot Path Planning

Abstract

This paper presents a simple yet efficient dynamic programming (DP) shortest path algorithm for real-time collision-free robot path planning applicable to situations where targets and barriers are permitted to move. The algorithm works in real time and requires no prior knowledge of target or barrier movements. In the case that the barriers are stationary, this paper proves that this algorithm always results in the robot catching the target provided it moves at greater speed than the target, and the dynamic system update frequency is sufficiently large. Like most robot path planning approaches, the environment is represented by a topologically organized map. Each grid point on the map has only local connections to its neighboring grid points from which it receives information in real-time. The information stored at each point is a current estimate of the distance to the nearest target and the neighbor from which this distance was determined. Updating the distance estimate at each grid point is done using only information gathered from the point's neighbours, that is, each point can be considered an independent processor, and the order in which grid points are updated is not determined based on global knowledge of the current distances at each point or the previous history of each point. The robot path is determined in real-time completely from information at the robot's current grid-point location. The computational effort to update each point is minimal allowing for rapid propagation of the distance information outward along the grid from target locations. In the static situation, where both targets and barriers do not move, this algorithm is a DP solution to the shortest path problem, but is restricted by lack of global knowledge. In this case, this paper proves that the dynamic system converges in a small number of iterations to a state where the minimal distance to a target is recorded at each grid point and shows that this robot path-planning algorithm can be made to always choose an optimal path. The effectiveness of the algorithm is demonstrated through a number of simulations.