Allocation de tâches, Formation de coalition, Systèmes multi-agents, Tâches interdépendantes, Programmation par contraintes

L'allocation des tâches à plusieurs agents autonomes devant accomplir des tâches complexes a été l'un des domaines de recherche récents sur les systèmes multi-agents. Dans de nombreuses applications, les agents sont coopératifs et doivent effectuer des tâches qui nécessitent chacune une combinaison de différentes capacités dont peut se doter un sous-ensemble d'agents. Dans ce cas, nous pouvons utiliser la formation de coalitions comme paradigme pour affecter des coalitions d'agents à des tâches. Les solutions à ce problème d'allocation de tâches, pour les systèmes robotiques en particulier, trouvent plusieurs applications dans le monde réel et prennent de plus en plus de l'importance dans les domaines de la défense, de l'espace, de la gestion des catastrophes, de l'exploration sous-marine, de la logistique, de la fabrication de produits et de l'assistance dans les services de santé. De multiples mécanismes de formation de coalitions et d'allocation de tâches ont été introduits dans l'état de l'art, tenant rarement compte des tâches interdépendantes. Cependant, il est récurrent de trouver des tâches dont la qualité ne peut être évaluée sans considérer les autres tâches dans des applications réelles. Ces tâches sont appelées interdépendantes par opposition aux tâches indépendantes qui, elles, peuvent être évaluées individuellement, ce qui entraîne une évaluation globale de l'allocation des tâches qui additionne simplement toutes les évaluations des tâches. La recherche dans le passé a conduit à de nombreuses méthodes d'allocation de tâches qui traitent le cas des tâches indépendantes sous différents angles et sous différents paradigmes. D'autres travaux résolvent le cas des tâches interdépendantes, mais ils le font soit de manière centralisée avec une complexité très élevée, soit uniquement pour le cas des dépendances de précédence. Cependant, de nombreuses formes d'interdépendance peuvent exister entre les tâches dans les applications du monde réel. Ces applications nécessitent que les mécanismes d'allocation des tâches soient décentralisés et anytime, pouvant renvoyer une solution à tout moment quitte à l'améliorer s'il reste du temps, pour répondre à des problèmes de sensibilité au temps et de robustesse. Dans cette thèse, nous considérons des environnements multi-agents coopératifs où les tâches sont multi-agents et interdépendantes, et les méthodes d'allocation des tâches doivent être décentralisées et anytime. À cet égard, nous proposons une formalisation du problème qui considère les attributs qualitatifs et quantitatifs des agents et des tâches, et qui capture les dépendances des tâches que ça soit au niveau des exigences ou au niveau de l'évaluation des allocations. Nous introduisons une nouvelle approche avec un mécanisme de formation de coalition décentralisé anytime qui permet aux agents dotés de capacités complémentaires de former, de manière autonome et dynamique, des structures de coalitions faisables qui accomplissent une tâche globale et composite. Cette approche est basée sur la formation d'une structure de coalition faisable permettant aux agents de décider quelle coalition rejoindre et donc quelle tâche accomplir afin que toutes les tâches soient faisables. Ensuite, les structures formées sont progressivement améliorées via des remplacements d'agents pour optimiser l'évaluation globale de l'allocation, le but étant d'accomplir les tâches avec les meilleures performances possibles. Nous analysons la complexité de nos algorithmes et montrons que, bien que le problème général soit NP-complet, notre mécanisme fournit une solution dans un temps acceptable. Des scénarios d'application simulés sont utilisés pour démontrer la valeur ajoutée de notre approche.