Abstract
A multi-agent system is considered, comprised of a square 2D cell field of cells with uniform agents controlled by finite state machines (FSMs). Each cell contains a particle with one out of four colors, which can be changed by the agents. Initially the agents and colors are randomly distributed. The objective is to form a specific target pattern belonging to a predefined pattern class. The target patterns (path patterns) shall consist of preferably long narrow paths with the same color. The quality of the path patterns is measured by a degree of order, which is computed by counting matching 3 x 3 patterns (templates). The used agents can perform 32 actions, combinations of moving, turning and coloring. They react on the own color, the color in front, and blocking situations. The agents’ behavior is determined by an embedded FSM with 6 states. For a given 8 x 8 field, near optimal FSMs were evolved by a genetic procedure separately for k = 1 .. 48 agents. The evolved agents are capable to form path patterns with a high degree of order. Agents, evolved for a 8 x 8 field, are able to structure a 16 x 16 field successfully, too. The whole multi-agent system was modeled by cellular automata. In the implementation of the system, the CA-w model (cellular automata with write access) was used in order to reduce the implementation effort and speed up the simulation.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Shi, D., He, P., Lian, J., Chaud, X., et al.: Magnetic alignment of carbon nanofibers in polymer composites and anisotropy of mechanical properties. Journal of Applied Physics 97, 064312 (2005)
Itoh, M., Takahira, M., Yatagai, T.: Spatial Arrangement of Small Particles by Imaging Laser Trapping System. Optical Review 5(I), 55–58 (1998)
Jiang, Y., Narushima, T., Okamoto, H.: Nonlinear optical effects in trapping nanoparticles with femtosecond pulses. Nature Physics 6, 1005–1009 (2010)
Halbach, M., Hoffmann, R., Both, L.: Optimal 6-state algorithms for the behavior of several moving creatures. In: El Yacoubi, S., Chopard, B., Bandini, S. (eds.) ACRI 2006. LNCS, vol. 4173, pp. 571–581. Springer, Heidelberg (2006)
Hoffmann, R., Désérable, D.: CA Agents for All-to-All Communication Are Faster in the Triangulate Grid. In: Malyshkin, V. (ed.) PaCT 2013. LNCS, vol. 7979, pp. 316–329. Springer, Heidelberg (2013)
Komann, M., Ediger, P., Fey, D., Hoffmann, R.: On the Effectiveness of Evolution Compared to Time-Consuming Full Search of Optimal 6-State Automata. In: Vanneschi, L., Gustafson, S., Moraglio, A., De Falco, I., Ebner, M. (eds.) EuroGP 2009. LNCS, vol. 5481, pp. 280–291. Springer, Heidelberg (2009)
Ediger, P., Hoffmann, R.: CA Models for Target Searching Agents. Automata 2009, J. Electronic Notes in Theor. Comp. Science (ENTCS) 252, 41–54 (2009)
Komann, M., Mainka, A., Fey, D.: Comparison of evolving uniform, non-uniform cellular automaton, and genetic programming for centroid detection with hardware agents. In: Malyshkin, V. (ed.) PaCT 2007. LNCS, vol. 4671, pp. 432–441. Springer, Heidelberg (2007)
Mesot, B., Sanchez, E., Peña, C.-A., Perez-Uribe, A.: SOS++: Finding Smart Behaviors Using Learning and Evolution. In: Artificial Life VIII, pp. 264–273. MIT Press, Cambridge (2002)
Blum, M., Sakoda, W.: On the capability of finite automata in 2 and 3 dimensional space. In: 18th IEEE Symp. on Foundations of Computer Science, pp. 147–161 (1977)
Hoffmann, R.: Rotor-routing algorithms described by CA–w. Acta Phys. Polonica B Proc. Suppl. 5(1), 53–68 (2012)
Hoffmann, R.: The GCA-w massively parallel model. In: Malyshkin, V. (ed.) PaCT 2009. LNCS, vol. 5698, pp. 194–206. Springer, Heidelberg (2009)
Hoffmann, R.: GCA–w algorithms for traffic simulation. Acta Phys. Polonica B Proc. Suppl. 4(2), 183–200 (2011)
Deutsch, A., Dormann, S.: Cellular Automaton Modeling of Biological Pattern Formation. Birkäuser (2005)
Bonabeau, E.: From Classical Models of Morphogenesis to Agent-Based Models of Pattern Formation. Santa Fe Institute Working Paper: 1997-07-063
Hamann, H.: Pattern Formation as a Transient Phenomenon in the Nonlinear Dynamics of a Multi-Agent System. In: Proc. of MATHMOD 2009 (2009)
Nagpal, R.: Programmable Pattern-Formation and Scale-Independence. MIT Artificial Intelligence Lab (2002)
Spicher, A., Fatèz, N., Simonin, O.: From Reactive Multi-Agents Models to Cellular Automata - Illustration on a Diffusion-Limited Aggregation Model. In: ICAART 2009, pp. 422–429 (2009)
Bandini, S., Vanneschi, L., Wuensche, A., Shehata, A.B.: A Neuro-Genetic Framework for Pattern Recognition in Complex Systems. Fundam. Inform. 87(2), 207–226 (2008)
Junges, R., Klügl, F.: Programming Agent Behavior by Learning in Simulation Models. Applied Artificial Intelligence 26(4), 349–375 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Hoffmann, R. (2014). How Agents Can Form a Specific Pattern. In: Wąs, J., Sirakoulis, G.C., Bandini, S. (eds) Cellular Automata. ACRI 2014. Lecture Notes in Computer Science, vol 8751. Springer, Cham. https://doi.org/10.1007/978-3-319-11520-7_70
Download citation
DOI: https://doi.org/10.1007/978-3-319-11520-7_70
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11519-1
Online ISBN: 978-3-319-11520-7
eBook Packages: Computer ScienceComputer Science (R0)