Ce travail de thèse porte sur l'étude des systèmes complexes par une démarche de modélisation et simulation (M&S). La plupart des questionnements sur ces systèmes nécessitent de prendre en compte plusieurs points de vue simultanément. Il faut alors considérer des phénomènes évoluant à des échelles (temporelles et spatiales) et des niveaux de résolutions (de microscopique à macroscopique) différents. De plus, l'expertise nécessaire pour décrire le système vient en général de plusieurs domaines scientifiques. Les défis sont alors de concilier ces points de vues hétérogènes, et d'intégrer l'existant de chaque domaine (formalismes et logiciels de simulation) tout en restant dans le cadre rigoureux de la démarche de M&S. Pour répondre à ces défis, nous mobilisons à la fois des notions de modélisation multi-niveau (intégration de représentations micro/macro), de modélisation hybride (intégration de formalismes discrets/continus), de simulation parallèle, et d'ingénierie logicielle (interopérabilité logiciel, et ingénierie dirigée par les modèles). Nous nous inscrivons dans la continuité des travaux de M&S existants autour de l'approche AA4MM et du formalisme DEVS. Nous étudions en effet dans cette thèse en quoi ces approches sont complémentaires et permettent, une fois combinées dans une démarche d'Ingénierie Dirigée par les Modèles (IDM), de répondre aux défis de la M&S des systèmes complexes. Notre contribution est double. Nous proposons d'une part les spécifications opérationnelles de l'intergiciel de co-simulation MECSYCO permettant de simuler en parallèle un modèle de manière rigoureuse et complètement décentralisée. D'autre part, nous proposons une approche d'IDM permettant de décrire de manière non-ambiguë des modèles, puis de systématiser leur implémentation dans MECSYCO. Nous évaluons les propriétés de notre approche à travers plusieurs preuves de concept portant sur la M&S du trafic autoroutier et sur la résolution numérique d'un système d'équations différentielles / This thesis is focused on the study of complex systems through a modeling and simulation (M&S) process. Most questions about such systems requiere to take simultaneously account of several points of view. Phenomena evolving at different (temporal and spatial) scales and at different levels of resolution (from micro to macro) have to be considered. Moreover, several expert skills belonging to different scientific fields are needed. The challenges are then to reconcile these heterogeneous points of view, and to integrate each domain tools (formalisms and simulation software) within the rigorous framework of the M&S process. In order to solve these issues, we mobilise notions from multi-level modeling, hybrid modeling, parallel simulation and software engineering. Regarding these fields, we study the complementarity of the AA4MM approach and the DEVS formalism into the scope of the model-driven engineering (MDE) approach. Our contribution is twofold. We propose the operational specifications of the MECSYCO co-simulation middleware enabling the parallel simulation of complex systems models in a rigorous and decentralized way. We also define an MDE approach enabling the non-ambiguous description of complex systems models and their automatic implementation in MECSYCO. We show the properties of our approach with several proofs of concept

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-05-08T18:37:11Z No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5) / Approved for entry into archive by Caroline Xavier (caroline.xavier@pucrs.br) on 2018-05-15T19:07:36Z (GMT) No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5) / Made available in DSpace on 2018-05-15T19:14:18Z (GMT). No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5) Previous issue date: 2018-03-27 / Sistemas multiagentes freq?entemente cont?m ambientes complexos e din?micos, nos quais os planos dos agentes podem falhar a qualquer momento durante a execu??o do sistema. Al?m disso, novos objetivos podem aparecer para os quais n?o existem nenhum plano dispon?vel. T?cnicas de planejamento s?o bem adequadas para lidar com esses problemas. H? uma quantidade extensa de pesquisa em planejamento centralizado para um ?nico agente, por?m, at? ent?o planejamento multiagente n?o foi completamente explorado na pr?tica. Plataformas multiagentes tipicamente proporcionam diversos mecanismos para coordena??o em tempo de execu??o, frequentemente necess?rios em planejamento online. Neste contexto, planejamento multiagente descentralizado pode ser eficiente e eficaz, especialmente em dom?nios fracamente acoplados, al?m de garantir algumas propriedades importantes em sistemas de agentes como privacidade e autonomia. N?s abordamos esse problema ao apresentar uma t?cnica para planejamento multiagente online que combina aloca??o de objetivos, planejamento individual utilizando rede de tarefas hier?rquicas (HTN), e coordena??o em tempo de execu??o para apoiar a realiza??o de objetivos sociais em sistemas multiagentes. Especificamente, n?s apresentamos um framework chamado Decentralised Online Multi-Agent Planning (DOMAP). Experimentos com tr?s dom?nios fracamente acoplados demonstram que DOMAP supera quatro planejadores multiagente do estado da arte com respeito a tempo de planejamento e tempo de execu??o, particularmente nos problemas mais dif?ceis. / Multi-agent systems often contain dynamic and complex environments where agents? course of action (plans) can fail at any moment during execution of the system. Furthermore, new goals can emerge for which there are no known plan available in any of the agents? plan library. Automated planning techniques are well suited to tackle both of these issues. Extensive research has been done in centralised planning for singleagents, however, so far multi-agent planning has not been fully explored in practice. Multi-agent platforms typically provide various mechanisms for runtime coordination, which are often required in online planning (i.e., planning during runtime). In this context, decentralised multi-agent planning can be efficient as well as effective, especially in loosely-coupled domains, besides also ensuring important properties in agent systems such as privacy and autonomy. We address this issue by putting forward an approach to online multi-agent planning that combines goal allocation, individual Hierarchical Task Network (HTN) planning, and coordination during runtime in order to support the achievement of social goals in multi-agent systems. In particular, we present a planning and execution framework called Decentralised Online Multi-Agent Planning (DOMAP). Experiments with three loosely-coupled planning domains show that DOMAP outperforms four other state-of-the-art multi agent planners with regards to both planning and execution time, particularly in the most difficult problems.

