JACIII Vol.11 No.9 pp. 1099-1106
doi: 10.20965/jaciii.2007.p1099


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

February 28, 2007
June 14, 2007
November 20, 2007
cellular automata, pursuit problem, multiple mobile robots, cooperative behavior

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:
Yoshinobu Adachi and Masayoshi 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:
  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.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 05, 2021