Research on the Sheepdog Problem Using  Cellular Automata

Yoshinobu Adachi; Masayoshi Kakikura

doi:10.20965/jaciii.2007.p1099

single-jc.php

« previous

JACIII Vol.11 No.9 pp. 1099-1106

doi: 10.20965/jaciii.2007.p1099

(2007)

Paper:

Views over last 60 days: 616

Research on the Sheepdog Problem Using Cellular Automata

Yoshinobu Adachi and Masayoshi Kakikura

Tokyo Denki University, 2-2 Nishiki-cho, Kanda, Chiyoda-ku, Tokyo 101-8457, Japan

Received:

February 28, 2007

Accepted:

June 14, 2007

Published:

November 20, 2007

Keywords:

cellular automata, pursuit problem, multiple mobile robots, cooperative behavior

Abstract

The simulation framework we propose for complex path planning problems with multiagent systems focuses on the sheepdog problem for handling distributed autonomous robot systems – an extension of the pursuit problem for handling one prey robot and multiple predator robot. The sheepdog problem involves a more complex issue in which multiple dog robot chase and herd multiple sheep robot. We use the Boids model and cellular automata to model sheep flocking and chase and herd behavior for dog robots. We conduct experiments using a Sheepdog problem simulator and study cooperative behavior.

Cite this article as:

Y. Adachi and M. Kakikura, “Research on the Sheepdog Problem Using Cellular Automata,” J. Adv. Comput. Intell. Intell. Inform., Vol.11 No.9, pp. 1099-1106, 2007.

Data files:

References

[1] C. W. Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics,” SIGGRAPH 1987 Conf. Proc., 21(4), pp. 25-34.
[2] W. J. Crowther, “Rule-based guidance for flight vehicle flocking,” submitted to the Journal of Guidance, Dynamics and Control, Sep., 2002.
[3] U. Frisch, D. d’Humieres, B. Hasslacher, P. Lallemand, Y. Pomeau, and P. Rivet, “Lattice Gas Hydrodynamics in Two and Three Dimensions,” Complex Systems, 1, pp. 649-707, 1987.
[4] G. W. Baxter and R. P. Behringer, “Cellular automata models of granular flow,” Physical Review A, Vol.42, No.2, pp. 1017-1020, 1990.
[5] M. S. Alber, M. A. Kiskowski, J. A. Glazier, and Y. Jiang, “On Cellular Automaton Approaches to Modeling Biological Cells,” Mathematical Systems Theory in Biology, Communication, IMA 134, Springer-Verlag, New York, pp. 1-40, 2002.
[6] H. M. Botee and E. Bonabeau, “Evolving And Colony Optimization,” Adv. Complex Systems, 1, pp. 149-159, 1998.
[7] H. Kawamura, M. Yamamoto, K. Suzuki, and A. Ohuchi, “Multiple Ant Colonies Algorithm Based on Colony Level Interactions,” IEICE Trans, Fundamentals, Vol.E83-A, No.2, pp. 371-379, Feb., 2000.
[8] T. Suzudo, “Spatial Pattern Formation in Asynchronous Cellular Automata with Mass Conservation,” Physica A, Vol.343 C, pp. 185-200, 2004.
[9] K. Takahashi and M. Kakikura, “Research on cooperative capture by multiple mobile robots –a proposition of cooperative capture strategies in the pursuit problem–,” Distributed Autonomous Robotic Systems, Vol.5, pp. 393-402, 2002.
[10] H. Yamaguchi, “A Cooperative Hunting Behavior by Mobile Robot Troops,” IEEE Int. Conf. Robotics and Automation, p. 3204, 1998.
[11] N. Shimoyama, K. Sugawara, T. Mizuguchi, Y. Hayakawa, and M. Sano, “Collective Motion In a System of Motile Element,” Physical Review Letters, Vol.76, No.20, pp. 3870-3873, 1996.
[12] G. Lee, Y. Komatsu, S. Sone, and N. Y. Chong, “Formation navigation of a team of mobile robots adapting to an environment,” Int. Symposium on Robotics, Int. Federation of Robotics, 2005.

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

[1] [1] C. W. Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics,” SIGGRAPH 1987 Conf. Proc., 21(4), pp. 25-34.

[2] [2] W. J. Crowther, “Rule-based guidance for flight vehicle flocking,” submitted to the Journal of Guidance, Dynamics and Control, Sep., 2002.

[3] [3] U. Frisch, D. d’Humieres, B. Hasslacher, P. Lallemand, Y. Pomeau, and P. Rivet, “Lattice Gas Hydrodynamics in Two and Three Dimensions,” Complex Systems, 1, pp. 649-707, 1987.

[4] [4] G. W. Baxter and R. P. Behringer, “Cellular automata models of granular flow,” Physical Review A, Vol.42, No.2, pp. 1017-1020, 1990.

[5] [5] M. S. Alber, M. A. Kiskowski, J. A. Glazier, and Y. Jiang, “On Cellular Automaton Approaches to Modeling Biological Cells,” Mathematical Systems Theory in Biology, Communication, IMA 134, Springer-Verlag, New York, pp. 1-40, 2002.

[6] [6] H. M. Botee and E. Bonabeau, “Evolving And Colony Optimization,” Adv. Complex Systems, 1, pp. 149-159, 1998.

[7] [7] H. Kawamura, M. Yamamoto, K. Suzuki, and A. Ohuchi, “Multiple Ant Colonies Algorithm Based on Colony Level Interactions,” IEICE Trans, Fundamentals, Vol.E83-A, No.2, pp. 371-379, Feb., 2000.

[8] [8] T. Suzudo, “Spatial Pattern Formation in Asynchronous Cellular Automata with Mass Conservation,” Physica A, Vol.343 C, pp. 185-200, 2004.

[9] [9] K. Takahashi and M. Kakikura, “Research on cooperative capture by multiple mobile robots –a proposition of cooperative capture strategies in the pursuit problem–,” Distributed Autonomous Robotic Systems, Vol.5, pp. 393-402, 2002.

[10] [10] H. Yamaguchi, “A Cooperative Hunting Behavior by Mobile Robot Troops,” IEEE Int. Conf. Robotics and Automation, p. 3204, 1998.

[11] [11] N. Shimoyama, K. Sugawara, T. Mizuguchi, Y. Hayakawa, and M. Sano, “Collective Motion In a System of Motile Element,” Physical Review Letters, Vol.76, No.20, pp. 3870-3873, 1996.

[12] [12] G. Lee, Y. Komatsu, S. Sone, and N. Y. Chong, “Formation navigation of a team of mobile robots adapting to an environment,” Int. Symposium on Robotics, Int. Federation of Robotics, 2005.