Redundancy Allocation Problem (RAP) is a well known mathematical problem for modeling series-parallel systems. It is a combinatorial optimization problem which focuses on determining an optimal assignment of components in a system design. Due to the diverse possible selection of components, the RAP is proved to be NP-hard. Therefore, many algorithms, especially heuristic algorithms were proposed and implemented in the past several decades, committed to provide innovative methods or better solutions. In recent years, multi-agent system (MAS) is proposed for modeling complex systems and solving large scale problems. It is a relatively new programming concept with the ability of self-organizing, self-adaptive, autonomous administrating, etc. These features of MAS inspire us to look at the RAP from another point of view. An RAP can be divided into multiple smaller problems that are solved by multiple agents. The agents can collaboratively solve optimal RAP solutions quickly and efficiently. In this research, we proposed to solve RAP using MAS. This novel approach, to the best of our knowledge, has not been proposed before, although multi-agent approaches have been widely used for solving other large and complex nonlinear problems. To demonstrate that, we analyzed and evaluated four benchmark RAP problems in the literature. From the results, the MAS approach is shown as an effective and extendable method for solving the RAP problems. / Electrical and Computer Engineering

Power networks are one of the most complex systems in the field of electrical and computer engineering. In power networks, power supply-demand balancing can be achieved in a static or a dynamic model. In a static model, the power network cannot be easily adapted to intentional or unintentional network topology changes because the network design is predetermined, whereas in a dynamic model, the power network can be dynamically constructed and reconfigured at run-time, which leads to a more nimble, flexible, and stable system. In this dissertation, a novel Market-based Multi-agent System (MMS) is proposed to solve supply-demand balancing and power restoration problems in a dynamic model. The power network is modeled as a market environment consisting of Belief-Desire-Intention (BDI) agents representing three characters: 1) consumer, 2) supplier, and 3) middleman. The BDI agents are able to negotiate power supply and demand of the power network, with consumers exploring the market and exchanging power information with neighboring middlemen and suppliers. So long as all consumers and suppliers establish supply-demand relationships represented in tree data structures, a qualified minimal access structure is found as the lower bound of the system reliability. When contingencies occur, the agents can quickly respond and restore loads guided by the relationships using minimum computational resource. Based on case studies and simulation results, the proposed approach delivers more effective performance of contingencies response and better computation time efficiency as the scale of the power network expands. The proposed MMS shows promises for solving various real-world power supply-demand and restoration problems, and serves as a solid foundation for future power networks refinement and improvement. / Electrical and Computer Engineering

Modeling or simulating Complex Adaptive Systems (CASs) is both important and challenging. As the name suggests, CASs are systems consisting of large numbers of interacting adaptive compartments. They are studied across a wide range of disciplines and have unique properties. They model such systems as multicellular organisms, ecosystems, social networks, and many more. They are complex, in the sense that they are dynamical, nonlinear, and heterogeneous systems that cannot be simply scaled up/down. However, they are self-organized, in the sense that they can evolve into specific structures/patterns without guidance from outside sources. Modeling/Simulating CASs is challenging, not only because of the high complexity, but also because of the difficulty in explaining the underlying mechanism behind self-organization. The goal of this research is to provide a modeling framework as well as a simulation platform to advance the study of CASs. We argue that there are common principles behind self-organization processes of different systems across different domains. We explore, analyze, and perform experiments into these principles. We propose and implement modeling templates such as short-term and long-term adaptivity. We incorporate techniques from systems theory, employing computing paradigms, including multi-agent system and asynchronous message passing. We also consider an application from the biological domain to model and simulate under our framework, treating it as a CAS for validation purposes. / Ph. D.

