Adaptive Division-of-Labor Control Algorithm for Multi-Robot Systems

Yusuke Ikemoto; Toru Miura; Hajime Asama

doi:10.20965/jrm.2010.p0514

single-rb.php

« previous

JRM Vol.22 No.4 pp. 514-525

doi: 10.20965/jrm.2010.p0514

(2010)

Paper:

Views over last 60 days: 485

Adaptive Division-of-Labor Control Algorithm for Multi-Robot Systems

Yusuke Ikemoto^, Toru Miura^, and Hajime Asama^

^*Graduate School of Science and Engineering for Research, University of Toyama, 3190 Gofuku, Toyama 930-8555, Japan

^**Graduate School of Environmental Science, Hokkaido University, CN10 W5, Kita-ku, Sapporo 060-0810, Japan

^***Department of Precision Engineering, School of Engineering, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan

Received:

December 25, 2009

Accepted:

April 20, 2010

Published:

August 20, 2010

Keywords:

multi-robot system, collective behavior, division of labor, adaptability

Abstract

An advanced function for multi-robot systems is the division of labor. There are some studies proposing a multi-agent reinforcement learning method for a division of labor. However, it often requires much time to converge. Many studies focusing on division-of-labor control inspired biological phenomenon have been reported. In those methods, whether heterogeneous or homogeneous state is determined by self-organization, however, group performance improvement is not guaranteed because decentralized control is typically complicated. In this study, we propose adaptive division-of-labor control, enabling adaptive selection of homogeneous or heterogeneous group state. We demonstrate the adaptability of proposal method versus working conditions and address the performance improvement by mathematical analysis. To evaluate the effectiveness of the proposed method, we treat foraging by multi-robot systems and confirm that the robot group inevitably organizes the division of labor with group performance improvement in computer simulations.

Cite this article as:

Y. Ikemoto, T. Miura, and H. Asama, “Adaptive Division-of-Labor Control Algorithm for Multi-Robot Systems,” J. Robot. Mechatron., Vol.22 No.4, pp. 514-525, 2010.

Data files:

References

[1] S. Garnier, J. Gautrais, and G. Theraulaz, “The biological principles of swarm intelligence,” Swarm Intelligence, Vol.1, No.1, pp. 3-31, 2007.
[2] M. Tan, “Multi-agent reinforcement learning: Independent vs. cooperative agents,” In Int. Conf. on Machine Learning ICML, Amherst, MA, 1993.
[3] M. V. N. Prasad, V. R. Lesser, and S. E. Lander, “Learning organizational roles in a heterogeneous multi-agent system,” Proc. of the Second Int. Conf. on Multiagent Systems, Kyoto, Japan, AAAI Press, 1996.
[4] K. Takadama, S. Nakasuka, and T. Terano, “Multiagent Reinforcement Learning with Organizational-learning Oriented Classifier System,” IEEE Int. Conf. on Evolutionary Computation, pp. 63-68, 1998.
[5] T. Yasuda and K. Ohkura, “Autonomous Role Assignment in a Homogeneous Multi-Robot System,” J. of Robotics and Mechatronics, Vol.17, No.5, pp. 596-604, 2005.
[6] E. O. Wilson, “Sociobiology: The New Synthesis,” Cambridge, MA: Harvard, University Press, 2000.
[7] S. N. Beshers and J. H. Fewell, “Models of division of labor in social insects. Annual Review of Entomology,” Vol.46, No.1, pp. 413-440, 2001.
[8] E. Bonabeau, G. Theraulaz, and J. L. Deneubourg, “Fixed response thresholds and the regulation of division of labour in insect societies,” Bulletin of Mathematical Biology, Vol.60, pp. 753-807, 1998.
[9] G. Theraulaz, J. Gervet, and S. Semenoff, “Social regulation of foraging activities in Polistes dominulus Christ: a systemic approach to behavioural organization,” Behaviour, Vol.116, pp. 292-320, 1991.
[10] G. Theraulaz, E. Bonabeau, and J. L. Deneubourg, “Response threshold reinforcements and division of labour in insect societies,” Proc. of the Royal Society of London. Vol.B265, pp. 327-332. 1998.
[11] Z.-Y. Huang, G. E. Robinson, S. S. Tobe, and K. J. Yagi, “Hormonal regulation of behavioural development in the honey bee is based on changes in the rate of juvenile hormone biosynthesis,” J. of Insect Physiology. Vol.37, pp. 733-41, 1991.
[12] D. Naug and R. Gadagkar, “Flexible division of labor mediated by social interactions in an insect colony: a simulation model,” J. of Theoretical Biology, Vol.97, pp. 123-33, 1999.
[13] Y. Ikemoto, T. Miura, and H. Asama, “Adaptive Division of Labor Control for Robot Group,” In The Int. Conf. on Intelligent Robots and Systems 2009(IROS2009), pp. 2409-2414, 2009.
[14] S. Shahshahni, “A new mathematical framework. for the study of linkage and selection,” Memoirs of the American Mathematical Society, Vol.17, No.211, Jan. 1979.
[15] K. Sigmund, “The Maximum Principle for Replicator Equations, Lotka-Volterra Approach to Dynamical Systems,”M. Peschel, edit., Berlin Akademie Verlag, pp. 63-71, 1985.
[16] E. Akin, “The differential geometry of population genetics and evolutionary games,” In Lessard, S., editor, Kluwer, Dordrecht, Mathematical and Statistical Developments of Evolutionary Theory, pp. 1-93, 1990.
[17] P. Schuster and K. Sigmund, “Replicator Dynamics,” J. of Theoretical Biology. Vol.100, pp. 533-538, 1983.
[18] J. M. Smith, “Evolution and the Theory of Games,” Cambridge University Press, 1982.
[19] R. Horie and E. Aiyoshi, “Variable metric gradient projection method and replicator equation,” Proc. of IEEE Int. Conf. on Systems, Man, and Cybernetics, Vol.3, pp. 515-520, 1999.
[20] J. Hofbauer and K. Sigmund, “Evo. Games and Pop. Dynamics,” Cambridge University Press, 1998.
[21] T. Mizuguchi and M. Sano, “Proportion Regulation of Biological Cells in Globally Coupled Nonlinear Systems,” Physical Review Letters, Vol.75, pp. 966-969, 1995.
[22] S. Camazine, N. R. Franks, J. Sneyd, E. Bonabeau, and J. L. Deneubourg, “Self-Organization in Biological Systems,” Princeton Univ. Press, 2003.
ISBN 0691116245.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] S. Garnier, J. Gautrais, and G. Theraulaz, “The biological principles of swarm intelligence,” Swarm Intelligence, Vol.1, No.1, pp. 3-31, 2007.

