Randomized Preprocessing of Configuration Space for Path Planning: Articulated Robots

L. E. Kavraki and J.-C. Latombe, “Randomized Preprocessing of Configuration Space for Path Planning: Articulated Robots,” in Proceedings of the IEEE/RSJ/GI International Conference on Intelligent Robots and Systems (IROS), Munchen, Germany, 1994, pp. 1764–1771.


This paper describes the application of a recent approach to path planning for robots with many degrees of freedom (DOF) to articulated robots moving in two or three dimensional static environments. The planning approach, which itself is not restricted to articulated robots, consists of a preprocessing and a planning stage. The preprocessing is done only once for a given environment and generates a connected network of randomly, but properly selected, collision-free configurations (nodes). The planning then connects any given initial and final configurations of the robot to two nodes of the network and computes a path through the network between these two nodes. We show that after paying the preprocessing cost, planning is extremely fast for many difficult examples involving 7-DOF and 12-DOF robots. The approach is particularly attractive for many-DOF robots which have to perform many successive point-to-point motions in the same environment.

Publisher: http://dx.doi.org/10.1109/IROS.1994.407619

PDF preprint: http://kavrakilab.org/publications/kavraki-latombe1994randomized-preprocessing-of_2.pdf