Main content

An Efficient Dynamic System for Real-Time Robot Path Planning

Show simple item record

dc.contributor.author Willms, Allan R.
dc.contributor.author Yang, Simon X.
dc.date.accessioned 2013-10-18T17:48:21Z
dc.date.available 2013-10-18T17:48:21Z
dc.date.issued 2006
dc.identifier.uri http://hdl.handle.net/10214/7591
dc.description.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. en_US
dc.language.iso en_US en_US
dc.publisher IEEE, Transactions on Systems, Man, and Cybernetics B en_US
dc.rights Attribution-NonCommercial-NoDerivs 2.5 Canada *
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ *
dc.subject collision avoidance en_US
dc.subject dynamic environment en_US
dc.subject dynamic programming en_US
dc.subject dynamic system en_US
dc.subject mobile robot en_US
dc.subject path planning en_US
dc.subject real-time navigation en_US
dc.title An Efficient Dynamic System for Real-Time Robot Path Planning en_US
dc.type Article en_US
dc.rights.license All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.
dcterms.relation IEEE Trans. Syst., Man, Cybern. B, Cybern. 36 (4) (2006) 755-766


Files in this item

Files Size Format View Description
Willms_Yang_IEEE_TSMCB_2006.pdf 616.5Kb PDF View/Open Main article - postprint

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 2.5 Canada Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 2.5 Canada