Routing in the Triangular Grid with Evolved Agents
Patrick Ediger, Rolf Hoffman and Dominique Deserable
Given a triangular grid of N cells (communication nodes) with toroidal connections. The goal was to solve the routing problem with N/2 agents, each of the agents having the task to a transport a message from a source to a target. This task is also known as multiple target searching. The agents shall behave according to a control algorithm implemented as finite state machine (FSM). Using a genetic procedure (island genetic algorithm) control algorithms were evolved that could solve successfully all the test cases under consideration. For comparison, intelligent random walkers were defined, which directly try to move to the target, or deviate from their way with a certain probability. It turned out that the evolved agents perform the task 22% faster than the intelligent random walkers.
Keywords: Cellular Automata; Multi-Agent System; Genetic Algorithm; 6-valent Torus; Routing.