Self-reconfiguration algorithms for robotic systems

Self-reconfiguration algorithms for robotic systems

Konstantin S. Zakharov
Saint-Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences (SPIIRAS), Laboratory of Autonomous Robotic Systems, Programmer, 21, Tikhoretsky pr., Saint-Petersburg, 194064, Russia, tel.: +7(931)363-58-96, This email address is being protected from spambots. You need JavaScript enabled to view it.

Irina V. Vatamaniuk
Saint-Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences (SPIIRAS), Laboratory of Autonomous Robotic Systems, Junior Research Scientist, 21, Tikhoretsky pr., Saint-Petersburg, 194064, Russia, tel.: +7(812)328-44-50, This email address is being protected from spambots. You need JavaScript enabled to view it.

Konstantin D. Krestovnikov
Saint-Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences (SPIIRAS), Laboratory of Autonomous Robotic Systems, Junior Research Scientist, 21, Tikhoretsky pr., Saint-Petersburg, 194064, Russia, tel.: +7(812)328-44-50, This email address is being protected from spambots. You need JavaScript enabled to view it.


Received 17 September 2018

Abstract
In the work, the algorithms and concepts for reconfiguration of chain-type robots were investigated, and reconfiguration planning algorithms were developed. Based on the survey results, an original approach to solving the reconfiguration problem was proposed, namely the decomposition of the general problem into two subtasks: movement of individual modules to the target point and control of the obtained robotic complex. Within the framework of this study, only the subtask of reconfiguration planning was considered. Three algorithms were developed: the target assignment, the search for the optimal path, and the movement of the robot module. This combination of algorithms allowed solving the problem of moving the modules in space and further linking with each other.

Key words
Modular robots, self-reconfiguration, path search, distributed control, reconfiguration of robots.

Acknowledgements
Research was carried out with support of Russian Academy of Sciences (RAS) Program I.29.

DOI
https://doi.org/10.31776/RTCJ.6407

Bibliographic description
Zakharov, K., Vatamaniuk, I. and Krestovnikov, K. (2018). Self-reconfiguration algorithms for robotic systems. Robotics and Technical Cybernetics, 4(21), pp.48-59.

UDC identifier:
004.896

