{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:15:34Z","timestamp":1760231734271,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2022,10,5]],"date-time":"2022-10-05T00:00:00Z","timestamp":1664928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany\u2019s Excellence Strategy\u2014EXC-2023 Internet of Production","award":["390621612"],"award-info":[{"award-number":["390621612"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotics"],"abstract":"<jats:p>We introduce a kinematic graph in this article. A kinematic graph results from structuring the data obtained from the sampling method for sampling-based motion planning algorithms in robotics with the motivation to adapt the method to the positioning problem of robotic manipulators. The term kinematic graph emphasises the fact that any path computed by sampling-based motion planning algorithms using a kinematic graph is guaranteed to correspond to a feasible motion for the positioning of the robotic manipulator. We propose methods to combine the information from the configuration and task spaces of the robotic manipulators to cluster the samples. The kinematic graph is the result of this systematic clustering and a tremendous reduction in the size of the problem. Hence, using a kinematic graph, it is possible to effectively employ sampling-based motion planning algorithms for robotic manipulators, where the problem is defined in higher dimensions than those for which these algorithms were developed. Other barriers that hindered adequate utilisation of such algorithms for robotic manipulators with articulated arms, such as the non-injective surjection of the forward kinematic function, are also addressed in the structure of the kinematic graph.<\/jats:p>","DOI":"10.3390\/robotics11050105","type":"journal-article","created":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T03:07:28Z","timestamp":1665371248000},"page":"105","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Kinematic Graph for Motion Planning of Robotic Manipulators"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1824-3433","authenticated-orcid":false,"given":"Burkhard","family":"Corves","sequence":"first","affiliation":[{"name":"Institute of Mechanism Theory, Machine Dynamics and Robotics (IGMR), RWTH Aachen University, 52062 Aachen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6295-3235","authenticated-orcid":false,"given":"Amir","family":"Shahidi","sequence":"additional","affiliation":[{"name":"Institute of Mechanism Theory, Machine Dynamics and Robotics (IGMR), RWTH Aachen University, 52062 Aachen, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2022,10,5]]},"reference":[{"key":"ref_1","unstructured":"Biagiotti, L., and Melchiorri, C. (2008). Trajectory Planning for Automatic Machines and Robots, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","article-title":"An algorithm for planning collision-free paths among polyhedral obstacles","volume":"22","author":"Wesley","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1109\/JRA.1987.1087095","article-title":"A simple motion-planning algorithm for general robot manipulators","volume":"3","year":"1987","journal-title":"IEEE J. Robot. Autom."},{"key":"ref_4","unstructured":"Khatib, O. (1985, January 25\u201328). Real-time obstacle avoidance for manipulators and mobile robots. Proceedings of the 1985 IEEE International Conference on Robotics and Automation, St. Louis, MO, USA."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"LaValle, S.M. (2006). Planning Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511546877"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1109\/TSMC.1985.6313352","article-title":"A subdivision algorithm in configuration space for find path with rotation","volume":"SMC-15","author":"Brooks","year":"1985","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Siciliano, B., and Khatib, O. (2016). Springer Handbook of Robotics, Springer International Publishing.","DOI":"10.1007\/978-3-319-32552-1"},{"key":"ref_8","unstructured":"Koren, Y., and Borenstein, J. (1991, January 7\u201312). Potential field methods and their inherent limitations for mobile robot navigation. Proceedings of the IEEE Conference on Robotics and Automation, Sacramento, CA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Lindemann, S.R., and LaValle, S.M. (2005). Current issues in sampling-based motion planning. Robotics Research, Proceedings of the Eleventh International Symposium, Siena, Italy, 19\u201322 October 2003, Springer.","DOI":"10.1007\/11008941_5"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/TRO.2004.838026","article-title":"Fast replanning for navigation in unknown terrain","volume":"21","author":"Koenig","year":"2005","journal-title":"IEEE Trans. Robot."},{"key":"ref_11","unstructured":"Stentz, A. (August, January Canada). The focussed D* algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence, Montreal, QC."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1999","DOI":"10.1109\/LRA.2019.2899668","article-title":"Minimizing task-space Frechet error via efficient incremental graph search","volume":"4","author":"Holladay","year":"2019","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.mechmachtheory.2006.02.001","article-title":"A new and efficient algorithm for the inverse kinematics of a general serial 6R manipulator","volume":"42","author":"Husty","year":"2007","journal-title":"Mech. Mach. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Lynch, K.M., and Park, F.C. (2017). Modern Robotics, Mechanics Planning, and Control, Cambridge University Press.","DOI":"10.1017\/9781316661239"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"9992","DOI":"10.1016\/j.ifacol.2020.12.2717","article-title":"Kinematic Control of Serial Manipulators Using Clifford Algebra","volume":"53","author":"Shahidi","year":"2020","journal-title":"IFAC-PapersOnLine"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1109\/TASE.2018.2805878","article-title":"Global redundancy resolution via continuous pseudoinversion of the forward kinematic map","volume":"15","author":"Hauser","year":"2018","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Berenson, D., Srinivasa, S.S., Ferguson, D., Collet, A., and Kuffner, J.J. (2009, January 12\u201317). Manipulation planning with workspace goal regions. Proceedings of the 2009 IEEE International Conference on Robotics and Automation, Kobe, Japan.","DOI":"10.1109\/ROBOT.2009.5152401"},{"key":"ref_18","unstructured":"LaValle, S.M. (2022, February 27). Rapidly-Exploring Random Trees: A New Tool for Path Planning. Available online: http:\/\/msl.cs.illinois.edu\/~lavalle\/papers\/Lav98c.pdf."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1177\/0278364913507983","article-title":"Single-and dual-arm motion planning with heuristic search","volume":"33","author":"Cohen","year":"2014","journal-title":"Int. J. Robot. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1109\/TRO.2014.2340191","article-title":"Balancing exploration and exploitation in sampling-based motion planning","volume":"30","author":"Rickert","year":"2014","journal-title":"IEEE Trans. Robot."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Scheurer, C., and Zimmermann, U.E. (2011, January 9\u201313). Path planning method for palletizing tasks using workspace cell decomposition. Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China.","DOI":"10.1109\/ICRA.2011.5980573"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Mesesan, G., Roa, M.A., Icer, E., and Althoff, M. (2018, January 1\u20135). Hierarchical path planner using workspace decomposition and parallel task-space rrts. Proceedings of the 2018 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Madrid, Spain.","DOI":"10.1109\/IROS.2018.8593870"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1109\/LRA.2017.2773669","article-title":"HDRM: A Resolution Complete Dynamic Roadmap for Real-Time Motion Planning in Complex Scenes","volume":"3","author":"Yang","year":"2017","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1115\/1.4011045","article-title":"A kinematic notation for lower-pair mechanisms based on matrices","volume":"22","author":"Denavit","year":"1955","journal-title":"J. Appl. Mech."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Khalil, W., and Kleinfinger, J. (1986, January 7\u201310). A new geometric notation for open and closed-loop robots. Proceedings of the 1986 IEEE International Conference on Robotics and Automation, San Francisco, CA, USA.","DOI":"10.1109\/ROBOT.1986.1087552"},{"key":"ref_26","unstructured":"Angeles, J. (2013). Rational Kinematics, Springer."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Khalil, W., and Dombre, E. (2002). Modeling Identification and Control of Robots, CRC Press.","DOI":"10.1016\/B978-190399666-9\/50014-2"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Uicker, J.J., Ravani, B., and Sheth, P.N. (2013). Matrix Methods in the Design Analysis of Mechanisms and Multibody Systems, Cambridge University Press.","DOI":"10.1017\/CBO9781139032339"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s11044-017-9582-7","article-title":"Screw and Lie group theory in multibody kinematics","volume":"43","year":"2018","journal-title":"Multibody Syst. Dyn."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Angeles, J. (2007). Fundamentals of Robotic Mechanical Systems, Springer.","DOI":"10.1007\/978-0-387-34580-2"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1109\/ACCESS.2014.2302442","article-title":"Sampling-based robot motion planning: A review","volume":"2","author":"Elbanhawi","year":"2014","journal-title":"IEEE Access"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_34","unstructured":"Likhachev, M., Gordon, G.J., and Thrun, S. (2003, January 8\u201313). ARA*: Anytime A* with provable bounds on sub-optimality. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.artint.2003.12.001","article-title":"Lifelong Planning A*","volume":"155","author":"Koenig","year":"2004","journal-title":"Artif. Intell."},{"key":"ref_36","first-page":"476","article-title":"D* Lite","volume":"15","author":"Koenig","year":"2002","journal-title":"Aaai\/iaai"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","article-title":"Probabilistic roadmaps for path planning in high-dimensional configuration spaces","volume":"12","author":"Kavraki","year":"1996","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_38","unstructured":"Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Longman Publishing Co., Inc."},{"key":"ref_39","first-page":"453","article-title":"Kinematically Adapted Sampling-Based Motion Planning Algorithm for Robotic Manipulators","volume":"Volume 24","author":"Shahidi","year":"2022","journal-title":"Advances in Robot Kinematics"},{"key":"ref_40","unstructured":"Peixoto, T.P. (2022, February 27). The Graph-Tool Python Library. Available online: https:\/\/doi.org\/10.6084\/M9.FIGSHARE.1164194.V14."},{"key":"ref_41","unstructured":"Kinzig, T. (2021). Search-Based Path Planning for Positioning of Robot Manipulators. [Master\u2019s Thesis, RWTH Aachen University]."}],"container-title":["Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2218-6581\/11\/5\/105\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:46:41Z","timestamp":1760143601000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2218-6581\/11\/5\/105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,5]]},"references-count":41,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["robotics11050105"],"URL":"https:\/\/doi.org\/10.3390\/robotics11050105","relation":{},"ISSN":["2218-6581"],"issn-type":[{"type":"electronic","value":"2218-6581"}],"subject":[],"published":{"date-parts":[[2022,10,5]]}}}