Computer Science - Multiagent Systems Publications (50)


Computer Science - Multiagent Systems Publications

Swarms of robots will revolutionize many industrial applications, from targeted material delivery to precision farming. Controlling the motion and behavior of these swarms presents unique challenges for human operators, who cannot yet effectively convey their high-level intentions to a group of robots in application. This work proposes a new human-swarm interface based on novel wearable gesture-control and haptic-feedback devices. Read More

The computability power of a distributed computing model is determined by the communication media available to the processes, the timing assumptions about processes and communication, and the nature of failures that processes can suffer. In a companion paper we showed how dynamic epistemic logic can be used to give a formal semantics to a given distributed computing model, to capture precisely the knowledge needed to solve a distributed task, such as consensus. Furthermore, by moving to a dual model of epistemic logic defined by simplicial complexes, topological invariants are exposed, which determine task solvability. Read More

Black-Scholes (BS) is the standard mathematical model for option pricing in financial markets. Option prices are calculated using an analytical formula whose main inputs are strike (at which price to exercise) and volatility. The BS framework assumes that volatility remains constant across all strikes, however, in practice it varies. Read More

This dissertation is motivated by the need, in today's globalist world, for a precise way to enable governments, organisations and other regulatory bodies to evaluate the constraints they place on themselves and others. An organisation's modus operandi is enacting and fulfilling contracts between itself and its participants. Yet, organisational contracts should respect external laws, such as those setting out data privacy rights and liberties. Read More

The analysis in Part I revealed interesting properties for subgradient learning algorithms in the context of stochastic optimization when gradient noise is present. These algorithms are used when the risk functions are non-smooth and involve non-differentiable components. They have been long recognized as being slow converging methods. Read More

In large-scale natural disasters, humans are likely to fail when they attempt to reach high-risk sites or act in search and rescue operations. Robots, however, outdo their counterparts in surviving the hazards and handling the search and rescue missions due to their multiple and diverse sensing and actuation capabilities. The dynamic formation of optimal coalition of these heterogeneous robots for cost efficiency is very challenging and research in the area is gaining more and more attention. Read More

In this work a mixed agent-based and discrete event simulation model is developed for a high frequency bus route in the Netherlands. With this model, different passenger growth scenarios can be easily evaluated. This simulation model helps policy makers to predict changes that have to be made to bus routes and planned travel times before problems occur. Read More

Human societies around the world interact with each other by developing and maintaining social norms, and it is critically important to understand how such norms emerge and change. In this work, we define an evolutionary game-theoretic model to study how norms change in a society, based on the idea that different strength of norms in societies translate to different game-theoretic interaction structures and incentives. We use this model to study, both analytically and with extensive agent-based simulations, the evolutionary relationships of the need for coordination in a society (which is related to its norm strength) with two key aspects of norm change: cultural inertia (whether or how quickly the population responds when faced with conditions that make a norm change desirable), and exploration rate (the willingness of agents to try out new strategies). Read More

A social approach can be exploited for the Internet of Things (IoT) to manage a large number of connected objects. These objects operate as autonomous agents to request and provide information and services to users. Establishing trustworthy relationships among the objects greatly improves the effectiveness of node interaction in the social IoT and helps nodes overcome perceptions of uncertainty and risk. Read More

The paper proposes a hierarchical, agent-based, DES supported, distributed architecture for networked organization control. Taking into account enterprise integration engineering frameworks and business process management techniques, the paper intends to apply control engineering approaches for solving some problems of coordinating networked organizations, such as performance evaluation and optimization of workflows. Read More

Recent progress in artificial intelligence enabled the design and implementation of autonomous computing devices, agents, that may interact and learn from each other to achieve certain goals. Sometimes however, a human operator needs to intervene and interrupt an agent in order to prevent certain dangerous situations. Yet, as part of their learning process, agents may link these interruptions that impact their reward to specific states, and deliberately avoid them. Read More

We study the problem of cooperative inference where a group of agents interact over a network and seek to estimate a joint parameter that best explains a set of observations. Agents do not know the network topology or the observations of other agents. We explore a variational interpretation of the Bayesian posterior density, and its relation to the stochastic mirror descent algorithm, to propose a new distributed learning algorithm. Read More