The air transportation system has grown significantly during the past few decades. The demand for air travel has increased tremendously as compared to the increase in the supply. The air transportation system can be divided into four subsystems: airports, airlines, air traffic control, and passengers, each of them having different interests. These subsystems interact in a very complex way resulting in various phenomena. On the airport side, there is excessive flight demand during the peak hours that frequently exceeds the airport capacity resulting in serious flight delays. These delays incur costs to the airport, passengers, and airlines. The air traffic pattern is also affected by the characteristics of the air transportation network. The current network structure of most major airlines in United States is a hub-and-spoke network. The airports are interested in reducing congestion, especially during the peak time. The airlines act as direct demand to the airport and as the supplier to the passengers. They sometimes compete with other airlines on certain routes and sometimes they collaborate to maximize revenue. The flight schedule of airlines directly affects the travel demand. The flight schedule that minimizes the schedule delay of passengers in directed and connected flights will attract more passengers. The important factors affecting the airline revenue include ticket price, departure times, frequency, and aircraft type operated on each route. The revenue generated from airline depends also on the behavior of competing airlines, and their flight schedules. The passengers choose their flight based on preferred departure times, offered ticket prices, and willingness of airlines to minimize delay and cost. Hence, all subsystems of air transportation system are inter-connected to each other, meaning, strategy of each subsystem directly affects the performance of other subsystems. This interaction between the subsystems makes it more difficult to analyze the air transportation system. Traditionally, analytical top-down approach has been used to analyze the air transportation problem. In top-down approach, a set of objectives is defined and each subsystem is fixed in the overall scheme. On the other hand, in a bottom-up approach, many issues are addressed simultaneously and each individual system has greater autonomy to make decisions, communicate and to interact with one another to achieve their goals when considering complex air transportation system. Therefore, it seems more appropriate to approach the complex air traffic congestion and airline competition problems using a bottom-up approach. In this research, an agent-based model for the air transportation system has been developed. The developed model considers each subsystem as an independent type of agent that acts based on its local knowledge and its interaction with other agents. The focus of this research is to analyze air traffic congestion and airline competition in a hub-and-spoke network. The simulation model developed is based on evolutionary computation. It seems that the only way for analyzing emergent phenomenon (such as air traffic congestion) is through the development of simulation models that can simulate the behavior of each agent. In the agent-based model developed in this research, agents that represent airports can increase capacity or significantly change landing fee policy, while the agents that represent airlines learn all the time, change their markets, fare structure, flight frequencies, and flight schedules. Such a bottom-up approach facilitates a better understanding of the complex nature of congestion and gains more insights into the competition in air transportation, hence making it easier to understand, predict and control the overall performance of the complex air transportation system. / Ph. D.

This dissertation addresses a fundamental question of multi-agent coordination: what infor- mation should be sent to whom and when, with the limited resources available to each agent? Communication requirements for multi-agent systems can be rather high when an accurate picture of the environment and the state of other agents must be maintained. To reduce the impact of multi-agent coordination on networked systems, e.g., power and bandwidth, this dissertation introduces new concepts to enable Intelligent Knowledge Distribution (IKD), including Constrained-action POMDPs (CA-POMDP) and concurrent decentralized (CoDec) POMDPs for an agnostic plug-and-play capability for fully autonomous systems. Each agent runs a CoDec POMDP where all the decision making (motion planning, task allocation, asset monitoring, and communication) are separated into concurrent individual MDPs to reduce the combinatorial explosion of the action and state space while maintaining dependencies between the models. We also introduce the CA-POMDP with action-based constraints on partially observable Markov decision processes, rewards driven by the value of information, and probabilistic constraint satisfaction through discrete optimization and Markov chain Monte Carlo analysis. IKD is adapted real-time through machine learning of the actual environmental impacts on the behavior of the system, including collaboration strategies between autonomous agents, the true value of information between heterogeneous systems, observation probabilities and resource utilization. / Doctor of Philosophy / This dissertation addresses a fundamental question behind when multiple autonomous sys- tems, like drone swarms, in the field need to coordinate and share data: what information should be sent to whom and when, with the limited resources available to each agent? Intelligent Knowledge Distribution is a framework that answers these questions. Communication requirements for multi-agent systems can be rather high when an accurate picture of the environment and the state of other agents must be maintained. To reduce the impact of multi-agent coordination on networked systems, e.g., power and bandwidth, this dissertation introduces new concepts to enable Intelligent Knowledge Distribution (IKD), including Constrained-action POMDPs and concurrent decentralized (CoDec) POMDPs for an agnostic plug-and-play capability for fully autonomous systems. The IKD model was able to demonstrate its validity as a "plug-and-play" library that manages communications between agents that ensures the right information is being transmitted at the right time to the right agent to ensure mission success.