De nos jours, les informations liées au déplacement et à la mobilité dans un réseau de transport représentent sans aucun doute un potentiel important.Ces travaux visent à mettre en œuvre un Système d’Information de Service d’Aide à la Mobilité Urbaine (SISAMU).Le SISAMU doit pouvoir procéder par des processus de décomposition des requêtes simultanées en un ensemble de tâches indépendantes. Chaque tâche correspond à un service qui peut être proposé par plusieurs fournisseurs d’information en concurrence, avec différents coûts, temps de réponse et formats. Le SISAMU est lié à un Réseau informatique Etendu et distribué de Transport Multimodal (RETM) qui comporte plusieurs sources d’information hétérogènes des différents services proposés aux utilisateurs de transport. L’aspect dynamique, distribué et ouvert du problème, nous a conduits à adopter une modélisation multi-agent pour assurer au système une évolution continue et une flexibilité pragmatique. Pour ce faire, nous avons proposé d’automatiser la modélisation des services en utilisant la notion d’ontologie. Notre SISAMU prend en considération les éventuelles perturbations sur le RETM.Ansi, nous avons créé un protocole de négociation entre les agents. Le protocole de négociation proposé qui utilise l’ontologie de la cartographie se base sur un système de gestion des connaissances pour soutenir l'hétérogénéité sémantique. Nous avons détaillé l’Algorithme de Reconstruction Dynamique des Chemins des Agents (ARDyCA) qui est basé sur l’approche de l’ontologie cartographique. Finalement, les résultats présentés dans cette thèse justifient l’utilisation de l’ontologie flexible et son rôle dans le processus de négociation / Nowadays, information related on displacement and mobility in a transport network represents certainly a significant potential. So, this work aims to modeling, to optimize and to implement an Information System of Services to Aid the Urban Mobility (ISSAUM).The ISSAUM has firstly to decompose each set of simultaneous requests into a set of sub-requests called tasks. Each task corresponds to a service which can be proposed different by several information providers with different. An information provider which aims to propose some services through our ISSAUM has to register its ontology. Indeed, ISSAUM is related to an Extended and distributed Transport Multimodal Network (ETMN) which contains several heterogeneous data sources. The dynamic and distributed aspects of the problem incite us to adopt a multi-agent approach to ensure a continual evolution and a pragmatic flexibility of the system. So, we proposed to automate the modeling of services by using ontology idea. Our ISSAUM takes into account possible disturbance through the ETMN. In order to satisfy user requests, we developed a negotiation protocol between our system agents. The proposed ontology mapping negotiation model based on the knowledge management system for supporting the semantic heterogeneity and it organized as follow: Negotiation Layer (NL), the Semantic Layer (SEL), and the Knowledge Management Systems Layer(KMSL).We detailed also the reassignment process by using Dynamic Reassigned Tasks (DRT) algorithm supporting by ontology mapping approach. Finally, the experimental results presented in this thesis, justify the using of the ontology solution in our system and its role in the negotiation process

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).

