Abstract
Considered is a 2D cellular automaton with moving agents. Each cell contains a particle with a certain spin/color that can be turned by an agent. Four colors are used. The objective is to align the spins in parallel along horizontal and vertical lines, in order to form long orthogonal “line patterns”. The quality of a line pattern is measured by a degree of order computed by counting matching 3 x 3 patterns. Additional markers are used and signals between agents are introduced in order to improve the task efficiency. The agents’ behavior is controlled by a finite state machine (FSM). An agent can perform 128 actions altogether as combinations of moving, turning, color changing, marker setting and signaling. It reacts on its own state and on the sensed colors, markers and signals. For a given set of n x n fields, near optimal FSM were evolved by a genetic algorithm. The evolved agents are capable of forming line patterns with a limited degree of order. The scalability of two FSM against a varying number of agents is studied as well as the efficiency gain through the newly introduced signals.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Deutsch, A., Dormann, S.: Cellular Automaton Modeling of Biological Pattern Formation. Birkäuser, Basel (2005)
Shi, D., He, P., Lian, J., Chaud, X., Bud’ko, S.L., Beaugnon, E., Wang, L.M., Ewing, R.C., Tournier, R.: Magnetic alignment of carbon nanofibers in polymer composites and anisotropy of mechanical properties. J. App. Phys. 97, 064312 (2005)
Itoh, M., Takahira, M., Yatagai, T.: Spatial arrangement of small particles by imaging laser trapping system. Opt. Rev. 5(1), 55–58 (1998)
Jiang, Y., Narushima, T., Okamoto, H.: Nonlinear optical effects in trapping nanoparticles with femtosecond pulses. Nat. Phys. 6, 1005–1009 (2010)
Roberts, Jr., G.: X-ray laser explores how to write data with light. National Accelerator Laboratory, 19 March 2013. https://www6.slac.stanford.edu/news
Press, D., Ladd, T.D., Zhang, B., Yamamoto, Y.: Complete quantum control of a single quantum dot spin using ultrafast optical pulses. Nature 456, 218–221 (2008)
Hoffmann, R.: How agents can form a specific pattern. In: Wçs, J., Sirakoulis, G., Bandini, S. (eds.) ACRI 2014. LNCS, vol. 8751, pp. 660–669. Springer, Heidelberg (2014)
Hoffmann, R.: Cellular automata agents form path patterns effectively. Acta Phys. Pol. B Proc. Suppl. 9(1), 63–75 (2016)
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)
Ediger, P., Hoffmann, R.: Optimizing the creature’s rule for all-to-all communication. In: Adamatzky, A., Alonso-Sanz, R., Lawniczak, A., (eds.) Automata-2008: Theory and Applications of Cellular Automata, pp. 398–412 (2008)
Ediger, P., Hoffmann, R.: Solving all-to-all communication with CA agents more effectively with flags. In: Malyshkin, V. (ed.) PaCT 2009. LNCS, vol. 5698, pp. 182–193. Springer, Heidelberg (2009)
Hoffmann, R., Désérable, D.: All-to-all communication with cellular automata agents in 2D grids. J. Supercomp. 69(1), 70–80 (2014)
Ediger, P., Hoffmann, R.: CA models for target searching agents. Elec. Notes Theor. Comp. Sci. 252, 41–54 (2009)
Ediger, P., Hoffmann, R., Désérable, D.: Routing in the triangular grid with evolved agents. J. Cell. Automata 7(1), 47–65 (2012)
Ediger, P., Hoffmann, R., Désérable, D.: Rectangular vs triangular routing with evolved agents. J. Cell. Automata 8(1–2), 73–89 (2013)
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.: Artificial Life VIII. SOS++: Finding Smart Behaviors Using Learning and Evolution. MIT Press, Cambridge (2002)
Blum, M., Sakoda, W.J.: On the capability of finite automata in 2 and 3 dimensional space. In: SFCS 1977, pp. 147–161 (1977)
Bonabeau, E.: From classical models of morphogenesis to agent-based models of pattern formation. Artif. Life 3(3), 191–211 (1997)
Hamann, H.: Pattern Formation as a Transient Phenomenon in the Nonlinear Dynamics of a Multi-agent System. MATHMOD, Vienna (2009)
Nagpal, R.: Programmable pattern-formation and scale-independence. In: Minai, A.A., Bar-Yam, Y. (eds.) Unifying Themes in Complex Systems IV: Proceedings of the Fourth International Conference on Complex Systems, pp. 275–282. Springer Berlin Heidelberg, Berlin, Heidelberg (2008). http://dx.doi.org/10.1007/978-3-540-73849-7_31
Yamins, D., Nagpal, R.: Automated global-to-local programming in 1-D spatial multi-agent systems. In: Proceedings of 7th International Conference AAMAS, pp. 615–622 (2008)
Bandini, S., Vanneschi, L., Wuensche, A., Shehata, A.B.: A neuro-genetic framework for pattern recognition in complex systems. Fund. Inf. 87(2), 207–226 (2008)
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.: Rotor-routing algorithms described by CA-w. Acta Phys. Pol. B Proc. Suppl. 5(1), 53–67 (2012)
Hoffmann, R., Désérable, D.: Routing by cellular automata agents in the triangular lattice. In: Sirakoulis, G., Adamatzky, A. (eds.) Robots and Lattice Automata, Emergence, Complexity and Computation, vol. 13, pp. 117–147. Springer, Switzerland (2015)
Hardy, J., Pomeau, Y., de Pazzis, O.: Time evolution of a two-dimensional classical lattice system. Phys. Rev. Lett. 31(5), 276–279 (1973)
Achasova, S., Bandman, O., Markova, V., Piskunov, S.: Parallel Substitution Algorithm - Theory and Application. World Scientific, Singapore (1994)
Bouré, O., Fatès, N., Chevrier, V.: Probing robustness of cellular automata through variations of asynchronous updating. Nat. Comp. 11(4), 553–564 (2012)
Bandini, S., Bonomi, A., Vizzari, G.: An analysis of different types and effects of asynchronicity in cellular automata update schemes. Nat. Comput. 11(2), 277–287 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Hoffmann, R., Désérable, D. (2016). Line Patterns Formed by Cellular Automata Agents. In: El Yacoubi, S., Wąs, J., Bandini, S. (eds) Cellular Automata. ACRI 2016. Lecture Notes in Computer Science(), vol 9863. Springer, Cham. https://doi.org/10.1007/978-3-319-44365-2_42
Download citation
DOI: https://doi.org/10.1007/978-3-319-44365-2_42
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44364-5
Online ISBN: 978-3-319-44365-2
eBook Packages: Computer ScienceComputer Science (R0)