Computer Science - Multiagent Systems Publications (50)


Computer Science - Multiagent Systems Publications

Successful analysis of player skills in video games has important impacts on the process of enhancing player experience without undermining their continuous skill development. Moreover, player skill analysis becomes more intriguing in team-based video games because such form of study can help discover useful factors in effective team formation. In this paper, we consider the problem of skill decomposition in MOBA (MultiPlayer Online Battle Arena) games, with the goal to understand what player skill factors are essential for the outcome of a game match. Read More

We investigate the effects of social interactions in task al- location using Evolutionary Game Theory (EGT). We propose a simple task-allocation game and study how different learning mechanisms can give rise to specialised and non- specialised colonies under different ecological conditions. By combining agent-based simulations and adaptive dynamics we show that social learning can result in colonies of generalists or specialists, depending on ecological parameters. Read More

Multi-agent path finding (MAPF) is well-studied in artificial intelligence, robotics, theoretical computer science and operations research. We discuss issues that arise when generalizing MAPF methods to real-world scenarios and four research directions that address them. We emphasize the importance of addressing these issues as opposed to developing faster methods for the standard formulation of the MAPF problem. Read More

Until now mean-field-type game theory was not focused on cognitively-plausible models of choices in humans, animals, machines, robots, software-defined and mobile devices strategic interactions. This work presents some effects of users' psychology in mean-field-type games. In addition to the traditional "material" payoff modelling, psychological patterns are introduced in order to better capture and understand behaviors that are observed in engineering practice or in experimental settings. Read More

This paper investigates the task assignment problem for multiple dispersed robots constrained by limited communication range. The robots are initially randomly distributed and need to visit several target locations while minimizing the total travel time. A centralized rendezvous-based algorithm is proposed, under which all the robots first move towards a rendezvous position until communication paths are established between every pair of robots either directly or through intermediate peers, and then one robot is chosen as the leader to make a centralized task assignment for the other robots. Read More

All-pay auctions, a common mechanism for various human and agent interactions, suffers, like many other mechanisms, from the possibility of players' failure to participate in the auction. We model such failures, and fully characterize equilibrium for this class of games, we present a symmetric equilibrium and show that under some conditions the equilibrium is unique. We reveal various properties of the equilibrium, such as the lack of influence of the most-likely-to-participate player on the behavior of the other players. Read More

Online learning with streaming data in a distributed and collaborative manner can be useful in a wide range of applications. This topic has been receiving considerable attention in recent years with emphasis on both single-task and multitask scenarios. In single-task adaptation, agents cooperate to track an objective of common interest, while in multitask adaptation agents track multiple objectives simultaneously. Read More

Managing micro-tasks on crowdsourcing marketplaces involves balancing conflicting objectives -- the quality of work, total cost incurred and time to completion. Previous agents have focused on cost-quality, or cost-time tradeoffs, limiting their real-world applicability. As a step towards this goal we present Octopus, the first AI agent that jointly manages all three objectives in tandem. Read More


In multi-robot systems where a central decision maker is specifying the movement of each individual robot, a communication failure can severely impair the performance of the system. This paper develops a motion strategy that allows robots to safely handle critical communication failures for such multi-robot architectures. For each robot, the proposed algorithm computes a time horizon over which collisions with other robots are guaranteed not to occur. Read More

We consider a swarm of $n$ autonomous mobile robots, distributed on a 2-dimensional grid. A basic task for such a swarm is the gathering process: all robots have to gather at one (not predefined) place. The work in this paper is motivated by the following insight: On one side, for swarms of robots distributed in the 2-dimensional Euclidean space, several gathering algorithms are known for extremely simple robots that are oblivious, have bounded viewing radius, no compass, and no "flags" to communicate a status to others. Read More

This paper extends and adapts an existing abstract model into an empirical metropolitan region in Brazil. The model - named SEAL: a Spatial Economic Agent-based Lab - comprehends a framework to enable public policy ex-ante analysis. The aim of the model is to use official data and municipalities spatial boundaries to allow for policy experimentation. Read More

Matrix games like Prisoner's Dilemma have guided research on social dilemmas for decades. However, they necessarily treat the choice to cooperate or defect as an atomic action. In real-world social dilemmas these choices are temporally extended. Read More

This paper studies scenarios of cyclic dominance in a coevolutionary spatial model in which game strategies and links between agents adaptively evolve over time. The Optional Prisoner's Dilemma (OPD) game is employed. The OPD is an extended version of the traditional Prisoner's Dilemma where players have a third option to abstain from playing the game. Read More

In many problems, agents cooperate locally so that a leader or fusion center can infer the state of every agent from probing the state of only a small number of agents. Versions of this problem arise when a fusion center reconstructs an extended physical field by accessing the state of just a few of the sensors measuring the field, or a leader monitors the formation of a team of robots. Given a link cost, the paper presents a polynomial time algorithm to design a minimum cost coordinated network dynamics followed by the agents, under an observability constraint. Read More