[2] [2] M. Tan, “Multi-agent reinforcement learning: Independent vs. cooperative agents,” In Int. Conf. on Machine Learning ICML, Amherst, MA, 1993.

[3] [3] M. V. N. Prasad, V. R. Lesser, and S. E. Lander, “Learning organizational roles in a heterogeneous multi-agent system,” Proc. of the Second Int. Conf. on Multiagent Systems, Kyoto, Japan, AAAI Press, 1996.

[4] [4] K. Takadama, S. Nakasuka, and T. Terano, “Multiagent Reinforcement Learning with Organizational-learning Oriented Classifier System,” IEEE Int. Conf. on Evolutionary Computation, pp. 63-68, 1998.

[5] [5] T. Yasuda and K. Ohkura, “Autonomous Role Assignment in a Homogeneous Multi-Robot System,” J. of Robotics and Mechatronics, Vol.17, No.5, pp. 596-604, 2005.

[6] [6] E. O. Wilson, “Sociobiology: The New Synthesis,” Cambridge, MA: Harvard, University Press, 2000.

[7] [7] S. N. Beshers and J. H. Fewell, “Models of division of labor in social insects. Annual Review of Entomology,” Vol.46, No.1, pp. 413-440, 2001.

[8] [8] E. Bonabeau, G. Theraulaz, and J. L. Deneubourg, “Fixed response thresholds and the regulation of division of labour in insect societies,” Bulletin of Mathematical Biology, Vol.60, pp. 753-807, 1998.

[9] [9] G. Theraulaz, J. Gervet, and S. Semenoff, “Social regulation of foraging activities in Polistes dominulus Christ: a systemic approach to behavioural organization,” Behaviour, Vol.116, pp. 292-320, 1991.

[10] [10] G. Theraulaz, E. Bonabeau, and J. L. Deneubourg, “Response threshold reinforcements and division of labour in insect societies,” Proc. of the Royal Society of London. Vol.B265, pp. 327-332. 1998.

[11] [11] Z.-Y. Huang, G. E. Robinson, S. S. Tobe, and K. J. Yagi, “Hormonal regulation of behavioural development in the honey bee is based on changes in the rate of juvenile hormone biosynthesis,” J. of Insect Physiology. Vol.37, pp. 733-41, 1991.

[12] [12] D. Naug and R. Gadagkar, “Flexible division of labor mediated by social interactions in an insect colony: a simulation model,” J. of Theoretical Biology, Vol.97, pp. 123-33, 1999.

[13] [13] Y. Ikemoto, T. Miura, and H. Asama, “Adaptive Division of Labor Control for Robot Group,” In The Int. Conf. on Intelligent Robots and Systems 2009(IROS2009), pp. 2409-2414, 2009.

[14] [14] S. Shahshahni, “A new mathematical framework. for the study of linkage and selection,” Memoirs of the American Mathematical Society, Vol.17, No.211, Jan. 1979.

[15] [15] K. Sigmund, “The Maximum Principle for Replicator Equations, Lotka-Volterra Approach to Dynamical Systems,”M. Peschel, edit., Berlin Akademie Verlag, pp. 63-71, 1985.

[16] [16] E. Akin, “The differential geometry of population genetics and evolutionary games,” In Lessard, S., editor, Kluwer, Dordrecht, Mathematical and Statistical Developments of Evolutionary Theory, pp. 1-93, 1990.

[17] [17] P. Schuster and K. Sigmund, “Replicator Dynamics,” J. of Theoretical Biology. Vol.100, pp. 533-538, 1983.

[18] [18] J. M. Smith, “Evolution and the Theory of Games,” Cambridge University Press, 1982.

[19] [19] R. Horie and E. Aiyoshi, “Variable metric gradient projection method and replicator equation,” Proc. of IEEE Int. Conf. on Systems, Man, and Cybernetics, Vol.3, pp. 515-520, 1999.

[20] [20] J. Hofbauer and K. Sigmund, “Evo. Games and Pop. Dynamics,” Cambridge University Press, 1998.

[21] [21] T. Mizuguchi and M. Sano, “Proportion Regulation of Biological Cells in Globally Coupled Nonlinear Systems,” Physical Review Letters, Vol.75, pp. 966-969, 1995.

[22] [22] S. Camazine, N. R. Franks, J. Sneyd, E. Bonabeau, and J. L. Deneubourg, “Self-Organization in Biological Systems,” Princeton Univ. Press, 2003.
ISBN 0691116245.

Adaptive Division-of-Labor Control Algorithm for Multi-Robot Systems

Yusuke Ikemoto*, Toru Miura**, and Hajime Asama***

Yusuke Ikemoto^, Toru Miura^, and Hajime Asama^