New Zealand

Shuhua Liu, Tieli Sun and Chih-cheng Hung (January 30th 2011). Multi-Robot Task Allocation Based on Swarm Intelligence, Multi-Robot Systems, Trends and Development, Toshiyuki Yasuda, IntechOpen, DOI: 10.5772/13106.

Gabriel Oliver and José Guerrero (January 30th 2011). Auction and Swarm Multi-Robot Task Allocation Algorithms in Real Time Scenarios, Multi-Robot Systems, Trends and Development, Toshiyuki Yasuda, IntechOpen, DOI: 10.5772/13281. 

Mildreth Alcaraz-Mejia, Raul Campos-Rodriguez and Marco Caballero-Gutierrez (June 7th 2017). Modeling and Simulation of Task Allocation with Colored Petri Nets, Computer Simulation, Dragan Cvetkovic, IntechOpen, DOI: 10.5772/67950. 

We present an overview of the Task Coordination (TC) problem in multiagent systems and discuss the specific elements that are required to develop a solution to this problem. Task coordination refers to a twofold problem where an exogenously imposed state of affairs should be satisfied by a multiagent system (MAS): (1) the agents need to be assigned tasks to fulfill the given state of affairs (task allocation) and (2) the behavior of agents needs to be monitored to evaluate whether their tasks are fulfilled so that responsibility for dismissed tasks can be determined (task responsibility). This becomes especially challenging when agents are autonomous and may have imperfect information about their environment. Then, the allocation of tasks and responsibilities should regard agents&#39; strategic ability under imperfect information. To date, existing work on the application of strategic reasoning for task allocation assumes perfect information for agents (dismissing imperfect information settings) and allocates tasks to individual agents (dismissing the potential for allocating tasks to agent groups). This calls for TC frameworks able to model task allocation in imperfect information settings and by allowing the allocation of tasks to agent groups. Such a framework should also be able to determine the responsibility of agents for dismissed tasks via a task responsibility mechanism that complements the task allocation procedure. This work discusses various aspects of the TC problem, sets forward a conceptual analysis on expected properties of potential solution concepts, and presents the overview of a suggested approach for developing a TC framework using techniques from formal strategic reasoning.


AAMAS 2020

Task Coordination in Multiagent Systems

applied formal methods

responsibility reasoning

task coordination in mas

strategic reasoning

task allocation

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 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). 

We present an overview of the Task Coordination (TC) problem in multiagent systems and discuss the specific elements that are required to develop a solution to this problem. Task coordination refers to a twofold problem where an exogenously imposed state of affairs should be satisfied by a multiagent system (MAS): (1) the agents need to be assigned tasks to fulfill the given state of affairs (task allocation) and (2) the behavior of agents needs to be monitored to evaluate whether their tasks are fulfilled so that responsibility for dismissed tasks can be determined (task responsibility). This becomes especially challenging when agents are autonomous and may have imperfect information about their environment. Then, the allocation of tasks and responsibilities should regard agents' strategic ability under imperfect information. To date, existing work on the application of strategic reasoning for task allocation assumes perfect information for agents (dismissing imperfect information settings) and allocates tasks to individual agents (dismissing the potential for allocating tasks to agent groups). This calls for TC frameworks able to model task allocation in imperfect information settings and by allowing the allocation of tasks to agent groups. Such a framework should also be able to determine the responsibility of agents for dismissed tasks via a task responsibility mechanism that complements the task allocation procedure. This work discusses various aspects of the TC problem, sets forward a conceptual analysis on expected properties of potential solution concepts, and presents the overview of a suggested approach for developing a TC framework using techniques from formal strategic reasoning.


technical paper

Although plenty of qualitative logical frameworks have been pro- posed to evaluate and model trust in multi-agent sittings, these ap- proaches generally ignore reasoning about quantitative aspects such as degrees of trust. In this paper, we address this limitation from the modelling and verification perspectives. We start by constructing TCTLG , a logical language to represent the quantitative aspect of trust and present a set of its reasoning postulates. Moreover, we develop and implement a new symbolic model checking algorithm and open source tool for quantifying the relationships among the interacting agents. Finally, we investigate the complexity and evaluate our approach using a case study in the health care domain.


Computationally Grounded Quantitative Trust with Time

Defenders in security problems often use anomaly detection (AD) to examine effects of (adversarial) actions and detect malicious behavior. Attackers seek to accomplish their goal (e.g., exfiltrate data) while avoiding the detection. Game theory can be used to reason about this interaction. While AD has been used in game-theoretic frameworks before, we extend the existing works to more realistic settings by (1) allowing players to have continuous action spaces and (2) assuming that the defender cannot perfectly observe the action of the attacker. We solve our model by (1) extending existing algorithms that discretize the action spaces and use linear programming and (2) by training a neural network using an algorithm based on exploitability descent, termed EDA. While both algorithms are applicable for low feature-space dimensions, EDA produces less exploitable strategies and scales to higher dimensions. In a data exfiltration scenario, EDA outperforms a range of classifiers when facing a targeted exploitative attacker.


Discovering Imperfectly Observable Adversarial Actions using Anomaly Detection

In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences [13]: each agent belongs to one of the two types (e.g., juniors and seniors, artists and engineers), and agents’ preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem.


