Submitted by Fabricia Fialho Reginato (fabriciar) on 2015-06-17T01:05:19Z No. of bitstreams: 1 AndersonCruz.pdf: 7416070 bytes, checksum: 04604058e57f063a3ae4859f4aef2c09 (MD5) / Made available in DSpace on 2015-06-17T01:05:19Z (GMT). No. of bitstreams: 1 AndersonCruz.pdf: 7416070 bytes, checksum: 04604058e57f063a3ae4859f4aef2c09 (MD5) Previous issue date: 2011 / Nenhuma / A cada ano, a informação ganha mais importância no meio corporativo e a utilização de sistemas de tecnologia de informação é cada vez mais comum em empresas dos mais diversos segmentos. No entanto, estes sistemas são compostos por aplicações que são sujeitas a vulnerabilidades que podem comprometer a confidencialidade, integridade e disponibilidade, ou seja, a segurança destas informações. Fornecedores de tecnologia estão sempre corrigindo falhas em suas ferramentas e disponibilizando correção para seu produtos para que estes se tornem mais seguros. O processo de correção de uma falha leva um determinado tempo até que o cliente possa atualizar o seu sistema. Muitas vezes este tempo não é suficiente para evitar um incidente de segurança, o que torna necessário soluções de contorno para diminuir riscos referentes aos aplicativos vulneráveis. O processo de análise/avaliação na Gestão de Riscos prioriza as ações que são tomadas para mitigar estes riscos. Este processo é árduo, envolvendo a identificação de vulnerabilidades para as aplicações utilizadas na empresa, sendo que o número de vulnerabilidades aumenta diariamente. Para apoiar na análise de riscos de tecnologia da informação, este trabalho propõe um método para geração automática de uma Rede Bayesiana baseado em sistemas multiagentes. O sistema multiagente conta com quatro agentes, sendo um destinado a monitorar as vulnerabilidades na National Vulnerability Database, outro para monitorar os ativos que compõem o negócio da organização, outro para monitorar os incidentes ocorridos no ambiente da organização e outro, destinado a reunir todas estas informações com o intuindo de determinar um fator de risco para os ativos da organização. Este último agente utiliza Redes Bayesianas para determinar o risco dos ativos. O método proposto mostrou-se eficiente para identificar mudanças no ambiente da organização e alterar o risco dos ativos de acordo com os diversos fatores que influenciam no seu cálculo, como o surgimento e/ou alteração de uma vulnerabilidade, surgimento e/ou alteração na base de dados de configuração de ativos da organização e identificação e/ou alteração no relato de incidentes de segurança no ambiente da empresa. Este resultado deve-se a utilização de Redes Bayesianas para calcular o risco dos ativos, visto que esta é capaz de considerar a relação causal entre os ativos da organização. / Every year information gains more significance in the corporative scenario and information technology system use is incresingly more commom on different segment companies. However, these systems are composed by applications that are under vulnerabilities that can compromise the confidentiality, integrity and availability, i.e. infomation security. Technology providers are always correcting flaws in their tools and providing it for their products in order for them to be safer. The flaw correction process considers some time until the client update his system. Many times this window is not enough to avoid a security incident, which turns necessary workarounds for minimizing risks concerning these vulnerable applications. The risks evaluation/analysis process aims primarily actions to mitigate these risks. This process is ardous, involving the identification of vulnerabilities in the used applications of a company, with this number growing each day. For supporting the information technology risks evaluation/analysis, a method for automated generation of a Bayesian Network multiagent system was proposed. This system is composed by four agents, one being destinated to monitoring vulnerabilities in National Vulnerability Database, another one for monitoring actives that compose the organition business, another one is responsible for to monitor the incidents occured in the organization enviroment and another one to gather all these information with the objective of determining a risk factor for the organization actives. The last one uses a Bayesian Network in order to determine the risk factor for the organization actives. The proposed method has shown to be effective in the identification of enviroment changes and in the changing of active risks according with several factors that influence its calculation, such as the emergence or changing of vulnerabilities, emergence or alteration on the business organization actives configuration database or identification and alteration of security incidents report on the company enviroment.

