Endogenous control of multi-agent systems for solving complex problems.

Summary This work addresses the problem of endogenous control in Multi-Agent Systems (MAS) for solving complex problems, which we explore through the critical resource sharing problem. The so-called complex problems that we address are characterized by a combinatorial explosion of the number of solutions with the size of the problems, a strong dynamic of the problem data induced by an open environment in which many events can take place, a high systemic complexity resulting from the interdependencies between the numerous variables of the problem and finally a decentralization of the solving process imposed by a physical and functional distribution of the variables that is incompatible with a centralized vision of the problem. A complete survey of the search spaces associated with such problems is unrealistic in an acceptable time, it is then necessary to employ so-called incomplete resolution methods. Whatever the incomplete approach considered, the incomplete path of the search space requires control in order to maximize the probability of converging to a satisfactory solution. We identify three levels of control of the search space independently of the approach used: a static control (a priori definition of the system behavior), a dynamic control (evolving during the solution according to predefined mechanisms) and an adaptive control (evolving dynamically during the solution). We show that an endogenous control of the system's activity, i.e. an adaptive control stemming from the agents' own activity, is necessary to guide the path of the search space in the context of complex problem solving. These works have been realized in a context of industrial collaboration and are based on an approach developed in previous works: CESNA (Complex Exchanges between Stigmergic Negotiating Agents). CESNA is a self-organizing multi-agent approach exploiting agents located in an environment materializing the problem and exploited by a resolution process based on a stigmergic negotiation between the agents. The application case used by the CESNA approach to illustrate this work is the critical resource sharing problem, characterized by a limited set of resources exploited by a large number of consumers. Our contributions are of two types: first, we have proposed evolutions of the representation of the problem used by the initial approach (CESNA) in order to remove the limitations preventing a scaling up, and second, we have defined a new model (MANA: Multi-level bAlancing Negotiating Agents) using this new representation with a new resolution process based on endogenous mechanisms of control of the system activity. These mechanisms rely on the materialization of the microscopic effects of the macroscopic phenomenon to be guided (the path of the search space) in order to make it locally perceptible by the agents. Our measurements show that this new model allows the passage to scale (the resolution of large industrial problems) and a significant improvement of the resolution performances compared to the initial approach, thus showing the effectiveness of the guidance allowed by the mechanisms used.