United Kingdom

Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic  applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is  to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations  as well as polynomial-time algorithms for the general setting and important restricted settings.

AAMAS 2021

Multi-Robot Task Allocation—Complexity and Approximation

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS 2020

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

technical paper

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

We present Strategy RV, a tool that allows to approximate the verification of Alternating-time Temporal Logic under imperfect information and perfect recall, which is known to be undecidable, by using Runtime Verification. The tool uses an interface to enter the game model and the specifications and to provide results. We test Strategy RV in a variant of the Curiosity rover scenario and provide some experimental results.

Strategy RV: A Tool to Approximate ATL Model Checking under Imperfect Information and Perfect Recall

In AI, Multi-Agent Systems are able to model many kind of collective behavior and have therefore a wide range of application. In this paper, we propose a logical framework (Logic of "Inferable") which enable reasoning about whether a group of agents can perform an action, highlighting the concepts of cost of actions and of budget that agents have available to perform actions. The focus is on modeling the group dynamics of cooperative agents.

A Logic of Inferable in Multi-Agent Systems with Budget and Costs

Recently, we have proposed a framework for verification of agents' abilities in asynchronous multi-agent systems, together with an algorithm for automated reduction of models. The semantics was built on the modeling tradition of distributed systems. As we show here, this can sometimes lead to counterintuitive interpretation of formulas when reasoning about the outcome of strategies.

Strategic Abilities of Asynchronous Agents: Semantic Side Effects

The goal of this work is to propose a framework for representing and reasoning about the rules governing a combinatorial exchange. Such a framework is at first interest as long as we want to build up digital marketplaces based on auction, a widely used mechanism for automated transactions. Hence the framework should fulfill two requirements: (i) it should enable bidders to express their bids on combinations of goods and (ii) it should allow describing the rules governing some market, namely the legal bids, the allocation and payment rules. To do so, we define a logical language in the spirit of the Game Description Language: the Combinatorial Exchange Description Language is the first language for describing combinatorial exchange in a logical framework. The contribution is two-fold: first, we illustrate the general dimension by representing different kinds of protocols, and second, we show how to reason about auction properties in this machine-processable language.

A General Framework for the Logical Representation of Combinatorial Exchange Protocols

Agents operating in the open world often produce negative side effects (NSE), which are difficult to identify at design time. We examine how a human can assist an agent, beyond providing feedback, and exploit their broader scope of knowledge to mitigate the impacts of NSE. We formulate this problem as a human-agent team with decoupled objectives. The agent optimizes its assigned task, during which its actions may produce NSE. The human shapes the environment through minor reconfiguration actions so as to mitigate the impacts of agent's side effects, without significantly degrading agent performance. We present an algorithm to solve this problem. Empirical evaluation shows that the proposed framework can successfully mitigate NSE, without affecting the agent's ability to complete its assigned task.

Mitigating Negative Side Effects via Environment Shaping

Tournaments are commonly used to identify winners, for example in sports. We study the computational complexity of problems related to scheduling the matches in a tournament and predicting the outcome with a special focus on round-robin tournaments, which is the most prominent tournament type used in sports. Besides the general financial and intrinsically motivated interest of various agents in tournament prediction, the recently very relevant winner determination for suddenly discontinued tournaments is a strong motivation. We show the immense theoretical complexity of predicting the winners in round-robin tournaments even under the assumption that only three matchdays remain to be played. On the other hand, we present an FPT algorithm and analyze its practical complexity using experiments on real-world and generated data, showing the applicability of the algorithm in praxis. To the best of our knowledge, this is the first exact and not purely brute-force oriented approach for predicting round-robin tournaments.

Complexity of Scheduling and Predicting Round-Robin Tournaments

