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.

Real-Time Optimization (RTO) is a family of techniques that pursue to improve the performance of chemical processes. As general scheme, the method reevaluates the process conditions in a frequent basis and tries to adjust some selected variables, taking into account the plant state, actual operational constraints and optimization objectives. Several RTO approaches have born from the academy research and industrial practices, at the same time that more applications have been implemented in real facilities. Between the main motivations to apply RTO are the dynamic of markets, the seek for quality in the process results and environmental sustainability. That is why the interest on deeply understand the phases and steps involved in an RTO application has increased in recent years. Nevertheless, the fact that most of the existing RTO systems have been developed by commercial organizations makes it difficult to meet that understanding. This work studies the nature of RTO systems from a software point of view. Software requirements for a generic system are identied. Based on that, a software architecture is proposed that could be adapted for specfic cases. Benefits of the designed architecture are listed. At the same time, the work proposes a new approach to implement that architecture as a Multi-Agent System (MAS). Two RTO system prototypes were developed then, one for a well-know academic case study and the other oriented to be used in a real unit. The benefits of the MAS approach and the architecture, for researching on the RTO field and implementation on real plants, are analyzed in the text. A sub-product of the development, a software framework covering main concepts from the RTO ontology, is proposed as well. As the framework was designed to be generic, it can be used in new applications development and extended to very specific scenarios. / Otimização em Tempo Real (OTR) é uma família de técnicas que buscam melhorar o desempenho dos processos químicos. Como esquema geral, o método reavalia frequentemente as condições do processo e tenta ajustar algumas variáveis selecionadas, levando em considera ção o estado da planta, restrições operacionais e os objetivos da otimização. Várias abordagens para OTR t^em surgido da pesquisa acadêmica e das práticas industriais, ao mesmo tempo em que mais aplicações têm sido implementadas em plantas reais. As principais motivações para aplicar OTR são: a dinâmica dos mercados, a busca de qualidade nos resultados dos processos e a sustentabilidade ambiental. É por isso que o interesse em entender as fases e etapas envolvidas em uma aplicação OTR cresceu nos últimos anos. No entanto, o fato de que a maioria dos sistemas OTR em operação foram desenvolvidos por organizações comerciais dificulta o caminho para chegar nesse entendimento. Este trabalho analisa a natureza dos sistemas OTR desde o ponto de vista do software. Os requerimentos para um sistema genérico são levantados. Baseado nisso, é proposta uma arquitetura de software que pode ser adaptada para casos específicos. Os benefícios da arquitetura projetada foram listados. Ao mesmo tempo, o trabalho propõe uma nova abordagem para implementar essa arquitetura: Sistema Multi-Agentes (SMA). Dois protótipos de sistema OTR foram desenvolvidos. O primeiro aplicado num estudo de caso bem conhecido na literatura acadêmica. O segundo voltado para ser usado em uma unidade industrial. Os benefícios da abordagem SMA e da arquitetura, tanto na pesquisa relacionada com OTR, quanto na implementação em plantas reais, são analisados no texto. Um arcabouço de software que abrange os principais conceitos da ontologia OTR é proposto como resultado derivado do desenvolvimento. O arcabouço foi projetado para ser genérico, possibilitando seu uso no desenvolvimento de novas aplicações OTR e sua extensão a cenários muito específicos.

