Controle distrubué d'une organisation de robots

Abstract

AU terme de ce manuscrit, nous nous proposons de faire un récapitulatif de notre travail, d’analyser globalement les résultats obtenus et enfin de dresser des perspectives qui permettront d’une part, de finaliser les objectifs que nous nous étions fixés au début de ce mémoire et d’autre part, d’envisager de nouveaux axes de recherche comme une suite logique de ce travail. Dans ce mémoire, nous avons étudié et développé une approche méthodologique et algorithmique pour l’ordonnancement distribué et dynamique de tâches soumises à des contraintes temporelles et de ressources, dans le contexte de la robotique distribuée. L’approche proposée se base sur le paradigme multi-agents, mettant en œuvre un modèle de coopération pour l’ordonnancement dynamique de tâches, négociant en fonction des informations limitées dont les agents disposent, afin de s’adapter aux changement de l’environnement dans lequel ils évoluent, c’est à dire établir dynamiquement de nouveaux ordonnancements de tâches (plans de tâches) lors de l’exécution d’une mission. Ainsi, nous avons exposé un modèle générique d’organisation multi-agents. Ce modèle privilégie à la fois la distribution de la décision, l’autonomie et la réactivité des agents ainsi que la coordination décentralisée. Il s’agit d’une architecture hybride, s’appuyant sur des capacités délibératives pour raisonner dans des situations complexes et des capacités réactives pour respecter des échéances. Nous avons défini les comportements des agents par des plans comportementaux locaux et des protocoles de négociation qui ont pour objectif de réaliser un partage de connaissances ou une allocation de tâches entre les agents. La solution au problème d’ordonnancement consiste d’abord en un traitement local (au niveau de l’agent perturbé) puis en cas d’échec, passe par une résolution coordonnée qui met en œuvre des négociations entre agents, permettant de réaliser une coopération informationnelle et/ou une coopération par allocation de tâches. Deux critères sont pris en compte dans la recherche de solutions : le nombre de tâche de type prédécesseur affectées par une perturbation et le retard moyen induit au niveau de toute l’organisation. Par ailleurs, la recherche d’une solution coordonnée peut passer par la propagation des contraintes de l’agent perturbé à un autre afin d’assurerla cohérence globale de réalisation d’une mission. Pour garantir une réactivité de l’organisation qui doit être compatible avec sa dynamique, nous avons proposé et développé un ensemble d’heuristiques associé à des mécanismes de négociation en vue de réduire le temps de recherche de solution. Une bonne partie de ce travail de magistère a été consacrée à la validation des modèles proposés, pour laquelle une application de simulation multi-agents à été développée. L’analyse statistique des résultats de l’exécution d’un grand nombre de scénarii générés aléatoirement par un générateur aléatoire de scénarii développé, montre que des agents logiciels employant les algorithmes proposés sont capables d’ordonnancer dynamiquement et sans visibilité globale de l’état du système, des tâches soumises à des contraintes de précédence et d’échéance. En effet, l’algorithme d’allocation de tâches trouve effectivement des allocations équilibrant la charge de l’ensemble de robots. Les résultats obtenus de l’exécution des scénarii sont dans la plupart des cas meilleurs si les agents adoptent les heuristiques proposées. Nous avons également étudié et validé expérimentalement la complexité algorithmique du modèle proposé. Cette complexité concerne les coûts calculatoires des algorithmes associés aux agents, ainsi que le nombre de messages échangés entre agents, dans les processus de négociation. Le nombre de messages échangés évolue quasi-linéairement en fonction du nombre de contraintes de précédence et du nombre de nouvelles tâche, et indépendamment du nombre d’agents. Compte tenu des différents points que nous avons abordés au cours de ce mémoire, nous proposons dans un cadre de travaux futurs d’aborder d’autres points : – Comparaison avec des solutions globalement optimales, obtenues par un Solveur optimal. La solution optimale, représente un ordonnancement de toutes les tâches, dont le temps d’exécution de bout en bout est minimal. Elle ne peut être établie que lorsque le système est entièrement observable, c’est-à-dire en traitant l’ensemble des tâches et leurs contraintes de manière centralisée. – Il reste à valider expérimentalement la prise en compte d’autres contraintes : contraintes multiples de précédence entre tâches (la tâche d’un agent est liée à plusieurs tâche d’autres agents). – Lever certaines hypothèses retenues dans le cadre de l’algorithmique présentée, par exemple la nécessité d’un seul robot à la fois pour réaliser une tâche. Dans un MRS, une tâche peut nécessiter plusieurs robots en même temps (transport d’objets lourds, etc)