Ce travail concerne la commande des systèmes multi-agent d’ordre fractionnaire utilisant une topologie de communication fixe. Premièrement, la production en formation avec atténuation absolue et retard de communication est étudiée. Pour cela, une loi de commande et des conditions suffisantes sont proposées. Toutefois, dans certains scénarios, il est souhaitable que tous les agents atteignent la formation souhaitée tout en se déplacent en groupe, au lieu d’un rendez-vous à un point fixe. Ce cas sera traité en étudiant la production en formation avec atténuation relative et retard de communication. Troisièmement, la poursuite par consensus des systèmes avec un état de référence variable dans le temps est étudiée. Une loi de commande commune et une seconde basée sur la prédiction d’erreur sont proposées, et le problème du consensus est résolu quand le graphe de communication contient un arbre dirigé. Il a été prouvé que la convergence du système est plus rapide en utilisant la loi basée sur la prédiction d’erreur plutôt que celle de commande commune. Enfin, les lois de commande ci-dessus sont étendues au cas de la poursuite en formation. En effet, dans de nombreux cas, l'information peut être envoyée à partir d'un état de référence vers les agents voisins uniquement et non pas à l’ensemble des agents. Afin de résoudre ce problème, une loi de commande est proposée afin de résoudre le problème du consensus avec un état de référence constant. Puis, deux lois de commande sont proposées afin de résoudre le problème du consensus avec un état de référence variant dans le temps. Ces lois sont étendues pour résoudre le problème de la poursuite en formation / This thesis focuses on the distributed coordination of fractional-order multi-agent systems under fixed directed communication graph. Firstly, formation producing with absolute damping and communication delay of fractional-order multi-agent systems is studied. A control law is proposed and some sufficient conditions are derived for achieving formation producing. However, in some scenarios, it might be desirable that all agents achieve formation and move as a group, instead of rendezvous at a stationary point. Therefore, secondly, formation producing with relative damping and communication delay is considered. Thirdly, consensus tracking of fractional-order multi-agent systems with a time-varying reference state is studied. A common control law and a control law based on error predictor are proposed, and it is shown that the control laws are effective when a communication graph has directed spanning trees. Meanwhile, it is proved that the convergence of systems is faster using the control law based on error predictor than by the common one. Finally, the above control laws are extended to achieve formation-tracking problems. In fact, in many cases information can be sent from a reference state to only its neighbor agents not to all the agents. In order to solve the above problem, an effective control law is given to achieve consensus with a constant reference state. Then, an effective general control law and an effective particular one are proposed to achieve consensus with a time-varying reference state. Furthermore, the above control laws are extended to achieve the formation tracking problems

