Top

Published in:

2018 | OriginalPaper | Chapter

Termination and Stability Levels in Evolved CA Agents for the Black–Pattern Task

Authors : Rolf Hoffmann, Dominique Désérable, Franciszek Seredyński

Published in: Cellular Automata

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Given a 2d Cellular Automaton (CA) with mobile agents controlled by a finite state automaton (algorithm). Initially the field is colored white and agents are randomly placed. They have the task to color the whole field into black in shortest time. The objective is to find algorithms that (1) can form the black–pattern, (2) keep it stable and then (3) change into a global state where all agents stop their activity. Four levels of stability are distinguished, depending on the grade of inactivity after having formed the pattern. For systems with up to four agents we found such algorithms by applying genetic algorithms (GA) and manual post fine tuning. Performances and simulations of these algorithms are presented.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Towards Self-organizing Sensor Networks: Game-Theoretic -Learning Automata-Based Approach

next chapter Size Effect in Cellular Automata Based Disease Spreading Model

The GA method was very time consuming (millions of multi-agent simulations) and took around 4 weeks of computation time on a state–of–the–art quad-core PC 3.5 GHz.

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). https://doi.org/10.1007/11861201_66CrossRef

Tummolini, L., Castelfranchi, C.: Trace signals: the meanings of stigmergy. In: Weyns, D., Parunak, H.V.D., Michel, F. (eds.) E4MAS 2006. LNCS (LNAI), vol. 4389, pp. 141–156. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71103-2_8CrossRef

Weyns, D., Van Dyke Parunak, H., Michel, F., Holvoet, T., Ferber, J.: Environments for multiagent systems State-of-the-art and research challenges. In: Weyns, D., Van Dyke Parunak, H., Michel, F. (eds.) E4MAS 2004. LNCS (LNAI), vol. 3374, pp. 1–47. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-32259-7_1CrossRef

Matocha, J., Camp, T.: A taxonomy of distributed termination detection algorithms. J. Syst. Softw. 43(3), 207–221 (1998)CrossRef

Wellman, M.P., Walsh, E.W.: Distributed quiescence detection in multiagent negotiation. In: Fourth International Conference on Multi-Agent Systems, ICMAS, pp. 317–324 (2000)

Lahlouhi, A.: MAS-td: an approach to termination detection of multi-agent systems. In: Gelbukh, A., Espinoza, F.C., Galicia-Haro, S.N. (eds.) MICAI 2014. LNCS (LNAI), vol. 8856, pp. 472–482. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13647-9_42CrossRef

Hoffmann, R., Désérable, D.: Generating maximal domino patterns by cellular automata agents. In: Malyshkin, V. (ed.) PaCT 2017. LNCS, vol. 10421, pp. 18–31. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62932-2_2CrossRef

Hoffmann, R.: How agents can form a specific pattern. In: Wąs, J., Sirakoulis, G.C., Bandini, S. (eds.) ACRI 2014. LNCS, vol. 8751, pp. 660–669. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11520-7_70CrossRef

Title: Termination and Stability Levels in Evolved CA Agents for the Black–Pattern Task
Authors: Rolf Hoffmann
Dominique Désérable
Franciszek Seredyński
Publisher: Springer International Publishing
Book: Cellular Automata
Print ISBN: 978-3-319-99812-1

Electronic ISBN: 978-3-319-99813-8

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-99813-8_12

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner