Agent Coordination Mechanisms for Solving a Partitioning Task

Multi Agent Systems and Swarm Intelligence are two recent and very promising topics in current computer science research. Swarm intelligence deals with large sets of individuals or agents that are regarded as a self-organizing system showing emergent behaviour. Ideas from biology are often and successfully applied to (optimization) problems in the computer science area. Nature provides several examples of complex architectures that are created by very simple insects with highly limited abilities. These insects live in social colonies and coordinate their actions by a concept called stigmergy. A frequently occurring question when designing multi agent or swarm systems that are (partly) inspired by natural examples is how to coordinate a large group of individuals or instances. This matter is closely connected with the question about the essential characteristics and parameters for both the whole system and each single agent. This thesis deals with these fundamental questions of multi agent and swarm intelligence systems. It presents several approaches for the different problems that might arise during system design. As background for all these approaches, a complex optimization problem has been chosen. The Online Partitioning Problem (OPP) addresses the uniform distribution of a group of agents onto targets under several restrictions, i.e. distance minimization and feature restriction. It is intriguing because it is easy to state but often very difficult to solve. Using such a reference problem allows us to compare the single approaches with each other. Though the presented new approaches deal only with this OPP, most of them can easily be adapted to other problems or are general concepts.