This thesis contributes to the formalisation of the notion of an agent within the class of finite multivariate Markov chains. Agents are seen as entities that act, perceive, and are goal-directed. We present a new measure that can be used to identify entities (called $\iota$-entities), some general requirements for entities in multivariate Markov chains, as well as formal definitions of actions and perceptions suitable for such entities. Read More

This paper contains an axiomatic study of consistent approval-based multi-winner rules, i.e., voting rules that select a fixed-size group of candidates based on approval ballots. Read More

If the influence diagram (ID) depicting a Bayesian game is common knowledge to its players then additional assumptions may allow the players to make use of its embodied irrelevance statements. They can then use these to discover a simpler game which still embodies both their optimal decision policies. However the impact of this result has been rather limited because many common Bayesian games do not exhibit sufficient symmetry to be fully and efficiently represented by an ID. Read More

In this paper, a distributed average tracking problem is studied for Lipschitz-type nonlinear dynamical systems. The objective is to design distributed average tracking algorithms for locally interactive agents to track the average of multiple reference signals. Here, in both the agents' and the reference signals' dynamics, there is a nonlinear term satisfying the Lipschitz-type condition. Read More

In this paper, we argue that the future of Artificial Intelligence research resides in two keywords: integration and embodiment. We support this claim by analyzing the recent advances of the field. Regarding integration, we note that the most impactful recent contributions have been made possible through the integration of recent Machine Learning methods (based in particular on Deep Learning and Recurrent Neural Networks) with more traditional ones (e. Read More

We study the problem of planning tours for an Unmanned Aerial Vehicle (UAV) to visit a given set of sites in the least amount of time. This is the classic Traveling Salesperson Problem (TSP). UAVs have limited battery life and as a result may not be able to visit all the points on a single charge. Read More

The usual epistemic S5 model for multi-agent systems is a Kripke graph, whose edges are labeled with the agents that do not distinguish between two states. We propose to uncover the higher dimensional information implicit in the Kripke graph, by using as a model its dual, a chromatic simplicial complex. For each state of the Kripke model there is a facet in the complex, with one vertex per agent. Read More

In search engines, online marketplaces and other human-computer interfaces large collectives of individuals sequentially interact with numerous alternatives of varying quality. In these contexts, trial and error (exploration) is crucial for uncovering novel high-quality items or solutions, but entails a high cost for individual users. Self-interested decision makers, are often better off imitating the choices of individuals who have already incurred the costs of exploration. Read More

Norms have been extensively proposed as coordination mechanisms for both agent and human societies. Nevertheless, choosing the norms to regulate a society is by no means straightforward. The reasons are twofold. Read More

We present AutonoVi:, a novel algorithm for autonomous vehicle navigation that supports dynamic maneuvers and satisfies traffic constraints and norms. Our approach is based on optimization-based maneuver planning that supports dynamic lane-changes, swerving, and braking in all traffic scenarios and guides the vehicle to its goal position. We take into account various traffic constraints, including collision avoidance with other vehicles, pedestrians, and cyclists using control velocity obstacles. Read More

An event-based state estimation approach for reducing communication in a networked control system is proposed. Multiple distributed sensor agents observe a dynamic process and sporadically transmit their measurements to estimator agents over a shared bus network. Local event-triggering protocols ensure that data is transmitted only when necessary to meet a desired estimation accuracy. Read More

Motivated by economic dispatch and linearly-constrained resource allocation problems, this paper proposes a novel Distributed Approx-Newton algorithm that approximates the standard Newton optimization method. A main property of this distributed algorithm is that it only requires agents to exchange constant-size communication messages. The convergence of this algorithm is discussed and rigorously analyzed. Read More

We consider the problem of controlling the spatiotemporal probability distribution of a robotic swarm that evolves according to a reflected diffusion process, using the space- and time-dependent drift vector field parameter as the control variable. In contrast to previous work on control of the Fokker-Planck equation, a zero-flux boundary condition is imposed on the partial differential equation that governs the swarm probability distribution, and only bounded vector fields are considered to be admissible as control parameters. Under these constraints, we show that any initial probability distribution can be transported to a target probability distribution under certain assumptions on the regularity of the target distribution. Read More

In this paper, we focus on applications in machine learning, optimization, and control that call for the resilient selection of a few elements, e.g. features, sensors, or leaders, against a number of adversarial denial-of-service attacks or failures. Read More

Recently the dynamics of signed networks, where the ties among the agents can be both positive (attractive) or negative (repulsive) have attracted substantial attention of the research community. Examples of such networks are models of opinion dynamics over signed graphs, recently introduced by Altafini (2012,2013) and extended to discrete-time case by Meng et al. (2014). Read More

In this paper we consider the problem of identifying intersections between two sets of d-dimensional axis-parallel rectangles. This is a common problem that arises in many agent-based simulation studies, and is of central importance in the context of High Level Architecture (HLA), where it is at the core of the Data Distribution Management (DDM) service. Several realizations of the DDM service have been proposed; however, many of them are either inefficient or inherently sequential. Read More

This paper focuses on a passivity-based distributed reference governor (RG) applied to a pre-stabilized mobile robotic network. The novelty of this paper lies in the method used to solve the RG problem, where a passivity-based distributed optimization scheme is proposed. In particular, the gradient descent method minimizes the global objective function while the dual ascent method maximizes the Hamiltonian. Read More

This paper presents a novel approach for localising a GPS (Global Positioning System)-denied Unmanned Aerial Vehicle (UAV) with the aid of a GPS-equipped UAV in three-dimensional space. The GPS-equipped UAV makes discrete-time broadcasts of its global coordinates. The GPS-denied UAV simultaneously receives the broadcast and takes direction of arrival (DOA) measurements towards the origin of the broadcast in its local coordinate frame (obtained via an inertial navigation system (INS)). Read More

This paper presents the first ever approach for solving \emph{continuous-observation} Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) and their semi-Markovian counterparts, Dec-POSMDPs. This contribution is especially important in robotics, where a vast number of sensors provide continuous observation data. A continuous-observation policy representation is introduced using Stochastic Kernel-based Finite State Automata (SK-FSAs). Read More

