Πολλά συστήματα πολλαπλών διαμεσολαβητών είναι εμπνευσμένα από διάφορες κοινωνίες εντόμων, τα οποία συλλογικά πετυχαίνουν διάφορους στόχους οι οποίοι είναι αδύνατο να επιτευχθούν σε ατομικό επίπεδο. Στις περισσότερες περιπτώσεις, κινητήρια δύναμη στην «συνεργασία» και τη συλλογικότητα των εντόμων είναι η στιγματική συμπεριφορά (stigmergy). Ο όρος αυτός χρησιμοποιείται στη βιολογία για να περιγράψει τον τρόπο επίδρασης αλλαγών στο περιβάλλον που προέκυψαν από μια παρελθοντική συμπεριφορά κάποιων κοινωνικών εντόμων στην συμπεριφορά ατόμων της ίδιας ομάδας. Χαρακτηριστικά παραδείγματα από τη φύση βρίσκουμε σε κάποια είδη μυρμηγκιών με τον τρόπο αναζήτησης τροφής και τη δημιουργία διαδρομών μεταξύ φωλιάς και πηγών τροφής ή την κατασκευαστική διαδικασία των τερμιτών. Αν και η έννοια αυτή είναι άρρητα συνδεδεμένη με την έκκριση μιας η περισσοτέρων χημικών ουσιών (στίγματα) για την έμμεση επικοινωνία μεταξύ ατόμων μιας κοινωνίας εντόμων, έχει εφαρμοστεί σε διαφορετικούς τομείς της επιστήμης των υπολογιστών. Αν και ένα μέρος του κλάδου της τεχνητής ζωής ασχολείται με μια ένα- προς -ένα αντιστοίχηση του έμμεσου αυτού τρόπου επικοινωνίας σε ομάδες ρομπότ που λειτουργούν στον πραγματικό κόσμο με την έκκριση κάποιας αντίστοιχης ουσίας, μεγάλο επιστημονικό ενδιαφέρον υπάρχει για την αναγωγή της έννοιας και της λειτουργίας της στιγματικής συμπεριφοράς στον ψηφιακό κόσμο: Η έννοια των ψηφιακών φερορμονών ή των στιγματικών πακέτων συναντάται, κυρίως σε αντίστοιχους αλγορίθμους δρομολόγησης πακέτων σε ένα δίκτυο κόμβων. Όσο αφορά στην ένα -προς- ένα αντιστοίχηση μηχανισμών σε συστήματα διαμεσολαβητών που λειτουργούν αναλογικά (αισθητήρες) στον πραγματικό κόσμο υπάρχουν περιπτώσεις όπου ενώ ένας στιγματικός μηχανισμός που εμφανίζεται στη φύση φαινομενικά βοηθά στην αντιμετώπιση του προβλήματος που το σύστημα καλείται να αντιμετωπίσει. Η υλοποίηση όμως ενός τέτοιου μηχανισμού μπορεί να είναι ανέφικτη λόγω τεχνικών ή / και οικονομικών λόγων. Ένας προτεινόμενος τρόπος αντιμετώπισης του προβλήματος αυτού είναι η αντιστοίχηση (προσέγγιση) ενός τέτοιου μηχανισμού με ένα μηχανισμό επικοινωνίας ο οποίος θα προσφέρει αντίστοιχα αποτελέσματα χωρίς επιπλέον ή με το μικρότερο κόστος. Για το σκοπό αυτό μπορεί να γίνει χρήση της τεχνολογίας μεταφοράς αναλογικών (π.χ ήχος, φως) ή ψηφιακών σημάτων (π.χ πακέτα δεδομένων). Πόσο στιγματικός όμως είναι μια ένας τρόπος επικοινωνίας μέσω μηνυμάτων, και ποιες είναι οι παραδοχές για κάτι τέτοιο; Μπορεί να υπάρξει αντιστοίχηση της επικοινωνίας (μέσω φερορμονών) που εμφανίζεται στη φύση με κάποιο τρόπο (ασύρματης) επικοινωνίας ο οποίος να μπορεί να εφαρμοστεί σε διαμεσολαβητές περιορισμένων δυνατοτήτων? Η αντιστοίχηση μπορεί να αξιολογηθεί με ποιοτικά κριτήρια όπως η εμφάνιση ή όχι μιας επιθυμητής συμπεριφοράς του συστήματος. Στη διπλωματική αυτή διατριβή παρουσιάζεται ένα μοντέλο ψηφιακής επικοινωνίας το οποίο θεωρητικά αντιστοιχεί στην ποιοτική στιγματική συμπεριφορά ενός συστήματος διαμεσολαβητών. Επιπλέον, εισάγονται δυο μετρήσιμα κριτήρια αξιολόγησης βάση των οποίων μπορεί να γίνει σύγκριση διαφορετικών τρόπων επικοινωνίας. Τα κριτήρια αυτά προκύπτουν από τη μοντελοποίηση μιας κοινής πλατφόρμας – συστήματος διαμεσολαβητών για ένα συγκεκριμένο σενάριο λειτουργίας. Αφού πραγματοποιήθηκαν τρεις σειρές εξομοιώσεων, προέκυψε ότι το σύστημα με χρήση ψηφιακής επικοινωνίας μπορεί να επιτύχει αυτοοργανωτική συμπεριφορά αντίστοιχη με τη συμπεριφορά όταν χρησιμοποιείται στιγματική επικοινωνία ή καμία επικοινωνία. Παρόλα αυτά, η απόδοση του συστήματος βάση των κριτηρίων αξιολόγησης δεν ήταν καλύτερη για τις περισσότερες εξομοιώσεις, κάτι που δεν ήταν θεωρητικά αναμενόμενο. Τέλος, τα αποτελέσματα των εξομοιώσεων οδηγούν σε διάφορα συμπεράσματα τα οποία πρέπει να λαμβάνονται υπόψη στη μελέτη τέτοιων συστημάτων. / Multiagent systems are inspired from insect societies, which collectively achieve different targets, each of is impossible to complete by an individual. In most cases, the driving force to insect “cooperation” and collectiveness is stigmergic behavior. This concept is used in biology to describe the way that environmental changes that occur as a result of a behavior of some social insects, affects the behavior of individuals of the same species. A prominent nature –based example is found in some ant species, where individuals use pheromones during food acquisition, creating different routes between the nest and several food sources. Another example is the termite nest building process. Stigmergy is associated to the emission of one or several chemical substances (stigmata), so as to achieve forms of indirect communication between individuals of a society, although, this concept has been used in different sections of the Computer Science. While much effort is done from the Artificial Life discipline to achieve a one-to-one equivalence of this indirect form of communication into groups of robots that operate in the real world by emitting a pheromone-alike substance, there is much interest in converting this stigmergic behavior to the digital world. The concept of digital pheromones (or stigmergic packets) is met in relative network routing algorithms. Staying on the one-to-one equivalence, there are cases and situations where a proposed stigmergic mechanism can be applied in a multiagent system, where each individual is operating using sensors and actuators inside the real world. However, the implementation of such a mechanism may be unfeasible because of technical, technological or economic reasons. A suggestion to counterattack this limitation is to approximate the stigmergic solution using a different communication mechanism, which may combine feasible, low cost implementation with corresponding to the stigmergic mechanism results. To achieve that, analog (eg light, sound) or digital (data packets) signals may be used. The question is, by using these new concepts, the mechanism of communication is classified as stigmergic and, if yes, are there any admissions? Is there any digital communication analog to the stigmergic communication which may be used to robotic and limited agents? This hypothetical equivalent can be evaluated using qualitative measures like the relevance (or absence) of a desired system behavior In this master thesis, I use a digital communication model which is theoretically assumed to be relative to the quantitative stigmergic behavior of a multiagent system. Additionally, two measurable evaluation criteria are introduced. By using these criteria, different mechanisms of communication may be compared to each other. These criteria result from the modeling of the common platform-multiagent system for a particular scenario of operation. By performing three different series of simulation, there was demonstrated that by using digital communication, the system achieves self organizing behavior relative to the behavior of the same system, using stigmergic or no form of communication. Still, the system performance (according to the introduced evaluation criteria) was not better for most cases of simulations, as it may be expected. Finally, the results lead to several conclusions that must be taken under consideration and further attention for the study of swarm intelligence based systems.

