The paper reports studies on the motion planning problem for planar star-shaped manipulators. These manipulators are formed by joining k “legs” to a common point (like the thorax of an insect) and then fixing the “feet” to the ground. The result is a planar parallel manipulator with k - 1 independent closed loops. A topological analysis is used to understand the global structure of the configuration space so that the planning problem can be solved exactly. The worst-case complexity of the algorithm is O(k3N 3), where N is the maximum number of links in a leg. Examples illustrating the method are given.
Amato, N., Bayazit, B., Dale, L., Jones, C., and Vallejo, D. (1998). OBPRM: An obstacle-based PRM for 3D workspaces . In Robotics: The Algorithmic Perspective (eds P. Agarwal, L. Kavraki, and M. Mason), pp.156—168, A. K. Peters, Natick, MA.
2.
Banga, J.R. and Seider, W.D. (1996). Global optimization of chemical processes using stachastic algorithms. In State of the Art in Global Optimization: Computational Methods and Applications (eds C.A. Floudas and P.M. Pardalos), pp.563—583, Kluwer Academic Publishers.
3.
Barraquand, J. and Latombe, J.-C. (1991). Nonholonomic multibody mobile robots: controllability and motion planning in the presence of obstacles. IEEE Interantional Conference on Robotics and Automation, pp.2328—2335.
4.
Bohlin, R. and Kavraki, L. (2000). Path planning using lazy PRM. IEEE International Conference on Robotics and Automation, pp.521—528.
5.
Boor, V., Overmas, M., and van der Stappen, A.F. (1999). The Gaussian sampling strategy for probabilistic roadmap planners. IEEE International Conference on Robotics and Automation.
6.
Burdick, J.W. (1989). On the inverse kinematics of redundant manipulators: characterization of the self-motion manifolds. IEEE International Conferemce on Robotics and Automation (ICRA), May, pp.264—270.
7.
Canny, J.F. (1988). The Complexity of Robot Motion Planning. Mit Press, Cambridge, MA1988.
8.
Cherif, M. and Gupta, K.K. (1989). Planning quasi-static fingertip manipulation for reconfiguring objects. IEEE Transactions on Robotics and Automation , 15(5): 837—848.
9.
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 of the 2002 IEEE International Conference on Robotics and Automation , pp.2141—2146.
10.
Dash, A.K., I-Ming, C., Song-Huat, Y., and Guilin, Y. (2003). Singularity-free path planning of parallel manipulators using clustering algorithm and line geometry. Robotics and Automation, 1: 761—766.
11.
Han, L. and Amato, N.M. (2001). A kinematics-based probabilistic roadmap method for closed chain systems. In Algorithmic and Computational Robotics: New Directions (eds B. R. Donald , K. M. Lynch, and D. Rus), pp.233—246, A. K. Peters, Wellesley, MA.
12.
Hsu, D., Latombe, J.C., and Motwani, R. (1997). Path planning in expansive configuration spaces . IEEE International Conference on Robotics and Automation.
13.
Jacobs, D.J., Reider, A.J., Kuhn, L.A., and Thorpe, M.F. (YEAR??). Protein flexibility predictions using graph theory. PROTEINS: Structure, Function, and Genetics, 44: 150—165.
14.
Kamiyama, Y., Tezuka, M., and Toma, T. (1998). Homology of the configuration spaces of quasi-equilateral polygon linkages. Transactions of the American Mathematical Society, 350(12): 4869—4896.
15.
Kapovich, M. and Millson, J. (1995). On the moduli spaces of polygons in the Euclidean plane. Journal of Differential Geometry, 42: 133—164.
16.
Kavraki, L.E., Švestka, P., Latombe, J.C., and Overmars, M.H. (1996). Probablistic roadmaps for path planning in high-dimensional configuration space. IEEE Transactions on Robotics and Automation , 12(4): 566—580.
17.
Koditschek, D.E. (1987). Exact robot navigation by means of potential functions: some topological considerations. IEEE International Conference on Robotics and Automation, pp.1—6.
18.
Kuffner, J.J. and LaValle, S.M. (2000). RRT-Connect: an efficient approach to single-query path planning. IEEE International Conference on Robotics and Automation, pp.995—1001.
LaValle, S.M. and Kuffner, J.J. (2001). Rapidly-exploring random trees: progress and prospects . In Algorithmic and Computational Robotics: New Directions (eds B. R. Donald, K. M. Lynch, and D. Rus), pp.293—308, A. K. Peters, Wellesley, MA.
21.
LaValle, S.M. and Kuffner, J.J. (1999). Randomized kinodynamic planning. IEEE International Conference on Robotics and Automation.
22.
Lozano-Perez (1983). Spatial planning: a configuration space approach. IEEE Transactions on Computers, C-32(2): 108— 119.
23.
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.
24.
Nenchev, D.N., Tsumaki, Y., and Uchiyama, Y. (2000). Singularity-consistent parameterization of robot motion and control. The International Journal of Robotics Research, 19(2): 159—182.
25.
Rimon, E. and Koditschek, D.E. (1988). Exact robot navigation using cost functions: the case of distinct spherical boundaries in E n . IEEE International Conference on Robotics and Automation, pp.1791—1796.
26.
Rimon, E. and Koditschek, D.E. (1989). The construction of analytic diffeomorphisms for exact robot navigation on Star Worlds. IEEE International Conference on Robotics and Automation, pp.21—26.
27.
Schwartz, J., Hopcroft, J., and Sharir, M. (1987). Planning, Geometry, and Complexity of Robot Motion . Ablex.
28.
Schwartz, J.T. and Sharir, M. (1983). On the piano movers II. General techniques for computing topological properties on real algebraic manifolds. AdvancedApplied Mathematics, 4: 298—351.
29.
Sefrioui, J. and Gosselin, C.M. (1995). On the quadratic nature of the singularity curves of planar three-degree-of-freedom parallel manipulators. Mechanism andMachine Theory, 30(4): 533—551.
30.
Shvalb, N., Shoham, M., and Blanc, D. (1998). The configuration space of an arachnoid mechanism . Forum Mathemaicum, 17(6): 1033—1042.
31.
Trinkle, J.C. and Milgram, R.J. (2002). Complete path planning for closed kinematic chains with spherical joints. International Journal of Robotics Research , 21(9): 773—789.
32.
Yakey, J., 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.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
