Traitement des conflits dans les CSP distribués (une approche multi-agents avec facteurs d'influence)

Depuis quelques années, apparaissent des travaux sur les problèmes de satisfaction de contraintes distribués (CSP distribué) qui définissent un problème comme un quadruplet variables, domaines, contraintes et agents. Ces travaux sur les CSP distribués sont le fruit d une réflexion sur les CSP à proprement parler traités sous l angle des systèmes multi-agent (SMA). Chaque agent d un SMA gère au niveau local une partie distribuée du CSP correspondant au problème initial. L une des difficultés majeures des CSP distribués survient, lorsqu à partir des solutions locales aux agents, il faut constituer une solution globale. En effet, des conflits apparaissent et nécessitent, pour être résolus, de relâcher des contraintes. Dans notre approche, ces relâchements sont effectués localement aux agents. L idée originale proposée vise à prendre en compte les caractéristiques essentielles détectées lors de l inconsistance de ce CSP. Plus précisément, elle est basée sur la proposition de facteurs permettant de modéliser et d orienter efficacement les relâchements globaux et locaux de contraintes en cas d inconsistance (sur-contraint) dans un CSP distribué afin d obtenir si nécessaire, une solution alternative. Nous dénombrons trois facteurs influençant les mécanismes de contrôle du CSP : le facteur d influence de variables, le facteur d influence de contraintes et le facteur d influence sur l agent. Les facteurs précédents fournissent ainsi à chaque agent, des informations nécessaires pour la détection des inconsistances et la résolution distribuée du problème global. Enfin, nous détaillons les algorithmes et validons par une série de problèmes classiques munis de contraintes aléatoires notre approche.Since several years, an increasing interest appears in the research on the distributed constraint satisfaction problem (distributed CSP) in which a problem is defined as a quadruplet: variables, domains, constraints and agents. These works are the fruit of a reflection on the application of multi-agent technique to CSP solving. Every agent of a multi-agent system handles a distributed part of the CSP corresponding to the initial problem. One of the major difficulties of the distributed CSP is over-constrained problem. Indeed, to resolve the conflicts appeared, it is necessary to relax constraints. In our approach, these relaxations are made locally to the agents. The proposed approach aims at taking into account the essential characteristics detected in case of inconsistency (over-constrained). It is based on the proposal of factors allowing to model and to guide effectively the global and local constraints relaxations in case of inconsistency in a distributed CSP, in order to obtain, if necessary, an alternative solution. We specify three factors influencing the control mechanisms of the CSP: the influence factor of variables, the influence factor of constraints and the influence factor on the agent. These factors provide for each agent, necessary information for the detection of the inconsistency and the distributed resolution for the global problem. Finally, we detail the algorithms and validate our approach by a series of classic problems provided with random constraints.VALENCIENNES-BU Sciences Lettres (596062101) / SudocSudocFranceF