Literatura académica sobre el tema "Agent multi-Tâches"

L’évolution du contexte de défense aéronaval nécessite une modification majeure de l’architecture des systèmes de senseurs actuels afin de maitriser les futures menaces et d’intégrer les nouveaux dispositifs et senseurs à venir. Ces senseurs, hétérogènes, complémentaires et embarqués sur des plateformes navales ou aériennes, sont essentiels pour l’acquisition de données de l’environnement et l’établissement de la situation tactique. Dans ce contexte, les plateformes peuvent collaborer et partager leurs ressources senseurs pour accomplir de nouvelles fonctionnalités et établir un panorama global de la situation. Dans cette thèse, nous avons conçu et développé un système multi-agent pour l’allocation de tâches à des ressources distribuées sur des plateformes distinctes dans le but d’accomplir des capacités collaboratives. Nous présentons des scénarios illustrant les besoins opérationnels auxquels l’architecture doit répondre, établissant ainsi un cahier des charges. Ensuite, nous détaillons les étapes de la conception et de l’implémentation de cette nouvelle architecture, en décrivant chaque type d’agent et les interactions possibles entre eux. Nous proposons un algorithme d’enchère nécessitant des échanges entre les agents, soumis aux contraintes de bande passante et de latence. Enfin, nous présentons un banc d’essai intégrant des outils de capture et de visualisation de métriques du système, permettant l’évaluation des concepts d’agents et de leurs mécanismes de communication. L’objectif est de démontrer que notre architecture répond aux besoins opérationnels spécifiés, notamment le passage à l’échelle des algorithmes et des interfaces de communications des agents, la résistance aux pannes et la performance du système
The changing context of naval and aerial defense requires a major modification of current sensor system architectures to overcome future threats and to integrate next generation devices and sensors. These sensors, heterogeneous, complementary, and embedded on naval or aerial platforms, are essential for acquiring data from the environment in order to establish the tactical situation. In this context, platforms can collaborate and share their sensor resources to achieve new functionalities and set up a global overview of the situation. In this thesis, we have designed and developed a multi-agent system for allocating tasks to distributed resources on distinct platforms in order to accomplish collaborative capabilities. We present scenarios illustrating the operational needs that the architecture must meet, thus establishing a set of specifications. Then, we detail the steps involved in designing and implementing this new architecture, describing each type of agent and the possible interactions between them. We propose an auction algorithm requiring exchanges between agents, subject to bandwidth and latency constraints. Finally, we present a test bed integrating tools for capturing and display system metrics, allowing the evaluation of agent concepts and their communication mechanisms. The objective is to demonstrate that our architecture meets the specified operational requirements, in particular the scalability of the agents’ algorithms and communication interfaces, fault tolerance, and system performance

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
Task allocation among multiple autonomous agents that must accomplish complex tasks has been one of the focusing areas of recent research in multi-agent systems. In many applications, the agents are cooperative and have to perform tasks that each requires a combination of different capabilities that a subset of agents can have. In this case, we can use coalition formation as a paradigm to assign coalitions of agents to tasks. For robotic systems, in particular, solutions to this task allocation problem have several and increasingly important real-world applications in defense, space, disaster management, underwater exploration, logistics, product manufacturing, and support in healthcare facilities support. Multiple coalition formation and task allocation mechanisms were introduced in the prior art, seldom accounting for interdependent tasks. However, it is recurrent to find tasks whose quality cannot be evaluated without considering the other tasks in real-world applications. These tasks are called interdependent in contrast to independent tasks that can be individually assessed, resulting in a global evaluation of the tasks' allocation that sums all the tasks' evaluations. Research in the past has led to many task allocation algorithms that address the case of independent tasks from different angles and under different paradigms. Other works solve the case of the interdependent tasks, but they do it either centrally with very high complexity or only for the case of precedence dependencies. However, many forms of interdependence may exist between tasks in real-world applications. In addition, these applications need task allocation mechanisms to be decentralised and available at anytime to allow them to return a solution at any time and to improve it if there is time left, to respond to their time-sensitivity and robustness issues. In this dissertation, we consider cooperative multi-agent environments where tasks are multi-agent and interdependent, and task allocation methods have to be decentralized and available at anytime. In this regard, we propose a problem formalisation that considers the agents' and the tasks' qualitative and quantitative attributes and captures the tasks' dependencies on the requirements level and the allocation evaluation level. We introduce a novel approach with a token-passing anytime decentralised coalition formation mechanism. The approach enables agents with complementary capabilities to form, autonomously and dynamically, feasible coalition structures that accomplish a global, composite task. It is based on forming a feasible coalition structure that allows the agents to decide which coalition to join and thus which task to do so that all the tasks can be feasible. Then, the formed structures are incrementally improved via agent replacements to optimise the global evaluation. The purpose is to accomplish the tasks with the best possible performance. The analysis of our algorithms' complexity shows that although the general problem is NP-complete, our mechanism provides a solution within an acceptable time. Simulated application scenarios are used to demonstrate the added value of our approach

