New Zealand

Miłosz Michalski (July 24th 2013). Computational Complexity in the Analysis of Quantum Operations, Open Systems, Entanglement and Quantum Optics, Andrzej Jamiolkowski, IntechOpen, DOI: 10.5772/56159. 

Randa Khemiri, Nejmeddine Bahri, Fatma Belghith, Soulef Bouaafia, Fatma Elzahra Sayadi, Mohamed Atri and Nouri Masmoudi (October 23rd 2019). Fast Motion Estimation’s Configuration Using Diamond Pattern and ECU, CFM, and ESD Modes for Reducing HEVC Computational Complexity [Online First], IntechOpen, DOI: 10.5772/intechopen.86792. 

Weiqi Li (December 12th 2019). Solution Attractor of Local Search System: A Method to Reduce Computational Complexity of the Traveling Salesman Problem [Online First], IntechOpen, DOI: 10.5772/intechopen.90521. 

When dealing with election data it is reasonable to assume that the votes are incomplete or noisy. The reasons are manifold and range from cost-intensive elicitation to manipulation. We study the important questions of evaluating elections with incomplete data and the robustness of elections with noisy data from a computational point of view. To capture different motivations, we consider three models for the distribution of preferences: the uniform distribution over the completions of incomplete preferences inspired by the possible winner problem, the dispersion around complete preferences, also called Mallows noise model, and a model in which the distribution over the votes of each voter is explicitly given. We consider both approval vector preferences and linear order preferences and show that the complexity of the problem can vary greatly depending on the voting rule, the distribution model, and the parameterization.


AAMAS 2020

Complexity of Election Evaluation and Probabilistic Robustness

probabilistic social choice

voting

computational complexity

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

AAAI 2022

technical paper

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

In this paper, we propose a self-adaptive approach to build a smart traffic light management dealing with intersections. This approach relies on the multiagent systems architecture, suitable to support a distributed and collaborative mechanism of regulation while taking into account dynamic changes in the traffic flow. In our solution, the agents model the intersections and can decide how long is the duration of traffic lights according to their perception of the traffic flow. Each intersection agent uses a behavior tree to update the traffic light status (i.e. switch from green to red lights and vice-versa), changing the duration of each status dynamically, according to the number of cars perceived in each intersection. We also demonstrate how dynamic traffic control policies can be used in a collaborative scenario to regulate traffic flow. 


Adaptive and Collaborative Agent-based Traffic Regulation Using Behavior Trees

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.


Task Coordination in Multiagent Systems

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.


Downloads

Next from AAMAS 2020

Adaptive and Collaborative Agent-based Traffic Regulation Using Behavior Trees

Similar lecture

Truth-Tracking via Approval Voting: Size Matters

.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

Adaptive and Collaborative Agent-based Traffic Regulation Using Behavior Trees

Similar lecture

Truth-Tracking via Approval Voting: Size Matters

Downloads