Robust environment perception is essential for decision-making on robots operating in complex domains. Intelligent task execution requires principled treatment of uncertainty sources in a robot's observation model. This is important not only for low-level observations (e. Read More

We consider Arrovian aggregation of preferences over lotteries that are represented by skew-symmetric bilinear (SSB) utility functions, a significant generalization of von Neumann-Morgenstern utility functions due to Fishburn, in which utility is assigned to pairs of alternatives. We show that the largest domain of preferences that simultaneously allows for independence of irrelevant alternatives and Pareto optimality when comparing lotteries based on accumulated SSB welfare is a domain in which preferences over lotteries are completely determined by ordinal preferences over pure alternatives. In particular, a lottery is preferred to another lottery if and only if the former is more likely to return a preferred alternative. Read More

The model presented in this paper experiments with a comprehensive simulant agent in order to provide an exploratory platform in which simulation modelers may try alternative scenarios and participation in policy decision-making. The framework is built in a computationally distributed online format in which users can join in and visually explore the results. Modeled activity involves daily routine errands, such as shopping, visiting the doctor or engaging in the labor market. Read More

A distributed algorithm is described for finding a common fixed point of a family of m>1 nonlinear maps M_i : R^n -> R^n assuming that each map is a paracontraction and that at least one such common fixed point exists. The common fixed point is simultaneously computed by m agents assuming each agent i knows only M_i, the current estimates of the fixed point generated by its neighbors, and nothing more. Each agent recursively updates its estimate of a fixed point by utilizing the current estimates generated by each of its neighbors. Read More

This paper analyses the DeGroot-Friedkin model for evolution of the individuals' social powers in a social network when the network topology varies dynamically (described by dynamic relative interaction matrices). The DeGroot-Friedkin model describes how individual social power (self-appraisal, self-weight) evolves as a network of individuals discuss a sequence of issues. We seek to study dynamically changing relative interactions because interactions may change depending on the issue being discussed. Read More

Voting systems typically treat all voters equally. We argue that perhaps they should not: Voters who have supported good choices in the past should be given higher weight than voters who have supported bad ones. To develop a formal framework for desirable weighting schemes, we draw on no-regret learning. Read More