This dissertation presents a cartographic approach to the dynamic vehicle routing problem with time windows and stochastic customers (DVRPTWSC). The objectives are to minimize the total travel time and maximize the number of new requests served. Addressing the DVRPTWSC requires solving the vehicle routing problem with time windows (VRPTW). A memetic algorithm (MA) for the VRPTW is proposed. The MA prunes the search space using the information gathered by a clustering procedure, which is applied to customers spatial data. The cartographic approach to the DVRPTWSC is incorporated into a multiagent system where a dispatcher agent plans the routes for vehicle agents. Before creating the initial routing plan, a cartographic processing is applied. This procedure uses hierarchical clustering to divide the region where customers are located into a hierarchy of nested regions. The initial routing plan considers known requests and potential requests sampled from known probability distributions. It is created using the search operators of the MA, which in turn use the information obtained from the hierarchical clustering to perform the search. Over the planning horizon, the dispatcher updates the routing plan: Potential requests that were included in the initial routing plan and do not materialize are removed and new requests are processed using the assignation of requests based on nested regions (ARNR). The ARNR procedure is aimed at reducing the number of vehicles considered for serving new requests. It tries to assign the requests among the vehicles that can serve them at low detour costs. The nested regions created in the cartographic processing are used to identify such vehicles. Experimental results show that the proposed MA performs competitively with state-of-the-art heuristics for the VRPTW. The proposed approach to the DVRPTWSC outperforms approaches that do not include potential requests in the initial routing plan. The use of the ARNR procedure significantly reduces the number of vehicles considered for serving new requests, and it yields solutions similar to those obtained when considering all vehicles in operation. The proposed approach performs consistently under three levels of dynamism: low, medium, and high. / Esta dissertação apresenta uma abordagem cartográfica para o problema de roteamento de veículos dinâmico com janelas de tempo e clientes estocásticos (DVRPTWSC, por sua sigla em inglês). Os objetivos considerados são minimizar o tempo total de viagem e maximizar o número de pedidos novos atendidos. Para abordar o DVRPTWSC é necessário resolver o problema de roteamento de veículos com janelas de tempo (VRPTW, por sua sigla em inglês). Assim, para tratar o VRPTW propõe-se um algoritmo memético (MA, por sua sigla em inglês). O MA reduz o espaço de busca usando informação obtida por meio de um procedimento de clusterização, o qual é aplicado aos dados espaciais dos clientes. Para o DVRPTWSC, a abordagem cartográfica é incorporada em um sistema multiagente, no qual um agente roteirizador planeja as rotas para os agentes veículos. O processamento cartográfico é aplicado antes de criar o plano de rotas inicial para o DVRPTWSC. Este procedimento usa clusterização hierárquica para dividir a região onde estão os clientes em uma hierarquia de regiões encaixadas. O plano de rotas inicial considera pedidos conhecidos e pedidos potenciais amostrados de distribuições de probabilidade conhecidas. Para obter o plano de rotas inicial, usam-se os operadores de busca do MA, os quais utilizam a informação obtida da clusterização hierárquica para fazer a busca. Ao longo do horizonte de planejamento, o roteirizador atualiza o plano de rotas: Pedidos potenciais que foram considerados no plano de rotas inicial e que não foram consolidados são removidos e novos pedidos são incluídos usando o procedimento assignation of requests based on nested regions (ARNR). O procedimento ARNR visa reduzir o número de veículos considerados para atender novos pedidos. Para isso, tenta designar os novos pedidos aos veículos disponíveis para o atendimento que possuem os menores custos de desvio da rota pré-determinada. As regiões encaixadas criadas no processamento cartográfico são utilizadas para identificar esses veículos. Para o VRPTW, resultados experimentais mostram que o MA proposto é competitivo com métodos do estado da arte. A abordagem proposta para o DVRPTWSC supera abordagens que não incluem pedidos potenciais no plano de rotas inicial. O uso do procedimento ARNR reduz significativamente o número de veículos considerados para atender novos pedidos, e produz soluções similares às produzidas quando se consideram todos os veículos em operação. A abordagem desenvolvida para o DVRPTWSC tem um desempenho consistente para três níveis de dinamismo: baixo, médio e alto.