Public announcement logic (PAL) extends multi-agent epistemic logic with dynamic operators modelling the effects of public communication. Allowing quantification over public announcements lets us reason about the existence of an announcement to reach a certain epistemic goal. Two notable examples of logics of quantified announcements are arbitrary public announcement logic (APAL) and group announcement logic (GAL). The notion of common knowledge plays an important role in PAL, and in particular in characterisations of epistemic states that an agent or a group of agents might make come about by performing public announcements. In this paper, we study extensions of APAL and GAL with common knowledge, which has not been done before. We consider both conservative extensions where the semantics of the quantifiers is not changed, as well as extensions where the scope of quantification also includes common knowledge formulas. We compare the expressivity of these extensions relative to each other and other connected logics, and provide sound and complete axiomatisations.

Quantified Announcements and Common Knowledge

The bipolar argumentation framework (BAF) setting is an extension of Dung’s setting for abstract argumentation, that considers an additional relation, called support relation. Several interpretations of such a support relation have been pointed out so far, including deductive, necessity, general and backing supports. These notions of support capture different kinds of interactions between arguments, that do not primarily correspond to attacks. In this paper, we propose a new notion of support, called monotonic support. Our approach is axiomatic: two postulates are introduced for capturing the intuition that underlies this notion of support in formal terms. The first postulate, monotony, prevents the support relation from downgrading the acceptance status of the supported argument. The second postulate, non-triviality, requires the existence of BAFs for which supporting an argument leads to increase its acceptance status. We present a general family of extension-based semantics for BAFs, called support score-based (SSB) semantics, that satisfy the two postulates and are parameterized by some aggregation functions. We prove a characterisation result linking the postulates that a SBB semantics satisfies with the properties of the aggregation functions used to define it. We also show that none of the previously introduced semantics for BAFs satisfies the monotony postulate.

On a Notion of Monotonic Support for Bipolar Argumentation Frameworks

A fair competition, based on the concept of envy-freeness, is a non-eliminating competition where each contestant (team or individual player) may not play against all other contestants, but the total difficulty for each contestant is the same: the sum of the initial rankings of the opponents for each contestant is the same. Similar to other non-eliminating competitions like the Round-robin competition or the Swiss-system competition, the winner of the fair competition is the contestant who wins the most games. The Fair Non-Eliminating Tournament (Fair-NET ) problem can be used to schedule fair competitions whose infrastructure is known. In the Fair-NET problem, we are given an infrastructure of a tournament represented by a graph G and the initial rankings of the contestants represented by a multiset of integers S. The objective is to decide whether G is S-fair, i.e., there exists an assignment of the contestants to the vertices of G such that the sum of the rankings of the neighbors of each contestant in G is the same constant k&#8712; N. We initiate a study of the classical and parameterized complexity of Fair-NET with respect to several central structural parameters motivated by real world scenarios, thereby presenting a comprehensive picture of it.

Multivariate Analysis of Scheduling Fair Competitions

We investigate whether Jacobi preconditioning, accounting for the bootstrap term in temporal difference (TD) learning, can help boost performance of adaptive optimizers. Our method, TDprop, computes a per-parameter learning rate based on the diagonal preconditioning of the TD update rule. We show how this can be used in both n-step returns and TD(?). Our theoretical findings demonstrate that including this additional preconditioning information is comparable to normal semi-gradient TD if the optimal learning rate is found for both via a hyperparameter search. This matches our experimental results. In Deep RL experiments using Expected SARSA, TDprop meets or exceeds the performance of Adam in all tested games under near-optimal learning rates, but a well-tuned SGD can yield similar performance in most settings. Our findings suggest that Jacobi preconditioning may improve upon Adam in Deep RL, but despite incorporating additional information from the TD bootstrap term, may not always be better than SGD. Moreover, they suggest that more theoretical investigations are needed to understand adaptive optimizers under optimal hyperparameter regimes in TD learning: simpler methods may, surprisingly, be theoretically comparable after a hyperparameter search.

Multi-Robot Task Allocation—Complexity and Approximation

Downloads

Next from AAMAS 2021

Strategy RV: A Tool to Approximate ATL Model Checking under Imperfect Information and Perfect Recall

Similar lecture

Off Policy Deep Reinforcement Learning with Analogous Disentangled Exploration

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES