Title:
|
An Efficient Dynamic System for Real-Time Robot Path Planning |
Author:
|
Willms, Allan R.; Yang, Simon X.
|
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. |
URI:
|
http://hdl.handle.net/10214/7591
|
Date:
|
2006 |
Rights:
|
Attribution-NonCommercial-NoDerivs 2.5 Canada |
Terms of Use:
|
All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated. |
Related Publications:
|
IEEE Trans. Syst., Man, Cybern. B, Cybern. 36 (4) (2006) 755-766 |