Topic overview

Multiagent Systems

1840 works5855 researchers

Open map Browse papers

Map preview

Start with the graph, then narrow the list

1840works

5855researchers

Next steps

Use the topic as a working map

Open the full map for clusters, then return here to scan ranked papers and people.

Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Curiosity-Aware Bargaining

Opponent modeling consists in modeling the strategy or preferences of an agent thanks to the data it provides. In the context of automated negotiation and with machine learning, it can result in an advantage so overwhelming that it may restrain some casual agents to be part of the bargaining process. We qualify as "curious" an agent driven by the desire of negotiating in order to collect information and improve its opponent model. However, neither curiosity-based rational-ity nor curiosity-robust protocol have been studied in automatic negotiation. In this paper, we rely on mechanism design to propose three extensions of the standard bargaining protocol that limit information leak. Those extensions are supported by an enhanced rationality model, that considers the exchanged information. Also, they are theoretically analyzed and experimentally evaluated.

preprint2016arXiv

Minimal Actuator Placement with Bounds on Control Effort

We address the problem of minimal actuator placement in linear systems so that the volume of the set of states reachable with one unit or less of input energy is lower bounded by a desired value. First, following the recent work of Olshevsky, we prove that this is NP-hard. Then, we provide an efficient algorithm which, for a given range of problem parameters, approximates up to a multiplicative factor of O(logn), n being the network size, any optimal actuator set that meets the same energy criteria; this is the best approximation factor one can achieve in polynomial time, in the worst case. Moreover, the algorithm uses a perturbed version of the involved control energy metric, which we prove to be supermodular. Next, we focus on the related problem of cardinality-constrained actuator placement for minimum control effort, where the optimal actuator set is selected to maximize the volume of the set of states reachable with one unit or less of input energy. While this is also an NP-hard problem, we use our proposed algorithm to efficiently approximate its solutions as well.

preprint2016arXiv

Network, Popularity and Social Cohesion: A Game-Theoretic Approach

In studies of social dynamics, cohesion refers to a group's tendency to stay in unity, which -- as argued in sociometry -- arises from the network topology of interpersonal ties between members of the group. We follow this idea and propose a game-based model of cohesion that not only relies on the social network, but also reflects individuals' social needs. In particular, our model is a type of cooperative games where players may gain popularity by strategically forming groups. A group is socially cohesive if the grand coalition is core stable. We study social cohesion in some special types of graphs and draw a link between social cohesion and the classical notion of structural cohesion. We then focus on the problem of deciding whether a given social network is socially cohesive and show that this problem is CoNP-complete. Nevertheless, we give two efficient heuristics for coalition structures where players enjoy high popularity and experimentally evaluate their performances.

preprint2016arXiv

Fault-Tolerant Adaptive Parallel and Distributed Simulation

Discrete Event Simulation is a widely used technique that is used to model and analyze complex systems in many fields of science and engineering. The increasingly large size of simulation models poses a serious computational challenge, since the time needed to run a simulation can be prohibitively large. For this reason, Parallel and Distributes Simulation techniques have been proposed to take advantage of multiple execution units which are found in multicore processors, cluster of workstations or HPC systems. The current generation of HPC systems includes hundreds of thousands of computing nodes and a vast amount of ancillary components. Despite improvements in manufacturing processes, failures of some components are frequent, and the situation will get worse as larger systems are built. In this paper we describe FT-GAIA, a software-based fault-tolerant extension of the GAIA/ARTÌS parallel simulation middleware. FT-GAIA transparently replicates simulation entities and distributes them on multiple execution nodes. This allows the simulation to tolerate crash-failures of computing nodes; furthermore, FT-GAIA offers some protection against byzantine failures since synchronization mes

preprint2016arXiv

Distributed Probabilistic Bisection Search using Social Learning

We present a novel distributed probabilistic bisection algorithm using social learning with application to target localization. Each agent in the network first constructs a query about the target based on its local information and obtains a noisy response. Agents then perform a Bayesian update of their beliefs followed by an averaging of the log beliefs over local neighborhoods. This two stage algorithm consisting of repeated querying and averaging runs until convergence. We derive bounds on the rate of convergence of the beliefs at the correct target location. Numerical simulations show that our method outperforms current state of the art methods.

preprint2016arXiv

A Hybrid Network/Grid Model of Urban Morphogenesis and Optimization

We describe a hybrid agent-based model and simulation of urban morphogenesis. It consists of a cellular automata grid coupled to a dynamic network topology. The inherently heterogeneous properties of urban structure and function are taken into account in the dynamics of the system. We propose various layout and performance measures to categorize and explore the generated configurations. An economic evaluation metric was also designed using the sensitivity of segregation models to spatial configuration. Our model is applied to a real-world case, offering a means to optimize the distribution of activities in a zoning context.

