Self-reconfigurable robots are versatile systems consisting of large numbers of independent modules. Effective use of these systems requires parallel actuation and planning, both for efficiency and independence from a central controller. In this paper we present the PacMan algorithm, a technique for distributed actuation and planning for systems with two- or three-dimensional unit-compressible modules. We give two versions of the algorithm along with correctness analysis. We also analyze the parallel actuation capability of the algorithm, showing that it will not deadlock and will avoid disconnecting the robot. We have implemented PacMan on the Crystal robot, a hardware system developed in our lab, and we present experiments and discuss the feasibility of large-scale implementation.
Get full access to this article
View all access options for this article.
References
1.
Butler, Z., and Rus, D. 2002. Distributed motion planning for 3D robots with unit-compressible modules . In Workshop on the Algorithmic Foundation of Robotics.
2.
Butler, Z., and Rus, D. June 2003. Distributed planning and control for modular robots with unit-compressible modules. Technical Report TR2003-462, Dartmouth Computer Science.
3.
Butler, Z., Byrnes, S., and Rus, D. 2001. Distributed motion planning for modular robots with unit-compressible modules . In Proceedings of the International Conference on Intelligent Robots and Systems, pp. 790-796 .
4.
Butler, Z., Fitch, R., and Rus, D. 2002a. Experiments in distributed control of modular robots. In Experimental Robotics VIII, pp. 307-316.
5.
Butler, Z., Fitch, R., and Rus, D. 2002b. Distributed control for unit-compressible robots: Goal-recognition, locomotion and splitting . IEEE/ASME Transactions on Mechatronics7(4): 418-430 .
6.
Castano, A., Shen, W.-M., and Will, P. 2000. CONRO: Towards deployable robots with inter-robots metamorphic capabilities . Autonomous Robots8(3): 309-324 .
7.
Chiang, C.-H., and Chirikjian, G. 2001. Modular robot motion planning using similarity metrics . Autonomous Robots10(1): 91-106 .
8.
Chirikjian, G. 1994. Kinematics of a metamorphic robot system . In Proceedings of IEEE ICRA, pp. 449-455 .
9.
Fukuda, T., and Kawauchi, Y. 1990. Cellular robotic system (CEBOT) as one of the realization of self-organizing intelligent universal manipulator . In Proceedings of IEEE ICRA, pp. 662-667 .
10.
Kotay, K., and Rus, D. 1999. Locomotion versatility through self-reconfiguration . Robotics and Autonomous Systems26: 217-232 .
11.
Kotay, K., and Rus, D. 2000. Algorithms for self-reconfiguring molecule motion planning . In Proceedings of the International Conference on Intelligent Robots and Systems, pp. 2184-2193 .
12.
Lee, W. H., and Sanderson, A. 2001. Dynamic analysis and distributed control of the tetrabot modular reconfigurable robot system . Autonomous Robots10(1): 67-82 .
13.
Murata, S., Kurokawa, H., and Kokaji, S. 1994. Self-assembling machine . In Proceedings of IEEE ICRA, pp. 442-448 .
14.
Murata, S., Kurokawa, H., Yoshida, E., Tomita, K., and Kokaji, S. May 1998. A 3D self-reconfigurable structure . In Proceedings of IEEE ICRA, pp. 432-439 .
15.
Murata, S., Yoshida, E., Kamimura, A., Kurokawa, H., Tomita, K., and Kokaji, S. 2002. M-TRAN: Self-reconfigurable modular robotic system . IEEE/ASME Transactions on Mechatronics7(4): 431-441 .
16.
Nguyen, A., Guibas, L., and Yim, M. 2000. Controlled module density helps reconfiguration planning . In Algorithmic and Computational Robotics: Proceedings of WAFR 2000, pp. 23-35 .
17.
Pamecha, A., Chiang, C.-J., Stein, D., and Chirikjian, G. 1996. Design and implementation of metamorphic robots . In Proceedings of the 1996 ASME Design Engineering Technical Conference and Computers in Engineering Conference, pp. 1-10 .
18.
Pamecha, A., Ebert-Uphoff, I., and Chirikjian, G. 1997. Useful metrics for modular robot motion planning . IEEE Transactions on Robotics and Automation13(4): 531-545 .
19.
Rus, D., and Vona, M. 2001. Crystalline robots: Self-reconfiguration with unit-compressible modules . Autonomous Robots10(1): 107-124 .
20.
Salemi, B., Shen, W.-M., and Will, P. 2001. Hormone-controlled metamorphic robots . In Proceedings of IEEE ICRA, pp. 4194-4199 .
21.
Suh, J., Homans, S., and Yim, M. 2002. Telecubes: Mechanical design of a module for self-reconfigurable robotics . In Proceedings of IEEE ICRA, pp. 4095-4101 .
22.
Tomita, K., Murata, S., Kurokawa, H., Yoshida, E., and Kokaji, S. 1999. Self-assembly and self-repair method for a distributed mechanical system . IEEE Transactions on Robotics and Automation15(6): 1035-1045 .
23.
Ünsal, C., Kiliççöte, H., and Khosla, P. 2001. A modular self-reconfigurable bipartite robotic system: Implementation and motion planning . Autonomous Robots10(1): 23-40 .
24.
Vassilvitskii, S., Yim, M., and Suh, J. 2002. A complete, local and parallel reconfiguration algorithm for cube style modular robots . In Proceedings of IEEE ICRA, pp. 117-122 .
25.
Walter, J. E., Tsai, E. M., and Amato, N. M. 2002. Choosing good paths for fast distributed reconfiguration of hexagonal metamorphic robots . In Proceedings of IEEE ICRA, pp. 102-109 .
26.
Walter, J. E., Welch, J. L., and Amato, N. M. 2002. Concurrent metamorphosis of hexagonal robot chains into simple connected configurations . IEEE Transactions on Robotics and Automation18(6): 945-956 .
27.
Yim, M. 1993. A reconfigurable modular robot with multiple modes of locomotion . In Proceedings of JSME Conference on Advanced Mechatronics, Tokyo, Japan, pp. 283-288 .
28.
Yim, M., Duff, D., and Roufas, K. 2000. PolyBot: a modular reconfigurable robot . In Proceedings of IEEE ICRA, pp. 514-520 .
29.
Yim, M., Zhang, Y., Lamping, J., and Mao, E. 2001. Distributed control for 3D metamorphosis . Autonomous Robots10(1): 41-56 .
30.
Yoshida, E., Murata, S., Kamimura, A., Tomita, K., Kurokawa, H., and Kokaji, S. 2000. Motion planning of self-reconfigurable modular robot . In Proceedings of International Symposium on Experimental Robotics.
31.
Yoshida, E., Murata, S., Kokaji, S., Kamimura, A., Tomita, K., and Kurokawa, H. 2002. Get back in shape! IEEE Robotics and Automation Magazine9(4): 54-60 .
