{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:33:29Z","timestamp":1756992809990,"version":"3.38.0"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2011,1,14]],"date-time":"2011-01-14T00:00:00Z","timestamp":1294963200000},"content-version":"unspecified","delay-in-days":13,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotica"],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:title>SUMMARY<\/jats:title><jats:p>Motion planning for self-reconfiguring robots can be made efficient by exploiting potential reductions to suitably large subspaces. However, there are no general techniques for identifying suitable restrictions that have a positive effect on planning efficiency. We present two approaches to understanding the structure that is required of the subspaces, which leads to improvement in efficiency of motion planning. This work is presented in the context of a specific motion planning procedure for a hexagonal metamorphic robot. First, we use ideas from spectral graph theory \u2013 empirically estimating the algebraic connectivity of the state space \u2013 to show that the HMR model is better structured than many alternative motion catalogs. Secondly, using ideas from graph minor theory, we show that the infinite sequence of subspaces generated by configurations containing increasing numbers of subunits is well ordered, indicative of regularity of the space as complexity increases. We hope that these principles could inform future algorithm design for many different types of self-reconfiguring robotics problems.<\/jats:p>","DOI":"10.1017\/s0263574710000718","type":"journal-article","created":{"date-parts":[[2011,1,14]],"date-time":"2011-01-14T15:37:39Z","timestamp":1295019459000},"page":"73-85","source":"Crossref","is-referenced-by-count":5,"title":["A characterization of the reconfiguration space of self-reconfiguring robotic systems"],"prefix":"10.1017","volume":"29","author":[{"given":"Tom","family":"Larkworthy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subramanian","family":"Ramamoorthy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,1,14]]},"reference":[{"key":"S0263574710000718_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2005.08.009"},{"key":"S0263574710000718_ref19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026504804984"},{"key":"S0263574710000718_ref1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045468"},{"key":"S0263574710000718_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"S0263574710000718_ref12","doi-asserted-by":"crossref","unstructured":"12. Larkworthy T. and Ramamoorthy S. , \u201cAn effecient algorithm for self-reconfiguration planning in a modular robot,\u201d In Robotics and Automation, Proceedings., IEEE International Conference on, pp. 5139\u20135146 (2010).","DOI":"10.1109\/ROBOT.2010.5509482"},{"key":"S0263574710000718_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/70.611311"},{"key":"S0263574710000718_ref2","doi-asserted-by":"crossref","unstructured":"2. Butler Z. , Kotay K. , Rus D. and Tomita K. , \u201cGeneric decentralized control for a class of self-reconfigurable robots,\u201d Proceedings of the 2002 International Conference on Robotics and Automation (ICRA 2002), pp. 809\u2013816.","DOI":"10.1109\/ROBOT.2002.1013457"},{"volume-title":"Graph Theory","year":"2005","author":"Diestel","key":"S0263574710000718_ref5"},{"key":"S0263574710000718_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/1656274.1656278"},{"volume-title":"Spectral Graph Theory","year":"1997","author":"Chung","key":"S0263574710000718_ref4"},{"volume-title":"Artificial Intelligence: A Modern Approach","year":"1995","author":"Russell","key":"S0263574710000718_ref20"},{"key":"S0263574710000718_ref3","first-page":"449","article-title":"Kinematics of a metamorphic robotic system","volume":"1","author":"Chirikjian","journal-title":"Robotics and Automation, Proceedings., 1994 IEEE International Conference on"},{"key":"S0263574710000718_ref11","unstructured":"11. Larkworthy T. , Hayes G. and Ramamoorthy S. , \u201cGeneral motion planning methods for self-reconfiguration planning,\u201d Towards Auton. Robot. Sys. (2009)."},{"key":"S0263574710000718_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TMECH.2002.806220"},{"key":"S0263574710000718_ref10","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"S0263574710000718_ref8","doi-asserted-by":"crossref","unstructured":"8. Kavraki L. E. , Svestka P. , Latombe J.-C. and Overmars M. H. , In Robotics and Automation, Proceedings., IEEE, International Conference on Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces, pp. 566\u2013580 (1997).","DOI":"10.1109\/70.508439"},{"key":"S0263574710000718_ref15","doi-asserted-by":"crossref","unstructured":"15. Pamecha A. , Chiang C. , Stein D. and Chirikjian G. , \u201cDesign and implementation of metamorphic robots,\u201d In The ASME Design Engineering Technical Conference and Computers in Engineering Conference (1996).","DOI":"10.1115\/96-DETC\/MECH-1149"},{"key":"S0263574710000718_ref18","doi-asserted-by":"crossref","unstructured":"18. Reif J. and Slee S. , \u201cOptimal kinodynamic motion planning for 2d reconfiguration of self-reconfigurable robots,\u201d Robot. Sci. Syst. (2007).","DOI":"10.15607\/RSS.2007.III.020"},{"volume-title":"C4.5: Programs for Machine Learning","year":"1993","author":"Quinlan","key":"S0263574710000718_ref17"},{"key":"S0263574710000718_ref9","doi-asserted-by":"crossref","unstructured":"9. Kirby B. T. , Aksak B. , Campbell J. D. , Hoburg J. F. , C T. . Mowry, Pillai P. and Goldstein S. C. , \u201cA modular robotic system using magnetic force effectors,\u201d Intelligent Robots and Systems, IEEE\/RSJ International Conference on, pp. 2787\u20132793 (29 2007-Nov. 2 2007).","DOI":"10.1109\/IROS.2007.4399444"}],"container-title":["Robotica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0263574710000718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T20:07:30Z","timestamp":1740859650000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0263574710000718\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["S0263574710000718"],"URL":"https:\/\/doi.org\/10.1017\/s0263574710000718","relation":{},"ISSN":["0263-5747","1469-8668"],"issn-type":[{"type":"print","value":"0263-5747"},{"type":"electronic","value":"1469-8668"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}