One of the main challenges posed by 4G wireless communication systems is achieving flexible, programmable multi-standard radio transceivers with maximum hardware share amongst different standards at a minimum power consumption. Evaluating the feasibility and performance of different multi-standard/multi-band radio solutions at an early stage, i.e. system level, is key for succeeding in surmounting this challenge. This entails for- mulation of the transceiver budget for several RF architectures and frequency plans with different degrees of hardware sharing. This task is complicated by the fact that transceiver blocks can have different implementations that lead to different performances. The tools that are available for use at present have only analysis capabilities or address only one standard and/or receiver architecture at a time.In the belief that a new approach to this problem is necessary, the work that has led to this thesis proposes a novel methodology that automates the design-space explo- ration of integrated multi-standard wireless radio receivers. This methodology has been implemented in a multi-standard RF Transceiver Architecture Comparison Tool, TACT. TACT helps surmounting many of the challenges faced by RF system designers targeting multi-standard/multi-band radio receivers.The goal of the algorithms TACT is built upon is to find a multi-standard receiver frequency plan and budget that meets or exceeds the specifications of the addressed wire- less standards while keeping the requirements of each of the receiver blocks as relaxed as possible. TACT offers RF engineers a deep insight into the receiver behavior at a very early stage of the design flow. It models the impact of critical circuit non-idealities using a high level of abstraction. This reduces the number of design iterations and, thus, the time-to-market of the solution. The reuse of already available intellectual property (IP) blocks is also considered in TACT, what can result in a significant cost reduction of the receiver implementation. A combination of a behavioural-based cooperative multi-agent optimization and deterministic techniques is proposed.The capabilities of the proposed techniques and developed tool are illustrated through case studies addressing different design challenges the design of multi-standard receivers present.The last part of this thesis is devoted to one of the key blocks of any communica- tions receiver: the analog-to-digital converter. This work focuses on modeling and design methodologies for continuous-time ΔΣ modulators. A method to evaluate the stability margin of continuous-time ΔΣ modulators as a function of the timing uncertainty effects is proposed. / QC 20100907 / RaMSiS

In this thesis, we investigate a special class of multi-agent systems, which we call reciprocal multi-agent (RMA) systems. The evolution of agents in a RMA system is governed by interactions between pairs of agents. Each interaction is reciprocal, and the magnitude of attraction/repulsion depends only on distances between agents. We investigate the class of RMA systems from four perspectives, these are two basic properties of the dynamical system, one formula for computing the Morse indices/co-indices of critical formations, and one formation control model as a variation of the class of RMA systems. An important aspect about RMA systems is that there is an equivariant potential function associated with each RMA system so that the equations of motion of agents are actually a gradient flow. The two basic properties about this class of gradient systems we will investigate are about the convergence of the gradient flow, and about the question whether the associated potential function is generically an equivariant Morse function. We develop systematic approaches for studying these two problems, and establish important results. A RMA system often has multiple critical formations and in general, these are hard to locate. So in this thesis, we consider a special class of RMA systems whereby there is a geometric characterization for each critical formation. A formula associated with the characterization is developed for computing the Morse index/co-index of each critical formation. This formula has a potential impact on the design and control of RMA systems. In this thesis, we also consider a formation control model whereby the control of formation is achieved by varying interactions between selected pairs of agents. This model can be interpreted in different ways in terms of patterns of information flow, and we establish results about the controllability of this control system for both centralized and decentralized problems. / Engineering and Applied Sciences

The design of public transport system must take into account different dimensions to solve two main problems of optimization: the vehicles scheduling and driver scheduling. In our work, we focused on bus driver scheduling. Its objective is to minimize the number of drivers in accordance with social and environmental constraints. By its combinatorial nature, bus driver scheduling is considered a complex task in the design process of network transport. We have proposed an approach based on hyper-heuristics whose main advantage lies in their ability to adapt to different problems. We are particularly interested in a cooperative approach, which is able to take into account changes in the resolution process. We have extended the functionality and improved performance of the traditional framework of hyper- heuristics by proposing a pattern based on an organizational model. The proposed algorithm consists of a combination of several phases and several levels. The metaphor of the coalition is used to make cooperate several hyper-heuristics. The coalition is intended to favor diversified solutions and expand search capacity with decentralized control where each hyper-heuristic has certain autonomy. It is thus possible to consider different ways of cooperation between the hyper-heuristics: sharing solutions, learning by mimetism or carrying out different competitive search strategies. The experiment was carried out both on real-world instances and benchmarks. It gave good results on both quality of solution and execution time

