Optimal robotic path planning using dynamic-programming and randomization

Path planning is a key element in the development of autonomous robitics, particularly for space applications. Such a technique should ideally produce paths which are optimal in accordance to a specified criterion. A new method based on dynamic programming with randomization is presented here that can provide optimal paths. The introduction of randomization in the discretization grid counters longstanding criticism of the use of dynamic programming in path planning. The technique can be applied to mobile robots as well as articulated manipulators. Moreover, test results demonstrate the effectiveness and practicality of the method. Examples of path-planning problems involving two- and three-link robitic arms and a mobile robot aboard a representative space station are also presented.