This thesis studies formation control for a class of general leader-follower multi-agent systems with Control Barrier Functions (CBFs) such that connectivity maintenance is fulfilled for all the neighboring agents. In leader-follower multi-agent systems, only the leader agents are controlled by the externally designed input, while the followers are guided through their dynamic couplings with the neighboring agents. The main problem is how to keep all adjacent agents maintain within the communication distance during the formation process. In this thesis, Control Barrier Functions (CBFs) are utilized in order to maintain connectivity among the neighboring agents. This thesis firstly introduces a general first-order leader-follower multi-agent systems with proper connectivity constrains. All edges in the system are divided into three categories: follower-follower edges, leader-follower edges and leader-leader edges. Three different kinds of edges are discussed individually. For each category, the relevant topological conditions and control barrier functions are defined and proved for both tree graphs and general graphs. Several simulation examples are implemented to verify the developed results. Both theory and simulation results show that the developed results are a strong support for the formation control of leader-follower system in order to achieve connectivity maintenance. / Denna avhandling studerar formationskontroll för en klass av generella ledare-följare multi-agent-system med kontrollbarriärfunktioner (CBFs) så att anslutningsunderhållet uppfylls för alla angränsande agenter. I ledar-följare multi-agent-system är det bara ledaragenterna som styrs av den externt utformade ingången, medan följaren guidas genom sina dynamiska kopplingar med grannagenterna. Huvudproblemet är hur man kan hålla alla intilliggande agenter inom kommunikationsavståndet under bildningsprocessen. I det här examensarbetet används kontrollbarriärfunktioner (CBF) för att upprätthålla förbindelser mellan angränsande agenter. Detta examensarbete introducerar först ett allmänt första ordningens ledare-följare multi-agentsystem med korrekta anslutningsbegränsningar. Alla kanter i systemet är indelade i tre kategorier: efterföljarkanter, ledare-följarkanter och ledare-ledarkanter. Tre olika sorters kanter diskuteras individuellt. För varje kategori definieras och bevisas de relevanta topologiska förhållandena och kontrollbarriärfunktionerna för både trädgrafer och allmänna grafer. Flera simuleringsexempel implementeras för att verifiera de framtagna resultaten. Både teori- och simuleringsresultat visar att de utvecklade resultaten är ett starkt stöd för bildandet av ledare-följare-system för att uppnå anslutningsunderhåll

e-Learning is becoming an influential role as an economic method and a flexible mode of study in the institutions of higher education today which has a presence in an increasing number of college and university courses. e-Learning as system of systems is a dynamic and scalable environment. Within this environment, e-learning is still searching for a permanent, comfortable and serviceable position that is to be controlled, managed, flexible, accessible and continually up-to-date with the wider university structure. As most academic and business institutions and training centres around the world have adopted the e-learning concept and technology in order to create, deliver and manage their learning materials through the web, it has become the focus of investigation. However, management, monitoring and collaboration between these institutions and centres are limited. Existing technologies such as grid, web services and agents are promising better results. In this research a new architecture has been developed and adopted to make the e-learning environment more dynamic and scalable by dividing it into regional data grids which are managed and monitored by agents. Multi-agent technology has been applied to integrate each regional data grid with others in order to produce an architecture which is more scalable, reliable, and efficient. The result we refer to as Regionally Distributed Architecture for Dynamic e-Learning Environment (RDADeLE). Our RDADeLE architecture is an agent-based grid environment which is composed of components such as learners, staff, nodes, regional grids, grid services and Learning Objects (LOs). These components are built and organised as a multi-agent system (MAS) using the Java Agent Development (JADE) platform. The main role of the agents in our architecture is to control and monitor grid components in order to build an adaptable, extensible, and flexible grid-based e-learning system. Two techniques have been developed and adopted in the architecture to build LOs' information and grid services. The first technique is the XML-based Registries Technique (XRT). In this technique LOs' information is built using XML registries to be discovered by the learners. The registries are written in Dublin Core Metadata Initiative (DCMI) format. The second technique is the Registered-based Services Technique (RST). In this technique the services are grid services which are built using agents. The services are registered with the Directory Facilitator (DF) of a JADE platform in order to be discovered by all other components. All components of the RDADeLE system, including grid service, are built as a multi-agent system (MAS). Each regional grid in the first technique has only its own registry, whereas in the second technique the grid services of all regional grids have to be registered with the DF. We have evaluated the RDADeLE system guided by both techniques by building a simulation of the prototype. The prototype has a main interface which consists of the name of the system (RDADeLE) and a specification table which includes Number of Regional Grids, Number of Nodes, Maximum Number of Learners connected to each node, and Number of Grid Services to be filled by the administrator of the RDADeLE system in order to create the prototype. Using the RST technique shows that the RDADeLE system can be built with more regional grids with less memory consumption. Moreover, using the RST technique shows that more grid services can be registered in the RDADeLE system with a lower average search time and the search performance is increased compared with the XRT technique. Finally, using one or both techniques, the XRT or the RST, in the prototype does not affect the reliability of the RDADeLE system.

