Motion planning for spatially constrained robots is difficult due to additional constraints placed on the robot, such as closure constraints for closed chains or requirements on end-effector placement for articulated linkages. It is usually computationally too expensive to apply sampling-based planners to these problems since it is difficult to generate valid configurations. We overcome this challenge by redefining the robot’s degrees of freedom and constraints into a new set of parameters, called reachable distance space (RD-space), in which all configurations lie in the set of constraint-satisfying subspaces. This enables us to directly sample the constrained subspaces with complexity linear in the number of the robot’s degrees of freedom. In addition to supporting efficient sampling of configurations, we show that the RD-space formulation naturally supports planning and, in particular, we design a local planner suitable for use by sampling-based planners. We demonstrate the effectiveness and efficiency of our approach for several systems including closed chain planning with multiple loops, restricted end-effector sampling, and on-line planning for drawing/sculpting. We can sample single-loop closed chain systems with 1,000 links in time comparable to open chain sampling, and we can generate samples for 1,000-link multi-loop systems of varying topologies in less than a second.
Bayazit, O.B., Xie, D. and Amato, N.M. ( 2005). Iterative relaxation of constraints: A framework for improving automated motion planning. Proceedings IEEE International Conference Intelligent Robotic Systems (IROS), Edmonton, Alberta, Canada, pp. 3433-3440.
2.
Cortés, J. and Siméon, T. ( 2003). Probabilistic motion planning for parallel mechanisms . Proceedings IEEE International Conference Robotics and Automation (ICRA), Taipei, Taiwan, pp. 4354-4359.
3.
Cortés, J. and Siméon, T. ( 2005). Sampling-based motion planning under kinematic loop-closure constraints. Algorithmic Foundations of Robotics VI. Berlin , Springer, pp. 75-90.
4.
Cortés, J., Siméon, T. and Laumond, J.P. ( 2002). A random loop generator for planning the motions of closed kinematic chains using PRM methods. Proceedings IEEE International Conference Robotics and Automation (ICRA), Washington, DC, pp. 2141-2146.
5.
Garber, M. and Lin, M.C. ( 2003). Constraint-based motion planning using Voronoi diagrams . In Algorithmic Foundations of Robotics V. Berlin, Springer, pp. 541-558.
6.
Gharbi, M., Cortés, J. and Siméon, T. ( 2008). A sampling-based planner for dual-arm manipulation. Proceedings IEEE/ASME International Conference Advances in Mechanics (AIM), Xi’an, China.
7.
Han, L. ( 2004). Hybrid probabilistic roadmap-Monte Carlo motion planning for closed chain systems with spherical joints. Proceedings IEEE International Conference Robotics and Automation (ICRA), New Orleans, LA, pp. 920- 926.
8.
Han, L. and Amato, N.M. ( 2001). A kinematics-based probabilistic roadmap method for closed chain systems. New Directions in Algorithmic and Computational Robotics. Boston, MA, A. K. Peters, pp. 233-246.
9.
Han, L. and Rudolph, L. ( 2007a). Inverse kinematics for a serial chain with joints under distance constraints. Robotics Science and Systems II. Cambridge, MA, The MIT Press, pp. 177-184.
10.
Han, L. and Rudolph, L. ( 2007b). A unified geometric approach for inverse kinematics of a spatial chain with spherical joints. Proceedings IEEE International Conference Robotics and Automation (ICRA), Roma, Italy, pp. 4420- 4427.
11.
Han, L. and Rudolph, L. ( 2009). Simplex-tree based kinematics of foldable objects as multi-body systems involving loops. Robotics Science and Systems IV. Cambridge, MA, The MIT Press.
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 Int. Workshop on Algorithmic Foundations of Robotics (WAFR), New York, NY.
13.
Kallmann, M., Aubel, A., Abaci, T. and Thalmann, D. ( 2003). Planning collision-free reaching motion for interactive object manipulation and grasping. Computer Graphics Forum , 22(3): 313-322.
14.
Kavraki, L.E., Lamiraux, F. and Holleman, C. ( 1998). Towards planning for elastic objects. Robotics: The Algorithmic Perspective. Natick, MA, A. K. Peters , pp. 313-325.
15.
Kavraki, L.E., Švestka, P., Latombe, J.C. and Overmars, M.H. ( 1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12(4): 566-580.
16.
Khatib, O., Yokoi, K., Chang, K., Ruspini, D., Holmberg, R. and Casal, A. ( 1996). Vehicle/arm coordination and multiple mobile manipulator decentralized cooperation. Proceedings IEEE International Conference Intelligent Robotic Systems (IROS), Osaka, Japan, pp. 546-553.
17.
Kotay, K., Rus, D., Vona, M. and McGray, C. ( 1998). The self-reconfiguring robotic molecule: Design and control algorithms. Robotics: The Algorithmic Perspective, Agarwal, P. K., Kavraki, L. E. and Mason, M. T. (eds). Boston, MA, A. K. Peters, pp. 375-386.
18.
Ladd, A.M. and Kavraki, L.E. ( 2004). Using motion planning for knot untangling. The International Journal of Robotics Research, 23(7-8): 797-808.
19.
Lamiraux, F. and Kavraki, L.E. ( 1999). Path planning for elastic plates under manipulation constraints . Proceedings IEEE International Conference Robotics and Automation (ICRA), Detroit, MI, pp. 151-156.
20.
Lamiraux, F. and Kavraki, L.E. ( 2001). Planning paths for elastic objects under manipulation constraints. The International Journal of Robotics Research , 20(3): 188-208.
LaValle, S., Yakey, J. and Kavraki, L. ( 1999). A probabilistic roadmap approach for systems with closed kinematic chains. Proceedings IEEE International Conference Robotics and Automation (ICRA), Detroit, MI , pp. 1671-1676.
23.
LaValle, S.M. and Kuffner, J.J. ( 2001). Rapidly-exploring random trees: Progress and prospects . New Directions in Algorithmic and Computational Robotics, Natick, MA, A. K. Peters , pp. 293-308.
24.
Lee, C.S.G. and Ziegler, M. ( 1984). Geometric approach in solving inverse kinematics of puma robots. IEEE Transactions on Aerospace and Electronic Systems , 20(6): 695- 706.
25.
Liu, G. and Trinkle, J.C. ( 2005). Complete path planning for planar closed chains among point obstacles. Robotics Science and Systems I. Cambridge, MA, The MIT Press, 33- 40.
26.
Liu, G., Trinkle, J.C. and Shvalb, N. ( 2006). Motion planning for a class of planar closed-chain manipulators . Proceedings IEEE International Conference Robotics and Automation (ICRA), Orlando, FL, pp. 133-138.
27.
Merlet, J.-P. ( 2002). Still a long way to go on the road for parallel mechanisms . ASME Bienneal Mechanisms and Robotics Conference , Montreal, Canada.
28.
Milgram, R.J. and Trinkle, J.C. ( 2004). The geometry of configuration spaces for closed chains in two and three dimensions. Homology, Homotopy and Applications , 6(1): 237-267.
29.
Moll, M. and Kavraki, L.E. ( 2006). Path planning for deformable linear objects. IEEE Transactions on Robotics and Automation, 22(4): 625-636.
30.
Nguyen, A., Guibas, L.J. and Yim, M. ( 2001). Controlled module density helps reconfiguration planning . New Directions in Algorithmic and Computational Robotics. Boston, MA, A. K. Peters , pp. 23-36.
31.
Oriolo, G. and Mongillo, C. ( 2005). Motion planning for mobile manipulators along given end-effector paths. Proceedings IEEE International Conference Robotics and Automation (ICRA), Barcelona, Spain, pp. 2154- 2160.
32.
Oriolo, G., Ottavi, M. and Vendittelli, M. ( 2002). Probabilistic motion planning for redundant robots along given end-effector paths. Proceedings IEEE International Conference Intelligent Robotic Systems (IROS), Lausanne , Switzerland, pp. 1657-1662.
33.
Reif, J.H. ( 1979). Complexity of the mover’s problem and generalizations . Proceedings IEEE Symposium on Foundations of Computer Science (FOCS), San Juan, Puerto Rico, pp. 421-427.
34.
Saha, M. and Isto, P. ( 2006). Motion planning for robotic manipulation of deformable linear objects. Proceedings IEEE International Conference Robotics and Automation (ICRA), Orlando, FL , pp. 2478-2484.
35.
Shvalb, N., Shoham, M., Liu, G. and Trinkle, J.C. ( 2007). Motion planning for a class of planar closed-chain manipulators . The International Journal of Robotics Research, 26(5): 457-473.
36.
Singh, A.P., Latombe, J.-C. and Brutlag, D.L. ( 1999). A motion planning approach to flexible ligand binding . International Conference on Intelligent Systems for Molecular Biology (ISMB), pp. 252-261.
37.
Stilman, M. ( 2007). Task constrained motion planning in robot joint space . Proceedings IEEE International Conference Intelligent Robotic Systems (IROS), pp. 3074- 3081.
38.
Tang, X., Thomas, S. and Amato, N.M. ( 2007). Planning with reachable distances: Fast enforcement of closure constraints. Proceedings IEEE International Conference Robotics and Automation (ICRA), Roma, Italy, pp. 2694- 2699.
39.
Tang, X., Thomas, S. and Amato, N.M. ( 2008). Planning with reachable distances. Proceedings International Workshop on Algorithmic Foundations of Robotics (WAFR), Guanajuato, México.
40.
Trinkle, J.C. and Milgram, R.J. ( 2002). Complete path planning for closed kinematic chains with spherical joints. The International Journal of Robotics Research , 21(9): 773- 789.
41.
Whitney, H. ( 1932). Non-separable and planar graphs. Transactions of the American Mathematical Society, 34: 339- 362.
42.
Whitney, H. ( 1933). 2-isomorphic graphs. American Journal of Mathematics, 55: 245-254.
43.
Xie, D. and Amato, N.M. ( 2004). A kinematics-based probabilistic roadmap method for high DOF closed chain systems. Proceedings IEEE International Conference Robotics and Automation (ICRA), New Orleans, LA, pp. 473-478.
44.
Yakey, J.H., LaValle, S.M. and Kavraki, L.E. ( 2001). Randomized path planning for linkages with closed kinematic chains. IEEE Transactions on Robotics and Automation, 17(6): 951-958.
45.
Yao, Z. and Gupta, K. ( 2005). Path planning with general end-effector constraints: using task space to guide configuration space search. Proceedings IEEE International Conference Intelligent Robotic Systems (IROS) , Edmonton, Alberta, Canada, pp. 1875-1880.
46.
Yao, Z. and Gupta, K. ( 2006). Self-motion graph in path planning for redundant robots along specified end-effector paths. Proceedings IEEE International Conference Robotics and Automation (ICRA), Orlando, FL, 2004-2009.