La politique des transports dans le monde et en Europe évolue vers une vision co-modale. Cette nouvelle politique n’oppose plus la voiture au transport public mais encourage une combinaison de tous les modes de transport en espérant ainsi assurer un développement rentable et durable.Nous focalisons notre étude sur le service transport de personnes qui s’inscrit au cœur des politiques co-modales en combinant tous les modes de transport en commun (métro, bus..) et promeut de nouveaux modes d’utilisation de la voiture particulière comme le covoiturage (partage d’un véhicule personnel) ou l’AutoPartage (voiture en libre-service).Toutefois, pour générer un itinéraire exploitant les services de plusieurs opérateurs de transport, il faut consulter plusieurs sites internet. Selon le déplacement à réaliser, cette tâche de planification complexe peut être très difficile à réaliser et ne garantit pas l’optimalité de l’itinéraire sélectionné.Nous nous sommes donc intéressés à la conception d’un système d’aide au déplacement capable de fournir une information voyageur (co-modale) en mettant en relation plusieurs opérateurs de transport (en commun et individuel). Le système en question doit être capable d’assister l’utilisateur dans la phase de planification par la constitution d’un carnet de voyage proposant plusieurs itinéraires multi-opérateurs. De plus, il assiste l’utilisateur en cas de perturbation en l’informant et en lui proposant des itinéraires de secours. Ce travail est basé sur des avancées technologiques qui facilitent l’optimisation dans un environnement distribué (Multi-agent - SOA) et rendent l’information accessible grâce à un grand nombre de médias (téléphone, PDA..) / Today's transport policy in the world, and more specifically in Europe, is moving towards a co-modal vision. This new policy does not oppose private to public transport but encourages a combination of all modes of transportation in the hope of assuring a lasting development.We focus our study on one special service: people transport which combines all modes of public transport (train, subway, tram, bus ..) and integrates new ways of car use such as carpooling (sharing a personal vehicle and the travel cost between drivers and passengers) and the EcoPartage (self-service cars in town).However, to generate a route using several transport operators, we have to check different Internet websites. This complex planning task can be very difficult and does not guarantee the optimality of the selected route.We are therefore interested in designing a support information system capable of providing comodal information linking several transport operators (public and individual).The system in question must be able to assist the user in the planning phase by offering a travelogue suggesting several possible routes; each route may include one or more transport operator (public or individual ones).In addition, it assists the user during the trip by informing him in case of disturbance and by proposing alternatives routes if necessary.This work is based on various technological developments in order to facilitate the information optimization in a distributed environment (Multi-agent - SOA) and make the information accessible to the user through a large number of media (telephone, mobile, PDA ...)

La simulation constitue une approche majeure pour la conception, le développement, l’analyse et l’évolution des systèmes urbains. Dans le contexte de cette thèse, nous nous intéressons à la modélisation et à la simulation des déplacements de flux (piéton, véhicule, cycle) au sein d’environnements urbains. Le contexte industriel dans lequel s’inscrit également cette thèse impose de considérer les déplacements de chaque entité dans un univers modélisé en trois dimensions. Nous proposons d’aborder les nombreux défis scientifiques et technologiques en modélisant les flux sous la forme d’entités autonomes appelées agents. La simulation orientée-agent nécessite de définir trois mécanismes principaux : le comportement des agents, leurs interactions avec les autres agents et leurs interactions avec l’environnement dans lequel ils évoluent. Ce dernier modélise la structure du monde ainsi que sa dynamique endogène. Malheureusement, il reste difficile de trouver des modèles d’environnement répondant aux différentes problématiques scientifiques et technologiques abordées dans cette thèse. Par conséquent, nous proposons un modèle d'environnement, nommé HEDGE (HEterogenous Dual Graph Environment). Il est basé sur une décomposition de l’environnement en zones reliées par des liens de navigation et de perception. Cette structure de graphe est au centre de notre modèle. Elle a été conçue pour permettre une modélisation naturelle de l’environnement et une simulation efficace du système constitué par cet environnement et les agents. Les missions et les processus dynamiques de l’environnement sont modélisés à l’aide de mécanismes inspirés des lois de la Physique. Les actions fournies par les agents et par les algorithmes calculant la dynamique endogène de l’environnement sont des forces à appliquer aux objets du monde. Un modèle de détection et de résolution de conflits entre ces forces est utilisé afin de garantir un état cohérent du modèle de l’environnement. Dans la dernière partie de cette thèse, nous illustrons l’utilisation du modèle HEDGE dans le cadre de deux projets d’aménagement de la ville de Belfort et de sa communauté d’agglomérations Le produit de l’application de ce modèle est utilisé à des fins d’études techniques (études préliminaires, avant-projet), de communication (concertations et débats publics) et de promotion (expositions, valorisation) sous la forme de logiciels interactifs en 3D. / Simulation constitutes a major approach for the conception, development, analysis and evolution of urban systems. This thesis focusses on the modeling and simulation of movements (pedestrian, vehicle, cycle) within urban environments. The industrial context associated with this thesis requires to consider the movements of each entity in a three dimensional universe. In this thesis, we propose to address the scientific and technological challenges by using autonomous entities, called agents, to model the individuals. In agent-based simulation three elements must be defined: the agent behaviors, their interactions with other agents, and with the environment. The environment models the structure of the world and its endogenous dynamics. Unfortunately, it is still difficult to find an environment model that answers all the different scientific and technological problems addressed in this thesis. Consequently, an environment model named HEterogenous Dual Graph Environment (or HEDGE) is proposed. The HEDGE model is based on a decomposition of the environment using zones that are linked with navigation and perception links. This graph structure is at the center of our model. It is designed to “naturally” model the environment, and it allows an efficient simulation of the system composed of the environment and the agents. The environment’s missions and dynamic processes are modeled using mechanisms, which are inspired by the laws of Physics. The actions provided by the agents and the endogenous dynamics algorithms correspond to physical forces to apply to objects in the world. A model of conflict detection and resolution between those forces is used to ensure the coherence of the environment model state. In the last part of this thesis, the HEDGE model is used in the context of two urban planning projects in the city of Belfort, and its metropolitan area. The product of this model’s application is used in the context of technical studies (preliminary studies, pre-project), communication (consultation and public debates) and promotion (exposition, valorization) in the form of interactive 3D software.

