CA Models for Target Searching Agents

Agents in a cellular grid have the task to move from their start positions to their individual target positions as fast as possible. Four models using agents are proposed that can be applied to the problem. These models are conform to the CA paradigm. The agents have either a moving direction (directed agent) or not (undirected agent). The agents behave either in a deterministic way according to a control automaton inside of each agent or they behave randomly. In order to find the best behaving agents, control automata (“algorithms”) were evolved using a genetic island model. Near optimal algorithms were evolved separately for k=1 to k=256 agents in a 32×32 environment using 20 random initial configurations for each k. Then these algorithms were ranked using another set of 100 initial configurations for each k. It turned out that the agents behave better with respect to speed and reliability in this order: (1) controlled directed agents, (2) random directed agents, (3) random undirected agents, and (4) controlled undirected agents. Although the controlled directed agents (optimized for each k) can solve all the given 100 initial configurations in the ranking set, it can not be assured that no deadlocks may occur for other initial configurations.