Mes travaux s'intègrent aux recherches menées dans l'équipe SMAC de CRIStAL en Intelligence Artificielle Distribuée.Les sciences des données exploitent de larges volumes de données sur lesquelles des calculs sont effectués en parallèle par différents nœuds. Ces applications mettent à l'épreuve l'informatique distribuée en ce qui concerne l'allocation de tâches et l'équilibrage de charge. J'étudie dans cette thèse le problème de l'allocation continue de jobs concurrents, composés de tâches situées, sous-jacent au déploiement d'applications de traitement de données massives sur une grappe de serveurs. L'objectif est de minimiser le délai moyen de réalisation de ces jobs, appelée flowtime.Je propose dans ce document un modèle multi-agents d'assignation tâches-exécutants où les nœudsde calcul sont contrôlés par des agents collaboratifs, appelés agents-nœuds, qui négocient des réallocations locales pour aboutir à une meilleure répartition des tâches. Ces négociations se déroulent au fil de l'exécution des tâches. Grâce à leur modèle des pairs, les agents-nœuds sont capables d'identifier des opportunités au sein de l'allocation courante pour marchander des délégations voire des échanges de tâches avec leurs semblables. Pour améliorer la réactivité (responsiveness) de la stratégie multi-agents qui repose sur l'exécution asynchrone de comportements individuels en interaction, le processus de négociation s'appuie sur de multiples négociations bilatérales concurrentes.Mes campagnes d'expérimentation permettent de valider empiriquement l'efficacité de la réactivitéde ma stratégie multi-agents. En effet, ma méthode favorise un réordonnancement rapide des tâches,plutôt que la recherche de la solution optimale, ce qui permet une adaptation rapide. Mes expérimentations montrent que, lorsqu'elle est exécutée de manière concurrente au processus de consommation,notre stratégie de réallocation : (1) réduit significativement le temps de réordonnancement ; (2) améliorele délai moyen de réalisation ; (3) ne pénalise pas la consommation ; (4) est robuste aux aléas d'exécution ; et (5) s'adapte à la libération de jobs
My work is part of the research done by the SMAC team in the laboratory CRIStAL in Distributed Artificial Intelligence.Data sciences exploit large datasets on which computations are performed in parallel by differentnodes. These applications challenge distributed computing in terms of task allocation and load-balancing.In this thesis, I study the problem of continuous allocation of concurrent jobs, composed of situated tasks,underlying the deployment of massive data processing applications on a cluster of servers. The objectiveis to minimise the mean flowtime of these jobs.In this paper, I propose a multi-agent task-worker assignment model where computing nodes are controlled by collaborative agents, called node agents, which negotiate local task reallocations to achieve a bettertask distribution. These negotiations take place during the tasks execution. Thanks to their peer modelling,node agents are able to identify opportunities within the current allocation to negotiate task delegationsor even swaps with their peers. To improve the responsiveness of the multi-agent strategy, which is basedon the asynchronous execution of interacting individual behaviours, the negotiation process is based onmultiple concurrent bilateral negotiations.My experimental campaigns allow me to empirically validate the efficiency of the reactivity of mymulti-agent strategy. This is because my method encourages rapid reordering of tasks, rather than thesearch for the optimum solution, which allows responsiveness. My experiments show that, when executedconcurrently with the consumption process, our reallocation strategy : (1) significantly reduces the rescheduling time ; (2) improves the flowtime ; (3) does not penalise the consumption ; (4) is robust to executionhazards ; and (5) adapts to the release of jobs