preprint2016arXiv

The formal-logical characterisation of lies, deception, and associated notions

Defining various dishonest notions in a formal way is a key step to enable intelligent agents to act in untrustworthy environments. This review evaluates the literature for this topic by looking at formal definitions based on modal logic as well as other formal approaches. Criteria from philosophical groundwork is used to assess the definitions for correctness and completeness. The key contribution of this review is to show that only a few definitions fully comply with this gold standard and to point out the missing steps towards a successful application of these definitions in an actual agent environment.

preprint2016arXiv

Brain-Swarm Interface (BSI): Controlling a Swarm of Robots with Brain and Eye Signals from an EEG Headset

This work presents a novel marriage of Swarm Robotics and Brain Computer Interface technology to produce an interface which connects a user to a swarm of robots. The proposed interface enables the user to control the swarm's size and motion employing just thoughts and eye movements. The thoughts and eye movements are recorded as electrical signals from the scalp by an off-the-shelf Electroencephalogram (EEG) headset. Signal processing techniques are used to filter out noise and decode the user's eye movements from raw signals, while a Hidden Markov Model technique is employed to decipher the user's thoughts from filtered signals. The dynamics of the robots are controlled using a swarm controller based on potential fields. The shape and motion parameters of the potential fields are modulated by the human user through the brain-swarm interface to move the robots. The method is demonstrated experimentally with a human controlling a swarm of three M3pi robots in a laboratory environment, as well as controlling a swarm of 128 robots in a computer simulation.

preprint2016arXiv

ARES: Adaptive Receding-Horizon Synthesis of Optimal Plans

We introduce ARES, an efficient approximation algorithm for generating optimal plans (action sequences) that take an initial state of a Markov Decision Process (MDP) to a state whose cost is below a specified (convergence) threshold. ARES uses Particle Swarm Optimization, with adaptive sizing for both the receding horizon and the particle swarm. Inspired by Importance Splitting, the length of the horizon and the number of particles are chosen such that at least one particle reaches a next-level state, that is, a state where the cost decreases by a required delta from the previous-level state. The level relation on states and the plans constructed by ARES implicitly define a Lyapunov function and an optimal policy, respectively, both of which could be explicitly generated by applying ARES to all states of the MDP, up to some topological equivalence relation. We also assess the effectiveness of ARES by statistically evaluating its rate of success in generating optimal plans. The ARES algorithm resulted from our desire to clarify if flying in V-formation is a flocking policy that optimizes energy conservation, clear view, and velocity alignment. That is, we were interested to see if o

preprint2016arXiv

Agent-based Model for Spot and Balancing Electricity Markets

We present a simple, yet realistic, agent-based model of an electricity market. The proposed model combines the spot and balancing markets with a resolution of one minute, which enables a more accurate depiction of the physical properties of the power grid. As a test, we compare the results obtained from our simulation to data from Nord Pool.

preprint2015arXiv

The projection method for continuous-time consensus seeking

For the case where the dependency digraph has no spanning in-tree, we characterize the region of convergence of the basic continuous-time distributed consensus algorithm and show that consensus can be achieved by employing the method of orthogonal projection, which has been proposed for the discrete-time coordination problem.

preprint2016arXiv

An argumentative agent-based model of scientific inquiry

In this paper we present an agent-based model (ABM) of scientific inquiry aimed at investigating how different social networks impact the efficiency of scientists in acquiring knowledge. As such, the ABM is a computational tool for tackling issues in the domain of scientific methodology and science policy. In contrast to existing ABMs of science, our model aims to represent the argumentative dynamics that underlies scientific practice. To this end we employ abstract argumentation theory as the core design feature of the model. This helps to avoid a number of problematic idealizations which are present in other ABMs of science and which impede their relevance for actual scientific practice.

preprint2016arXiv

Optimal Target Assignment and Path Finding for Teams of Agents

We study the TAPF (combined target-assignment and path-finding) problem for teams of agents in known terrain, which generalizes both the anonymous and non-anonymous multi-agent path-finding problems. Each of the teams is given the same number of targets as there are agents in the team. Each agent has to move to exactly one target given to its team such that all targets are visited. The TAPF problem is to first assign agents to targets and then plan collision-free paths for the agents to their targets in a way such that the makespan is minimized. We present the CBM (Conflict-Based Min-Cost-Flow) algorithm, a hierarchical algorithm that solves TAPF instances optimally by combining ideas from anonymous and non-anonymous multi-agent path-finding algorithms. On the low level, CBM uses a min-cost max-flow algorithm on a time-expanded network to assign all agents in a single team to targets and plan their paths. On the high level, CBM uses conflict-based search to resolve collisions among agents in different teams. Theoretically, we prove that CBM is correct, complete and optimal. Experimentally, we show the scalability of CBM to TAPF instances with dozens of teams and hundreds of agents

