رسائل دكتوراة
French
2007
Controle distrubué d'une organisation de robots
Ali Mellit, Wahid Boufaghes
كلية العلوم والعلوم الهندسية-جامعة عبد الرحمان ميرة - بجاية · الجزائر
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ésau début de ce mémoire et d’autre part, d’envisager de nouveaux axes de recherchecomme une suite logique de ce travail.Dans ce mémoire, nous avons étudié et développé une approche méthodologique etalgorithmique pour l’ordonnancement distribué et dynamique de tâches soumises à descontraintes 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 unmodè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 dynamiquementde nouveaux ordonnancements de tâches (plans de tâches) lors de l’exécution d’unemission. Ainsi, nous avons exposé un modèle générique d’organisation multi-agents. Cemodè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 complexeset 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 allocationde tâches entre les agents. La solution au problème d’ordonnancement consiste d’aborden un traitement local (au niveau de l’agent perturbé) puis en cas d’échec, passe parune résolution coordonnée qui met en œuvre des négociations entre agents, permettantde réaliser une coopération informationnelle et/ou une coopération par allocation detâches. Deux critères sont pris en compte dans la recherche de solutions : le nombre detâche de type prédécesseur affectées par une perturbation et le retard moyen induit auniveau de toute l’organisation. Par ailleurs, la recherche d’une solution coordonnée peutpasser 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éduirele temps de recherche de solution.Une bonne partie de ce travail de magistère a été consacrée à la validation desmodè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énariigénérés aléatoirement par un générateur aléatoire de scénarii développé, montre que desagents 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 à descontraintes de précédence et d’échéance. En effet, l’algorithme d’allocation de tâchestrouve 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 meilleurssi 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 nombrede messages échangés entre agents, dans les processus de négociation. Le nombre demessages échangés évolue quasi-linéairement en fonction du nombre de contraintes depré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 Solveuroptimal. 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 établieque 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. Dansun MRS, une tâche peut nécessiter plusieurs robots en même temps (transportd’objets lourds, etc)
