Coordination temporelle de plans d’agents interdépendants : une première approche totalement distribuée

En planification et ordonnancement, les réseaux temporels simples avec incertitude (STNU) permettent de gérer sous forme de contraintes les durées des activités lorsque certaines d’entre elles ne peuvent être décidées par l’agent exécutant le plan. Pour un agent unique, cette incertitude provient de l’environnement. Dans les systèmes multi-agents, elle peut provenir des autres agents : le modèle MISTNU (Multiple Interdependent STNU) a récemment été introduit pour manipuler de telles durées partagées, contrôlées par un agent mais observées par les autres. Vérifier la contrôlabilité (c’est-à-dire la satisfiabilité temporelle) d’un MISTNU global équivaut à une vérification locale par chaque agent. Mais un nouveau problème dit de réparation est apparu : lorsque certains plans sont incontrôlables, les agents peuvent-ils négocier les bornes des intervalles de durée possibles pour retrouver la contrôlabilité? Des algorithmes centralisés de type SMT ont été développés, mais dans cet article, nous proposons un premier algorithme totalement distribué, en nous concentrant sur la propriété de Faible  Contrôlabilité. Notre approche, inspirée des problèmes de satisfaction de contraintes distribués (DisCSP), modélise les cycles incohérents du réseau comme des contraintes inter- agents et applique une forme adaptée de  backtracking distribué pour les réparer. Cet algorithme s’avère plus performant que l’algorithme centralisé initial, alors même que plusieurs pistes d’amélioration sont discutées.