Le formalisme CSP (Problème de Satisfaction de Contraintes) permet de représenter de nombreux problèmes de manière simple et efficace. Cependant, une partie de ces problèmes ne peut être résolue de manière classique et centralisée. Les causes peuvent être diverses : temps de rapatriement des données prohibitif, sécurité des données non garantie, etc. Les CSP Distribués(DisCSP), domaine intersectant celui des SMA et des CSP, permettent de modéliser et de résoudre ces problèmes naturellement distribués. Les raisonnements intra-agent et inter-agents sont alors basés sur un ensemble de relations entre différentes variables. Les agents interagissent afin de construire une solution globale à partir des solutions locales. Nous proposons, dans ce travail, un algorithme de résolution de DisCSP nommé Distributed Backtracking with Sessions (DBS) permettant de résoudre des DisCSP où chaque agent dispose d'un problème local complexe. DBS a la particularité de ne pas utiliser de nogoods comme la majorité des algorithmes de résolution de DisCSP mais d'utiliser à la place des sessions. Ces sessions sont des nombres permettant d'attribuer un contexte à chaque agent ainsi qu'à chaque message échangé durant la résolution du problème. Il s'agit d'un algorithme complet permettant l'utilisation de filtres sur les messages échangés sans remettre en cause la preuvede complétude. Notre proposition est évaluée, dans les cas mono-variable et multi-variables par agents, sur différents benchmarks classiques (les problèmes de coloration de graphes distribués et les DisCSP aléatoires) ainsi que sur un problème d'exploration en environnement inconnu.