In human societies, people's willingness to compete and strive for better social status as well as being envious of those perceived in some way superior lead to social structures that are intrinsically hierarchical. Here we propose an agent-based, network model to mimic the ranking behaviour of individuals and its possible repercussions in human society. The main ingredient of the model is the assumption that the relevant feature of social interactions is each individual's keenness to maximise his or her status relative to others. Read More

Interactions between vehicles and pedestrians have always been a major problem in traffic safety. Experienced human drivers are generally able to analyze the environment and choose driving strategies that will help them avoid crashes. What is not yet clear, however, is how automated vehicles will interact with pedestrians. Read More

Affiliations: 1Department of Computer Science, Stony Brook University, USA, 2SRI International, USA, 3Cyber-Physical Systems Group, Technische Universität Wien, Austria, 4Cyber-Physical Systems Group, Technische Universität Wien, Austria, 5Department of Computer Science, Stony Brook University, USA, 6Department of Computer Science, Stony Brook University, USA

We introduce the concept of a V-formation game between a controller and an attacker, where controller's goal is to maneuver the plant (a simple model of flocking dynamics) into a V-formation, and the goal of the attacker is to prevent the controller from doing so. Controllers in V-formation games utilize a new formulation of model-predictive control we call Adaptive-Horizon MPC (AMPC), giving them extraordinary power: we prove that under certain controllability assumptions, an AMPC controller is able to attain V-formation with probability 1. We define several classes of attackers, including those that in one move can remove R birds from the flock, or introduce random displacement into flock dynamics. Read More

Affect Control Theory (ACT) is a powerful and general sociological model of human affective interaction. ACT provides an empirically derived mathematical model of culturally shared sentiments as heuristic guides for human decision making. BayesACT, a variant on classical ACT, combines affective reasoning with cognitive (denotative or logical) reasoning as is traditionally found in AI. Read More

Organic Computing is an initiative in the field of systems engineering that proposed to make use of concepts such as self-adaptation and self-organisation to increase the robustness of technical systems. Based on the observation that traditional design and operation concepts reach their limits, transferring more autonomy to the systems themselves should result in a reduction of complexity for users, administrators, and developers. However, there seems to be a need for an updated definition of the term "Organic Computing", of desired properties of technical, organic systems, and the objectives of the Organic Computing initiative. Read More

This paper studies optimal communication and coordination strategies in cyber-physical systems for both defender and attacker within a game-theoretic framework. We model the communication network of a cyber-physical system as a sensor network which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noises. The sensors communicate with the estimator over a coherent Gaussian multiple access channel. Read More

How to self-localize large teams of underwater nodes using only noisy range measurements? How to do it in a distributed way, and incorporating dynamics into the problem? How to reject outliers and produce trustworthy position estimates? The stringent acoustic communication channel and the accuracy needs of our geophysical survey application demand faster and more accurate localization methods. We approach dynamic localization as a MAP estimation problem where the prior encodes dynamics, and we devise a convex relaxation method that takes advantage of previous estimates at each measurement acquisition step; The algorithm converges at an optimal rate for first order methods. LocDyn is distributed: there is no fusion center responsible for processing acquired data and the same simple computations are performed for each node. Read More

Social conventions govern countless behaviors all of us engage in every day, from how we greet each other to the languages we speak. But how can shared conventions emerge spontaneously in the absence of a central coordinating authority? The Naming Game model shows that networks of locally interacting individuals can spontaneously self-organize to produce global coordination. Here, we provide a gentle introduction to the main features of the model, from the dynamics observed in homogeneously mixing populations to the role played by more complex social networks, and to how slight modifications of the basic interaction rules give origin to a richer phenomenology in which more conventions can co-exist indefinitely. Read More

The high mobility of Army tactical networks, combined with their close proximity to hostile actors, elevates the risks associated with short-range network attacks. The connectivity model for such short range connections under active operations is extremely fluid, and highly dependent upon the physical space within which the element is operating, as well as the patterns of movement within that space. To handle these dependencies, we introduce the notion of "key cyber-physical terrain": locations within an area of operations that allow for effective control over the spread of proximity-dependent malware in a mobile tactical network, even as the elements of that network are in constant motion with an unpredictable pattern of node-to-node connectivity. Read More

This paper addresses the problem of synchronizing orthogonal matrices over directed graphs. For synchronized transformations (or matrices), composite transformations over loops equal the identity. We formulate the synchronization problem as a least-squares optimization problem with nonlinear constraints. Read More

In recent years, we have observed a significant trend towards filling the gap between social network analysis and control. This trend was enabled by the introduction of new mathematical models describing dynamics of social groups, the advancement in complex networks theory and multi-agent systems, and the development of modern computational tools for big data analysis. The aim of this tutorial is to highlight a novel chapter of control theory, dealing with applications to social systems, to the attention of the broad research community. Read More