Uma importante parte de um sistema multiagente é o seu mecanismo de coordenação que permite que os agentes possam agir de maneira coesa em direção aos seus objetivos, sejam eles individuais ou coletivos. Um agente pode optar por cooperar para atingir um determinado objetivo que seria inalcançável através de ações individuais, para realizar uma tarefa de maneira mais eficiente ou simplesmente porque ele foi projetado para tal. Em todos os casos, a formação de coalizões (grupos de agentes que concordam em coordenar suas ações em torno de um objetivo comum) é uma questão fundamental. O problema de geração de estruturas de coalizão entre agentes (conjunto de todas as combinações de coalizões) é um tópico de pesquisa que recebeu muita atenção principalmente na resolução do problema quando considerado como um jogo de função característica, onde o valor das coalizões independe dos agentes que não estão presentes nela. Essa abordagem, apesar de ser indicada para muitos tipos de problema, não cobre toda a área de pesquisa do assunto, visto que em muitos casos a criação de uma coalizão irá afetar os demais agentes do sistema. Quando o sistema possui agentes com objetivos sobrepostos ou contrários, uma coalizão cujos recursos são destinados a completar tais objetivos irá influenciar as demais coalizões desse sistema. Essa influência se chama externalidade e, nesses casos, o problema de formação de estruturas de coalizão deve ser tratado como um jogo de partição. Apesar das pesquisas na área de jogos de partição serem recentes, elas trazem resultados promissores e há alguns poucos algoritmos já desenvolvidos para buscar soluções a esse problema. A busca pela melhor estrutura de coalizão geralmente demanda que seja calculado o valor de todas possíveis coalizões, a fim de se encontrar aquele conjunto cuja soma dos valores das coalizões forneça o melhor resultado. Esse processo requer um alto número de computações e de memória, devido à natureza exponencial do problema. Assim, ao invés de apenas um agente central realizar todas as operações, é mais eficiente do ponto de vista do uso de recursos computacionais distribuir essas operações entres os diversos agentes presentes no sistema. Além dos benefícios computacionais, distribuir o processo de busca pela melhor estrutura de coalizão permitiria trabalhar com questões como privacidade e tolerância a falhas, tendo em vista que as informações não estão concentradas em um único agente. Apesar disso, não há na literatura qualquer algoritmo capaz de solucionar o problema de geração de estrutura de coalizão em ambientes distribuídos e que sejam modelados como jogos de partição. A proposta desse trabalho é utilizar a fundamentação teórica existente acerca do problema de formação de estruturas de coalizão (modelados tanto como jogos de função característica quanto como jogos de partição) para criar um algoritmo distribuído capaz de encontrar a estrutura de coalizão ótima em ambientes que possuam externalidade. Esse algoritmo utiliza como base a ordenação das coalizões e dos agentes para permitir a distribuição do cálculo dos limites superiores e inferiores de cada coalizão. Após, esses valores são utilizados para se encontrar o subespaço mais provável de conter a estrutura de coalizão ótima. Com base nos experimentos, percebe-se que o algoritmo encontrou a estrutura de coalizão ótima buscando em apenas uma pequena parte do espaço de busca. Para os experimentos com 16 agentes, o algoritmo foi capaz de encontrar a solução ótima procurando em apenas 0,01% do espaço de busca. Também, é demonstrado que em cenários com externalidade negativa os agentes necessitaram investigar um espaço de busca menor para encontrar a estrutura de coalizão ótima que em cenários com externalidade positiva. Experimentos também demonstram que o algoritmo não consegue encontrar a estrutura de coalizão ótima quando há falhas na comunicação entre os agentes. / An important part of a multi-agent system is its coordination mechanism that allows the agents to act cohesively towards their goals, whether individual or collective. An agent can choose to cooperate to achieve a certain goal that would be unattainable through individual actions, to perform a task more efficiently or simply because it was designed to do so. In all cases, the formation of coalitions (group of agents that agree to coordinate their actions around a common goal) is a key issue. The problem of generating coalition structures between agents (set of all combinations of coalitions) is a research topic that has received much attention mostly on solving the problem when considered as a characteristic function game, where the value of coalitions is independent of agents that are not part of it. This approach, although suitable for many types of problem, does not cover the whole area of research on the subject, since in many cases the creation of a coalition will affect the other agents of the system. When the system has agents with overlapping goals or opposing goals, a coalition whose resources are devoted to completing these objectives will influence the other coalitions of that system. This influence is called externality, and in these cases, the problem of formation of coalition structures should be treated as a partition function game. Although research in the area of partition games is recent, it brings promising results and there are few algorithms already developed to find solutions to this problem. The search for the best coalition structure generally requires computation of the value of all possible coalitions in order to find the set that the sum of the values of the coalitions provides the best result. This process requires a large number of computations and memory due to the exponential nature of the problem. Hence, instead of just one central agent performing all operations, it is more efficient to distribute those operations among several agents. Besides the computational benefits, distributing the search process for the best coalition structure would address issues such as privacy and fault tolerance, given that the information is not concentrated in a single agent. Nevertheless, in the literature there is not algorithm capable of solving the problem of coalition structure generation in decentralized environments and modeled as partition function game. The purpose of this work is to use the existing theoretical foundations for solving the coalition structure generation problem (modeled both as a characteristic function game and as a partition function game) to create a distributed algorithm capable of finding the optimal coalition structure in environments that have externality. This algorithm uses as a base the ordering of coalitions and agents to distribute the calculation of the upper and lower limits for each coalition. Afterwards, these values are used to find the subspace more likely to contain the optimal coalition structure. Based on experiments, the algorithm found the optimal coalition structure searching only a small part of the search space. For the experiments with 16 agents, the algorithm was able to find the solution looking at just 0.0001%of the search space. Also, it is shown that in scenarios with negative externality agents need to investigate a smaller search space to find the optimal coalition structure than in scenarios with positive externality. Experiments also show that the algorithm can not find the optimal coalition structure when there are failures in the communication among the agents.