One of the main focus of research on multi-agent systems is that of coordination in a group of agents to solve problems that are beyond the capability of a single agent. Each agent in the multi-agent system has limited capacity and/or knowledge which makes coordination a challenging task. Applications of multi-agent systems in space and ocean exploration, military surveillance and rescue missions, require the agents to achieve some consensus in their motion. The consensus has to be achieved and maintained without a centralized controller. Multi-agent system research borrows ideas from the biological world where such motion consensus strategies can be found in the flocking of birds, schooling of fishes, and colony of ants. One such classes of strategies are the cyclic pursuit strategies which mimic the behavior of dogs, birds, ants, or beetles, where one agent pursues another in a cyclic manner, and are commonly referred to as the `bugs' problem, In the literature, cyclic pursuit laws have been applied to a swarm of homogenous agents, where there exists a predefined cyclic connection between agents and each agent follows its predecessor. At equilibrium, the agents reach consensus in relative positions. Equilibrium formation, convergence, rate of convergence, and stability are some of the aspects that have been studied under cyclic pursuit. In this thesis, the notion of cyclic pursuit has been generalized. In cyclic pursuit, usually agents are homogenous in the sense of having identical speeds and controller gains where an agent has an unique predecessor whom it follows. This is defined as the basic cyclic pursuit (BCP) and the sequence of connection among the agents is defined as the Pursuit sequence (PS). We first generalize this system by assuming heterogeneous speed and controller gains. Then, we consider a strategy where an agent can follow a weighted centroid of a group of other agents instead of a single agent. This is called centroidal cyclic pursuit (CCP). In CCP, the set of weights used by the agents are assumed to be the same. We generalize this further by considering the set of weights adopted by each agent to be different. This defines a generalized centroidal cyclic pursuit (GCCP). The behavior of the agents under BCP, CCP and GCCP are studied in this thesis. We show that a group of holonomic agents, under the cyclic pursuit laws ¡ BCP, CCP and GCCP ¡ can be represented as a linear system. The stability of this system is shown to depend on the gains of the agents. A stable system leads to a rendezvous of the agents. The point of rendezvous, also called the reachable point, is a function of the gains. In this thesis, the conditions for stability of the heterogeneous system of agents in cyclic pursuit are obtained. Also, the reachable point is obtained as a function of the controller gains. The reachable set, which is a region in space where rendezvous can occur, given the initial positions of the agents, are determined and a procedure is proposed for calculating the gains of the agents for rendezvous to occur at any desired point within the reachable set. Invariance properties of stability, reachable point and reachable set, with respect to the pursuit sequence and the weights are shown to exist for these linear cyclic pursuit laws. When the linear system is unstable, the agents are shown to exhibit directed motion. We obtain the conditions under which such directed motion is possible. The straight line asymptote to which the agents converge is characterized by the gains and the pursuit sequence of the agents. The straight lines asymptote always passes through a point, called the asymptote point, for given initial positions and gains of the agents. This invariance property of the asymptote point with respect to the pursuit sequence and the weights are proved. For non-homonymic agents, cyclic pursuit strategies give rise to a system of nonlinear state equations. It is shown that the system at equilibrium converges to a rigid polygonal formation that rotates in space. The agents move in concentric circles at equilibrium. The formation at equilibrium and the conditions for equilibrium are obtained for heterogeneous speeds and controller gains. The application of cyclic pursuit strategies to autonomous vehicles requires the satisfaction of some realistic restrictions like maximum speed limits, maximum latex limits, etc. The performances of the strategies with these limitations are discussed. It is also observed that the cyclic pursuit strategies can also be used to model some behavior of biological organisms such as schools of fishes.

This thesis addresses a multi-agent search problem where several agents, equipped with sensors and communication devices, search an unknown area. Lack of information about the search space is modeled as an uncertainty density distribution. A sequential deploy and search (SDS) strategy is formulated where the agents are first deployed to maximize single step search effectiveness. To achieve an optimal deployment, a multi-center objective function defined using the Voronoi cells and the uncertainty distribution is optimized. It is shown that the critical points of this objective function are the centroids of the Voronoi cells. A proportional control law is proposed that makes the agents move to their respective “centroids”. Assuming agents to be first order dynamical systems and using LaSalle's invariance principle, it is shown that the closed-loop system converges globally asymptotically to the critical points. It is also shown that the sequential deploy and search strategy is spatially distributed with respect to the Delaunay graph corresponding to any given agent configuration. Next, a combined deploy and search (CDS) strategy is proposed where, instead of first deploying agents and then performing the search, the agents engage in search operation as they move toward the centroids. This strategy gives rise to shorter agent trajectories compared to the SDS strategy. Then the problem is formulated with practical constraints such as sensor range limits and limit on maximum speed of the agents. A few issues relating to implementation of the proposed search strategies are also addressed. Finally, the assumption of homogeneous agents is relaxed and agents equipped with sensors with heterogeneous capabilities are considered. A generalized Voronoi partitioning scheme is proposed and used to formulate a heterogeneous locational optimization problem. In this problem the agents are deployed in the search space optimizing the sensor effectiveness. As earlier, the two search strategies are proposed. Simulation experiments are carried out to validate the performance of the proposed search strategies. The simulation results indicate that both the proposed search strategies perform quite well even when the conditions deviated from the nominal. It is also shown that the combined deploy and search strategy leads to shorter and smoother trajectories than those of the sequential deploy and search strategy with the same parameters.

Les travaux de cette thèse s’articulent autour des « problèmes d’ordonnancement multiagent avec une fonction objectif globale ». Ces modèles considèrent différents agents associés à des sous-ensembles de travaux disjoints, chacun d’eux vise à minimiser un objectif qui ne dépend que de ses propres travaux. Un critère global est aussi considéré, qui est appliqué à la totalité des travaux. La résolution de ces problèmes revient à trouver les meilleurs compromis entre les critères des agents et le critère global. Ces problèmes sont une classe particulière des problèmes d’ordonnancement « multi-agents » qui ont connu une grande expansion, reflétant leurs intérêts dans le domaine de l’ordonnancement. / This thesis addresses the multi-agent scheduling problems with a global objective function. We consider the problems featured by various agents, each of which is associated with a distinct subset of jobs. Each agent aims at minimizing a certain objective function, which only operates on its assigned jobs. A global criterion associated with a global agent is applied on the whole set of the jobs. Solving these problems involves finding the best compromises between the requirements of agents and that of the global agent. These problems belong to a particular class of multi-criteria scheduling problems. Such a class has drawn a significant interest to researchers in the area of scheduling and operational research.