A major challenge faced in the design of large-scale cyber-physical systems, such as power systems, the Internet of Things or intelligent transportation systems, is that traditional distributed optimal control methods do not scale gracefully, neither in controller synthesis nor in controller implementation, to systems composed of millions, billions or even trillions of interacting subsystems. This paper shows that this challenge can now be addressed by leveraging the recently introduced System Level Approach (SLA) to controller synthesis. In particular, in the context of the SLA, we define suitable notions of separability for control objective functions and system constraints such that the global optimization problem (or iterate update problems of a distributed optimization algorithm) can be decomposed into parallel subproblems. Read More

Voter control problems model situations in which an external agent tries toaffect the result of an election by adding or deleting the fewest number of voters. The goal of the agent is to make a specific candidate either win (\emph{constructive} control) or lose (\emph{destructive} control) the election. We study the constructive and destructive voter control problems whenadding and deleting voters have a \emph{combinatorial flavor}: If we add (resp. Read More

In this work we study a multi-agent coordination problem in which agents are only able to communicate with each other intermittently through a cloud server. To reduce the amount of required communication, we develop a self-triggered algorithm that allows agents to communicate with the cloud only when necessary rather than at some fixed period. Unlike the vast majority of similar works that propose distributed event- and/or self-triggered control laws, this work doesn't assume agents can be "listening" continuously. Read More

Multi-agent systems (MAS) is able to characterize the behavior of individual agent and the interaction between agents. Thus, it motivates us to leverage the distributed constraint optimization problem (DCOP), a framework of modeling MAS, to solve the user association problem in heterogeneous networks (HetNets). Two issues we have to consider when we take DCOP into the application of HetNet including: (i) How to set up an effective model by DCOP taking account of the negtive impact of the increment of users on the modeling process (ii) Which kind of algorithms is more suitable to balance the time consumption and the quality of soltuion. Read More

Incentive mechanisms for crowdsourcing have been extensively studied under the framework of all-pay auctions. Along a distinct line, this paper proposes to use Tullock contests as an alternative tool to design incentive mechanisms for crowdsourcing. We are inspired by the conduciveness of Tullock contests to attracting user entry (yet not necessarily a higher revenue) in other domains. Read More

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. Read More

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. Read More

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. Read More

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. Read More

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. Read More

The paper proposes an analysis of liquid democracy (or, delegable proxy voting) from the perspective of binary aggregation and of binary diffusion models. We show how liquid democracy on binary issues can be embedded into the framework of binary aggregation with abstentions, enabling the transfer of known results about the latter---such as impossibility theorems---to the former. This embedding also sheds light on the relation between delegation cycles in liquid democracy and the probability of collective abstentions, as well as the issue of individual rationality in a delegable proxy voting setting. Read More

The current mainstream approach to train natural language systems is to expose them to large amounts of text. This passive learning is problematic if we are interested in developing interactive machines, such as conversational agents. We propose a framework for language learning that relies on multi-agent communication. Read More

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. Read More

Algorithms for equilibrium computation generally make no attempt to ensure that the computed strategies are understandable by humans. For instance the strategies for the strongest poker agents are represented as massive binary files. In many situations, we would like to compute strategies that can actually be implemented by humans, who may have computational limitations and may only be able to remember a small number of features or components of the strategies that have been computed. Read More

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. Read More

The paper studies the problem of achieving consensus in multi-agent systems in the case where the dependency digraph $\Gamma$ has no spanning in-tree. We consider the regularization protocol that amounts to the addition of a dummy agent (hub) uniformly connected to the agents. The presence of such a hub guarantees the achievement of an asymptotic consensus. Read More

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. Read More

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. Read More

Coalition formation typically involves the coming together of multiple, heterogeneous, agents to achieve both their individual and collective goals. In this paper, we focus on a special case of coalition formation known as Graph-Constrained Coalition Formation (GCCF) whereby a network connecting the agents constrains the formation of coalitions. We focus on this type of problem given that in many real-world applications, agents may be connected by a communication network or only trust certain peers in their social network. Read More

Consensus formation is investigated for multi-agent systems in which agents' beliefs are both vague and uncertain. Vagueness is represented by a third truth state meaning \emph{borderline}. This is combined with a probabilistic model of uncertainty. Read More

This article examines the problem of visual area coverage by a network of Mobile Aerial Agents (MAAs). Each MAA is assumed to be equipped with a downwards facing camera with a conical field of view which covers all points within a circle on the ground. The diameter of that circle is proportional to the altitude of the MAA, whereas the quality of the covered area decreases with the altitude. Read More

This article addresses the visual area coverage problem using a team of Unmanned Aerial Vehicles (UAVs). The UAVs are assumed to be equipped with a downward facing camera covering all points of interest within a circle on the ground. The diameter of this circular conic-section increases as the UAV flies at a larger height, yet the quality of the observed area is inverse proportional to the UAV's height. Read More

We present a distributed (non-Bayesian) learning algorithm for the problem of parameter estimation with Gaussian noise. The algorithm is expressed as explicit updates on the parameters of the Gaussian beliefs (i.e. Read More