Convexly Stratified Deformation Spaces and Efficient Path Planning for Planar Closed Chains with Revolute Joints

Abstract

Systems involving loops have been especially challenging in the study of robotics, partly because of the requirement to maintain loop closure constraints, conventionally formulated as highly nonlinear equations in joint parameters. In this paper, we present our novel triangle-tree-based approach and parameters for planar closed chains with revolute joints. For such a loop, the loop closure constraints are exactly, not approximately, a set of linear inequalities in our new parameters. Further, our new parameters provide explicit parametrization of the system deformation space (configuration space modulo the group of rigid motions of the system's ambient space respecting system specifications) and endow it with a nice geometry. More precisely, the deformation space of a generic planar loop with n revolute joints consists of 2^n-2 copies of one and the same convex polytope (which, when all of the link lengths are fixed, is bounded and of dimension n - 3), glued together into either one connected component or two (ignoring collision-free constraints), via proper boundary identification. Such a completely solved, stratified space of convex strata will have profound implications for these systems and lead to great simplifications in many kinematics related issues. For example, in essence, our approach makes path planning for planar loops with revolute joints no more difficult than for open chains. We also briefly point out the connection and extension of the work presented here to other systems such as spatial loops with spherical joints and systems involving multiple loops.

Keywords

configuration spaces deformation spaces convex stratification motion planning kinematics loop closure constraints triangle-based parameters construction trees of triangles

Get full access to this article

View all access options for this article.

References

Bayazit, O.B. , Xie, D. and Amato, N.M. (2005). Iterative relaxation of constraints: A framework for improving automated motion planning. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2005.

Canny, J. (1988). The Complexity of Robot Motion Planning. MIT Press, 1988.

Choset, H. , Burgard, W. , Hutchinson, S. , Kantor, G. , Kavraki, L.E. , Lynch, K. and Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementation. Cambridge, MA, MIT Press.

Connelly, R. , Demaine, E. and Rote, G. (2000). Straightening polygonal arcs and convexifying polygonal cycles. Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pp. 432-442.

Cortes, J. and Simeon, T. (2004) Sampling-based motion planning under kinematic loop closure constraints. Proceedings of the Workshop on Algorithmic Foundations of Robotics, 2004.

Craig, J.J. (1989). Introduction to Robotics: Mechanics and Control , 2nd edition. Reading, MA, Addison-Wesley.

Goresky, M. and MacPherson, R. (1988). Stratified Morse Theory. New York, Springer.

Han, L. and Amato, N.M. (2000). A kinematics-based probabilistic roadmap method for closed chain systems. Algorithmic and Computational Robotics New Directions. Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR 2000), pp. 233-246.

Han, L. and Rudolph, L. (2006). The inverse kinematics of a serial chain with joints under distance constraints. Proceedings of Robotics: Science and Systems (RSS), pp. 177-184.

10.

Han, L. and Rudolph, L. (2007). A unified geometric approach for inverse kinematics of a spatial chain with spherical joints. Proceedings of the International Conference on Robotics and Automation (ICRA 2007), pp. 4420-4427.

11.

Han, L. and Rudolph, L. (2008). Simplex-tree based kinematics of foldable objects as multi-body systems involving loops. Proceedings of Robotics: Science and Systems (RSS), 2008.

12.

Han, L. , Rudolph, L. , Blumenthal, J. and Valodzin, I. (2006). Stratified deformation space and path planning for a planar closed chain with revolute joints. Proceedings of the 7th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2006). New York, Springer.

13.

Kapovich, M. and Millson, J. (1995). On the moduli spaces of polygons in the Euclidean plane. Journal of Differential Geometry, 42: 133-164.

14.

Kavraki, L. , Svestka, P. , Latombe, J.C. and Overmars, M. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12(4): 566-580.

15.

Kuffner, J.J. and LaValle, S.M. (2000). RRT-Connect: an efficient approach to single-query path planning. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 995-1001.

16.

Latombe, J.C. (1991). Robot Motion Planning. Boston, MA, Kluwer Academic.

17.

LaValle, S.M. (2006). Planning Algorithms. Cambridge , Cambridge University Press. Also available at http://planning.cs.uiuc.edu/.

18.

LaValle, S. , Yakey, J. and Kavraki, L. (1999). A probabilistic roadmap approach for systems with closed kinematic chains. Proceedings of IEEE International Conference on Robotics and Automation (ICRA), 1999.

19.

Lenhart, W. and Whitesides, S. (1995). Reconfiguring closed polygon chains in Euclidean d-space. Discrete and Computational Geometry, 13:123-140, 1995.

20.

Liu, G. and Trinkle, J.C. (2005). Complete path planning for planar closed chains among point obstacles. Robotics: Science and Systems. Cambridge, MA, MIT Press.

21.

Liu, G. , Trinkle, J.C. and Milgram, R.J. (2004). Toward complete motion planning for planar 3R-manipulators among point obstacles. Proceedings of the International Workshop on Algorithmic Foundations of Robotics (WAFR), 2004 .

22.

Luenberger, D. (2004). Linear and Nonlinear Programming. Dordrecht, Kluwer Academic.

23.

Milgram, R. and Trinkle, J. (2002). The geometry of configuration spaces for closed chains in two and three dimensions. Homology, Homotopy, and Applications, 6(1): 237-267.

24.

Murray, R.M. , Li, Z. and Sastry, S.S. (1994). A Mathematical Introduction to Robotic Manipulation . Boca Raton, FL, CRC Press.

25.

Streinu, I. (2000). A combinatorial approach to planar non-colliding robot arm motion planning. Proceedings of the 41 st Annual Symposium on Foundations of Computer Science (FOCS 2000), pp. 443-453.

26.

Trinkle, J. and Milgram, R. (2002). Complete path planning for closed kinematic chains with spherical joints. The International Journal of Robotics Research, 21(9): 773-789.