Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-25T05:37:55.807Z Has data issue: false hasContentIssue false
  • English
  • Français

A characterization of the reconfiguration space of self-reconfiguring robotic systems

Published online by Cambridge University Press:  14 January 2011

Tom Larkworthy  and
Subramanian Ramamoorthy
Tom Larkworthy*
Affiliation:
Institute of Perception, Action and Behaviour, School of Informatics, University of Edinburgh, 10 Crichton Street, Edinburgh EH8 9AB email: [email protected]
Subramanian Ramamoorthy
Affiliation:
Institute of Perception, Action and Behaviour, School of Informatics, University of Edinburgh, 10 Crichton Street, Edinburgh EH8 9AB email: [email protected]
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

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 – empirically estimating the algebraic connectivity of the state space – 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.

Keywords

Self-reconfiguring roboticsMotion planningGraph theory
Type
Article
Information
Robotica , Volume 29 , Special Issue 1: Robotic Self-X Systems , January 2011 , pp. 73 - 85
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Abrams, A. and Ghrist, R., “State complexes for metamorphic robot systems,” Int. J. Robot. Res. 23 (7), 809–824 (2004).CrossRefGoogle Scholar
2.Butler, Z., Kotay, K., Rus, D. and Tomita, K., “Generic decentralized control for a class of self-reconfigurable robots,” Proceedings of the 2002 International Conference on Robotics and Automation (ICRA 2002), pp. 809–816.Google Scholar
3.Chirikjian, G. S., “Kinematics of a metamorphic robotic system,” Robotics and Automation, Proceedings., 1994 IEEE International Conference on, vol. 1, pp. 449–455.Google Scholar
4.Chung, F., Spectral Graph Theory (American Mathematical Society, Providence, RI, 1997).Google Scholar
5.Diestel, R., Graph Theory, vol. 173 of Graduate Texts in Mathematics, 3rd. ed. (Springer-Verlag, Heidelberg, 2005).Google Scholar
6.Ghrist, R. and Peterson, V., “The geometry and topology of reconfiguration,” Adv. Appl. Math. 38, 302–323 (2007).CrossRefGoogle Scholar
7.Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P. and Witten, I. H., “The weka data mining software: An update,” SIGKDD Explor. Newsl. 11 (1), 10–18 (2009).CrossRefGoogle Scholar
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–580 (1997).CrossRefGoogle Scholar
9.Kirby, B. T., Aksak, B., Campbell, J. D., Hoburg, J. F., C, T.. Mowry, Pillai, P. and Goldstein, S. C., “A modular robotic system using magnetic force effectors,” Intelligent Robots and Systems, IEEE/RSJ International Conference on, pp. 2787–2793 (29 2007-Nov. 2 2007).CrossRefGoogle Scholar
10.Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P., “Optimization by simulated annealing,” Science 220, 671–679 (1983).CrossRefGoogle ScholarPubMed
11.Larkworthy, T., Hayes, G. and Ramamoorthy, S., “General motion planning methods for self-reconfiguration planning,” Towards Auton. Robot. Sys. (2009).Google Scholar
12.Larkworthy, T. and Ramamoorthy, S., “An effecient algorithm for self-reconfiguration planning in a modular robot,” In Robotics and Automation, Proceedings., IEEE International Conference on, pp. 5139–5146 (2010).CrossRefGoogle Scholar
13.LaValle, S. M., Planning Algorithms (Cambridge University Press, Cambridge, U.K., 2006).CrossRefGoogle Scholar
14.Murata, S., Yoshida, E., Kamimura, A., Kurokawa, H., Tomita, K. and Kokaji, S., “M-tran: Self-reconfigurable modular robotic system,” Mechatron., IEEE/ASME Trans. 7 (4), 431–441 (2002).CrossRefGoogle Scholar
15.Pamecha, A., Chiang, C., Stein, D. and Chirikjian, G., “Design and implementation of metamorphic robots,” In The ASME Design Engineering Technical Conference and Computers in Engineering Conference (1996).CrossRefGoogle Scholar
16.Pamecha, A., Ebert-Uphoff, I. and Chirikjian, G., “Useful metrics for modular robot motion planning,” Robot. Automat., IEEE Trans. 13 (4), 531–545 (Aug 1997).CrossRefGoogle Scholar
17.Quinlan, R. J., C4.5: Programs for Machine Learning (Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993).Google Scholar
18.Reif, J. and Slee, S., “Optimal kinodynamic motion planning for 2d reconfiguration of self-reconfigurable robots,” Robot. Sci. Syst. (2007).CrossRefGoogle Scholar
19.Rus, D. and Vona, M., “Crystalline robots: Self-reconfiguration with compressible unit modules,” Auton. Robots 10 (1), 107–124 (2001).CrossRefGoogle Scholar
20.Russell, S. J. and Norvig, P., Artificial Intelligence: A Modern Approach (Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1995).Google Scholar