Rectangular vs Triangular Routing with Evolved Agents
Patrick Ediger, Rolf Hoffmann and Dominique Deserable
Multiple target searching with evolved agents is performed in a cellular automata network to solve the routing problem in the square toroidal grid. The agents shall behave according to a control algorithm implemented as a finite state machine (FSM). Using a genetic procedure, control algorithms were evolved that could solve successfully all the training cases under consideration. For comparison, an intelligent walker (IW) was defined that chooses a free minimal path among all minimal paths. In order to avoid deadlocks, a certain amount of randomness was added to the FSM- and IW-agents. This paper is a companion paper on a previous work dealing with a similar agent-based protocol running in the triangular torus. It yields comparative performance results between rectangular and triangular routing, giving advantage to the latter.
Keywords: Cellular automata (CA); multi-agent system; genetic algorithm; rectangular and triangular routing; performances.