Domino pattern formation by cellular automata agents

摘要

Considered is a 2d cellular automaton with moving agents in a multi-agent system. The objective is to find agents controlled by a finite-state program (FSP) that can form domino patterns. The quality of a formed pattern is measured by the degree of order computed by counting matching 3 x 3 templates. An agent reacts on its own color, the color in front and whether it is blocked or not. It can change the color, move or not and turn into any direction. Four FSPs were evolved with k agents (1 <= k <= 4) initially placed in the corners of the field. For a 12x12 training field, the aimed pattern could be formed with a 100% degree of order. The performance was also high with other field sizes. Livelocks are avoided by using three different variants of the evolved FSP. The degree of order usually fluctuates after reaching a certain threshold, but it can also be stable, and the agents may show the termination by running in a cycle or by stopping their activity.