preprint2016arXiv

Disruptive innovations in RoboCup 2D Soccer Simulation League: from Cyberoos'98 to Gliders2016

We review disruptive innovations introduced in the RoboCup 2D Soccer Simulation League over the twenty years since its inception, and trace the progress of our champion team (Gliders). We conjecture that the League has been developing as an ecosystem shaped by diverse approaches taken by participating teams, increasing in its overall complexity. A common feature is that different champion teams succeeded in finding a way to decompose the enormous search-space of possible single- and multi-agent behaviours, by automating the exploration of the problem space with various techniques which accelerated the software development efforts. These methods included interactive debugging, machine learning, automated planning, and opponent modelling. The winning approach developed by Gliders is centred on human-based evolutionary computation which optimised several components such as an action-dependent evaluation function, dynamic tactics with Voronoi diagrams, information dynamics, and bio-inspired collective behaviour.

preprint2016arXiv

Real-time Collision Handling in Railway Network:An Agent-based Approach

Advancement in intelligent transportation systems with complex operations requires autonomous planning and management to avoid collisions in day-to-day traffic. As failure and/or inadequacy in traffic safety system are life-critical, such collisions must be detected and resolved in an efficient way to manage continuously rising traffic. In this paper, we address different types of collision scenarios along with their early detection and resolution techniques in a complex railway system. In order to handle collisions dynamically in distributed manner, a novel agent based solution approach is proposed using the idea of max-sum algorithm, where each agent (train agent, station agent, and junction agent) communicates and cooperates with others to generate a good feasible solution that keeps the system in a safe state, i.e., collision free. We implement the proposed mechanism in Java Agent DEvelopment Framework (JADE). The results are evaluated with exhaustive experiments and compared with different existing collision handling methods to show the efficiency of our proposed approach.

preprint2016arXiv

Proportional Rankings

In this paper we extend the principle of proportional representation to rankings. We consider the setting where alternatives need to be ranked based on approval preferences. In this setting, proportional representation requires that cohesive groups of voters are represented proportionally in each initial segment of the ranking. Proportional rankings are desirable in situations where initial segments of different lengths may be relevant, e.g., hiring decisions (if it is unclear how many positions are to be filled), the presentation of competing proposals on a liquid democracy platform (if it is unclear how many proposals participants are taking into consideration), or recommender systems (if a ranking has to accommodate different user types). We study the proportional representation provided by several ranking methods and prove theoretical guarantees. Furthermore, we experimentally evaluate these methods and present preliminary evidence as to which methods are most suitable for producing proportional rankings.

preprint2016arXiv

Expander Graph and Communication-Efficient Decentralized Optimization

In this paper, we discuss how to design the graph topology to reduce the communication complexity of certain algorithms for decentralized optimization. Our goal is to minimize the total communication needed to achieve a prescribed accuracy. We discover that the so-called expander graphs are near-optimal choices. We propose three approaches to construct expander graphs for different numbers of nodes and node degrees. Our numerical results show that the performance of decentralized optimization is significantly better on expander graphs than other regular graphs.

preprint2016arXiv

A Scalable and Adaptable Multiple-Place Foraging Algorithm for Ant-Inspired Robot Swarms

Individual robots are not effective at exploring large unmapped areas. An alternate approach is to use a swarm of simple robots that work together, rather than a single highly capable robot. The central-place foraging algorithm (CPFA) is effective for coordinating robot swarm search and collection tasks. Robots start at a centrally placed location (nest), explore potential targets in the area without global localization or central control, and return the targets to the nest. The scalability of the CPFA is limited because large numbers of robots produce more inter-robot collisions and large search areas result in substantial travel costs. We address these problems with the multiple-place foraging algorithm (MPFA), which uses multiple nests distributed throughout the search area. Robots start from a randomly assigned home nest but return to the closest nest with found targets. We simulate the foraging behavior of robot swarms in the robot simulator ARGoS and employ a genetic algorithm to discover different optimized foraging strategies as swarm sizes and the number of targets are scaled up. In our experiments, the MPFA always produces higher foraging rates, fewer collisions, and lowe

preprint2016arXiv

Effect of long-range interactions on the phase transition of Axelrod's model