Dans la gestion des systèmes de soins, la maîtrise des flux hospitaliers et l’anticipation des tensions sont des enjeux majeurs. Le but de cette thèse est de contribuer à l’étude et au développement d’un Système Collaboratif d’Aide à l’Ordonnancement et à l’Orchestration (SysCAOO) des tâches de soins à compétences multiples pour gérer les tensions dans les Services d’Urgences Pédiatriques (SUP) afin d’améliorer la qualité de prise en charge des patients. Le SysCAOO intègre une approche Workflow collaboratif pour modéliser le parcours patient afin d’identifier les dysfonctionnements et les pics d’activités du personnel médical dans le SUP. L’aspect dynamique et incertain du problème nous a conduits à adopter une alliance entre les Systèmes Multi-Agent (SMA) et les Algorithmes Evolutionnaires (AE) pour le traitement et l’ordonnancement des tâches de soins en tenant compte du niveau d’expérience des acteurs du SUP et leurs disponibilités. En cas d’aléas dans le SUP, une coalition d’agents se forme pour collaborer et négocier afin de proposer des décisions d’orchestration du Workflow et minimiser le temps d’attente des patients en cours de leur prise en charge. Les résultats expérimentaux présentés dans cette thèse justifient l’intérêt de l’alliance entre les SMA et les Métaheuristiques afin de gérer les tensions dans le SUP. Les travaux de recherche présentés dans cette thèse s’intègrent dans le cadre du projet HOST (Hôpital : Optimisation, Simulation et évitement des tensions) (http://www.agence-nationale-recherche.fr/?Projet=ANR-11-TECS-0010)
Health care systems management and the avoidance of overcrowding phenomena are major issues. The aim of this thesis is to implement a Collaborative Support System for Scheduling and Orchestration (CSSystSO) of multi-skill health care tasks in order to avoid areas bottlenecks in the Pediatric Emergency Department (PED) and improve health care quality for patients. The CSSystSO integrates a collaborative Workflow approach to model patient journey in order to identify dysfunctions and peaks of activities of medical staff in the PED. The dynamic and uncertain aspect of the problem has led us to adopt an alliance between Multi-Agent Systems (MAS) and Evolutionary Algorithms (EA) for health care tasks treatment and scheduling taking into account the level of experience of the PED actors and their availabilities. In case of perturbations in the PED, a coalition of agents is formed to collaborate and negotiate in order to provide orchestration Workflow decisions to minimize the waiting time of patients during their treatment. The experimental results presented in this thesis justify the interest of the alliance between MAS and Metaheuristics to manage overcrowding phenomena in the PED. This work belongs to the project HOST (Hôpital: Optimisation, Simulation et évitement des tensions). (http://www.agence-nationale-recherche.fr/?Projet=ANR-11-TECS-0010)

Dans cette thèse, je présente le modèle NumJobs qui vise à simuler l'ensemble de l'économie, en se concentrant sur le marché du travail, afin d'évaluer l'impact de l'automatisation sur le marché du travail. Il s'agit d'un modèle à base d'agents avec environ 60000 agents, qui sont divisés en deux catégories : les individus, et les entreprises. Il contient plusieurs composantes liées entre elles : le marché du travail, la production de biens, la consommation, la démographie, la finance et l'automatisation numérique. Ce modèle est le résultat d'une large analyse des données disponibles pour les composantes des modèles, car nous avons essayé de limiter les éléments mis en œuvre pour lesquels nous n'avions pas de données. Le marché du travail est centré sur le référentiel ROME de Pole-Emploi, afin de disposer de vrais emplois, compétences et tâches, qui sont au cœur de l'interaction entre les individus et les entreprises au sein de la production. Les entreprises sont différenciées par leur effectif, leur secteur d'activité (NACE), ainsi que par le type de bien produit et ses caractéristiques. L'automatisation est modélisée comme des biens numériques qui peuvent être achetés par les entreprises et soit augmenter la productivité de la main-d'œuvre sur une tâche, soit remplacer cette même main-d'œuvre en automatisant la tâche. Les entreprises décident chaque année des tâches qu'elles souhaitent améliorer à l'aide de biens numériques, et comparer à la situation actuelle. Nous avons conçu deux expériences pour évaluer l'impact de l'automatisation sur le marché du travail : une expérience avec production locale uniquement, et une où la production est répartie avec une firme étrangère
In this PHD, I present the NumJobs model which aims to simulate the whole economy, focusing on the labor market, in order to evaluate the impact of automation on the labor market. This is an agent-based model with around 60000 agents, which are divided in two categories : individuals, and firms. It contains multiple linked components : the labor market, the production of goods, the consumption of goods, demography, finance, and digital automation. This model is the result of a large analysis of available data for the components of the models, as we tried to limit the implemented elements for which we didn’t have data. The labor market is centered around the ROME referential from Pole-Emploi, in order to have real jobs, skills, and tasks, which are at the core of the interaction between individuals and firms inside the production function. Firms are differentiated by their workforce, their sector of activity (NACE), as well as their produced good type and its characteristics. Automation is modelized as digital goods that can be bought by firms and either augment the productivity of labor on a task, or replace this same labor by automating the task. Firms decide on a yearly basis which tasks they want to improve with digital goods, and compare different categories of assistance goods and automation goods in order to select the best option and compare it with its current status. We designed two experiments to evaluate the impact of automation on the labor market : one where the production of digital goods is shared between local firms, and a foreign simulated actor, and another experiment where all digital goods are produced locally

Alors que les robots deviennent toujours plus présents dans les environnements humains, endossant toujours plus de tâches telles que le nettoyage, la surveillance ou encore le service en salle, leurs limites actuelles n’en deviennent que plus évidentes. Une de ces limites concerne leur capacité à naviguer en présence d’obstacles: ils chercheront systématiquement à les éviter, et resteront bloqués à défaut. Ce constat a mené à la création d’algorithmes de NAvigation en milieu MOdifiable (NAMO), devant permettre aux robots de manipuler les obstacles pour faciliter leurs déplacements. Néanmoins, ces algorithmes ont été conçus sous l’hypothèse qu’un seul robot agîsse dans l’environnement, biaisant les algorithmes à n’optimiser que son seul coût de déplacement – sans considération pour les humains ou d’autres robots. S’il est souhaitable que les robots puissent bénéficier de la capacité humaine à déplacer des obstacles, ils doivent néamoins le faire dans le respect des normes et règles sociales humaines. Nous avons donc étendu le problème de NAMO pour prendre en compte ces nouveaux aspects sociaux et multi-robots. En nous basant sur le concept d’espaces d’affordance, nous avons développé un modèle de coût d’occupation sociale permettant d’évaluer l’impact des objets déplacés sur la navigabilité de l’environnement. Nous avons implémenté (et amélioré) des algorithmes NAMO de référence, dans notre outil de simulation open source, puis les avons modifiés afin qu’ils puissent trouver un compromis entre coût de déplacement et coût d’occupation des obstacles manipulés – résultant en une amélioration de la navigabilité. Nous avons également développé une stratégie de coordination permettant d’exécuter ces mêmes algorithmes tels quels, sur plusieurs robots en parallèle, en absence de communication explicite, tout en préservant la garantie d’absence de collisions; vérifiant la pertinence de notre modèle de coût social en présence effective d’autres robots. Ces travaux constituent les premiers pas d’une NAMO Sociale et Multi-Robots
As robots become ever more commonplace in human environments, taking care of ever more tasks such as cleaning, security or food service, their current limitations only become more apparent. One such limitation is of their navigation capability in the presence of obstacles: they always avoid them, and freeze in place when avoidance is impossible. This is what brought about the creation of Navigation Among Movable Obstacles (NAMO) algorithms, expected to allow robots to manipulate obstacles as to facilitate their own movement. However, these algorithms were designed under the hypothesis of a single robot per environment, biasing NAMO algorithms into only optimizing the single robot's displacement cost - without any consideration for humans or other robots. While it is desirable to endow robots with the human capability of moving obstacles, they must however do so while respecting social norms and rules of humans. We have thus extended the NAMO problem as to take into account these new social and multi-robots aspects. By relying on the concept of affordance spaces, we have developed a social occupation cost model allowing the evaluation of the impact of moved objects on the environment's navigability. We implemented (and improved) reference NAMO algorithms, in our open source simulation tool, and modified them so that they may plan compromises between robot displacement cost and social occupation cost of moved obstacles - resulting in improved navigability. We also developed an implicit coordination strategy allowing the concurrent execution of these same algorithms by multiple robots as is, without any explicit communication requirements, while preserving the no-collision guarantee; verifying the relevance of our social occupation cost model in the actual presence of other robots. As such, this work constitutes the first steps towards a Social and Multi-Robot NAMO

Agir de manière autonome dans notre monde 3D requiert un large éventail de compétences, parmi lesquelles se trouvent la perception du milieu environnant, sa représentation précise et suffisamment efficace pour garder une trace du passé, la prise de décisions et l’action en vue d’atteindre des objectifs. Les animaux, par exemple les humains, se distinguent par leur robustesse lorsqu’il s’agit d’agir dans le monde. En particulier, ils savent s’adapter efficacement à de nouveaux environnements, mais sont aussi capables de maîtriser rapidement de nombreuses tâches à partir de quelques exemples. Ce manuscrit étudiera comment les réseaux neuronaux artificiels peuvent être entrainés pour acquérir un sous-ensemble de ces capacités. Nous nous concentrerons tout d’abord sur l’entrainement d’agents neuronaux à la cartographie sémantique, à la fois à partir d’un signal de supervision augmenté et avec des représentations neuronales de scènes. Les agents neuronaux sont souvent entrainés par apprentissage par renforcement (RL) à partir d’un signal de récompense peu dense. Guider l’apprentissage des capacités de cartographie d’une scène en ajoutant au signal de supervision des tâches auxiliaires favorisant le raisonnement spatial aidera à naviguer plus efficacement. Au lieu de travailler sur le signal d’entrainement des agents neuronaux, nous verrons également comment l’incorporation de représentations neuronales spécifiques de la sémantique et de la géométrie à l’architecture de l’agent peut contribuer à améliorer les performances de navigation sémantique. Ensuite, nous étudierons la meilleure façon d’explorer un environnement 3D afin de construire des représentations neuronales de l’espace qui soient aussi satisfaisantes que possible sur la base de métriques pensées pour la robotique que nous proposerons. Enfin, nous passerons d’agents de navigation à des agents multi-tâches et nous verrons à quel point il est important d’adapter les caractéristiques visuelles extraites des observations de capteurs à chaque tâche à accomplir pour réaliser une variété de tâches, mais aussi pour s’adapter à de nouvelles tâches inconnues à partir de quelques démonstrations. Ce manuscrit abordera donc différentes questions : Comment représenter une scène 3D et garder une trace de l’expérience passée dans un environnement ? – Comment s’adapter de manière robuste à de nouveaux environnements, scénarios et potentiellement de nouvelles tâches ? – Comment entrainer des agents à des tâches séquentielles à horizon long ? – Comment maîtriser conjointement toutes les sous-compétences requises ? – Quelle est l’importance de la perception en robotique ?
Autonomously behaving in the 3D world requires a large set of skills, among which are perceiving the surrounding environment, representing it precisely and efficiently enough to keep track of the past, making decisions and acting to achieve specified goals. Animals, for instance humans, stand out by their robustness when it comes to acting in the world. In particular, they can efficiently generalize to new environments, but are also able to rapidly master many tasks of interest from a few examples. This manuscript will study how artificial neural networks can be trained to acquire a subset of these abilities. We will first focus on training neural agents to perform semantic mapping, both from augmented supervision signal and with proposed neural-based scene representations. Neural agents are often trained with Reinforcement Learning (RL) from a sparse reward signal. Guiding the learning of scene mapping abilities by augmenting the vanilla RL supervision signal with auxiliary spatial reasoning tasks will help navigating efficiently. Instead of modifying the training signal of neural agents, we will also see how incorporating specific neural-based representations of semantics and geometry within the architecture of the agent can help improve performance in goal-driven navigation. Then, we will study how to best explore a 3D environment in order to build neural representations of space that are as satisfying as possible based on robotic-oriented metrics we will propose. Finally, we will move from navigation-only to multi-task agents, and see how important it is to tailor visual features from sensor observations to the task at hand to perform a wide variety of tasks, but also to adapt to new unknown tasks from a few demonstrations. This manuscript will thus address different important questions such as: How to represent a 3D scene and keep track of previous experience in an environment? – How to robustly adapt to new environments, scenarios, and potentially new tasks? – How to train agents on long-horizon sequential tasks? – How to jointly master all required sub-skills? – What is the importance of perception in robotics?

Cette thèse présente comment l’intégration de systèmes multi-agents au sein de systèmes embarqués peut permettre d’optimiser la gestion des tâches. Nous relevons un manque de flexibilité pour les systèmes embarqués et posons l’hypothèse d’une solution multi-agents permettant la prise en compte dynamique du contexte d’évolution du système. Les systèmes embarqués, intégrés à l’environnement utilisateur, sont contraints en termes d’espace physique et donc de ressources matérielles. Ces limites impliquent un besoin d’optimisation des ressources. Nous proposons d’expérimenter des algorithmes de négociation multi-agents pour déléguer des tâches entre les différentes ressources. Pour valider nos hypothèses, nous détaillons les caractéristiques des systèmes multi-agents, leurs comportements, leurs modèles,les plateformes sur lesquelles ils évoluent, leurs standards de communication et leurs algorithmes sociaux. Nous avons constaté que la majorité des travaux du domaine agent se concentraient sur d’autres problématiques. Par conséquent, nous avons proposé la formalisation de systèmes multiagents embarqués et d’une plateforme multi-agents adaptée. Nous avons ensuite expérimenté cette plateforme au sein de systèmes embarqués avec le cas d’étude du traitement d’images, notamment avec le calcul d’une interpolation de pixels. Nous avons mené des études de performances pour estimer le coût administratif d’une solution multiagents,puis avons considéré ces résultats au regard des gains de capacité de nos systèmes embarqués. Nos dernières expérimentations mettent à l’épreuve notre solution de délégation de tâches entre plusieurs cartes embarquées dans un contexte hétérogène
This thesis shows how the integration of multi-agents systems within embedded systems can optimize tasks management. We notice a lack of flexibility for embedded systems and hypothesize that a multi-agents solution will allow the dynamic consideration of the system context of evolution. Embedded systems, being integrated into the user environment, are limited in terms of physical space and thus hardware resources. These limits involve the necessity to optimize the resources. We suggest experimenting multi-agents negotiation algorithms to delegate tasks between several resources. To validate our hypotheses, we detail the characteristics of multi-agents systems, their behavior, their models, the platforms on which they evolve, their communication standards and their social algorithms.We observed that the majority of the works of the multi-agents domain concentrated on other problems. Therefore, we proposed the formalization of embedded multi-agents systems and of anadapted multi-agents platform. We then experimented this platform within embedded systems with the case study of image processing, especially the calculation of a pixels interpolation.We led performance studies to estimate the administrative cost of a multi-agents solution, then considered these results in relation to the capacity earnings of our embedded systems. Our last experiments put to the test our solution of tasks delegation between several embedded cards within a heterogeneous context

Le problème Rm||Cmax consiste à allouer un ensemble de tâches à m agents de sorte à minimiser le makespan de l’allocation, c’est-à-dire le temps d’exécution de l’ensemble des tâches. Ce problème est connu pour être NP-dur dès que les tâches sont allouées à deux agents ou plus (m ≥ 2). De plus, il est souvent admis que le coût d’une tâche est précisément estimé pour un agent et que ce coût ne varie pas au cours de l’exécution des tâches. Dans cette thèse, je propose une approche décentralisée et dynamique pour l’amélioration d’une allocation de tâches. Ainsi, à partir d’une allocation initiale et pendant qu’ils exécutent les tâches, les agents collaboratifs initient de multiples enchères pour réallouer les tâches qui restent à exécuter. Ces réallocations sont socialement rationnelles, c’est-à-dire qu’un agent accepte de prendre en charge une tâche initialement allouée à un autre agent si la délégation de cette tâche bénéficie à l’ensemble du système en faisant décroître le makespan. De plus, le dynamisme du procédé permet d’améliorer une allocation malgré une fonction de coût peu précise et malgré les variations de performances qui peuvent survenir lors de l’exécution des tâches. Cette thèse offre un cadre formel pour la modélisation et la résolution multi-agents d’un problème de réallocation de tâches situées. Dans un tel problème, la localité des ressources nécessaires à l’exécution d’une tâche influe sur son coût pour chaque agent du système. À partir de ce cadre, je présente le protocole d’interaction des agents et je propose plusieurs stratégies pour que les choix des agents aient le plus d’impact sur le makespan de l’allocation courante. Dans le cadre applicatif de cette thèse, je propose d’utiliser ce processus de réallocation de tâches pour améliorer le patron de conception MapReduce. Très utilisé pour le traitement distribué de données massives, MapReduce possède néanmoins des biais que la réallocation dynamique des tâches peut aider à contrer. J’ai donc implémenté un prototype distribué qui s’inscrit dans le cadre formel et implémente le patron de conception MapReduce. Grâce à ce prototype, je suis en mesure d’évaluer l’apport du processus de réallocation et l’impact des différentes stratégies d’agent
The Rm||Cmax problem consists in allocating a set of tasks to m agents in order to minimize the makespan of the allocation, i.e. the execution time of all the tasks. This problem is known to be NP-hard as soon as the tasks are allocated to two or more agents (m ≥ 2). In addition, it is often assumed that the cost of a task is accurately estimated for an agent and that this cost does not change during the execution of tasks. In this thesis, I propose a decentralized and dynamic approach to improve the allocation of tasks. Thus, from an initial allocation and while they are executing tasks, collaborative agents initiate multiple auctions to reallocate the remaining tasks to be performed. These reallocations are socially rational, i.e. an agent agrees to take on a task initially allocated to another agent if the delegation of this task benefits to the entire system by decreasing the makespan. In addition, the dynamism of the process makes it possible to improve an allocation despite an inaccurate cost function and despite the variations of performance that can occur during the execution of tasks. This thesis provides a formal framework for multi-agent modeling and multi-agent resolution of a located tasks reallocation problem. In such a problem, the locality of the resources required to perform a task affects its cost for each agent of the system. From this framework, I present the interaction protocol used by the agents and I propose several strategies to ensure that the choices of agents have the greatest impact on the makespan of the current allocation. In the applicative context of this thesis, I propose to use this tasks reallocation process to improve the MapReduce design pattern. Widely used for the distributed processing of massive data, MapReduce has biases that the dynamic tasks reallocation process can help to counter. I implemented a distributed prototype that fits into the formal framework and implements the MapReduce design pattern. Thanks to this prototype, I am able to evaluate the effectiveness of the reallocation process and the impact of the different agent strategies