Clustering Methods for Agent Distribution Optimization

Multiagent systems consist of a collection of agents that directly interact usually via a form of message passing. Information about these interactions can be analyzed in an online or offline way to identify clusters of agents that are related. The first part of this paper is dedicated to a formal definition of a proposed dynamic model for agent clustering and experimental results that demonstrate applicability of this novel approach. The main contribution is the ability to discover and visualize communication neighborhoods of agents at runtime, which is a novel approach not attempted so far. The second part of this paper deals with a static agent clustering problem where equally sized clusters with maximal intracluster communication among agents are sought in order to efficiently distribute agents across multiple execution units. The weakness of standard clustering approaches for solving this type of clustering problem is shown. First, these algorithms optimize the generated clustering with respect to just one criterion, and therefore, yield solutions with inferior quality relative to the other criteria. Second, the algorithms are deterministic; thus they can produce just a single solution for the given data. A multiobjective clustering approach based on an iterative optimization evolutionary algorithm called multiobjective prototype optimization with evolved improvement steps (mPOEMS) is proposed and its advantages are demonstrated. The most important observation is that mPOEMS produces numerous high-quality solutions in a single run from which a user can choose the best one. The best solutions found by mPOEMS are significantly better than the solutions generated by the compared clustering algorithms.