Hierarchical Organization of Agents Based on Galois Sub-Hierarchy for Complex Tasks Allocation in Massive MAS

摘要

A major challenge in the field of Multi-Agent Systems is to enable autonomous agents to allocate tasks efficiently. In previous work, we have developed a decentralized and scalable method for complex tasks allocation for Massive Multi-Agent System (MMAS) based on two steps: 1) hierarchical organization of agent groups using Formal Concepts Analysis approach (FCA), 2) computing the optimal allocation. The first step is computed by one agent named global allocator that computes Galois lattice representing the hierarchical structure of agent groups. Then, it simplifies the completed lattices by pruning unnecessary groups. The second step distributes the tasks allocation process among all agent groups. Nevertheless, the hierarchical organization process is still centralized. Moreover, generation of Galois lattice composed by all concepts (2~(min(|O|,|A|)) concepts in the worst cases. Where 0 and A means, respectively, the set of objects and the set of attributs) and then simplification of the hierarchy of such size are not useful. This paper extends our last approach to distribute the organization process of agent groups among all agents by providing extension to the Pulton algorithm that generates Galois Sub-Hierarchy which is a polynomial size representation of a concept lattice. This decentralized self-organization of agents provides a flexible infrastructure for agents' dynamicity in MMAS.