The work presented in this PhD thesis defines a new approach for the modeling and the conceptualization of enterprise business processes in the perspective of building intelligent assistance software tools to support these processes. The proposed approach defines an organizational ontology, named K-CRIO. Its description is based on the Ontology Web Language. To illustrate our work, an intelligent assistance system has been designed and implemented according to the result from the modeling and conceptualization of a specific business process with the K-CRIO Ontology. It is a web-based application that integrates and takes full advantage of multi-agent systems.The K-CRIO Ontology is an Ontology dedicated to the study of organizations and the analysis of business processes adopting an organizational point of view. Specifically, it is used to understand, analyze and reason about organizations and the processes they implement. The targeted organizations are those composed of entities involved throughout products' design and, to do so, following a defined business process. The range of this type of organizations is quite wide. We have thus limited our study to organizations that produce software as the final process goal, specifically IT enterprises delivering software products or services. In this context, the K-CRIO ontology could be used to model structure of the considered organizations and model human activities appearing in their business processes. This ontology could be used to support process assistance within the described organizations. More specifically, the ontology could provide means for reasoning, annotating resources, monitoring design processes, enabling searches and pro-actively proposing tips and proper content. In order to illustrate the usage of K-CRIO, we apply K-CRIO on two different processes: the Waterfall Model and the Scrum methodology. These examples are both classical software-development processes. Moreover, for Scrum, the famous agile software-development process widely used in software enterprises, we have designed and developed an intelligent assistance tool. This tool mainly helps Scrum Masters to make decision by monitoring Scrum project teams' activities within their various projects and collecting knowledge about these activities.

In this research, a context-aware mobile role playing game is developed to provide users with a series of story decorated quests and allows them to interact with specific real and virtual objects in the real world. The game is designed based on multi-agent architecture, which allows reusable and modular agents and makes the game much more flexible and scalable. The usefulness of the CAM-RPG is evaluated with a comprehensive experiment. The interesting findings are: (1) generated story in CAM-RPG positively influences users' attitude toward game use and increases users' perceived game usefulness; (2) users' game-playing confidence, degree of liking computer games, and attitude toward computer games significantly influence attitudes toward CAM-RPG; and (3) there is no gender difference for users' game acceptance, but users' computer game attitude, time spent playing computer games, and voluntariness of use do significantly influence users' acceptance. / 2012-02

No description available.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Dans la pratique, beaucoup de problèmes d'optimisation sont dynamiques : leur fonction objectif (ou fonction de coût) évolue au cours du temps. L'approche principalement adoptée dans la littérature consiste à adapter des algorithmes d'optimisation statique à l'optimisation dynamique, en compensant leurs défauts intrinsèques. Plutôt que d'emprunter cette voie, déjà largement explorée, l'objectif principal de cette thèse est d'élaborer un algorithme entièrement pensé pour l'optimisation dynamique. La première partie de cette thèse est ainsi consacrée à la mise au point d'un algorithme, qui doit non seulement se démarquer des algorithmes concurrents par son originalité, mais également être plus performant. Dans ce contexte, il s'agit de développer une métaheuristique d'optimisation dynamique. Deux algorithmes à base d'agents, MADO (MultiAgent algorithm for Dynamic Optimization) et MLSDO (Multiple Local Search algorithm for Dynamic Optimization), sont proposés et validés sur les deux principaux jeux de tests existant dans la littérature en optimisation dynamique : MPB (Moving Peaks Benchmark) et GDBG (Generalized Dynamic Benchmark Generator). Les résultats obtenus sur ces jeux de tests montrent l'efficacité des stratégies mises en oeuvre par ces algorithmes, en particulier : MLSDO est classé premier sur sept algorithmes évalués sur GDBG, et deuxième sur seize algorithmes évalués sur MPB. Ensuite, ces algorithmes sont appliqués à des problèmes pratiques en traitement de séquences d'images médicales (segmentation et recalage de séquences ciné-IRM cérébrales). A notre connaissance, ce travail est innovant, en ce sens que l'approche de l'optimisation dynamique n'avait jamais été explorée pour ces problèmes. Les gains de performance obtenus montrent l'intérêt d'utiliser les algorithmes d'optimisation dynamique proposés pour ce type d'applications