In recent years, there has been a flood of continuously changing information from a variety of web resources such as web databases, web sites, web services and programs. Online Social Networks (OSNs) represent such a field where huge amounts of information are being posted online over time. Due to the nature of OSNs, which offer a productive source for qualitative and quantitative personal information, researchers from various disciplines contribute to developing methods for extracting data from OSNs. However, there is limited research which addresses extracting data automatically. To the best of the author's knowledge, there is no research which focuses on tracking the real time changes of information retrieved from OSN profiles over time and this motivated the present work. This thesis presents different approaches for automated Data Extraction (DE) from OSN: crawler, parser, Multi Agent System (MAS) and Application Programming Interface (API). Initially, a parser was implemented as a centralized system to traverse the OSN graph and extract the profile's attributes and list of friends from Myspace, the top OSN at that time, by parsing the Myspace profiles and extracting the relevant tokens from the parsed HTML source files. A Breadth First Search (BFS) algorithm was used to travel across the generated OSN friendship graph in order to select the next profile for parsing. The approach was implemented and tested on two types of friends: top friends and all friends. In case of top friends, 500 seed profiles have been visited; 298 public profiles were parsed to get 2197 top friends' profiles and 2747 friendship edges, while in case of all friends, 250 public profiles have been parsed to extract 10,196 friends' profiles and 17,223 friendship edges. This approach has two main limitations. The system is designed as a centralized system that controlled and retrieved information of each user's profile just once. This means that the extraction process will stop if the system fails to process one of the profiles; either the seed profile (first profile to be crawled) or its friends. To overcome this problem, an Online Social Network Retrieval System (OSNRS) is proposed to decentralize the DE process from OSN through using MAS. The novelty of OSNRS is its ability to monitor profiles continuously over time. The second challenge is that the parser had to be modified to cope with changes in the profiles' structure. To overcome this problem, the proposed OSNRS is improved through use of an API tool to enable OSNRS agents to obtain the required fields of an OSN profile despite modifications in the representation of the profile's source web pages. The experimental work shows that using API and MAS simplifies and speeds up the process of tracking a profile's history. It also helps security personnel, parents, guardians, social workers and marketers in understanding the dynamic behaviour of OSN users. This thesis proposes solutions for web database processing on data extraction from OSNs by the use of parser and MAS and discusses the limitations and improvements.

The work presented herein focuses on the design of distributed autonomous controllers for collective behaviour of Micro-unmanned Aerial Vehicles (MAVs). Two alternative approaches to this topic are introduced: one based upon the Evolutionary Robotics (ER) paradigm, the other one upon flocking principles. Three computer simulators have been developed in order to carry out the required experiments, all of them having their focus on the modelling of fixed-wing aircraft flight dynamics. The employment of fixed-wing aircraft rather than the omni-directional robots typically employed in collective robotics significantly increases the complexity of the challenges that an autonomous controller has to face. This is mostly due to the strict motion constraints associated with fixed-wing platforms, that require a high degree of accuracy by the controller. Concerning the ER approach, the experimental setups elaborated have resulted in controllers that have been evolved in simulation with the following capabilities: (1) navigation across unknown environments, (2) obstacle avoidance, (3) tracking of a moving target, and (4) execution of cooperative and coordinated behaviours based on implicit communication strategies. The design methodology based upon flocking principles has involved tests on computer simulations and subsequent experimentation on real-world robotic platforms. A customised implementation of Reynolds’ flocking algorithm has been developed and successfully validated through flight tests performed with the swinglet MAV. It has been notably demonstrated how the Evolutionary Robotics approach could be successfully extended to the domain of fixed-wing aerial robotics, which has never received a great deal of attention in the past. The investigations performed have also shown that complex and real physics-based computer simulators are not a compulsory requirement when approaching the domain of aerial robotics, as long as proper autopilot systems (taking care of the ”reality gap” issue) are used on the real robots.

This dissertation concerns the self-organization behaviors in different types of multi-agent systems, and possible ways to apply interventions on top ofthat to achieve certain goals. A bounded confidence opinion dynamics modelis considered for the first two papers. Theoretical analysis of the model isperformed and modifications of the model are given so that it will have better properties in some aspect. Leader-follower based models are studied in the third to fifth papers where various optimal control problems are considered. Different methods such as Pontryagin minimum principle and dynamic programming are used to solve those optimal control problem. For complex problems, one may only get approximate solutions or suboptimal solutions.In Paper A and Paper B, we consider the continuous-time Hegselmann-Krause (H-K) model and its variations and target the problem of reaching consensus. A sufficient condition on the initial opinion distribution is givento guarantee consensus for the original continuous-time H-K model. A modified model is provided and proven to be able to lead a larger range of initial opinions to synchronization. An H-K model with an exo-system is also studied where sufficient conditions on the exo-system are given for the purpose of consensus.In Paper C and Paper D, optimal control problems with leader-followerbased multi-agent systems are discussed. Analytic solutions are derived if the dynamics is linear by applying Pontryagin minimum principle. For generalnon-linear leader-follower interactions, we provide a method that use sstatistic moments of the follower crowd to approximate the optimal control.The dynamic programming approach is used and certain approximation ofthe Hamilton-Jacobi-Bellman equations is needed. The computational burdenis so heavy that model predictive control method is required in practical applications.In Paper E, we apply a similar method to the approach used in PaperD to target a pollutant elimination problem. It implies that we can use themethod to attack optimal control problem with partial differential equation constraints by discretization in space. The dimension of the discretization is not related to the computational complexity since only the statistic moments are needed. / <p>QC 20161201</p>