Doctor of Philosophy / Electrical and Computer Engineering / Balasubramaniam Natarajan / A cyber-physical system (CPS) typically consists of networked computational elements that control physical processes. As an integral part of CPS, the widespread deployment of communicable sensors makes the task of monitoring and control quite challenging especially from the viewpoint of scalability and complexity. This research investigates two unique aspects of overcoming such barriers, making a CPS more robust against data explosion and network vulnerabilities. First, the correlated characteristics of high-resolution sensor data are exploited to significantly reduce the fused data volume. Specifically, spatial, temporal and spatiotemporal compressed sensing approaches are applied to sample the measurements in compressed form. Such aggregation can directly be used in centralized static state estimation even for a nonlinear system. This approach results in a remarkable reduction in communication overhead as well as memory/storage requirement. Secondly, an agent based architecture is proposed, where the communicable sensors (identified as agents) also perform local information processing. Based on the local and underdetermined observation space, each agent can monitor only a specific subset of global CPS states, necessitating neighborhood information exchange. In this framework, we propose an agent based static state estimation encompassing local consensus and least square solution. Necessary bounds for the consensus weights are obtained through the maximum eigenvalue based convergence analysis and are verified for a radial power distribution network. The agent based formulation is also applied for a linear dynamical system and the consensus approach is found to exhibit better and more robust performance compared to a diffusion filter. The agent based Kalman consensus filter (AKCF) is further investigated, when the agents can choose between measurements and/or consensus, allowing the economic allocation of sensing and communication tasks as well as the temporary omission of faulty agents. The filter stability is guaranteed by deriving necessary consensus bounds through Lyapunov stability analysis. The states dynamically estimated from AKCF can be used for state-feedback control in a model predictive fashion. The effect of lossy communication is investigated and critical bounds on the link failure rate and the degree of consensus that ensure stability of the agent based control are derived and verified via simulations.