Multi-agent systems have been used in a wide range of applications from computer-based simulations and mobile robots to agent-oriented programming and intelligent systems in real environments. However, the largest environment in which software agents can interact is, without any doubt, the World Wide Web and ever since its birth agents have been used in various applications such as search engines, e-commerce, and most recently the semantic web. However, agents have yet to be used on the Web in a way that leverages the full power of artificial intelligence and multi-agent systems, which have the potential of making life much easier for humans. This thesis investigates how this can be changed, and how agents can be brought to the core of the online experience in the sense that we want people to talk and interact with agents instead of "just using yet another application or website". We analyze what makes it hard to develop intelligent agents on the web and we propose a web agent model (WAM) inspired by recent results in multi-agent systems. Nowadays, a simple conceptual model is the key for widespread adoption of new technologies and this is why we have chosen the MASQ meta-model as the basis for our approach, which provides the best compromise in terms of simplicity of concepts, generality and applicability to the web. Since until now the model was introduced only in an informal way, we also provide a clear formalization of the MASQ meta-model.Next, we identify the three main challenges that need to be addressed when building web agents: integration of bodies, web semantics and user friendliness. We focus our attention on the first two and we propose a set of principles to guide the development of what we call strong web agents. Finally, we validate our proposal through the implementation of an award winning platform called Kleenk. Our work is just a step towards fulfilling the vision of having intelligent web agents mediate the interaction with the increasingly complex World Wide Web. / Multi-agent systems have been used in a wide range of applications from computer-based simulations and mobile robots to agent-oriented programming and intelligent systems in real environments. However, the largest environment in which software agents can interact is, without any doubt, the World Wide Web and ever since its birth agents have been used in various applications such as search engines, e-commerce, and most recently the semantic web. However, agents have yet to be used on the Web in a way that leverages the full power of artificial intelligence and multi-agent systems, which have the potential of making life much easier for humans. This thesis investigates how this can be changed, and how agents can be brought to the core of the online experience in the sense that we want people to talk and interact with agents instead of "just using yet another application or website". We analyze what makes it hard to develop intelligent agents on the web and we propose a web agent model (WAM) inspired by recent results in multi-agent systems. Nowadays, a simple conceptual model is the key for widespread adoption of new technologies and this is why we have chosen the MASQ meta-model as the basis for our approach, which provides the best compromise in terms of simplicity of concepts, generality and applicability to the web. Since until now the model was introduced only in an informal way, we also provide a clear formalization of the MASQ meta-model.Next, we identify the three main challenges that need to be addressed when building web agents: integration of bodies, web semantics and user friendliness. We focus our attention on the first two and we propose a set of principles to guide the development of what we call strong web agents. Finally, we validate our proposal through the implementation of an award winning platform called Kleenk. Our work is just a step towards fulfilling the vision of having intelligent web agents mediate the interaction with the increasingly complex World Wide Web.

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-03-26T18:03:05Z No. of bitstreams: 1 ARTUR_FREITAS_TES.pdf: 1489846 bytes, checksum: 61623f4503a4a916e72487f33c15e294 (MD5) / Approved for entry into archive by Tatiana Lopes (tatiana.lopes@pucrs.br) on 2018-04-06T16:46:51Z (GMT) No. of bitstreams: 1 ARTUR_FREITAS_TES.pdf: 1489846 bytes, checksum: 61623f4503a4a916e72487f33c15e294 (MD5) / Made available in DSpace on 2018-04-06T16:57:00Z (GMT). No. of bitstreams: 1 ARTUR_FREITAS_TES.pdf: 1489846 bytes, checksum: 61623f4503a4a916e72487f33c15e294 (MD5) Previous issue date: 2017-08-31 / A engenharia orientada a modelos fornece abstra??es e nota??es para melhorar a compreens?o e para apoiar a modelagem, codifica??o e verifica??o de aplica??es em dom?nios espec?ficos. As ontologias, por outro lado, fornecem defini??es formais e expl?citas de conceitualiza??es compartilhadas e permitem o uso de racioc?nio sem?ntico. Embora essas ?reas tenham sido desenvolvidas por diferentes comunidades, sinergias importantes podem ser alcan?adas quando ambas s?o combinadas. Essas vantagens podem ser exploradas no desenvolvimento de sistemas multiagentes, dada a sua complexidade e a necessidade de integrar v?rios componentes que s?o frequentemente abordados de diferentes ?ngulos. Este trabalho investiga como aplicar ontologias para engenharia de software orientada a agentes. Inicialmente, apresentamos uma nova abordagem de modelagem onde os sistemas multiagentes s?o projetados usando a ontologia OntoMAS proposta. Ent?o, descrevemos t?cnicas, implementadas em uma ferramenta, para ajudar os programadores a trazer seus conceitos em c?digo e tamb?m gerar c?digo automaticamente a partir de modelos instanciados da ontologia. V?rias vantagens podem ser obtidas a partir dessas novas abordagens para modelar e codificar sistemas multiagentes, como o racioc?nio sem?ntico para realizar infer?ncias e mecanismos de verifica??o. Mas a principal vantagem ? a linguagem de especifica??o unificada de alto n?vel (conhecimento) que permite modelar as tr?s dimens?es que est?o unidas em JaCaMo para que as especifica??es dos sistemas possam ser melhor comunicadas entre equipes em desenvolvimento. As avalia??es dessas propostas indicam que elas contribuem com os diferentes aspectos da engenharia de software orientada a agentes, como a especifica??o, verifica??o e programa??o desses sistemas. / Model-driven engineering provides abstractions and notations for improving the understanding and for supporting the modelling, coding, and verification of applications for specific domains. Ontologies, on the other hand, provide formal and explicit definitions of shared conceptualisations and enable the use of semantic reasoning. Although these areas have been developed by different communities, important synergies can be achieved when both are combined. These advantages can be explored in the development of multi-agent systems, given their complexity and the need for integrating several components that are often addressed from different angles. This work investigates how to apply ontologies for agentoriented software engineering. Initially, we present a new modelling approach where multiagent systems are designed using the proposed OntoMAS ontology. Then, we describe techniques, implemented in a tool, to help programmers bring their concepts into code and also generate code automatically from instantiated ontology models. Several advantages can be obtained from these new approaches to model and code multi-agent systems, such as semantic reasoning to carry out inferences and verification mechanisms. But the main advantage is the unified high (knowledge) level specification language that allows modelling the three dimensions that are united in the JaCaMo framework so that systems specifications can be better communicated across developing teams. The evaluations of these proposals indicate that they contribute with the different aspects of agent-oriented software engineering, such as the specification, verification, and programming of these systems.

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.