Stable Roommate Problem with Diversity Preferences

In this paper, we relate influence maximisation (IM) for the voting dynamics to models of network control in which external controllers interact with the intrinsic dynamics of opinion spread. In contrast to previous literature, which has mostly explored the discrete
setting, our focus is on continuous allocations of control. We develop an algorithm to numerically solve our IM problem via gradient ascent. We explore optimal allocations for leader-follower type networks for different budget scenarios and observe that optimal
allocations do not systematically target hub nodes, as it has been found in previous literature. Conversely, strategies are strongly opponent-depend, avoiding nodes targeted by the opponent if the opponent has a larger budget, while shadowing the opponent’s
allocation otherwise, i.e. targeting the same nodes as them.


Continuous Influence Maximisation for the Voter Dynamics: Is Targeting High-Degree Nodes a Good Strategy?

Distributed, Automated Calibration of Agent Based Model Parameters And Agent Behaviours

This paper presents a multi-robot long-term planning approach under uncertainty on the duration of tasks. The proposed method- ology takes advantage of generalized stochastic Petri nets to model multi-robot teams. It allows for unified modeling of action selection and uncertainty on duration of action execution. Goals are specified through the use of transition rewards and rewards per time unit. Our approach exploits the semantics provided by Markov reward automata in order to synthesize policies that optimize the long-run average reward. We provide an empirical evaluation on a simulated multi-robot monitoring problem, showing that the synthesized pol- icy outperforms a carefully hand-crafted policy.


Long-Run Multi-Robot Planning With Uncertain Task Durations

Fair division of land is an important practical problem that is commonly handled either by hiring assessors or by selling and dividing the proceeds. A third way to divide land fairly is via algorithms for fair cake-cutting. However, the current theory of fair cake-cutting is
not yet ready to optimally share a plot of land and such algorithms are seldom used in practical land-division.
We attempt to narrow the gap between theory and practice by performing extensive simulations of a classic cake-cutting algorithm on real land-value data. We improve the practical performance of this algorithm using heuristics we developed, and show their effectiveness on real land-value maps compared to actual assessment and sale data on various performance metrics. The cake-cutting algorithms perform better in most metrics.
We further examined the cake cutting algorithm with respect to strategic gain of an agent relative to a truthful agent. The strategic gain was found to be insignificant effect in cake-cutting algorithms.


Fair Cake-Cutting Algorithms with Real Land-Value Data

To transition from control theory to real applications, it is important to study missions such as Swarm Search and Service (SSS) where vehicles are not only required to search an area, but also service all jobs that they find. In SSS missions each type of job requires a group of vehicles to break-off from the swarm for a given amount of time to successfully service it. The required number of vehicles and the service rate are unique to each job type. Once a job has been completed the vehicles are able to return to the swarm for use elsewhere. If not enough vehicles are present in the swarm at the time that the job is identified, that job is dropped without being serviced. In SSS missions that occur in open environments, the arrival rate of jobs varies dynamically as vehicles move in and out of the swarm to service jobs. Human operators as tasked with effectively planning and managing these complex missions. This paper presents a user study that seeks to test the efficacy and ease-of-use of a prediction model known as the Hybrid Model as an aid in planning and monitoring tasks. Results show that the novel computational model aid allows operators to more effectively choose the necessary swarm size to handle expected mission workload, as well as, maintain sufficient situation awareness to evaluate the performance of the swarm during missions.


Human-in-the-loop Planning and Monitoring of Swarm Search and Service Missions

Representing unknown and missing knowledge about the environment is fundamental to leverage robot behavior and improve its performance in completing a task. However, reconstructing spatial knowledge beyond the sensory horizon of the robot is an extremely
challenging task. Existing approaches assume that the environment static and features repetitive patterns (e.g. rectangular rooms) or that it can be all generalized with pre-trained models. Our goal is to remove such assumptions and to introduce a novel methodology that allows the robot to represent unknown spatial knowledge in dynamic and unstructured environments. To this end, we exploit generative learning to (1) learn a distribution of spatial landmarks observed during the robot mission and to (2) generate missing in- formation in real-time. The proposed approach aims at supporting planning and decision-making processes needed for robot behaviors. In this paper, we describe architecture modeling the proposed approach and a first validation on a mobile platform.

GUESs: Generative Modeling of Unknown Environments and Spatial Abstraction for robots

In participatory budgeting, citizens can take part in the decision on which projects a city should spend money. Formally, the input is a set of items, each having a certain cost, while agents can express their preferences. The task is to choose a set of items respecting a given bound. Recently Talmon and Faliszewski introduced a framework for budgeting based on approval votes. This paper revisits the introduced methods axiomatically from an irresolute point of view, especially showing that two of the proposed methods coincide. The study is complemented by approximation results.


Downloads

Next from AAMAS 2020

Computationally Grounded Quantitative Trust with Time

Similar lecture

Design and Evaluations of Multi-Agent Simulation Model for Electric Power Sharing among Households

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2020

Computationally Grounded Quantitative Trust with Time

Similar lecture

Design and Evaluations of Multi-Agent Simulation Model for Electric Power Sharing among Households

Downloads