Uma importante parte de um sistema multiagente é o seu mecanismo de coordenação que permite que os agentes possam agir de maneira coesa em direção aos seus objetivos, sejam eles individuais ou coletivos. Um agente pode optar por cooperar para atingir um determinado objetivo que seria inalcançável através de ações individuais, para realizar uma tarefa de maneira mais eficiente ou simplesmente porque ele foi projetado para tal. Em todos os casos, a formação de coalizões (grupos de agentes que concordam em coordenar suas ações em torno de um objetivo comum) é uma questão fundamental. O problema de geração de estruturas de coalizão entre agentes (conjunto de todas as combinações de coalizões) é um tópico de pesquisa que recebeu muita atenção principalmente na resolução do problema quando considerado como um jogo de função característica, onde o valor das coalizões independe dos agentes que não estão presentes nela. Essa abordagem, apesar de ser indicada para muitos tipos de problema, não cobre toda a área de pesquisa do assunto, visto que em muitos casos a criação de uma coalizão irá afetar os demais agentes do sistema. Quando o sistema possui agentes com objetivos sobrepostos ou contrários, uma coalizão cujos recursos são destinados a completar tais objetivos irá influenciar as demais coalizões desse sistema. Essa influência se chama externalidade e, nesses casos, o problema de formação de estruturas de coalizão deve ser tratado como um jogo de partição. Apesar das pesquisas na área de jogos de partição serem recentes, elas trazem resultados promissores e há alguns poucos algoritmos já desenvolvidos para buscar soluções a esse problema. A busca pela melhor estrutura de coalizão geralmente demanda que seja calculado o valor de todas possíveis coalizões, a fim de se encontrar aquele conjunto cuja soma dos valores das coalizões forneça o melhor resultado. Esse processo requer um alto número de computações e de memória, devido à natureza exponencial do problema. Assim, ao invés de apenas um agente central realizar todas as operações, é mais eficiente do ponto de vista do uso de recursos computacionais distribuir essas operações entres os diversos agentes presentes no sistema. Além dos benefícios computacionais, distribuir o processo de busca pela melhor estrutura de coalizão permitiria trabalhar com questões como privacidade e tolerância a falhas, tendo em vista que as informações não estão concentradas em um único agente. Apesar disso, não há na literatura qualquer algoritmo capaz de solucionar o problema de geração de estrutura de coalizão em ambientes distribuídos e que sejam modelados como jogos de partição. A proposta desse trabalho é utilizar a fundamentação teórica existente acerca do problema de formação de estruturas de coalizão (modelados tanto como jogos de função característica quanto como jogos de partição) para criar um algoritmo distribuído capaz de encontrar a estrutura de coalizão ótima em ambientes que possuam externalidade. Esse algoritmo utiliza como base a ordenação das coalizões e dos agentes para permitir a distribuição do cálculo dos limites superiores e inferiores de cada coalizão. Após, esses valores são utilizados para se encontrar o subespaço mais provável de conter a estrutura de coalizão ótima. Com base nos experimentos, percebe-se que o algoritmo encontrou a estrutura de coalizão ótima buscando em apenas uma pequena parte do espaço de busca. Para os experimentos com 16 agentes, o algoritmo foi capaz de encontrar a solução ótima procurando em apenas 0,01% do espaço de busca. Também, é demonstrado que em cenários com externalidade negativa os agentes necessitaram investigar um espaço de busca menor para encontrar a estrutura de coalizão ótima que em cenários com externalidade positiva. Experimentos também demonstram que o algoritmo não consegue encontrar a estrutura de coalizão ótima quando há falhas na comunicação entre os agentes. / An important part of a multi-agent system is its coordination mechanism that allows the agents to act cohesively towards their goals, whether individual or collective. An agent can choose to cooperate to achieve a certain goal that would be unattainable through individual actions, to perform a task more efficiently or simply because it was designed to do so. In all cases, the formation of coalitions (group of agents that agree to coordinate their actions around a common goal) is a key issue. The problem of generating coalition structures between agents (set of all combinations of coalitions) is a research topic that has received much attention mostly on solving the problem when considered as a characteristic function game, where the value of coalitions is independent of agents that are not part of it. This approach, although suitable for many types of problem, does not cover the whole area of research on the subject, since in many cases the creation of a coalition will affect the other agents of the system. When the system has agents with overlapping goals or opposing goals, a coalition whose resources are devoted to completing these objectives will influence the other coalitions of that system. This influence is called externality, and in these cases, the problem of formation of coalition structures should be treated as a partition function game. Although research in the area of partition games is recent, it brings promising results and there are few algorithms already developed to find solutions to this problem. The search for the best coalition structure generally requires computation of the value of all possible coalitions in order to find the set that the sum of the values of the coalitions provides the best result. This process requires a large number of computations and memory due to the exponential nature of the problem. Hence, instead of just one central agent performing all operations, it is more efficient to distribute those operations among several agents. Besides the computational benefits, distributing the search process for the best coalition structure would address issues such as privacy and fault tolerance, given that the information is not concentrated in a single agent. Nevertheless, in the literature there is not algorithm capable of solving the problem of coalition structure generation in decentralized environments and modeled as partition function game. The purpose of this work is to use the existing theoretical foundations for solving the coalition structure generation problem (modeled both as a characteristic function game and as a partition function game) to create a distributed algorithm capable of finding the optimal coalition structure in environments that have externality. This algorithm uses as a base the ordering of coalitions and agents to distribute the calculation of the upper and lower limits for each coalition. Afterwards, these values are used to find the subspace more likely to contain the optimal coalition structure. Based on experiments, the algorithm found the optimal coalition structure searching only a small part of the search space. For the experiments with 16 agents, the algorithm was able to find the solution looking at just 0.0001%of the search space. Also, it is shown that in scenarios with negative externality agents need to investigate a smaller search space to find the optimal coalition structure than in scenarios with positive externality. Experiments also show that the algorithm can not find the optimal coalition structure when there are failures in the communication among the agents.

