121 |
Information Propagation Algorithms for Consensus Formation in Decentralized Multi-Agent SystemsHollander, Christopher 01 January 2015 (has links)
Consensus occurs within a multi-agent system when every agent is in agreement about the value of some particular state. For example, the color of an LED, the position or magnitude of a vector, a rendezvous location, the most recent state of data within a database, or the identity of a leader are all states that agents might need to agree on in order to execute their tasking. The task of the decentralized consensus problem for multi-agent systems is to design an algorithm that enables agents to communicate and exchange information such that, in finite time, agents are able to form a consensus without the use of a centralized control mechanism. The primary goal of this research is to introduce and provide supporting evidence for Stochastic Local Observation/Gossip (SLOG) algorithms as a new class of solutions to the decentralized consensus problem for multi-agent systems that lack a centralized controller, with the additional constraints that agents act asynchronously, information is discrete, and all consensus options are equally preferable to all agents. Examples of where these constraints might apply include the spread of social norms and conventions in artificial populations, rendezvous among a set of specific locations, and task assignment. This goal is achieved through a combination of theory and experimentation. Information propagation process and an information propagation algorithm are derived by unifying the general structure of multiple existing solutions to the decentralized consensus problem. They are then used to define two classes of algorithms that spread information across a network and solve the decentralized consensus problem: buffered gossip algorithms and local observation algorithms. Buffered gossip algorithms generalize the behavior of many push-based solutions to the decentralized consensus problem. Local observation algorithms generalize the behavior of many pull-based solutions to the decentralized consensus problem. In the language of object oriented design, buffered gossip algorithms and local observation algorithms are abstract classes; information propagation processes are interfaces. SLOG algorithms combine the transmission mechanisms of buffered gossip algorithms and local observation algorithms into a single "hybrid" algorithm that is able to push and pull information within the local neighborhood. A common mathematical framework is constructed and used to determine the conditions under which each of these algorithms are guaranteed to produce a consensus, and thus solve the decentralized consensus problem. Finally, a series of simulation experiments are conducted to study the performance of SLOG algorithms. These experiments compare the average speed of consensus formation between buffered gossip algorithms, local observation algorithms, and SLOG algorithms over four distinct network topologies. Beyond the introduction of the SLOG algorithm, this research also contributes to the existing literature on the decentralized consensus problem by: specifying a theoretical framework that can be used to explore the consensus behavior of push-based and pull-based information propagation algorithms; using this framework to define buffered gossip algorithms and local observation algorithms as generalizations for existing solutions to the decentralized consensus problem; highlighting the similarities between consensus algorithms within control theory and opinion dynamics within computational sociology, and showing how these research areas can be successfully combined to create new and powerful algorithms; and providing an empirical comparison between multiple information propagation algorithms.
|
122 |
Multi agent system for web database processing, on data extraction from online social networks.Abdulrahman, Ruqayya January 2012 (has links)
In recent years, there has been a
ood 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 eld where huge amounts of information are being posted online
over time. Due to the nature of OSNs, which o er 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 pro les over time and this motivated the
present work.
This thesis presents di erent 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 pro-
le's attributes and list of friends from Myspace, the top OSN at that
time, by parsing the Myspace pro les and extracting the relevant tokens
from the parsed HTML source les. A Breadth First Search (BFS) algorithm
was used to travel across the generated OSN friendship graph
in order to select the next pro le 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 pro les have been visited; 298 public
pro les were parsed to get 2197 top friends pro les and 2747 friendship
edges, while in case of all friends, 250 public pro les have been parsed
to extract 10,196 friends' pro les 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 pro le just once. This means that the extraction process will stop
if the system fails to process one of the pro les; either the seed pro le
( rst pro le 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 pro les continuously over time.
The second challenge is that the parser had to be modi ed to cope with
changes in the pro les' structure. To overcome this problem, the proposed
OSNRS is improved through use of an API tool to enable OSNRS
agents to obtain the required elds of an OSN pro le despite modi cations
in the representation of the pro le's source web pages. The experimental
work shows that using API and MAS simpli es and speeds up the
process of tracking a pro le'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. / Taibah University
|
123 |
Cooperative Control of Autonomous Ground VehiclesAkif, Mohammed, Geivald, Sebastian January 2021 (has links)
As autonomous ground vehicles grow in popularity,it is of interest to study how they could coordinate together andhow the technical systems can be implemented in a safe andeffective manner. The objective of this report is to examine howto autonomously move a formation of vehicles without collisionswith obstacles or other vehicles. This is done by considering threefundamental aspects: trajectory tracking, formation control andcollision avoidance. Firstly a trajectory tracking controller for anindividual vehicle is implemented, with the function of followinga desired trajectory. Secondly a displacement-based formationcontrol is explored for two models, the double-integrator modeland the nonholonomic model, with the objective of coordinatingmultiple vehicles to keep a certain formation. Lastly collisionavoidance is integrated in the formation control by adding arepulsive term to the formation controller. It is shown thatthe agents maintained formation while avoiding collision withobstacles and other agents. The implemented controllers wereverified through simulations in MATLAB. / Eftersom autonoma markfordon blir allt mer vanligt är det vikt att studera hur de kan samordna tillsammans och hur de tekniska systemen kan implementeras på ett säkert samt effektivt sätt. Syftet med denna rapport är att undersöka hur man autonomt kan flytta en formation av fordon utan kollisioner med hinder eller med andra fordon. Detta görs genom att tre grundläggande aspekter övervägs: projektilspårning, formationshållning och kollisionsundvikande. Först implementeras en regulator för projektilsspårning, där funktionen är att följa en önskad bana. Därefter undersöks två modeller inom förskjutningsbaserad formationshållning, med ambitionen att samordna alla fordon för att behålla formationen. Slutligen så integreras metoder för kollisionsundvikning med formationshållning genom att lägga till bortstötande teknik i regulatorn för formationshållning. Det visades att fordonen lyckades med att upprätthålla formationen samtidigt som kollisioner mellan hinder och andra fordon undveks. De implementerade regulatorerna verifierades genom simuleringar i MATLAB. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm
|
124 |
Inc-Part: Incremental Partitioning for Load Balancing in Large-Scale Behavioral SimulationsZhang, Y., Liao, X.F., Jin, H., Tan, G., Min, Geyong January 2015 (has links)
No / Large-scale behavioral simulations are widely used to study real-world multi-agent systems. Such programs normally run in discrete time-steps or ticks, with simulated space decomposed into domains that are distributed over a set of workers to achieve parallelism. A distinguishing feature of behavioral simulations is their frequent and high-volume group migration, the phenomenon in which simulated objects traverse domains in groups at massive scale in each tick. This results in continual and significant load imbalance among domains. To tackle this problem, traditional load balancing approaches either require excessive load re-profiling and redistribution, which lead to high computation/communication costs, or perform poorly because their statically partitioned data domains cannot reflect load changes brought by group migration. In this paper, we propose an effective and low-cost load balancing scheme, named Inc-part, based on a key observation that an object is unlikely to move a long distance (across many domains) within a single tick. This localized mobility property allows one to efficiently estimate the load of a dynamic domain incrementally, based on merely the load changes occurring in its neighborhood. The domains experiencing significant load changes are then partitioned or merged, and redistributed to redress load imbalance among the workers. Experiments on a 64-node (1,024-core) platform show that Inc-part can attain excellent load balance with dramatically lowered costs compared to state-of-the-art solutions.
|
125 |
Automating Software Development Processes Through Multi-Agent Systems : A Study in LLM-based Software Engineering / Automatisering av Mjukvaruutvecklingsprocesser genom användning av Multi-Agent System : En studie inom LLM-baserad mjukvaruutvecklingPeltomaa Åström, Samuel, Winoy, Simon January 2024 (has links)
In the ever-evolving landscape of Software Development, the demand for more efficient, scalable, and automated processes is paramount. The advancement of Generative AI has unveiled new avenues for innovative approaches to address this demand. This thesis explores one such avenue through the use of Multi-Agent Systems combined with Large Language Models (LLMs) to automate tasks within the development lifecycle. The thesis presents a structure for designing and developing an LLM-based multi-agent application by encompassing agent design principles, strategies for facilitating multi-agent collaboration, and providing valuable insights into the selection of an appropriate agent framework. Furthermore, the thesis showcases the developed application in its problem-solving capabilities with quantitative benchmarking results. Additionally, the study demonstrates practical implementations through examples of real-world applications. This study demonstrates the potential of utilizing LLM-based multi-agent systems in enhancing software development efficiency, offering companies a promising and powerful tool for streamlining Software Engineering workflows. / I den ständigt föränderliga världen av mjukvaruutveckling är behovet av mer effektiva, skalbara, och automatiserade metoder av stor betydelse. Framstegen inom generativ AI har öppnat nya möjligheter för utveckling av metoder för detta ändamål. Denna studie undersöker en sådan möjlighet genom användning av multi-agent system i samband med stora språkmodeller (Large Language Models, LLM) för automatisering av uppgifter inom utvecklingslivscykeln. Studien presenterar en struktur för design och utveckling av en LLM-baserad multi-agent applikation genom att bearbeta agentdesign och strategier för att underlätta samarbete mellan flera agenter och ge värdefulla insikter i valet av ett lämpligt agent-ramverk. Vidare demonstrerar studien den utvecklade applikationens problemlösningsförmåga med kvantitativa benchmark-resultat. Utöver detta inkluderar studien även exempel på genererade applikationer för att presentera konkreta exempel på implementeringar. Denna studie visar potentialen av att använda LLM-baserade multi-agent system för att förbättra effektiviteten inom mjukvaruutveckling, och erbjuder företag ett lovande och kraftfullt verktyg för effektivisering av arbetsflöden inom mjukvaruteknik.
|
126 |
Optimal control for data harvesting and signal model estimationZhu, Yancheng 29 January 2025 (has links)
2025 / Over the last decade, the application of Wireless Sensor Networks (WSNs) has surged in fields such as environmental monitoring, human health, and smart cities. With this wealth of technologies comes the challenge of how to extract volumes of data collected by such sensor nodes distributed over large, often remote, geographical regions. Data harvesting is the problem of extracting measurements from the remote nodes of WSNs using mobile agents such as ground vehicles or drones. The use of mobile agents can significantly reduce the energy consumption of sensor nodes relative to other modes of extracting the data, extending the lifetime and capabilities of the WSN. Moreover, in remote areas where GPS may not be feasible due to limited power resources on the sensor nodes, the need for accurate sensor node localization and signal broadcasting model estimation becomes critical. Therefore, designing the trajectory of mobile agents is crucial for rapid data collection and information gathering while adhering to vehicle constraints such as dynamics and energy usage. In this thesis, we focus on the application of optimal control methods to design trajectories for mobile agents in data harvesting. This thesis makes contributions in three areas: the creation of a parameterized optimal control policy, the application of a Deep Reinforcement Learning (DRL) based control, and the use of Fisher Information (FI) as a cost matrix in a Receding Horizon Control (RHC) method. Parameterized Optimal Control Policy: Our contributions in this area begin by considering a data harvesting problem in 1-D space. We use a Hamiltonian analysis to show that the optimal control can be described using a parameterized policy and then develop a gradient descent scheme using Infinitesimal Perturbation Analysis (IPA) to calculate the gradients of the cost function with respect to the control parameters. We also consider this problem in a multi-agent setting. To avoid collisions between agents, we apply a Control Barrier Function (CBF) technique to ensure the agents closely track the desired optimal trajectory to complete their mission while avoiding any collisions. Finally, we extend the problem to a mobile sensor scenario. In this more complicated setting we demonstrate that the optimization problem for the control policy parameters can be effectively solved using a heuristic approach. Deep-Reinforcement-Learning based Control: The parametric optimal control approach cannot be easily extended from the 1-D setting to 2-D space. For this reason, we turn to DRL techniques. We utilize Hamiltonian analysis again to get the necessary conditions for optimal control and then translate the problem to a Markov Decision Process (MDP) in discrete time. We apply reinforcement learning techniques, including double deep Q-learning and Proximal Policy Optimization (PPO), to find high-performing solutions across different scenarios. We demonstrate the effectiveness of these methods in 2-D simulations. Fisher-Information-based Receding Horizon Control: For the data harvesting problem in large scale unknown environments, estimating the parameters defining the broadcast model and the location of all the nodes in the environment is critical for efficient extraction of the data. To address that, we start with a Received Signal Strength (RSS) model that relies on a Line-of-Sight (LoS) path-loss model with measurements that are corrupted by Gaussian distributed noise. We first consider a single agent tasked with estimating these unknown parameters in discrete time, and then develop a Fisher Information Matrix (FIM) Receding Horizon (RH) controller for agent motion planning in real time. We also design a Neural Network (NN)-based controller to approximate the optimal solution to the Hamilton-Jacobi-Bellman (HJB) problem, maximizing information gain along a continuous time trajectory. Additionally, a two-stage formation-based RH controller is designed for multi-agent scenarios. The experiments demonstrate that the optimal control policy contribute to the high performance of data collection and the FI-based RHC methods enhance the estimation accuracy in various simulation environments.
|
127 |
Modélisation de l'hétérogénéité de croissance dans le système aquacole / Modelling growth heterogeneity in the fish raring systemCampeas, Arnaud 04 March 2008 (has links)
L’hétérogénéité de croissance est un problème récurrent en aquaculture dont le déterminisme est le résultat d’une interaction complexe de nombreux facteurs: alimentaires, populationnels, environnementaux et génétiques. Nous avons développé un modèle individu-centré (système multi-agent) pour reproduire in silico les phénomènes biologiques sous-jacents (Mo.B.I.Fish : Model of Behavioral Interaction of Fish). La première étape a consisté en l’élaboration d’un modèle de croissance capable de modéliser la prise de poids d’un poisson en fonction de son ingéré. Deux types de modèles ont été évalués (Scope For Growth et Dynamic Energy Budget) sur des données expérimentales de croissance et le SFG a été retenu. Il a ensuite été utilisé en validation pour évaluer l’importance de l’ingéré et d’autres facteurs dans l’hétérogénéité de croissance. La deuxième étape de modélisation a consisté en l’élaboration d’un modèle simulant les interactions sociales entre poissons. Ces interactions ont été simulées par un système multi agents qui reproduit des séries de combats entre deux individus dont l’issue est dépendante de leur poids, de leurs interactions passées, de leur génétique et d’un effet aléatoire. Le résultat de ces combats influence leur nourrissage individuel. A l’aide de 2 expérimentations ad hoc de croissance de perche en circuit fermé, nous avons pu calibrer et valider le modèle de façon à estimer l’importance des différents facteurs dans le déterminisme des combats. La comparaison entre le modèle et les données a été faite sur les variables « poids moyen »« coefficient de variation » et « coefficient de corrélation de Spearman ». Il est apparu ainsi que la taille avait une faible importance, et que le déterminisme des combats pouvait être, en première approche considéré comme purement aléatoire. L’effet mémoire permet de simuler le désordre des rangs de poids des poissons entre le début et la fin de la période de croissance / Growth heterogeneity is a recurrent problem in fish aquaculture. Its determinism is the result of complex interactions between numerous factors: feeding rate, social interactions, environmental conditions and genetics. We developed an individualized based model (multi-agent system) to reproduce in silico biological phenomena (Mo.B.I.Fish : Model of Behavioral Interaction of Fish). The first step of modelling consisted of choosing a model that could simulate growth knowing the food intake. Two models were compared (Scope For Growth and Dynamic Energy Budget) to experimental data of growing fish: we finally chose the SFG. This model was used in validation to evaluate the relative influence of the food intake (combined with other factors) on growth heterogeneity. The second step of modelling consisted of building a model which simulated social interactions between fish. These interactions were simulated with a multi-agent system that reproduced fights between two fish, in which the final result depended on the weight, experience of each fish, genetic and random effect. The result of the fight had direct influence on the individual intake. Two experiments were conducted on perch in recirculating system, which provided to us data to both calibrate and validate the model. The output of the model was the mean weight, the coefficient of variation of the weight and the Spearman's rank correlation coefficient of fish weight. Hence we could estimate the relative importance of each factor in the determinism of the fights. We observed that size had little or no effect, and that the determinism could be considered as completely random. The experience effect also allowed simulating accurately the rank of the weight of fish between the beginning and the end of the experiments
|
128 |
Modélisation structurelle des réseaux sociaux : application à un système d’aide à la décision en cas de crise sanitaire / Modelling structural of social networks : towards a decision support tool in case of a Public Health CrisisBasileu, Cynthia 02 December 2011 (has links)
Face à une situation de crise sanitaire liée à l’apparition d’une pandémie de grande envergure, des mesures adéquates doivent rapidement être prises pour la contenir tout en préservant la capacité de production de l’économie. D’autre part, beaucoup de travaux sont réalisés dans le domaine de la diffusion de la propagation d’une épidémie. C’est pourquoi, nous accentuons notre apport à un décideur afin de lui permettre de maintenir les fonctions minimums de survie de la société dans le cadre d’une crise sanitaire. Ainsi, nous proposons un modèle d’aide à la décision de gestion de crise sanitaire. Par ailleurs, la société est située au coeur de notre modèle. Nous sommes donc amenés à considérer un certain nombre d’interactions directes et indirectes entre divers individus. La théorie des graphes, et principalement les graphes aléatoires, permettent de gérer une à une ces relations. Or, dans notre cas, la gestion des relations une à une n’est pas appropriée d’autant plus que les relations peuvent varier sous l’influence de facteurs incontrôlables. Cela nous a conduits à proposer un modèle mathématique de réseaux stochastiques basé sur une extension de la théorie des graphes aléatoires. Il s’agit de la prétopologie stochastique qui est issue du couplage de deux théories mathématiques fondamentales, la prétopologie classique et les ensembles aléatoires. La simulation de notre modèle est effectuée selon une approche multi-agents. Nous avons opté pour cette approche car nous souhaitons mettre en place un modèle d’aide à la décision. Cette méthode va donc nous permettre de faire des simulations et des analyses de sensibilités. Nous avons une représentation explicite des comportements des individus qui ne sont pas figés. Située entre la théorie et l’ensemble des données de l’expérience, l’approche multi-agents permet de prendre en compte de manière simultanée les comportements individuels, les interactions entre les individus et les hypothèses dynamiques formulées dans le modèle. Cette approche sera couplée au système d’information géographique afin de considérer l’aspect spatial. Considéré comme un « oignon », le système d’information géographique permet d’exploiter différentes données et de les superposer sous forme de couches. Disposant de données épidémiologiques provenant des Groupes Régionaux d’Observation de la Grippe (GROG) et des données sociodémographiques issues de l’Institut National de la Statistique et des Etudes Economiques (INSEE), nous pourrons tester la robustesse de notre modèle. / To manage a public health crisis resulting from an outbreak of a large-scale pandemic, it is necessary to be capable of taking adequate measures very quickly. These measures must be taken to protect the productive capacity of the economy. Consequently, I have focused on the development of a « decision-making support » model with hybrid agents simulating the spreading of a pandemic, which is established on the medical characteristics of the virus as well as the socioeconomic structure of the concerned geographical zone. This socioeconomic structure being at the centre of the model, a pretopological modelling of the concept of social network is therefore proposed and integrated into the approach agent.
|
129 |
Metaheuristics for solving large size long-term car pooling problem and an extension / Métaheuristiques pour la résolution de problème de covoiturage régulier de grande taille et d'une extensionGuo, Yuhan 09 November 2012 (has links)
La dispersion spatiale de l'habitat et des activités de ces dernières décennies a fortement contribué à un allongement des distances et des temps de trajets domicile-travail. Cela a pour conséquence un accroissement de l'utilisation des voitures particulières, notamment au sein et aux abords des grandes agglomérations. Afin de réduire les impacts dus à l'augmentation du trafic routier, des services de covoiturage, où des usagers ayant la même destination se regroupent en équipage pour se déplacer, ont été mis en place partout dans le monde. Nous présentons ici nos travaux sur le problème de covoiturage régulier. Dans cette thèse, le problème de covoiturage régulier a été modélisé et plusieurs métaheuristiques de résolution ont été implémentées, testées et comparées. La thèse est organisée de la façon suivante: tout d'abord, nous commençons par présenter la définition et la description du problème ainsi que le modèle mathématique associé. Ensuite, plusieurs métaheuristiques pour résoudre le problème sont présentées. Ces approches sont au nombre de quatre: un algorithme de recherche locale à voisinage variable, un algorithme à base de colonies de fourmis, un algorithme génétique guidée et un système multi-agents génétiques auto-adaptatif. Des expériences ont été menées pour démontrer l'efficacité de nos approches. Nous continuons ensuite avec la présentation et la résolution d'une extension du problème de covoiturage occasionel comportant plusieurs destinations. Pour terminer, une plate-forme de test et d'analyse pour évaluer nos approches et une plate-forme de covoiturage sont présentées dans l'annexe. / Nowadays, the increased human mobility combined with high use of private cars increases the load on environment and raises issues about quality of life. The extensive use of private cars lends to high levels of air pollution, parking problem, traffic congestion and low transfer velocity. In order to ease these shortcomings, the car pooling program, where sets of car owners having the same travel destination share their vehicles, has emerged all around the world. We present here our research on the long-term car pooling problem. In this thesis, the long-term car pooling problem is modeled and metaheuristics for solving the problem are investigated. The thesis is organized as follows. First, the definition and description of the problem as well as its mathematical model are introduced. Then, several metaheuristics to effectively and efficiently solve the problem are presented. These approaches include a Variable Neighborhood Search Algorithm, a Clustering Ant Colony Algorithm, a Guided Genetic Algorithm and a Multi-agent Self-adaptive Genetic Algorithm. Experiments have been conducted to demonstrate the effectiveness of these approaches on solving the long-term car pooling problem. Afterwards, we extend our research to a multi-destination daily car pooling problem, which is introduced in detail manner along with its resolution method. At last, an algorithm test and analysis platform for evaluating the algorithms and a car pooling platform are presented in the appendix.
|
130 |
[en] A METHOD FOR MASSIVE AGENTS SIMULATION OF SEA SCENES FOR TV / FILM PRODUCTIONS / [pt] UM MÉTODO PARA SIMULAÇÃO EM MASSA DE AGENTES PARA CENAS DE MAR EM PRODUÇÕES PARA TV/CINEMAAARAO IRVING MANHAES MARINS 06 February 2015 (has links)
[pt] Esta dissertação de mestrado apresenta um método para simular cenas de mar para TV/Cinema com um grande número de agentes de vários tipos (embarcações, portos, pessoas, ...) para produções com elevado grau de realismo de imagem e comportamento dos agentes. Este método usa modelagem em lógica nebulosa (fuzzy) e programação no sistema MASSIVE de maneira a integrar os resultados com sistemas de rendering e composição de imagens de alta resolução. Um objetivo importante desta dissertação é criar um sistema que facilita o trabalho de modeladores e designers envolvidos no pipeline de produção. / [en] This MSc dissertation presents a method to simulate sea scenes for TV /
Film with a large number of agents of various types (vessels, ports, people ...) for
productions with a high degree of realism in both image and agent s behavior.
This method uses modeling in fuzzy logic and programming in the MASSIVE
system as the main approach to integrate the results with rendering systems and
high-resolution images composition. An important goal of this dissertation is to
create a system that facilitates the work of modelers and designers involved in the
production pipeline.
|
Page generated in 0.1102 seconds