Algorithmes pour la prise de decision distribuee en contexte hierarchique

mon grand amour, mes trésors Je tiens d'abord à remercier mes directeur et codirecteur de thèse, messieurs Pesant et Frayret.Monsieur Pesant a accepté avec enthousiasme de diriger cette thèse; j'ai bénéficié et appris énormément de cette collaboration.Quant à monsieur Frayret, je n'arrive pas à me rappeler l'avoir réellement choisi comme codirecteur : à l'époque, je lui ai présenté mon projet et la relation s'est développée naturellement, progressivement.Ses encouragements sans cesse renouvelés ont constitué un instrument des plus précieux.Merci également à madame Sophie D'Amours qui m'a accueilli au Consortium de recherche FORAC, il y a sept ans déjà.Elle dispose d'une faculté unique : celle de permettre aux gens de s'épanouir et de réaliser leurs rêves, en acceptant d'aller au-delà des conventions, hors des sentiers battus.Tout ceci aurait été impossible sans elle.Je lui en suis très reconnaissant.Également, je ne pourrais passer sous silence la contribution de monsieur Alain Rousseau.Il fut mon mentor -mon maître -à mon arrivée au consortium.Merci aussi à Constance Van Horne -présidente de mon « fan club » -qui m'a tant encouragé à entreprendre un doctorat.Merci également à Claude-Guy Quimper pour ses conseils judicieux tout au long de ce projet.Ton amitié m'est précieuse.Et surtout, merci aux membres de ma famille pour leur soutien indéfectible, plus particulièrement à Nathalie, Éric, et ma mère.Par le jeu des vases communicants, Nathalie s'est investie énormément pour que je puisse réaliser ce travail; je lui dois beaucoup.En terminant, merci à mon fils Jérémie, qui du haut de ses quatre ans, m'a prodigué le conseil suivant : « Papa, quand ça ne va pas, il faut garder son calme, ne pas se décourager et continuer.Comme Maurice Richard ». v Résumé Cette thèse a pour objet la coordination entre entités autonomes.De manière plus précise, nous nous intéressons à la coordination dans un contexte hiérarchique.Les problèmes étudiés montrent les caractéristiques suivantes : (1) il s'agit de problèmes d'optimisation distribués, (2) le problème est naturellement décomposé en sousproblèmes, (3) il existe a priori une séquence selon laquelle les sous-problèmes doivent être résolus, (4) les sous-problèmes sont sous la responsabilité de différentes entités et (5) chaque sous-problème est défini en fonction des solutions retenues pour les sousproblèmes précédents.Parmi les principaux domaines d'application, on trouve les systèmes d'aide à la décision organisationnels et les problèmes de synchronisation dans les chaînes logistiques industrielles.Ce dernier domaine sert de fil conducteur dans cette thèse : le travail de plusieurs unités de production est nécessaire pour fabriquer et livrer les commandes des clients.Différentes alternatives sont possibles en ce qui a trait aux pièces à utiliser, au choix des processus de fabrication, à l'ordonnancement des opérations et au transport.Chaque partenaire désire établir son plan de production (quoi faire, où et quand le faire), mais il est nécessaire pour eux de coordonner leurs activités.Les méthodes utilisées en pratique industrielle peuvent être qualifiées d'heuristiques de coordination.À l'opposé, il existe des algorithmes d'optimisation distribués et exacts, notamment les techniques de raisonnement sur contraintes distribuées (Distributed Constraint Optimization Problems, ou DCOP).Cependant, ces derniers algorithmes s'accommodent mal de la nature hiérarchique des problèmes étudiés et pourraient difficilement être utilisés en pratique.Les forces et les faiblesses des méthodes heuristiques et exactes nous ont donc amené à proposer de nouvelles approches.vi Nous proposons d'abord un formalisme appelé HDCOP (pour Hierarchical DCOP).Il permet de représenter formellement le problème, l'attribution des responsabilités entre les agents, la séquence de résolution et l'espace des solutions accessibles aux agents.L'espace de solutions est représenté par un arbre, ce qui permet aux agents d'utiliser un algorithme de recherche distribué de base en tant que mécanisme de coordination (e.g.SyncBB).Cet espace de coordination montre certaines caractéristiques particulières.Il s'agit d'un arbre non-binaire de profondeur fixe ayant un facteur de branchement très grand et variable d'un nœud à l'autre.Également, l'arbre est généré dynamiquement pendant la résolution.Dans ce contexte, même pour de très grands temps de calcul, un algorithme réalisant une recherche en profondeur (tel SyncBB) visite uniquement des solutions très semblables les unes des autres (puisque contenues dans la même zone de l'arbre).Pour remédier à ce problème, nous avons adapté au contexte multi-agent des stratégies de recherche réputées efficaces en environnement centralisé, à savoir les méthodes basées sur l'analyse des déviations (e.g.LDS).Ces méthodes sont très utilisées en programmation par contraintes classique.Nous proposons deux adaptations distribuées.Le premier algorithme (SyncLDS) est très simple d'implémentation mais permet le travail d'un seul agent à la fois.Le second (MacDS) permet aux agents de travailler simultanément.De plus, il montre certaines propriétés intéressantes pour un algorithme distribué : tolérance aux pannes de communication et à l'inversion de l'ordre des messages.Les deux méthodes permettent aux agents de découvrir de bien meilleures solutions qu'avec les méthodes de base.Cependant, MacDS réduit davantage le temps de calcul nécessaire pour l'atteinte d'une solution de qualité donnée.vii Finalement, nous avons proposé une stratégie de recherche adaptative appelée ADS.Les agents utilisent une forme d'apprentissage pour établir dynamiquement et collectivement quelles zones de l'arbre devraient être explorées en priorité.La méthode prend appui sur le fait que les arbres sont non-binaires; un modèle permet d'anticiper l'impact associé à la réalisation d'un retour-arrière vers un nœud donné, en se basant sur la qualité des solutions obtenues auparavant.L'efficacité du processus de coordination s'en voit grandement améliorée.Toutes ces méthodes ont été évaluées pour un cas réel de coordination dans une chaîne logistique de l'industrie forestière.Nous les avons également évaluées pour un large éventail de problèmes synthétiques, de manière à illustrer différentes propriétés des algorithmes.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.