References

  1. Yim, M., Duff, D.G. and Roufas, K.D. (2000). PolyBot: a modular reconfigurable robot. In: Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings.
  2. Shen, W.-M., Salemi, B. and Will, P. (2002). Hormone-inspired adaptive communication and distributed control for CONRO self-reconfigurable robots. IEEE Trans. on Robotics and Automation, 18(5), pp. 700-712.
  3. Murata, S., Yoshida, E., Kamimura, A., Kurokawa, H., Tomita, K. and Kokaji, S. (2002). M-TRAN: self-reconfigurable modular robotic system. IEEE/ASME Trans. Mech, 7(4), pp. 431-441.
  4. Hackaday.io. (2016). Dtto–Explorer Modular Robot. [on-line] Available at: https://hackaday.io/project/9976-dtto-explorer-modular-robot [Accessed 28.09.2018].
  5. Salemi, B., Moll, M. and Shen, W.-M. (2006). SUPERBOT: A deployable, multi-functional, and modular self-reconfigurable robotic system. In: IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems.
  6. Casal, A. (2002). Reconfiguration planning for modular self-reconfigurable robots. Doctoral Dissertation. Stanford University.
  7. Nelson, C.A. and Cipra, R.J. (2004). An algorithm for efficient self-reconfiguration of chain-type unit-modular robots. In: ASME 2004 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, pp. 1283-1291.
  8. Kamimura, A., Kurokawa, H., Yoshida, E., Murata, S., Tomita, K. and Kokaji, S. (2004). Distributed adaptive locomotion by a modular robotic system. M-TRAN II. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2370–2377.
  9. Kamimura, A., Kurokawa, H., Yoshida, E., Murata, S., Tomita, K. and Kokaji, S. (2003). Automatic locomotion pattern generation for modular robots. In: 2003 IEEE International Conference on Robotics and Automation, pp. 714–720.
  10. Payne, K., Salemi, B., Will, P. and Shen, W.-M. (2004). Sensor-based distributed control for chain-typed self-reconfiguration. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
  11. Hou, F. and Shen, W.-M. (2008). Distributed, dynamic, and autonomous reconfiguration planning for chain-type self-reconfigurable robots. In: IEEE International Conference on Robotics and Automation.
  12. Liu, J.G., Wang, Y.C., Li, B., Ma, S.G. and Tan, D.L. (2007). Center-Configuration Selection Technique for the Reconfigurable Modular Robot.
  13. Madey, G.R., Blake, M.B., Poellabauer, C., Lu, H., McCune, R.R. and Wei, Y. (2012). Applying DDDAS principles to command, control and mission planning for UAV swarms. In: International Conference on Computational Science, ICCS.
  14. Kotay, K. and Rus, D. (2000). Algorithms for self-reconfiguring molecule motion planning. In: Proceedings of the 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems.
  15. Rus, D. and Vona, M. (2001). Crystalline robots: Self-reconfiguration with compressible unit modules. M. Autonomous Robots, 10(1), pp. 107-124.
  16. Fitch, R., Butler, Z. and Rus, D. (2005). Reconfiguration planning among obstacles for heterogeneous self-reconfiguring robots. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, pp. 117-124.
  17. Larkworthy, T. and Ramamoorthy, S. (2010). An efficient algorithm for self-reconfiguration planning in a modular robot. In: Robotics and Automation (ICRA), 2010 IEEE International Conference on, pp. 5139-5146.
  18. Kuhn, H.W. (1955). The Hungarian Method for the Assignment Problem.
  19. Pamecha, A., Ebert-Uphoff, I. and Chirikjian, G.S. (1997). Useful metrics for modular robot motion planning. In: IEEE Transactions on Robotics and Automation, 13(4), pp. 531–545.
  20. Asadpour, M., Sproewitz, A., Billard, A., Dillenbourg, P. and Ijspeert, A.J. (2008). Graph signature for self-reconfiguration planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems.
  21. Asadpour, M., Ashtiani, M., Sproewitz, A. and Ijspeert, A. (2009). Graph signature for self-reconfiguration planning of modules with symmetry. In: IEEE/RSJ International Conference on Intelligent Robots and Systems.
  22. Ghallab, M., Nau, D. and Traverso, P. (2004). Automated planning: theory & practice.
  23. Nau, D.S. and et al. (2003). SHOP2: An HTN planning system. Journal of Artificial Intelligence Research, 20, pp. 379–404.
  24. Bihlmaier, A., Winkler, L. and Worn, H. (2013). Automated planning as a new approach for the self-reconfiguration of mobile modular robots. In: 9th International Workshop on Robot Motion and Control.
  25. Nourollah, A. and Razzazi, M. (2011). Minimum cost open chain reconfiguration. Discrete Applied Mathematics, 159(14), pp. 1418-1424.
  26. Kavraki, L.E., Svestka, P. and Latombe, J.-C. (1996). Overmars M.H. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. In: IEEE Transactions on Robotics and Automation, 12(4), pp. 566–580.
  27. Lavalle, S.M. (1998). Rapidly-Exploring Random Trees A New Tool for Path Planning. Report No. TR 98-11. Computer Science Department, Iowa State University.
  28. Jorgensen, M.W., Ostergaard, E.H. and Lund, H.H. (2004). Modular ATRON: modules for a self-reconfigurable robot. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
  29. Brandt, D. (2006). Comparison of A and RRT-Connect motion planning techniques for self-reconfiguration planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems.
  30. Golestan, K., Asadpour, M. and Moradi, H. (2010). A new graph signature calculation method based on power centrality for modular robots. Distributed Autonomous Robotic Systems. Springer Tracts in Advanced Robotics, 83.
  31. Christensen, D.J. (2006). Evolution of shape-changing and self-repairing control for the ATRON self-reconfigurable robot. In: Proceedings 2006 IEEE International Conference on Robotics and Automation.
  32. Pamecha, A., Ebert-Uphoff, I., Chirikjian, G. (1997). Useful metrics for modular robot motion planning. IEEE Transactions on Robotics and Automation, 13(4), pp. 531–545.
  33. Lal, S., Yamada, K. and Endo, S. (2008). Emergent motion characteristics of a modular robot through genetic algorithm. In: ICIC '08 Proceedings of the 4th international conference on Intelligent Computing: Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence, 5227, pp. 225–234.
  34. Christensen, D. J., Brandt, D. and Stoy, K. (2006). Towards artificial ATRON animals: scalable anatomy for self-reconfigurable robots. In: Robotics science and systems: workshop on modular self-reconfigurable systems.
  35. Kamimura, A., Kurokawa, H., Toshida, E., Tomita, K., Murata, S. and Kokaji, S. (2003). Automatic locomotion pattern generation for modular robots. In: IEEE International Conference on Robotics and Automation.
Editorial office address: 21, Tikhoretsky pr., Saint-Petersburg, Russia, 194064, tel.: +7(812) 552-13-25 e-mail: zheleznyakov@rtc.ru