Micro and macro lemmings simulations based on ants colonies

Abstract

Ant Colony Optimization (ACO) has been successfully applied to a wide number of complex and real domains. From classical optimization problems to video games, these kind of swarm-based approaches have been adapted, to be later used, to search for new meta-heuristic based solutions. This paper presents a simple ACO algorithm that uses a specifically designed heuristic, called common-sense, which has been applied in the classical video game Lemmings. In this game a set of lemmings must reach the exit point of each level, using a subset of finite number of skills, taking into account the contextual information given from the level. The paper describes both the graph model and the context-based heuristic, designed to implement our ACO approach. Afterwards, two different kind of simulations have been carried out to analyse the behaviour of the ACO algorithm. On the one hand, a micro simulation, where each ant is used to model a lemming, and a macro simulation where a swarm of lemmings is represented using only one ant. Using both kind of simulations, a complete experimental comparison based on the number and quality of solutions found and the levels solved, is carried out to study the behaviour of the algorithm under different game configurations.

Publication
European Conference on the Applications of Evolutionary Computation
Antonio Gonzalez-Pardo
Antonio Gonzalez-Pardo
PhD Computer Science

Lecturer at the Computer Science Department. Main research interests are related to Computational Intelligence and Metaheuristics applied to Social Networks Analysis, and the optimization of graph-based problems.