Aujourd’hui, la compétition croissante, l'expansion des marchés et les progrès de la technologie engendrent un raccourcissement du cycle de vie des processus de développement des produits afin d’en améliorer les performances en termes de délai, coût et qualité. Ce raccourcissement du cycle de vie a engendré un accroissement des volumes de déchet généré et des conséquences que cela peut avoir sur l’environnement. Au niveau de l’Union européenne, des directives ont été introduites, tels que la gestion des déchets d'équipements électriques et électroniques (WEEE), la restriction de l'utilisation de certaines substances dangereuses dans les équipements électriques et électroniques (RoHS) et les directives pour le traitement des batteries usagées (Battery); ces directives permettent de limiter l'utilisation et le recyclage des substances dangereuses nocives pour la santé et pour l'environnement.Ces nouvelles réglementations et normes, permettant de gérer de manière efficace les retours et la fin de vie des produits (recovery process), ont été mises en place afin d'obliger les entreprises à assumer leurs responsabilités en termes de gestion des produits en fin de vie. Certaines entreprises ont montré que les produits recyclés ou réutilisés peuvent être une source supplémentaire de revenu (recyclage des matériaux, ou réutilisation des composants après démontage) dans le processus de fabrication.Ces connaissances liées à la performance environnementale (au niveau des processus de conception, de production, de transport, d’entreposage, de récupération…) devraient êtres saisies, évaluées et capitalisées dans des bases de connaissances afin d’être prisent en compte durant les différents phases du cycle de vie des produits.Nos travaux de recherche proposent donc de développer une architecture de gestion des connaissances (Knowledge Management Architecture) basée sur un Système Multi-Agents. L’objectif est de proposer un système qui met l'accent sur les concepts de « durabilité des produits et des cycles de vie », en établissant des liens entre des Agents Logiciels détenteurs de connaissances liées à la réglementation environnementale et les Systèmes d’Information de type PLM. Ces interconnexions permettront aux décideurs de prendre en compte les impacts environnementaux dans leurs décisions et ceci à chaque phase du cycle de vie des produits. / The increasing of competition, expanding markets and advanced technology create shorten lifecycle and the development process to improve product performance in terms of time, cost and quality. These shorten products lifecycle have led to increase volumes of waste generation and consequence impact to environment. EU directives have been introduced, such as Waste Electrical and Electronic Equipment (WEEE), Restriction of the use of certain Hazardous Substances in electrical and electronic equipment (RoHS) and guidelines for the treatment of waste batteries (Battery), these directives are used to handle the hazardous substances which are harmful to human health and the environment.These regulations and standards have been put in place to force companies take their responsibilities on managing their products when reach to the end of life. Some companies have found that the returned product can be recycled or reused as an additional source of income (material recycling, or reuse of components after disassembly) in the manufacturing process.Knowledge related to the environmental performance (in terms of process design, production, transportation, storage, etc.) should be captured, evaluated and stored in knowledge base in order to share between users in different phases of the product lifecycle.Therefore, this research proposes a Knowledge Management Architecture based on a Multi-Agent System approach. The objective of this work is to propose a system that focuses on the concept of "sustainability” of products lifecycle by establishing the link between agents, who hold knowledge related to the environmental performances, and PLM system. The connection encourages companies considering the environmental impacts in their decision making at every stage of product lifecycle.

