MANA : A New Multi-agent Approach for Complex Assignment Problems

In this paper, Reactive Multi-Agent Systems handle complex assignment problems as decentralized negotiating problems. Each agent locally acts in order to make the system reach a satisfying configuration. We address here, the designing problem: how to accurately communicate the problem to agents, and increase their ability to coordinate? We identify two main aspects to consider: (1) how to express acquaintances between the agents in order to provide a support for a reactive resolution, (2) how to express the objects of the sharing, in (most often) a continuous environment. In this context, the paper explains and justifies the advantages to use a structured environment for each of the studied aspects, as a means to account for application problems and covered configurations. The introduction for such a support leads to a new issue: how to make this support evolve in order to fit combinatorial properties? We introduce a new approach MANA (Multi-level Balancing Negotiating Agents) that uses a self-organizing way to manage the resulting original configuration. We illustrate this approach on a scheduling problem, and present some preliminary results showing its performances.