Combining genetic algorithm and swarm intelligence for task allocation in a real time strategy game

Anderson R. Tavares, Gianlucca Lodron Zuin, Héctor Azpúrua, Luiz Chaimowicz

Abstract


Real time strategy games are complex scenarios where multiple agents must be coordinated in a dynamic, partially observable environment. In this work, we model coordination as a task allocation problem, in which specific tasks must be properly assigned to agents. We employ a task allocation algorithm based on swarm intelligence and adjust its parameters using a genetic algorithm. A fitness estimation method is employed to accelerate execution of the genetic algorithm. To evaluate this approach, we implement this coordination mechanism in the AI of a popular video game: StarCraft: BroodWar. Experiment results show that the genetic algorithm successfully adjusts task allocation parameters. Besides, we assess the trade-off between solution quality and execution time of the genetic algorithm with fitness estimation.

Keywords


Task allocation; Evolutionary algorithms; Real-time strategy.

Full Text:

PDF