Ces dernières années, les progrès en sciences de la gestion et de l’information ont transformé la Gestion de Processus d’Affaires (Business Process Management, BPM) en un sujet important, tant du côté de l’industrie que de celui de la recherche. Le BPM utilise des processus métiers pour améliorer la performance opérationnelle des organisations. Les processus métiers établissent un lien entre les personnes, les systèmes, et les différentes organisations, dans le but de créer de la valeur pour les parties prenantes. La cible de notre travail est la famille des systèmes BPM. Un système BPM est un système logiciel générique guidé par des modèles explicites de processus métier avec pour objectif d’exécuter et de gérer des processus opérationnels. Malgré le vaste éventail de sujets traités par ce domaine de recherche, il reste encore quelques questions qui méritent une étude plus approfondie. Un problème particulier concerne la médiation entre les systèmes BPM et les humains. L’interaction homme-machine dans ces systèmes repose sur des interfaces standard basées sur des listes de taches et des formulaires, ce qui est très contraignant pour les utilisateurs.Ceux-ci ont non seulement des difficultés à exécuter leurs processus métier, mais aussi a trouver le processus métier le mieux adapté à leurs besoins. Il serait beaucoup plus efficace d’utiliser des dialogues en langage naturel. Malheureusement les langages de modélisation de processus ne permettent pas de capturer ni de modéliser un domaine de discours. Le travail présent propose une approche originale de gestion du dialogue basée sur des systèmes multi-agents pour l’exécution des processus métier. La motivation globale pour ce travail fut de concevoir un modèle de dialogue extensible à différents domaines. Ce modèle s’appuie sur les ontologies de domaine, nécessitant un minimum d’effort d’adaptation pour améliorer l’interaction. Les résultats montrent tout le potentiel de notre approche multi-agent pour réaliser une médiation automatiquement, sans qu’il soit nécessaire de reconstruire les modèles de processus métier. / Over the last few years, the advances in management science and information technology have transformed the business process management (BPM) discipline into an important topic for both industry and academy. BPM uses business processes as the means for improving the operational performance of organizations, and setting processes are at the heart of BPM allows linking together people, systems, and different organizations to deliver value to stakeholders. The target of our work is the family of BPM systems. A BPM system is a generic software system that is driven by explicit process designs to enact and manage operational business processes. Despite the wide range of topics addressed by the academy on business processes, there are still aspects not addressed by prior research. A particular problem in this regard is the mediation between BPM systems and humans. Human interaction in those systems follows a standard user interface based predominantly on work item lists and forms. Thus, there is little room for creativity for users. They have not only difficulties in enacting their processes but also for searching the most suitable one for their needs. It would be more efficient to let humans interact in natural language. However, process modeling languages are an insufficient means of capturing and representing the domain of discourse. The present thesis develops an original approach to agent dialog management for the problem of business process enactment. The overarching motivation for this work was to design a dialog model scalable to different domains. The model relies on domain and business process ontologies, and necessitates a minimum effort of adaptation on ontologies to improve the interaction. Results indicate the potential of our agent-based approach to generate natural language.