Durant ces dernières années, la congestion du trafic urbain et la pollution de l'air sont devenus d'énormes problèmes dans de nombreuses villes dans le monde. Afin de réduire cette congestion, nous pouvons investir dans l'amélioration des infrastructures de la ville. Toutefois, cette solution reste très coûteuse à entreprendre et de ne permet pas de réduire la pollution de l'air. C'est pourquoi nous travaillons sur la mobilité intelligente afin de disposer d'une meilleure utilisation de la voiture. L'application de nouvelles technologies de l'information, tels que les systèmes multi-agents appliqués au contrôle de l'information de la circulation urbaine, a permis de créer et de déployer une gestion plus intelligente du trafic comme le système DRT (transport à la demande). L'objectif des systèmes multi-agents basés sur le DRT est de gérer les taxis de manière intelligente, afin d'accroître le nombre de passagers dans chaque véhicule, et en même temps à réduire le nombre de véhicules dans les rues. Cela permettra de réduire les émissions de CO2 et la pollution de l'air causée par les véhicules, ainsi que la congestion du trafic et les coûts financiers associés. La simulation multi-agents est considérée comme un outil efficace pour les services dynamiques urbains de la circulation. Toutefois, le principal problème est de savoir comment construire un agent à base de modèle pour cette problématique. Ces travaux de recherche présente une solution basée sur les systèmes multi-agents réactifs pour la problématique du transport à la demande (DRT), qui adopte une approche multi-agent de planification urbaine en utilisant des services de contrôle qui satisfont aux principales contraintes : réduction de la période totale creuse, demandes spéciales du client, augmentation du nombre de places utilisées dans un même taxi, utilisation du nombre minimal de véhicules, etc. Dans cette thèse, nous proposons un modèle multi-agents multicouche hybride distribué pour des problématiques en temps réel. Dans la méthode proposée, un agent pour chaque véhicule trouve un ensemble de routes pour sa recherche locale, et choisit un itinéraire en coopérant avec d'autres agents se trouvant dans son domaine de planification. Nous avons examiné expérimentalement, l'efficacité de la méthode proposée.

Les agents situés dans l'image fournissent un cadre privilégié pour la mise en oeuvre de stratégies coopératives et localement adaptées en segmentation d'image. Ils facilitent l'intégration des connaissances a priori, expressions d'un modèle, permettant ainsi de dégager de nouvelles contraintes indispensables à toutes les étapes de la vision par ordinateur (de la segmentation à l'interprétation). Nous proposons un cadre conceptuel pour l'architecture logicielle d'un système de vision bas-niveau basée sur des agents situés dans l'image. Une telle architecture est articulée en trois niveaux d'analyse et de description : 1. Description globale et structurelle de l'organisation regroupant les agents. Cette étape de description s'attache à établir les liens entre agents. Nous proposons comme élément organisationnel la pyramide irrégulière qui impose sa structure à la population d'agents, afin de garantir un comportement globalement contrôlable et convergent de ces derniers. 2. Description locale, fonctionnelle et comportementale des agents composant le système. Nous proposons une mise en oeuvre particulière de l'architecture logicielle de vision bas-niveau. Dans cette dernière, deux familles d'agents, qui traduisent des primitives région et contour, interagissent localement au sein de la pyramide. Notre objectif est de montrer comment cette méthodologie permet une implémentation riche, flexible et distribuée des aspects précédemment identifiés; à savoir : l'adaptation locale, l'intégration et l'expression d'incertitudes dans l'information a priori et des traitements coopératifs région/région et région/contour. 3. Finalement, une analyse globale, comparative et fonctionnelle vérifie que l'ensemble des interactions locales produit une bonne segmentation des images. Nous comparons notre approche avec d'autres méthodes de segmentation sur des images médicales et des images de synthèse.

Cette thèse porte sur des stratégies distribuées pour systèmes multi-robot. Tout d'abord, nous nous focalisons sur des algorithmes de consensus pour des systèmes hétérogènes qui représente, par exemple, différents modèles ou générations de robots. Dans la suite, nous proposons deux solutions pour améliorer les propriétés de connectivité du système. Tout d'abord, nous montrons comment améliorer la vitesse de convergence des algorithmes de consensus en modifiant les protocoles classiques. Plus précisément, nous appliquons le principe de retard stabilisant et nous montrons comment de l'information échantillonné convenablement peut être utilisée dans la design du contrôleur. Enfin, nous concevons et analysons un algorithme pour le déploiement d'agents compact. Dans cette approche, qui augmente le nombre de connexions du graphe, la configuration souhaitée de l'ensemble des robots est entièrement spécifiée par les angles inter-agents. La stratégie proposée est un algorithme complètement distribué, uniquement basée sur l'information locale qui permet l'auto-organisation du système.