Although various norms for reciprocity-based cooperation have been suggested that are evolutionarily stable against invasion from free riders, the process of alternation of norms and the role of diversified norms remain unclear in the evolution of cooperation. We clarify the co-evolutionary dynamics of norms and cooperation in indirect reciprocity and also identify the indispensable norms for the evolution of cooperation. Inspired by the gene knockout method, a genetic engineering technique, we developed the norm knockout method and clarified the norms necessary for the establishment of cooperation. Read More

Deep neural networks coupled with fast simulation and improved computation have led to recent successes in the field of reinforcement learning (RL). However, most current RL-based approaches fail to generalize since: (a) the gap between simulation and real world is so large that policy-learning approaches fail to transfer; (b) even if policy learning is done in real world, the data scarcity leads to failed generalization from training to test scenarios (e.g. Read More

This paper revisits the problem of multi-agent consensus from a graph signal processing perspective. By defining the graph filter from the consensus protocol, we establish the direct relation between average consensus of multi-agent systems and filtering of graph signals. This relation not only provides new insights of the average consensus, it also turns out to be a powerful tool to design effective consensus protocols for uncertain networks, which is difficult to deal with by existing time-domain methods. Read More

The integration of multiple viewpoints became an increasingly popular approach to deal with agent-based simulations. Despite their disparities, recent approaches successfully manage to run such multi-level simulations. Yet, are they doing it appropriately? This paper tries to answer that question, with an analysis based on a generic model of the temporal dynamics of multi-level simulations. Read More

The problem of achieving common understanding between agents that use different vocabularies has been mainly addressed by designing techniques that explicitly negotiate mappings between their vocabularies, requiring agents to share a meta-language. In this paper we consider the case of agents that use different vocabularies and have no meta-language in common, but share the knowledge of how to perform a task, given by the specification of an interaction protocol. For this situation, we present a framework that lets agents learn a vocabulary alignment from the experience of interacting. Read More

Affiliations: 1Albert-Ludwigs-Universität Freiburg, 2Technical University of Denmark, 3Albert-Ludwigs-Universität Freiburg, 4Albert-Ludwigs-Universität Freiburg

Epistemic planning can be used for decision making in multi-agent situations with distributed knowledge and capabilities. Recently, Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. We extend the DEL-based epistemic planning framework to include perspective shifts, allowing us to define new notions of sequential and conditional planning with implicit coordination. Read More

Epistemic planning can be used for decision making in multi-agent situations with distributed knowledge and capabilities. Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. In this paper, we aim to give an accessible introduction to DEL-based epistemic planning. Read More

One of the key challenges for multi-agent learning is scalability. In this paper, we introduce a technique for speeding up multi-agent learning by exploiting concurrent and incremental experience sharing. This solution adaptively identifies opportunities to transfer experiences between agents and allows for the rapid acquisition of appropriate policies in large-scale, stochastic, homogeneous multi-agent systems. Read More

One-sided matching mechanisms are fundamental for assigning a set of indivisible objects to a set of self-interested agents when monetary transfers are not allowed. Two widely-studied randomized mechanisms in multiagent settings are the Random Serial Dictatorship (RSD) and the Probabilistic Serial Rule (PS). Both mechanisms require only that agents specify ordinal preferences and have a number of desirable economic and computational properties. Read More

Many real-world problems, such as network packet routing and urban traffic control, are naturally modeled as multi-agent reinforcement learning (RL) problems. However, existing multi-agent RL methods typically scale poorly in the problem size. Therefore, a key challenge is to translate the success of deep learning on single-agent RL to the multi-agent setting. Read More

We consider elections where the voters come one at a time, in a streaming fashion, and devise space-efficient algorithms which identify an approximate winning committee with respect to common multiwinner proportional representation voting rules; specifically, we consider the Approval-based and the Borda-based variants of both the Chamberlin-- ourant rule and the Monroe rule. We complement our algorithms with lower bounds. Somewhat surprisingly, our results imply that, using space which does not depend on the number of voters it is possible to efficiently identify an approximate representative committee of fixed size over vote streams with huge number of voters. Read More

Congestion problems are omnipresent in today's complex networks and represent a challenge in many research domains. In the context of Multi-agent Reinforcement Learning (MARL), approaches like difference rewards and resource abstraction have shown promising results in tackling such problems. Resource abstraction was shown to be an ideal candidate for solving large-scale resource allocation problems in a fully decentralized manner. Read More