Axelrod's model with $F=2$ cultural features, where each feature can assume $k$ states drawn from a Poisson distribution of parameter $q$, exhibits a continuous nonequilibrium phase transition in the square lattice. Here we use extensive Monte Carlo simulations and finite size scaling to study the critical behavior of the order parameter $ρ$, which is the fraction of sites that belong to the largest domain of an absorbing configuration averaged over many runs. We find that it vanishes as $ρ\sim \left (q_c^0 - q \right)^β$ with $β\approx 0.25$ at the critical point $q_c^0 \approx 3.10$ and that the exponent that measures the width of the critical region is $ν^0 \approx 2.1$. In addition, we find that introduction of long-range links by rewiring the nearest-neighbors links of the square lattice with probability $p$ turns the transition discontinuous, with the critical point $q_c^p$ increasing from $3.1$ to $27.17$, approximately, as $p$ increases from $0$ to $1$. The sharpness of the threshold, as measured by the exponent $ν^p \approx 1$ for $p>0$, increases with the square root of the number of nodes of the resulting small-world network.

preprint2016arXiv

Structural Controllability of Multi-Agent Networks: Robustness against Simultaneous Failures

In this paper, structural controllability of a leader-follower multi-agent system with multiple leaders is studied from a graph-theoretic point of view. The problem of preservation of structural controllability under simultaneous failures in both the communication links and the agents is investigated. The effects of the loss of agents and communication links on the controllability of an information flow graph are previously studied. In this work, the corresponding results are exploited to introduce some useful indices and importance measures that help characterize and quantify the role of individual links and agents in the controllability of the overall network. Existing results are then extended by considering the effects of losses in both links and agents at the same time. To this end, the concepts of joint (r,s)-controllability and joint t-controllability are introduced as quantitative measures of reliability for a multi-agent system, and their important properties are investigated. Lastly, the class of jointly critical digraphs is introduced and it is stated that if a digraph is jointly critical, then joint t-controllability is a necessary and sufficient condition for remaining

preprint2016arXiv

Distributed Estimation for Adaptive Networks Based on Serial-Inspired Diffusion

Distributed estimation and processing in networks modeled by graphs have received a great deal of interest recently, due to the benefits of decentralised processing in terms of performance and robustness to communications link failure between nodes of the network. Diffusion-based algorithms have been demonstrated to be among the most effective for distributed signal processing problems, through the combination of local node estimate updates and sharing of information with neighbour nodes through diffusion. In this work, we develop a serial-inspired approach based on message-passing strategies that provides a significant improvement in performance over prior art. The concept of serial processing in the graph has been successfully applied in sum-product based algorithms and here provides inspiration for an algorithm which makes use of the most up-to-date information in the graph in combination with the diffusion approach to offer improved performance.

preprint2016arXiv

Digraphs with Distinguishable Dynamics under the Multi-Agent Agreement Protocol

In this work, the ability to distinguish digraphs from the output response of some observing agents in a multi-agent network under the agreement protocol has been studied. Given a fixed observation point, it is desired to find sufficient graphical conditions under which the failure of a set of edges in the network information flow digraph is distinguishable from another set. When the latter is empty, this corresponds to the detectability of the former link set given the response of the observing agent. In developing the results, a powerful extension of the all-minors matrix tree theorem in algebraic graph theory is proved which relates the minors of the transformed Laplacian of a directed graph to the number and length of the shortest paths between its vertices. The results reveal an intricate relationship between the ability to distinguish the responses of a healthy and a faulty multi-agent network and the inter-nodal paths in their information flow digraphs. The results have direct implications for the operation and design of multi-agent systems subject to multiple link losses. Simulations and examples are presented to illustrate the analytic findings.

preprint2016arXiv

A Majoritarian Representative Voting System

We present an alternative voting system that aims at bridging the gap between proportional representative systems and majoritarian, single winner election systems. The system lets people vote for multiple parties, but then assigns each ballot to a single party. This opens a whole range of possible systems, all representative. We show theoretically that this space is convex. Then among the possible parliaments we present an algorithm to produce the most majoritarian result. We then test the system and compare the results with a pure proportional and a majoritarian voting system showing how the results are comparable with the majoritarian system. Then we simulate the system and show how it tends to produce parties of exponentially decreasing size with always a first, major party. Finally we describe how the system can be used in a context of a parliament made up of two separate houses.

preprint2011arXiv

Performance and Convergence of Multi-user Online Learning

We study the problem of allocating multiple users to a set of wireless channels in a decentralized manner when the channel quali- ties are time-varying and unknown to the users, and accessing the same channel by multiple users leads to reduced quality due to interference. In such a setting the users not only need to learn the inherent channel quality and at the same time the best allocations of users to channels so as to maximize the social welfare. Assuming that the users adopt a certain online learning algorithm, we investigate under what conditions the socially optimal allocation is achievable. In particular we examine the effect of different levels of knowledge the users may have and the amount of communications and cooperation. The general conclusion is that when the cooperation of users decreases and the uncertainty about channel payoffs increases it becomes harder to achieve the socially opti- mal allocation.

374 works