Extended Abstracts

Computational models of motivation are tools that artificial agents can use to autonomously identify, prioritize, and select the goals they will pursue. Previous research has focused on developing computational models of arousal-based theories of motivation, including novelty, curiosity and interest. However, arousal-based theories represent only one aspect of motivation. In humans, for example, curiosity is tempered by other motivations such as the need for health, safety, competence, a sense of belonging, esteem from others or influence over others. To create artificial agents that can identify and prioritize their goals according to this broader range of needs, new kinds of computational models of motivation are required. This paper expands our `motivation toolbox' with a new computational model of achievement motivation for artificial agents. The model uses sigmoid curves to model approach of success and avoidance of failure. An experiment from human psychology is simulated to test the new model in virtual agents. The results are compared to human results and existing theoretical and computational models. Results show that virtual agents using our model exhibit statistically similar goal-selection characteristics to humans with corresponding motive profiles. In addition, our model outperforms existing models of achievement motivation in this respect. A Computational Model of Achievement Motivation for Artificial Agents Kathryn E. Merrickhas 2 papers

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper bounds from the previous DCOP when solving the next one in the sequence. Our experimental results show that the speedup gained from this procedure increases with the amount of memory the agents have available. Incremental DCOP Search Algorithms for Solving Dynamic DCOPs William Yeoh, Pradeep Varakanthamhas 4 papers, Xiaoxun Sunhas 2 papers, Sven Koenighas 2 papers

A traditional approach to reasoning about the trustworthiness of a transaction is to determine the trustworthiness of the specific agent involved, based on its past behavior. As a departure from such traditional trust models, we propose a transaction centered trust model (MetaTrust) where an agent uses its previous transactions to assess the trustworthiness of a potential transaction based on associated meta-information, which is capable of distinguishing successful transactions from unsuccessful ones. This meta information is harnessed using a machine learning algorithm (namely, discriminant analysis) to extract relationships between the potential transaction and previous transactions. MetaTrust: Discriminant Analysis of Local Information for Global Trust Assessment Liu Xin, Gilles Tredan, Anwitaman Datta

This paper studies the problem of collective decision-making in combinatorial domain where the agents' preferences are represented by qualitative models with TCP-nets (Tradeoffs-enhanced Conditional Preference Network). The features of TCP-nets enable us to easily encode human preferences and the relative importance between the decision variables; however, many group decision-making methods require numerical measures of degrees of desirability of alternative outcomes. To permit a natural way for preference elicitation while providing quantitative comparisons between outcomes, we present a computationally efficient approach that compiles individual TCP-nets into ordinal penalty scoring functions. After the individual penalty scores are computed, we further define a collective penalty scoring function to aggregate multiple agents' preferences. Efficient Penalty Scoring Functions for Group Decision-making with TCP-nets Minyi Lihas 3 papers, Quoc Bao Vohas 4 papers, Ryszard Kowalczykhas 4 papers

This paper presents a novel approach to intrusion detection using curious agents to detect anomalies in network data. Curious agents use computational models of novelty-seeking behavior and interest, based on human curiosity, to reason about their experiences in their environment. They are online, single-pass agents that respond to the similarity, frequency and recentness of their experiences. As such, they combine a number of important characteristics required for intrusion detection. This paper presents a generic, curious reflex agent model for network intrusion detection and the results of experiments with a number of variants of this model. Specifically, five different models of curiosity are compared for their ability to detect first instances of attacks in the KDD Cup data set. Results show that our curious agents can achieve high detection rates for intrusions, with moderate false-positive rates. A Curious Agent for Network Anomaly Detection Kamran Shafi, Kathryn E. Merrickhas 2 papers

Some agent-based models use digital analogs of insect pheromones for coordination. Such models are intermediate between classical agent-based models and equation-based “mean field” models. Their position in this range can be adjusted by pheromone parameters (notably, the propagation factor). Agents, Pheromones, and Mean-Field Models H. Van Dyke Parunak

We study the problem of automatically generating features for function approximation in reinforcement learning. We build on the work of Mahadevan and his colleagues, who pioneered the use of spectral clustering methods for basis function construction. Their methods work on top of a graph that captures state adjacency. Instead, we use bisimulation metrics in order to provide state distances for spectral clustering. The advantage of these metrics is that they incorporate reward information in a natural way, in addition to the state transition information. We provide theoretical bounds on the quality of the obtained approximation, which justify the importance of incorporating reward information. We also demonstrate empirically that the approximation quality improves when bisimulation metrics are used instead of the state adjacency graph in the basis function construction process. Basis Function Discovery using Spectral Clustering and Bisimulation Metrics Gheorghe Comanici, Doina Precuphas 2 papers

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use. Incentive Compatible Influence Maximization in Social Networks and Application to Viral Marketing Mayur Mohite, Y. Narahari

This paper analyzes bilateral multi-issue negotiation where the issues are indivisible, there are time constraints in the form of deadlines and discount factors. The issues are negotiated using the package deal procedure. The set of issues to be negotiated is called the negotiation agenda. The agenda is crucial since the outcome of negotiation depends on the agenda. This paper therefore looks at the decision making involved in choosing a negotiation agenda. The scenario we look at is as follows. There are m > 2 issues available for negotiation. But from these, an agent must choose g < m issues and negotiate on them. Thus the problem for an agent is to choose an agenda (i.e, a subset of g issues). Clearly, from all possible agendas (i.e., all possible combinations of g issues), an agent must choose the one that maximizes its expected utility and is therefore its optimal agenda. To this end, this paper presents polynomial time methods for choosing an agent's optimal agenda. On Optimal Agendas for Package Deal Negotiation Shaheen Fatima, Michael Wooldridgehas 6 papers, Nicholas R. Jenningshas 9 papers

We present an abstract framework that allows agents to form coalitions with agents that they believe to be trustworthy. In contrast to many other models, we take the notion of distrust to be our key social concept. We use a graph theoretic model to capture the distrust relations within a society, and use this model to formulate several notions of mutually trusting coalitions. We then investigate principled techniques for how the information present in our distrust model can be aggregated to produce individual measures of how trustworthy an agent is considered to be by a society. An Abstract Framework for Reasoning About Trust Elisabetta Erriquezhas 2 papers, Wiebe van der Hoekhas 5 papers, Michael Wooldridgehas 6 papers

Decentralized POMDPs provide a rigorous framework for multi-agent decision-theoretic planning. However, their high complexity has limited scalability. In this work, we present a promising new class of algorithms based on probabilistic inference for infinite-horizon ND-POMDPs—a restricted Dec-POMDP model. We first transform the policy optimization problem to that of likelihood maximization in a mixture of dynamic Bayes nets (DBNs). We then develop the Expectation-Maximization (EM) algorithm for maximizing the likelihood in this representation. The EM algorithm for ND-POMDPs lends itself naturally to a simple messagepassing paradigm guided by the agent interaction graph. It is thus highly scalable w.r.t. the number of agents, can be easily parallelized, and produces good quality solutions. Message-Passing Algorithms for Large Structured Decentralized POMDPs Akshat Kumar, Shlomo Zilbersteinhas 2 papers

We describe research on principles of context-sensitive reminding that show promise for serving in systems that work to jog peoples' memories about information that they may forget. The methods center on the construction and use of a set of distinct probabilistic models that predict (1) items that may be forgotten, (2) the expected relevance of the items in a situation, and (3) the cost of interruption associated with alerting about a reminder. We describe the use of this set of models in the Jogger prototype that employs predictions and decision-theoretic optimization to compute the value of reminders about meetings. Jogger: Models for Context-Sensitive Reminding Ece Kamar, Eric Horvitz

This paper presents an offline collision-free path planning algorithm for multiple mobile robots using a 2D spatial-time map. In this decoupled approach, a centralized planner uses a Spatio-Temporal A* algorithm to find the lowest time cost path for each robot in a sequentially order based on its assigned priority. Improvements in viable path solutions using wait time insertion and adaptive priority reassignment strategies are discussed. Spatio-Temporal A* Algorithms for Offline Multiple Mobile Robot Path Planning Wenjie Wang, Wooi Boon Goh

The aim of this research is to explore the influence of static visual cues on the perception of a character's personality traits: extraversion, agreeableness and emotional stability. To measure how users perceived personality, we conducted a web-based study with 133 subjects who rated 54 images of a virtual character with varying head orientations and gaze. Influence of Head Orientation in Perception of Personality Traits in Virtual Agents Diana Arellano, Nikolaus Bee, Kathrin Janowski, Elisabeth Andréhas 2 papers, Javier Varona, Francisco J. Perales

Conflicts exist in multi-agent systems for a number of reasons: agents have different interests and desires; agents hold different beliefs; agents make different assumptions. To resolve conflicts, agents need to better convey information to each other and facilitate fair negotiations yielding jointly agreeable outcomes. We present a two-agent, dialogical conflict resolution scheme developed with the Assumption-Based Argumentation (ABA) framework. Conflict Resolution with Argumentation Dialogues Xiuyi Fanhas 2 papers, Francesca Tonihas 2 papers

Bayesian games have been traditionally employed to describe and analyze situations in which players have private information or are uncertain about the game being played. However, computing Bayes-Nash equilibria can be costly, and becomes even more so if the common prior assumption (CPA) has to be abandoned, which is sometimes necessary for a faithful representation of real-world systems. We propose using the theory of reasoning patterns in Bayesian games to circumvent some of these difficulties. The theory has been used successfully in common knowledge (non-Bayesian) games, both to reduce the computational cost of finding an equilibrium and to aid human decision-makers in complex decisions. In this paper, we first show that reasoning patterns exist for every decision of every Bayesian game, in which the acting agent has a reason to deliberate. This implies that reasoning patterns are a complete characterization of the types of reasons an agent might have for making a decision. Second, we illustrate practical applications of reasoning patterns in Bayesian games, which allow us to answer questions that would otherwise not be easy in traditional analyses, or would be extremely costly. We thus show that the reasoning patterns can be a useful framework in analyzing complex social interactions. Reasoning Patterns in Bayesian Games Dimitrios Antoshas 2 papers, Avi Pfeffer

Wind power is becoming a significant source of electricity in many countries. However, the inherent uncertainty of wind generators does not allow them to participate in the forward electricity markets. In this paper, we foster a tighter integration of wind power into electricity markets by using a multi-agent coalition formation approach to form virtual power plants of wind generators and electric vehicles. We identify the four different phases in the life-cycle of a VPP, each characterised by its own challenges that need to be addressed. Using Coalitions of Wind Generators and Electric Vehicles for Effective Energy Market Participation Matteo Vasirani, Ramachandra Kotahas 2 papers, Renato L.G. Cavalcantehas 2 papers, Sascha Ossowski, Nicholas R. Jenningshas 9 papers

We consider the role of negotiation in deciding decommitment penalties. In our model, agents simultaneously negotiate over both the contract price and decommitment penalty in the contracting game and then decide whether to decommit from contracts in the decommitment game. Experimental results show that setting penalties through negotiation achieved higher social welfare than other exogenous penalty setting mechanisms. Negotiation Over Decommitment Penalty Bo Anhas 2 papers, Victor Lesserhas 4 papers

In the problem of multiagent patrol, a team of agents is required to repeatedly visit a target area in order to monitor possible changes in state. The growing popularity of this problem comes mainly from its immediate applicability to a wide variety of domains. In this paper we concentrate on frequency-based patrol, in which the agents' goal is to optimize a frequency criterion, namely, minimizing the time between visits to a set of interest points. In situations with varying environmental conditions, the influence of changes in the conditions on the cost of travel may be immense. For example, in marine environments, the travel time of ships depends on parameters such as wind, water currents, and waves. Such environments raise the need to consider a new multiagent patrol strategy which divides the given area into regions in which more than one agent is active, for improving frequency. We prove that in general graphs this problem is intractable, therefore we focus on simplified (yet realistic) cyclic graphs with possible inner edges. Although the problem remains generally intractable in such graphs, we provide a heuristic algorithm that is shown to significantly improve point-visit frequency compared to other patrol strategies. Ship Patrol: Multiagent Patrol under Complex Environmental Conditions Noa Agmonhas 2 papers, Daniel Urielihas 2 papers, Peter Stonehas 5 papers

Recently, an evolutionary model of Lenient Q-learning (LQ) has been proposed, providing theoretical guarantees of convergence to the global optimum in cooperative multi-agent learning. However, experiments reveal discrepancies between the predicted dynamics of the evolutionary model and the actual learning behavior of the Lenient Q-learning algorithm, which undermines its theoretical foundation. Moreover it turns out that the predicted behavior of the model is more desirable than the observed behavior of the algorithm. We propose the variant Lenient Frequency Adjusted Q-learning (LFAQ) which inherits the theoretical guarantees and resolves this issue. The advantages of LFAQ are demonstrated by comparing the evolutionary dynamics of lenient vs non-lenient Frequency Adjusted Q-learning. In addition, we analyze the behavior, convergence properties and performance of these two learning algorithms empirically in the Battle of the Sexes (BoS) and the Stag Hunt (SH). Significant deviations arise from the introduction of leniency, leading to profound performance gains in coordination games against both lenient and non-lenient learners. Empirical and Theoretical Support for Lenient Learning Daan Bloembergenhas 2 papers, Michael Kaisershas 3 papers, Karl Tuylshas 4 papers

A defining characteristic of intelligent software agents is their ability to flexibly and reliably pursue goals, and many modern agent platforms provide some form of goal construct. However, these platforms are surprisingly naive in their handling of interactions between goals. Whilst previous work has provided mechanisms to identify and react appropriately to various sorts of interactions, it has not provided a framework for reasoning about goal interactions that is generic, extensible, formally described, and that covers a range of interaction types. A Formal Framework for Reasoning about Goal Interactions Michael Winikoffhas 3 papers

Institutions offer the promise of a means to govern open systems, in particular, open multi-agent systems. Research in logics and their derived tools now support the specification, verification and enactment of institutions (or organizations, depending on the terminology of the tool). Most effort to date has tended to focus on the static properties of institutions, such as whether a particular state of affairs is reachable or not from a given set of initial conditions. Such models are useful in forcing the designer to state their intentions precisely, and for testing (static) properties. We call this off-line reasoning. We identify two problems in the direct utilization of off-line models in the governance of live systems: (i) static model artefacts that are typically aspects of agent behaviour in the dynamic model (ii) over-specification of constraints on actions, leading to undue limitation of agent autonomy. Agents need to be able to query an institution for (dynamic) properties. We call this on-line reasoning. In this paper we present a methodology to extract the on-line specification from an off-line one and use it to support BDI agents to realize a norm-governed multi-agent system. On-line Reasoning for Institutionally-Situated BDI agents Tina Balke, Marina De Vos, Julian Padget, Dimitris Traskas

There has been significant recent interest in computing good strategies for large games. Most prior work involves computing an approximate equilibrium strategy in a smaller abstract game, then playing this strategy in the full game. In this paper, we present a modification of this approach that works by constructing a deterministic strategy in the full game from the solution to the abstract game; we refer to this procedure as purification. We show that purification, and its generalization which we call thresholding, lead to significantly stronger play than the standard approach in a wide variety of experimental domains. One can view these approaches as ways of achieving robustness against one's own lossy abstraction. Strategy Purification Sam Ganzfriedhas 2 papers, Tuomas Sandholmhas 2 papers, Kevin Waugh

Container terminals play a critical role in international shipping and are under pressure to cope with increasing container traffic. The problem of managing container terminals effectively has a number of characteristics that suggest the use of agent technology would be beneficial. This paper describes a joint industry-university project which has explored the applicability of agent technology to the domain of container terminal management. Agent-Based Container Terminal Optimisation Stephen Cranefieldhas 2 papers, Roger Jarquin, Guannan Li, Brent Martin, Rainer Unland, Hanno-Felix Wagner, Michael Winikoffhas 3 papers, Thomas Young

Recent research has demonstrated that considering local interactions among agents in specific parts of the state space, is a successful way of simplifying the multi-agent learning process. By taking into account other agents only when a conflict is possible, an agent can significantly reduce the state-action space in which it learns. Current approaches, however, consider only the immediate rewards for detecting conflicts. This restriction is not suitable for realistic systems, where rewards can be delayed and often conflicts between agents become apparent only several time-steps after an action has been taken. In this paper, we contribute a reinforcement learning algorithm that learns where a strategic interaction among agents is needed, several time-steps before the conflict is reflected by the (immediate) reward signal. Solving Delayed Coordination Problems in MAS Yann-Michaël De Hauwere, Peter Vrancx, Ann Nowéhas 2 papers

This paper demonstrates a biologically- and psychologically- inspired human – like computational memory focusing on the retrieval mechanisms – Spreading Activation and Compound Cue for a companion agent's episodic memory (EM) that helps the agent to manage it's memory more efficiently and enable it to have a more natural interaction with the user. Human-like Memory Retrieval Mechanisms for Social Companions Mei Yii Limhas 2 papers, Ruth Ayletthas 2 papers, Patricia A. Vargashas 2 papers, Wan Ching Hohas 2 papers, João Dias

This research investigates event generalisation in computational episodic memory for artificial companions. Two studies indicated a preference of a biologically-inspired selective memory over an absolute memory companion. Consequently, we present a preliminary implementation of a forgetting mechanism that enables the companion to create “generalised event representations” from its experiences allowing the companion to learn from past encounters. Forgetting Through Generalisation - A Companion with Selective Memory Mei Yii Limhas 2 papers, Ruth Ayletthas 2 papers, Patricia A. Vargashas 2 papers, Sibylle Enz, Wan Ching Hohas 2 papers

With the advent of algorithmic coalitional game theory, it is important to design coalitional game representation schemes that are both compact and efficient with respect to solution concept computation. To this end, we propose a new representation for coalitional games, which is based on Algebraic Decision Diagrams (ADDs). Our representation is fully expressive, compact for many games of practical interest, and enables polynomial time Banzhaf Index, Shapley Value and core computation. Representation of Coalitional Games with Algebraic Decision Diagrams Karthik .V. Aadithya, Tomasz P. Michalak, Nicholas R. Jenningshas 9 papers

We present a self-adaptation mechanism for Network Intrusion Detection System which uses a game-theoretical mechanism to increase system robustness against targeted attacks on IDS adaptation. We model the adaptation process as a strategy selection in sequence of single stage, two player games. The key innovation of our approach is a secure runtime game definition and numerical solution and real-time use of game solutions for dynamic system reconfiguration. Our approach is suited for realistic environments where we typically lack any ground truth information regarding traffic legitimacy/maliciousness and where the significant portion of system inputs may be shaped by the attacker in order to render the system ineffective. Therefore, we rely on the concept of challenge insertion: we inject a small sample of simulated attacks into the unknown traffic and use the system response to these attacks to define the game structure and utility functions. This approach is also advantageous from the security perspective, as the manipulation of the adaptive process by the attacker is far more difficult. Our experimental results suggest that the use of game-theoretical mechanism comes with little or no penalty when compared to traditional self-adaptation methods. Game Theoretical Adaptation Model for Intrusion Detection System Martin Rehak, Michal Pěchoučekhas 5 papers, Martin Grill, Jan Stiborek, Karel Bartos

Bilateral bargaining has received a lot of attention in the multi-agent literature and has been studied with different approaches. According to the strategic approach, bargaining is modeled as a non-cooperative game with uncertain information and infinite actions. Its resolution is a long-standing open problem and no algorithm addressing uncertainty over multiple parameters is known. In this paper, we provide an algorithm to solve bargaining with any kind of one-sided uncertainty. Our algorithm reduces a bargaining problem to a finite game, solves this last game, and then maps its strategies with the original continuous game. We prove that with multiple types the problem is hard and only small settings can be solved in exact way. In the other cases, we need to resort to concepts of approximate equilibrium and to abstractions for reducing the size of the game tree. Solving Strategic Bargaining with Arbitrary One-Sided Uncertainty Sofia Ceppihas 2 papers, Nicola Gattihas 4 papers, Claudio Iuliano

Given an argumentation framework and a group of agents, the individuals may have divergent opinions on the status of the arguments. If the group needs to reach a common position on the argumentation framework, the question is how the individual evaluations can be mapped into a collective one. This problem has been recently investigated. In this paper, we study under which conditions these operators are Pareto optimal and whether they are manipulable. Manipulation in Group Argument Evaluation Martin Caminadahas 2 papers, Gabriella Pigozzihas 2 papers, Mikołaj Podlaszewskihas 2 papers

We propose an abstraction technique for model checking multi-agent systems given as modular interpreted systems (MIS) which allow for succinct representations of compositional systems. Specifications are given as arbitrary ATL formulae, i.e., we can reason about strategic abilities of groups of agents. Our technique is based on collapsing each agent's local state space with hand-crafted equivalence relations, one per strategic modality. We develop a model checking algorithm and prove its soundness. This makes it possible to perform model checking on abstractions (which are much smaller in size) rather than on the concrete system which is usually too complex, thereby saving space and time. Abstraction for Model Checking Modular Interpreted Systems over ATL Michael Köster, Peter Lohmann

Virtual Institutions (VI) provide many interesting possibilities for social virtual environments, collaborative spaces and simulation environments. VIs combine Electronic Institutions and 3D Virtual Worlds. While Electronic Institutions are used to establish the regulations which structure participants interactions, Virtual Worlds are used to facilitate human participation. In this paper we propose Virtual Institution Execution Environment (VIXEE) as an innovative communication infrastructure for Virtual Institutions. Main features of the infrastructure are i) the causal connection between Virtual World and Electronic Institutions layers, ii) the automatic generation and update of VIs 3D visualization and iii) the simultaneous participation of users from different Virtual World platforms. VIXEE an Innovative Communication Infrastructure for Virtual Institutions Tomas Trescak, Marc Esteva, Inmaculada Rodriguez

The idea of Smart Walkers is to equip customary rolling walkers with sensors in order to assist users, caregivers and clinicians. The integral part of the Smart Walkers is an autonomous agent which monitors the activity of the user, assesses his physical conditions, and detects potential risks of falls. In this paper, we study methods which enable the agent to recognize the user activity from the sensor measurements. The proposed methods use Conditional Random Fields with features based on discriminant rules. A special case are features which, in order to distinguish between two activities, compare the sensor measurements to thresholds learned by a linear classifier. Experiments with real user data show that the methods achieve a good accuracy; the best results are obtained using “smooth” thresholds based on sigmoid functions. Smart Walkers! Enhancing the Mobility of the Elderly Mathieu Sinn, Pascal Pouparthas 2 papers

Going along the questions of how, when and to what extent does empathy arise in humans, we propose an approach to model empathy for EMMA - an Empathic MultiModal Agent - based on three processing steps: First, the Empathy Mechanism by which an empathic emotion is produced. Second, the Empathy Modulation by which the empathic emotion is modulated. Third, the Expression of Empathy by which EMMA's modulated empathic emotion is expressed through her multiple modalities. The proposed model is integrated in a conversational agent scenario involving the virtual humans MAX and EMMA. Modeling Empathy for a Virtual Human: How, When and to What Extent? Hana Boukricha, Ipke Wachsmuthhas 2 papers

In the context of multi-agent hypothetical reasoning, agents typically have partial knowledge about their environments, and the union of such knowledge is still incomplete to represent the whole world. Thus, given a global query they need to collaborate with each other to make correct inferences and hypothesis, whilst maintaining global constraints. There are many real world applications in which the confidentiality of agent knowledge is of primary concern, and hence the agents may not share or communicate all their information during the collaboration. This extra constraint gives a new challenge to multi-agent reasoning. This paper shows how this dichotomy between “open communication” in collaborative reasoning and protection of confidentiality can be accommodated, by extending a general-purpose distributed abductive logic programming system for multi-agent hypothetical reasoning with confidentiality. Specifically, the system computes consistent conditional answers for a query over a set of distributed normal logic programs with possibly unbound domains and arithmetic constraints, preserving the private information within the logic programs. Multi-Agent Abductive Reasoning with Confidentiality Jiefei Ma, Alessandra Russo, Krysia Broda, Emil Lupu

BDI agents often have to make decisions about which plan is used to achieve a goal, and in which order goals are to be achieved. In this paper we describe how to incorporate preferences (based on the LPP language) into the BDI execution model. Reasoning About Preferences in BDI Agent Systems Simeon Visser, John Thangarajahhas 2 papers, James Harland

In this paper, we propose a new approach to using probabilistic hierarchical task networks (HTNs) as an effective method for agents to plan in conditions in which their problem-solving knowledge is uncertain, and the environment is non-deterministic. In such situations it is natural to model the environment as a Markov decision process (MDP). We show that using Earley graphs, it is possible to bridge the gap between HTNs and MDPs. We prove that the size of the Earley graph created for given HTNs is bounded by the total number of tasks in the HTNs and show that from the Earley graph we can then construct a plan for a given task that has the maximum expected value when it is executed in an MDP environment. Probabilistic Hierarchical Planning over MDPs Yuqing Tanghas 2 papers, Felipe Meneguzzihas 2 papers, Katia Sycarahas 7 papers, Simon Parsonshas 3 papers

Fair division methods offer guarantees to agents of the proportional size or quality of their share in a division of a resource (cake). These guarantees come with a price. Standard fair division methods (or “cake cutting” algorithms) do not find efficient allocations (not Pareto optimal). The lack of efficiency of these methods makes them less attractive for solving multi-agent resource and task allocation. Previous attempts to increase the efficiency of cake cutting algorithms for two agents resulted in asymmetric methods that were limited in their ability to find allocations in which both agents receive more than their proportional share. Trust can be the foundation on which agents exchange information and enable the exploration of allocations that are beneficial for both sides. On the other hand, the willingness of agents to put themselves in a vulnerable position due to their trust in others, results in loss of the fairness guarantees that motivate the design of fair division methods. In this work we extend the study on fair and efficient cake cutting algorithms by proposing a new notion of trust-based efficiency, which formulates a relation between the level of trust between agents and the efficiency of the allocation. Furthermore, we propose a method for finding trust-based efficiency. The proposed method offers a balance between the guarantees that fair division methods offer to agents and the efficiency that can be achieved by exposing themselves to the actions of other agents. When the level of trust is the highest, the allocation produced by the method is globally optimal (social welfare). Can Trust Increase the Efficiency of Cake Cutting Algorithms? Roie Zivanhas 2 papers

This research is motivated by problems in urban transportation and labor mobility, where the agent flow is dynamic, non-deterministic and on a large scale. In such domains, even though the individual agents do not have an identity of their own and do not explicitly impact other agents, they have implicit interactions with other agents. While there has been much research in handling such implicit effects, it has primarily assumed controlled movements of agents in static environments. We address the issue of decision support for individual agents having involuntary movements in dynamic environments. For instance, in a taxi fleet serving a city: (i) Movements of a taxi are uncontrolled when it is hired by a customer. (ii) Depending on movements of other taxis in the fleet, the environment and hence the movement model for the current taxi changes. Towards addressing this problem, we make three key contributions: (a) A framework to represent the decision problem for individuals in a dynamic population, where there is uncertainty in movements; (b) A novel heuristic technique called Iterative Sampled OPtimization (ISOP) and greedy heuristics to solve large scale problems in domains of interest; and (c) Analyze the solutions provided by our techniques on problems inspired from a real world data set of a taxi fleet operator in Singapore. As shown in the experimental results, our techniques are able to provide strategies that outperform “driver” strategies with respect to: (i) overall availability of taxis; and (ii) the revenue obtained by the taxi drivers. Decentralized Decision Support for an Agent Population in Dynamic and Uncertain Domains Pradeep Varakanthamhas 4 papers, Shih-Fen Cheng, Nguyen Thi Duong

In today's world, organizations are faced with increasingly large and complex problems that require decision-making under uncertainty. Current methods for optimizing such decisions fall short of handling the problem scale and time constraints. We argue that this is due to existing methods not exploiting the inherent structure of the organizations which solve these problems. We propose a new model called the OrgPOMDP (Organizational POMDP), which is based on the partially observable Markov decision process (POMDP). This new model combines two powerful representations for modeling large scale problems: hierarchical modeling and factored representations. In this paper we make three key contributions: (a) Introduce the OrgPOMDP model; (b) Present an algorithm to solve OrgPOMDP problems efficiently; and (c) Apply OrgPOMDPs to scenarios in an existing large organization, the Air and Space Operation Center (AOC). We conduct experiments and show that our OrgPOMDP approach results in greater scalability and greatly reduced runtime. In fact, as the size of the problem increases, we soon reach a point at which the OrgPOMDP approach continues to provide solutions while traditional POMDP methods cannot. We also provide an empirical evaluation to highlight the benefits of an organization implementing an OrgPOMDP policy. Adaptive Decision Support for Structured Organizations: A Case for OrgPOMDPs Pradeep Varakanthamhas 4 papers, Nathan Schurr, Alan Carlinhas 2 papers, Christopher Amato

The problem of unfair testimonies has to be addressed effectively to improve the robustness of reputation systems. We propose an integrated CLUstering-Based approach called iCLUB to filter unfair testimonies for reputation systems using multi-nominal testimonies, in multiagent-based electronic commerce. It adopts clustering and considers buying agents' local and global knowledge about selling agents. Experimental evaluation demonstrates promising results of our approach in filtering various types of unfair testimonies. iCLUB: An Integrated Clustering-Based Approach to Improve the Robustness of Reputation Systems Siyuan Liu, Jie Zhang, Chunyan Miaohas 3 papers, Yin-Leng Theng, Alex C. Kot

This work proposes new techniques for saving communication and computational resources when solving distributed constraint optimization problems in an environment where system hardware resources are clustered. Using a pre-computed policy and two phase propagation on Max-Sum algorithm, the system performance on Radar scheduling problem improves in terms of communication and computation. Effective Variants of Max-Sum Algorithm to Radar Coordination and Scheduling Yoonheui Kim, Michael Krainin, Victor Lesserhas 4 papers

It becomes critical to address human adversaries' bounded rationality in security games as the real-world deployment of such games spreads. To that end, the key contributions of this paper include: (i) new efficient algorithms for computing optimal strategic solutions using Prospect Theory and Quantal Response Equilibrium; (ii) the most comprehensive experiment to date studying the effectiveness of different models against human subjects for security games. Our new techniques outperform the leading contender for modelling human behavior in security games in experiment with human subjects. Improved Computational Models of Human Behavior in Security Games Rong Yanghas 2 papers, Christopher Kiekintveldhas 4 papers, Fernando Ordonez, Milind Tambehas 8 papers, Richard John

In the near future, there is potential for a tremendous expansion in the number of Earth-orbiting CubeSats, due to reduced cost associated with platform standardization, availability of standardized parts for CubeSats, and reduced launching costs due to improved packaging methods and lower cost launchers. However, software algorithms capable of efficiently coordinating CubeSats have not kept up with their hardware gains, making it likely that these CubSats will be severely underutilized. Fortunately, these coordination issues can be addressed with multiagent algorithms. In this paper, we show how a multiagent system can be used to address the particular problem of how a third party should bid for use of existing Earth-observing CubeSats so that it can achieve optical coverage over a key geographic region of interest. In this model, an agent is assigned to every CubeSat from which observations may be purchased, and agents must decide how much to offer for these services. We address this problem by having agents use reinforcement learning algorithms with agent-specific shaped rewards. The results show an eight fold improvement over a simple strawman allocation algorithm and a two fold improvement over a multiagent system using standard reward functions. Agent-Based Resource Allocation in Dynamically Formed CubeSat Constellations Chris HolmesParker, Adrian Agogino

Curiosity is an innately rewarding state of mind that, over the millennia, has driven the human race to explore and discover. Many researches in pedagogical science have confirmed the importance of being curious to the students' cognitive development. However, in the newly popular virtual world-based learning environments (VLEs), there is currently a lack of attention being paid to enhancing the learning experience by stimulating the learners' curiosity. In this paper, we propose a simple model for curious agents (CAs) which can be used to stimulate learners' curiosity in VLEs. Potential future research directions will be discussed. A Simple Curious Agent to Help People be Curious Han Yu, Zhiqi Shenhas 2 papers, Chunyan Miaohas 3 papers, Ah-Hwee Tan

In this paper we present the notion of Social Instruments as a set of mechanisms that facilitate the emergence of norms from repeated interactions between members of a society. Specifically, we focus on two social instruments: rewiring and observation. Our main goal is to provide agents with tools that allow them to leverage their social network of interactions when effectively addressing coordination and learning problems, paying special attention to dissolving metastable subconventions. Finally, we present a more sophisticated social instrument (observation + rewiring) for robust resolution of subconventions, which works dissolving SelfReinforcing Substructures (SRS) in the social network. Social Instruments for Convention Emergence Daniel Villatorohas 2 papers, Jordi Sabater-Mir, Sandip Senhas 2 papers

Despite much research in recent years, newly created multiagent learning (MAL) algorithms continue to have one or more fatal weaknesses. These weaknesses include slow learning rates, failure to learn non-myopic solutions, and inability to scale up to domains with many actions, states, and associates. To overcome these weaknesses, we argue that fundamentally different approaches to MAL should be developed. One possibility is to develop methods that allow people to teach learning agents. To begin to determine the usefulness of this approach, we explore the effectiveness of learning by demonstration (LbD) in repeated stochastic games. Learning By Demonstration in Repeated Stochastic Games Jacob W. Crandallhas 2 papers, Malek H. Altakrori, Yomna M. Hassan

Consumers of resources in realistic applications (e.g., web, multimedia) typically derive diminishing-return utilities from the amount of resource they receive. A resource provider who is deriving an equal amount of revenue from each satisfied user (e.g., by online advertising), can maximize the number of users by identifying a satisfaction threshold for each user, i.e., the minimal amount of resource the user requires in order to use the service (rather than drop out). A straightforward approach is to ask users to submit their minimal demands (direct revelation). Unfortunately, self-interested users may try to manipulate the system by submitting untruthful requirements. We propose an incentive-compatible mechanism for maximizing revenue in a resource allocation system where users are ex-ante symmetric (same amount of revenue for any satisfied user) and have diminishing-return utility functions. Users are encouraged by the mechanism to submit their true requirements and the system aims to satisfy as many users as possible. Unlike previous solutions, our mechanism does not require monetary payments from users or downgrading of service. Our mechanism satisfies the number of users within a constant factor of the optimum. Our empirical evaluation demonstrates that in practice, our mechanism can be significantly closer to the optimum than implied by the worst-case analysis. Our mechanism can be generalized to settings when revenue from each user can differ. Also, under some assumptions and adjustments, our mechanism can be used to allocate resource periodically over time. Maximizing Revenue in Symmetric Resource Allocation Systems When User Utilities Exhibit Diminishing Returns Roie Zivanhas 2 papers, Miroslav Dudík, Praveen Paruchuri, Katia Sycarahas 7 papers

Exceptions constitute a great deal of autonomous process execution. In order to resolve an exception, several participants should collaborate and exchange knowledge. We believe that argumentation technologies lend themselves very well to be used in this context, both for elaborating on possible causes of exceptions, and for exchanging the result of such elaboration. We propose an open and modular multi-agent framework for handling exceptions using agent dialogues and assumption-based argumentation as the underlying logic. Collaborative Diagnosis of Exceptions to Contracts Özgür Kafalıhas 2 papers, Francesca Tonihas 2 papers, Paolo Torronihas 2 papers

In this paper, we propose a genetic algorithm aided optimization scheme for designing the organization of hierarchical multiagent systems. We introduce the hierarchical genetic algorithm, in which hierarchical crossover with a repair strategy and mutation of small perturbation are used. The phenotypic hierarchical structure space is translated to the genome-like array representation space, which makes the algorithm genetic-operator-literate. Our experiments show that competitive structures can be found by the proposed algorithm. Compared with traditional operators, the new operators produced better organizations of higher utility more consistently. The proposed algorithm extends the search processes of the state-of-the-art multiagent organization design methodologies, and is more computationally efficient in a large search space. Genetic Algorithm Aided Optimization of Hierarchical Multiagent System Organization Ling Yu, Zhiqi Shenhas 2 papers, Chunyan Miaohas 3 papers, Victor Lesserhas 4 papers

In this paper we present and discuss a novel language restriction for modal logics for multiagent systems that can reduce the complexity of the satisfiability problem from EXPTIME-hard to NPTIME-complete. In the discussion we focus on a particular BDI logic, called TeamLog, which is a logic for modelling cooperating groups of agents and which possesses some of the characteristics typical to other BDI logics. Complexity of Multiagent BDI Logics with Restricted Modal Context Marcin Dziubiński

Forming effective coalitions is a major research challenge in AI and multi-agent systems. A Coalition Structure Generation (CSG) problem involves partitioning a set of agents into coalitions so that the social surplus is maximized. Ohta et al. introduce an innovative direction for solving CSG, i.e., by representing a characteristic function as a set of rules, a CSG problem can be formalized as the problem of finding a subset of rules that maximizes the sum of rule values under certain constraints. This paper considers two significant extensions of the formalization/algorithm of Ohta et al., i.e., (i) handling negative value rules and (ii) handling externalities among coalitions. Extension of MC-net-based Coalition Structure Generation: Handling Negative Rules and Externalities Ryo Ichimura, Takato Hasegawa, Suguru Uedahas 2 papers, Atsushi Iwasakihas 5 papers, Makoto Yokoohas 5 papers

The success of contract-based multiagent systems relies on agents complying with their commitments. When something goes wrong, the key to diagnosis lies within the commitments' mutual relations as well as their individual states. Accordingly, we explore how commitments are related through the three-agent commitment delegation operation. We then propose exception diagnosis based on such a relation. Diagnosing Commitments: Delegation Revisited Özgür Kafalıhas 2 papers, Paolo Torronihas 2 papers

In this paper we present a lightweight teamwork implementation through use of abstraction hierarchies. The basis of this implementation is ADAPT, which supports Autonomous Dynamic Agent Planning for Teamwork. ADAPT's novelty stems from how it succinctly decomposes teamwork problems into two separate planners: a task network for the set of activities to be performed by a specific agent and a separate group network for addressing team organization factors. Because abstract search techniques are the basis for creating these two components, ADAPT agents are able to effectively address teamwork in dynamic environments without explicitly enumerating the entire set of possible team states. During run-time, ADAPT agents then expand the teamwork states that are necessary for task completion through an association algorithm to dynamically link its task and group planners. As a result, ADAPT uses far fewer team states than existing teamwork models. We describe how ADAPT was implemented within a commercial training and simulation application, and present evidence detailing its success in concisely and effectively modeling teamwork. ADAPT: Abstraction Hierarchies to Succinctly Model Teamwork Meirav Hadad, Avi Rosenfeldhas 2 papers

We propose “Rip-off”, a new multi-player bargaining game based on the well-studied weighted voting game (WVG) model from cooperative game theory. Many different solution concepts, such as the Core and the Shapley value have been proposed to analyze models such as WVGs. However, there is little work on analyzing how humans actually play in such settings. We conducted several experiments where we let humans play “Rip-off”. Our analysis reveals that although solutions of games played by humans do suffer from certain biases, a player's average payoff over several games is roughly reflected by the Shapley value. Rip-off: Playing the Cooperative Negotiation Game Yoram Bachrachhas 2 papers, Pushmeet Kohlihas 2 papers, Thore Graepel

Online virtual worlds provide a rich platform for remote human interaction, and are increasingly being used as a simulation platform for multi-agent systems and as a way for software agents to interact with humans. It would therefore be beneficial to provide techniques allowing high-level agent development tools, especially cognitive agent platforms such as belief-desire-intention (BDI) programming frameworks, to be interfaced with virtual worlds. This is not a trivial task as it involves mapping potentially unreliable sensor readings from complex virtual environments to a domain-specific abstract logical model of observed properties and/or events. This paper investigates this problem in the context of agent interactions in a multi-agent system simulated in Second Life. We present a framework which facilitates the connection of any multi-agent platform with Second Life, and demonstrate it in conjunction with the Jason BDI interpreter. Interfacing a Cognitive Agent Platform with a Virtual World: a Case Study using Second Life Surangika Ranathunga, Stephen Cranefieldhas 2 papers, Martin Purvis

We show how to generate multi-agent Kripke models from message exchanges. With these models we can analyze the epistemic consequences of a message exchange. One novelty in this approach is that we include the messages in our logical language. This allows us to model messages that mention other messages and agents that reason about messages. Our framework can be used to model a wide range of different communication scenarios. Message-Generated Kripke Semantics Jan van Eijck, Floor Sietsma

We propose a method for using ethnographic field data to substantiate agent-based models for socially-oriented systems. We investigate in-situ use of domestic technologies created to encourage fun between grandparents and grandchildren separated by distance. The field data added an understanding of what intergenerational fun means when imbued with concrete activities. Our contribution is twofold. First, we extend the understanding of agent-oriented concepts by applying them to household interactions. Second, we establish a new method for informing quality goals with field data to enable development of novel applications in the domestic domain. Substantiating Quality Goals with Field Data for Socially-Oriented Requirements Engineering Sonja Pedell, Tim Miller, Leon Sterling, Frank Vetere, Steve Howard, Jeni Paay

The environment is an essential component of multi-agent systems, which is often used to coordinate the behaviour of individual agents. Recently many programming languages have been proposed to facilitate the implementation of such environments. This extended abstract is motivated by the emerging programming languages that are designed to implement environments in terms of normative concepts such as norms and sanctions. We propose a formal analysis of normative environment programs from a mechanism design perspective. By doing this we aim at relating normative environment programs to mechanism design, setting the stage for studying formal properties of these programs such as whether a set of norms implements a specific social choice function in a specific equilibria. Normative Programs and Normative Mechanism Design Nils Bullinghas 2 papers, Mehdi Dastanihas 4 papers

In this paper, we introduce a self-disclosure decision-making mechanism based on information-theoretic measures. This decision-making mechanism uses an intimacy measure between agents and the privacy loss that a particular disclosure may cause. Privacy-Intimacy Tradeoff in Self-disclosure Jose M. Suchhas 2 papers, Agustin Espinosa, Ana García-Forneshas 3 papers, Carles Sierrahas 2 papers

This paper proposes a reasoning process to allow agents to decide when and how norms should be violated or obeyed. The coherence-based reasoning mechanism proposed in this paper, allows norm aware agents to confront the norm compliance dilemma and build alternatives for such normative decisions. Reasoning About Norm Compliance Natalia Criadohas 2 papers, Estefania Argente, Vicente Bottihas 4 papers, Pablo Noriegahas 2 papers

We discuss the emergence of social norms for efficiently resolving conflict situations through reinforcement learning and investigate the features of the emergent norms, where conflict situations can be expressed by non-cooperative payoff matrix and will remain if they fail to resolve the conflicts. Emergence of Norms for Social Efficiency in Partially Iterative Non-Coordinated Games Toshiharu Sugawara

The term Multi-Agent Planning (MAP) refers to any kind of planning in domains in which several independent agents plan and act together. In this paper, we present a novel argumentation-based approach for multiple agents that plan cooperatively while having different abilities, different (and possibly conflicting) views of the world, and different rationalities. The argumentation-based partial-order planning model allows agents to solve MAP problems by proposing partial solutions, giving out opinions on the adequacy of these proposals and modifying them to the benefit of the overall process. We propose the use of a presumptive argumentation model based on the instantiation of argument schemes and associated critical questions to a MAP context. On the Construction of Joint Plans through Argumentation Schemes Oscar Sapena, Alejandro Torreño, Eva Onaindiahas 2 papers

Team Coverage Games (TCGs) are a representation of cooperative games, where the value a coalition generates depends on both individual contributions of its members and synergies between them. The synergies are expressed in terms of the importance of the agents in various teams. TCGs model the synergy as a reduction in utility that occurs when team members are missing, causing the team not to achieve its full potential. We focus on the case where the utility reduction incured is a concave function of the importance of the missing team members and analyze the domain from a computational game theoretic perspective. Team Coverage Games Yoram Bachrachhas 2 papers, Pushmeet Kohlihas 2 papers, Vladimir Kolmogorov

In previous work we and other authors have shown that agent-based systems are successful in optimizing delivery plans of single logistics companies and are meanwhile successfully productive in industry. In this paper we show that agent-based systems are particularly useful to also optimize transport across logistics companies. In inter-company optimization, privacy is of major importance between the otherwise competing companies. Some data has to be treated strictly private like the cost model or the constraint model. Other data like order information has to be shared. However, typically the amount of orders released to other companies has also to be limited. We show that our agent-based approach can be easily fine tuned to trade off privacy against the benefit of cooperation. Agent-based Inter-Company Transport Optimization Klaus Dorer, Ingo Schindler, Dominic Greenwood

This paper proposes a modularisation framework for BDI based agent programming languages developed from a software engineering perspective. Like other proposals, BDI modules are seen as encapsulations of cognitive components. However, unlike other approaches, modules are here instantiated and manipulated in a similar fashion as objects in object orientation. In particular, an agent's mental state is formed dynamically by instantiating and activating BDI modules. The agent deliberates on its active module instances, which interact by sharing their beliefs and goals. Belief/Goal Sharing BDI Modules Michal Cap, Mehdi Dastanihas 4 papers, Maaike Harbers

In this paper we propose a neural-symbolic architecture to represent and reason with norms in multi-agent systems. On the one hand, the architecture contains a symbolic knowledge base to represent norms and on the other hand it contains a neural network to reason with norms. The interaction between the symbolic knowledge and the neural network is used to learn norms. We describe how to handle normative reasoning issues like contrary to duties, dilemmas and exceptions by using a priority-based ordering between the norms in a neural-symbolic architecture. Neural Symbolic Architecture for Normative Agents Guido Boella, Silvano Colombo Tosatto, Artur d'Avila Garcez, Valerio Genovese, Dino Ienco, Leendert van der Torrehas 2 papers

The values shared within a society influence the (social) behaviour of the agents in that society. This connection goes through implicit and explicit norms. In the case of a norm conflict, an agent will decide to comply with one or more of the applicable norms, while violating others. Our interest is how the type of the norms may play a role in such decision, and take the chosen behaviour of an agent to depend on a personal preference order on the norm types. We distinguish three different types of norms: legal norms, social norms and private norms. We illustrate our approach using the introduction of the law prohibiting smoking in cafes: we present a simulation of this situation involving agents' preferences over different norm types. The results of this simulation are used for an explorative model for normative reasoning based on norm types. We discuss a possible connection between the composition of a society in terms of these profiles and its culture and the relevance of the model with respect to value sensitive design of socio-technological systems. No Smoking Here: Compliance Differences Between Legal and Social Norms Francien Dechesne, Virginia Dignumhas 3 papers

We present a modal logic of belief and announcements in a multi-agent setting. This logic allows to express not only that ψ holds after the announcement of φ as in standard public announcement logic (PAL), but also that the announcement of φ occurs. We use the logic to provide a formal analysis of several concepts that are relevant for multi-agent systems (MAS) theory and applications: the notions of communicative action (an agent informs another agent about something) and communicative intention (an agent has the intention to inform another agent about something), and the notion of information source. Agents That Speak: Modelling Communicative Plans and Information Sources in a Logic of Announcements Philippe Balbiani, Nadine Guiraudhas 2 papers, Andreas Herzig, Emiliano Lorinihas 2 papers

The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. It has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more generally to any two-sided market. Given a stable marriage problem, it is possible to find a male-optimal (resp., female-optimal) stable marriage in polynomial time. However, it is sometimes desirable to find stable marriages without favoring one group at the expenses of the other one. To achieve this goal, we consider a local search approach to find stable marriages with the aim of exploiting the nondeterminism of local search to give a fair procedure. We test our algorithm on classes of stable marriage problems, showing both its efficiency and its sampling capability over the set of all stable marriages, and we compare it to a Markov chain approach. Procedural Fairness in Stable Marriage Problems Mirco Gelain, Maria Silvia Pinihas 2 papers, Francesca Rossihas 2 papers, Kristen Brent Venablehas 2 papers, Toby Walshhas 2 papers

This paper studies the emergence of cooperation in the N-Player Prisoner's Dilemma (NPD) using a tag-mediated interaction model. Tags have been widely used to bias agent pairwise interactions which facilitates the emergence of cooperation. This paper shows some of the key parameters that influence the emergence of cooperation in an evolutionary setting. The aim of this paper is to demonstrate the most vital factors that are commonly ignored in many existing NPD studies. Tag-Based Cooperation in N-Player Dilemmas Enda Howley, Jim Duggan

The focus of multiagent planning research has recently turned towards domains with self-interested agents leading to the definition of Coalition-Planning Games (CoPGs). In this paper, we investigate algorithms for solving a restricted class of “safe” CoPGs, in which no agent can benefit from making another agent's plan invalid. We introduce a novel, generalised solution concept, and show how problems can be translated so that they can be solved by standard single-agent planners. However, standard planners cannot solve problems like this efficiently. We then introduce a new multiagent planning algorithm and the benefits of our approach are illustrated empirically in an example logistics domain. Heuristic Multiagent Planning with Self-Interested Agents Matt Crosby, Michael Rovatsoshas 2 papers

We present a novel method for analysing the behaviour of multiagent systems on the basis of the semantically rich information provided by agent communication languages and interaction protocols. Contrary to analysis methods that rely on observing more low-level patterns of behaviour, our method is based on exploiting the semantics. These languages and protocols which can be used to extract qualitative properties of observed interactions. This can be achieved by interpreting the logical constraints associated with protocol execution paths or individual messages as models of the context of an observed interaction, and using them as features of learning samples. Mining Qualitative Context Models from Multiagent Interactions Emilio Serrano, Michael Rovatsoshas 2 papers, Juan Botia

We present a novel representation of the prediction market using a partially observable stochastic game with information (POSGI), that can be used by each trading agent to precisely calculate the state of the market. We then propose that a correlated equilibrium (CE) strategy can be used by the agents to dynamically calculate the prices at which they should trade securities in the prediction market. Simulation results comparing the CE strategy within our POSGI model with five other strategies commonly used in similar markets show that the CE strategy results in improved price predictions and higher utilities to the agents as compared to other strategies. Partially Observable Stochastic Game-based Multi-Agent Prediction Markets Janyl Jumadinovahas 2 papers, Prithviraj Dasgupta

In this paper we present an organization transition model that is based on costs along with an associated organization transition mechanism. This mechanism calculates how a current instance of an organization can evolve to a future instance and how costly this evolution is. A Cost-Based Transition Approach for Multiagent Systems Reorganization Juan M. Alberolahas 2 papers, Vicente Juliánhas 2 papers, Ana García-Forneshas 3 papers

This paper introduces the first experiments of an innovative approach to the modeling and simulation of crowds of pedestrians considering the presence of groups as a crucial element influencing overall system dynamics. In-silico experimental results are discussed in relation to in-vitro experiments (experimental observations on the movement of pedestrians and groups). Towards an Agent-Based Proxemic Model for Pedestrian and Group Dynamics: Motivations and First Experiments Sara Manzoni, Giuseppe Vizzari, Kazumichi Ohtsuka, Kenichiro Shimura

The recent robot car competitions and demonstrations have convincingly shown that fully autonomous vehicles are feasible with current or near-future intelligent vehicle technology. Looking ahead to the time when such autonomous cars will be common, Dresner and Stone proposed a new intersection control protocol called Autonomous Intersection Management (AIM) and showed that by leveraging the capacities of autonomous vehicles we can devise a reservation-based intersection control protocol that is much more efficient than traffic signals and stop signs. Their proposed protocol, however, handles reservation requests one at a time and does not prioritize reservations according to their relative importance and vehicles' waiting times, causing potentially large inequalities in granting reservations. For example, at an intersection between a main street and an alley, vehicles from the alley can take a very long time to get reservations to enter the intersection. In this research, we introduce a prioritization scheme to prevent uneven reservation assignments in unbalanced traffic. Our experimental results show that our prioritizing scheme outperforms previous intersection control protocols in unbalanced traffic. Batch Reservations in Autonomous Intersection Management Neda Shahidi, Tsz-Chiu Au, Peter Stonehas 5 papers

This paper investigates the impact of reward shaping in multi-agent reinforcement learning as a way to incorporate domain knowledge about good strategies. In theory, potential-based reward shaping does not alter the Nash Equilibria of a stochastic game, only the exploration of the shaped agent. We demonstrate empirically the performance of statebased and state-action-based reward shaping in RoboCup KeepAway. The results illustrate that reward shaping can alter both the learning time required to reach a stable joint policy and the final group performance for better or worse. Multi-Agent, Reward Shaping for RoboCup KeepAway Sam Devlinhas 2 papers, Marek Grześhas 2 papers, Daniel Kudenkohas 2 papers

Decision making and game play in multiagent settings must often contend with behavioral models of other agents in order to predict their actions. One approach that reduces the complexity of the unconstrained model space is to group models that tend to be behaviorally equivalent. In this paper, we seek to further compress the model space by introducing an approximate measure of behavioral equivalence and using it to group models. Approximating Behavioral Equivalence of Models Using Top-K Policy Paths Yifeng Zeng, Yingke Chen, Prashant Doshihas 2 papers

An organizational modeling language can be used to specify an agent organization in terms of its roles, organizational structure, norms, etc. Using such an organizational specification to organize a multi-agent system should make the agents more effective in attaining their purpose, or prevent certain undesired behavior from occurring. Agents who want to enter and play roles in an organization are expected to understand and reason about the organizational specification. An important aspect that such organization-aware agents should be able to reason about is role enactment. In particular, agents should be able to reflect on whether they have the capabilities to play a role in an organization. In future work it needs to be made precise when an agent can be said to have a certain capability, and how an agent can reflect on its capabilities. This is necessary for programming role enactment in organization-aware agents. Reflection about Capabilities for Role Enactment M. Birna van Riemsdijkhas 2 papers, Virginia Dignumhas 3 papers, Catholijn M. Jonker, Huib Aldewereld

In this paper we describe a software assistant agent that can proactively assist human users situated in a time-constrained coalition environment. The cognitive workload is significantly increased when the user must not only cope with a complex environment, but also with a set of unaccustomed rules that prescribe how the coalition planning process must be carried out. In this context, we introduce the notion of prognostic norm reasoning to predict the user's likely normative violations, allowing the assistant agent to plan and take remedial actions before the violations actually occur. To the best of our knowledge, our approach is the first that manages norms in a proactive and autonomous manner. Prognostic Normative Reasoning in Coalition Planning Jean Oh, Felipe Meneguzzihas 2 papers, Katia Sycarahas 7 papers, Timothy J. Normanhas 2 papers

In this paper we discuss virtual agent perception in large scale open environment based MABS. Virtual Agent Perception in Large Scale Multi-Agent Based Simulation Systems Dane Kuiper, Rym Z. Wenkstern

This paper tackles the problem of exchanging arguments in negotiation dialogues, and provides first characterizations of the outcomes of such rich dialogues. A Formal Analysis of the Outcomes of Argumentation-based Negotiations Leila Amgoud, Srdjan Vesic

Norms or conventions can be used as external correlating signals to promote coordination between rational agents and hence have merited in-depth study of the evolution and economics of norms both in the social sciences and in multi-agent systems. While agent simulations can be used to gain a cursory idea of when and what norms can evolve, the estimations obtained by running simulations can be costly to obtain, provide no guarantees about the behavior of the system, and may overlook some rare occurrences. We use a theoretical approach to analyze a system of agents playing a convergence game and develop models that predict (a) how the system's behavior will change over time, (b) how much time it will take for it to converge to a stable state, and (c) how often the system will converge to a particular norm. Modeling the Emergence of Norms Logan Brooks, Wayne Iba, Sandip Senhas 2 papers

Humans create efficient social structures in a self-organized way. People tend to join groups with other people with similar characteristics. This is called homophily. This pa- per proposes how homophily can be introduced in Service- Oriented Multiagent Systems (SOMAS) to create efficient self-organized structures. Introducing Homophily to Improve Semantic Service Search in a Self-adaptive System E. del Valhas 2 papers, M. Rebollo, Vicente Bottihas 4 papers

The global objective of open multiagent systems might be in conflict with individual preferences of rational agents participating in such systems. Addressing this problem, we propose a mechanism able to attach incentives to agent actions such that the global utility of the system is improved. Such incentives are dynamically adjusted to each agent's preferences by using institutional agents called incentivators. Adaptive Regulation of Open MAS: an Incentive Mechanism based on Modifications of the Environment Roberto Centeno, Holger Billhardt

For an interesting class of emerging applications, a large robot team will need to distributedly allocate many more tasks than there are robots, with dynamically appearing tasks and a limited ability to communicate. The LA-DCOP algorithm can conceptually handle both large-scale problems and multiple tasks per robot, but has key limitations when allocating spatially distributed tasks. In this paper, we extend LA-DCOP with several alternative acceptance rules for robots to determine whether to take on an additional task, given the interaction with the tasks it has already committed to. We show that these acceptance rules dramatically outperform a naive LA-DCOP implementation. In addition, we developed a technique that lets the robots use completely local knowledge to adjust their task acceptance criteria to get the best possible performance at a given communication bandwidth level. Allocating Spatially Distributed Tasks in Large, Dynamic Robot Teams Steven Okamoto, Nathan Brooks, Sean Owens, Katia Sycarahas 7 papers, Paul Scerrihas 3 papers

We address the problem of optimally assigning spatially distributed tasks to a team of heterogeneous mobile agents in domains with inter-task temporal constraints, such as precedence constraints. Due to delay penalties, satisfying the temporal constraints impacts the overall team cost. We present a mathematical model of the problem, a benchmark anytime bounded optimal solution process, and an analysis of the impact of delay penalties on problem difficulty. Bounded Optimal Team Coordination with Temporal Constraints and Delay Penalties G. Ayorkor Korsah, Anthony Stentz, M. Bernardine Dias

In this paper we present a framework for perceptual attention for BDI-agents embodied in a virtual environment. To abstract from different data representations present in virtual environments, we introduce an ontological information model to define environment semantics. Further, the framework proposes an approach for goal-directed perception based on the specification of different interests, which define selected information from the environment an agent is interested in. These interests filter and extract specific information from a continuous incoming flow of sensory information. In this way we can find a balance between stimulus-driven control and goal based control over perception. Thus preventing an agent to become flooded with irrelevant information on the one hand or blinded for unexpected events that need to be reacted to on the other hand. A Perception Framework for Intelligent Characters in Serious Games Joost van Oijen, Frank Dignumhas 3 papers

To provide efficiency, current BDI agent programming languages with declarative goals only support a limited form of rationality – they ignore other concurrent intentions of the agent when selecting plans, and as a consequence, the selected plans may be inconsistent with these intentions. In this paper, we develop logical foundations for a rational BDI agent programming framework with prioritized declarative goals that addresses this deficiency. We ensure that the agent's chosen declarative goals and adopted plans are consistent with each other and with the agent's knowledge. We show how agents specified in our language satisfy some key rationality requirements. SR-APL: A Model for a Programming Language for Rational BDI Agents with Prioritized Goals Shakil M. Khan, Yves Lespérance

In this paper, we use LTL to specify acceptable/desirable behaviours for a system modelled as a Petri net, and create a Petri net realization of a supervisor that is guaranteed to enforce them, by appropriately restricting the uncontrolled behaviour of the system.We illustrate the method with an application to the specification of coordination requirements between the members of a team of simulated soccer robots. Designing Petri Net Supervisors for Multi-Agent Systems from LTL Specifications Bruno Lacerda, Pedro U. Lima

We study the problem of achieving cooperation between two self-interested agents that play a sequence of different randomly generated normal form games. The agent learns how much the opponent is willing to cooperate and reciprocates. We present empirical results that show that both agents benefit from cooperation and that a small number of games is sufficient to learn the cooperation level of the opponent. Friend or Foe? Detecting an Opponent's Attitude in Normal Form Games Steven Damerhas 2 papers, Maria Gini

Most traffic simulation frameworks move vehicles from some location A to some location B as the result of different equations of motion or fluid dynamics. As it is, reality is much more complex because what actually happens on the road is not only determined by physics of motion, but also by the perception and attitudes of the drivers. In this work, we introduce an approach which considers a driver's state of mind within large scale traffic simulations. For this purpose we describe a BDI based conceptualisation of a driver and extend common simulation topologies with service oriented concepts. The BDI Driver in a Service City Marco Lützenbergerhas 2 papers, Nils Masuch, Benjamin Hirsch, Sebastian Ahrndt, Axel Heßler, Sahin Albayrakhas 2 papers

We present a method for identifying actions that lead to observations which are only weakly informative in the context of partially observable Markov decision processes (POMDP). We call such actions as weak- (inclusive of zero-)information inducing. Policy subtrees rooted at these actions may be computed more efficiently. While zero-information inducing actions may be exploited without error, we show that the error due to the quicker backup for weak but non-zero information inducing actions is bounded. We demonstrate the substantial computational savings that exploiting such actions may bring to exact and approximate solutions of POMDPs. Identifying and Exploiting Weak-Information Inducing Actions in Solving POMDPs Ekhlas Sonu, Prashant Doshihas 2 papers

Despite their worst-case NEXP-complete planning complexity, DEC-POMDPs remain a popular framework for multiagent teamwork. This paper introduces effective teamwork under model uncertainty (i.e., potentially inaccurate transition and observation functions) as a novel challenge for DEC-POMDPs and presents MODERN, the first execution-centric framework for DEC-POMDPs explicitly motivated by addressing such model uncertainty. MODERN's shift of coordination reasoning from planning-time to execution-time avoids the high cost of computing optimal plans whose promised quality may not be realized in practice. There are three key ideas in MODERN: (i) it maintains an exponentially smaller model of other agents' beliefs and actions than in previous work and then further reduces the computation-time and space expense of this model via bounded pruning; (ii) it reduces execution-time computation by exploiting BDI theories of teamwork, and limits communication to key trigger points; and (iii) it limits its decision-theoretic reasoning about communication to trigger points and uses a systematic markup to encourage extra communication at these points — thus reducing uncertainty among team members at trigger points. Teamwork in Distributed POMDPs: Execution-time Coordination Under Model Uncertainty Jun-Young Kwak, Rong Yanghas 2 papers, Zhengyu Yinhas 2 papers, Matthew E. Taylorhas 4 papers, Milind Tambehas 8 papers

Planning as inference recently emerged as a versatile approach to decision-theoretic planning and reinforcement learning for single and multi-agent systems in fully and partially observable domains with discrete and continuous variables. Since planning as inference essentially tackles a non-convex optimization problem when the states are partially observable, there is a need to develop techniques that can robustly escape local optima. We propose two algorithms: the first one adds nodes to the controller according to an increasingly deep forward search, while the second one splits nodes in a greedy fashion to improve reward likelihood. Escaping Local Optima in POMDP Planning as Inference Pascal Pouparthas 2 papers, Tobias Lang, Marc Toussaint

Although much work has been done on designing autonomy and user interfaces for managing small teams of independent robots, much less is known about managing large-scale bio-inspired robot (BIRT) teams. In this paper, we explore human interaction with BIRT teams in an information foraging task. We summarize results from two small experiments that use two types of BIRT teams in a foraging task. The results illustrate differences in BIRT performance for different types of human interaction, and illustrate how performance robustness can vary as a function of interaction type. Toward Human Interaction with Bio-Inspired Teams Michael A. Goodrich, P. B. Sujit, Jacob W. Crandallhas 2 papers

Heuristic depressions are local minima of heuristic functions. While visiting one them, real-time (RT) search algorithms like LRTA will update the heuristic value for most of their states several times before escaping, resulting in costly solutions. Existing RT search algorithm tackle this problem by doing more search and/or lookahead but do not guide search towards leaving depressions. We present eLSS-LRTA, a new RT search algorithm based on LSSLRTA that actively guides search towards exiting regions with heuristic depressions. We show that our algorithm produces better quality solutions than LSS-LRTA for equal values of lookahead in standard RT benchmarks. Escaping Heuristic Depressions in Real-Time Heuristic Search Carlos Hernándezhas 2 papers, Jorge A. Baier

Most incomplete DCOP algorithms generally do not provide any guarantees on the quality of the solutions. In this paper, we introduce a new incomplete DCOP algorithm that can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete DCOP algorithms, while the run time of this algorithm is much shorter. Pseudo-tree-based Algorithm for Approximate Distributed Constraint Optimization with Quality Bounds Tenda Okimoto, Yongjoon Joe, Atsushi Iwasakihas 5 papers, Makoto Yokoohas 5 papers

Forming effective coalitions is a major research challenge in AI and multi-agent systems. Thus, coalitional games, including coalition structure generation, have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. In this paper, we develop a new concise representation scheme for a characteristic function, which is based on the idea of agent types. This representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes to further reduce the representation size. Concise Characteristic Function Representations in Coalitional Games Based on Agent Types Suguru Uedahas 2 papers, Makoto Kitaki, Atsushi Iwasakihas 5 papers, Makoto Yokoohas 5 papers

A number of real-world security scenarios can be cast as a problem of transiting an area patrolled by a mobile adversary, where the transiting agent aims to choose its route so as to minimize the probability of encountering the patrolling agent, and vice versa. We model this problem as a twoplayer zero-sum game on a graph, termed the transit game. In contrast to the existing models of area transit, where one of the players is stationary, we assume both players are mobile. We also explicitly model the limited endurance of the patroller and the notion of a base to which the patroller has to repeatedly return. Noting the prohibitive size of the strategy spaces of both players, we employ iterative oracle-based algorithms including a newly proposed accelerated scheme, to obtain optimum route selection strategies for both players. We evaluate the developed approach on a range of transit game instances inspired by real-world security problems in the urban and naval security domains. Iterative Game-theoretic Route Selection for Hostile Area Transit and Patrolling Ondřej Vaněkhas 4 papers, Michal Jakobhas 3 papers, Viliam Lisýhas 2 papers, Branislav Bošanskýhas 3 papers, Michal Pěchoučekhas 5 papers

We investigate how to improve cooperative communication between agents by representing knowledge bases as logic programs extended with abduction. In this proposal, agents try to provide explanations whenever they fail to answer a question. Query Relaxation is then employed to search for answers related to the query, characterizing cooperative behavior. Our contributions bring insightful improvements to relaxation attempts and the quality of related answers. We introduce rational explanations and use them to efficiently guide the search for related answers in a relaxation tree. Abduction Guided Query Relaxation Samy Sáhas 2 papers, João Alcântara

In [1], we introduced a novel distributed inference algorithm for the multiagent Gaussian inference problem, based on the framework of graphical models and message passing algorithms. We compare it to current state of the art techniques and we demonstrate that it is the most efficient one in terms of communication resources used. Moreover, we show experimentally that it outperforms the other methods in terms of estimation error on a general class of problems, even in presence of data loss. A Message Passing Approach To Multiagent Gaussian Inference for Dynamic Processes Stefano Ermon, Carla Gomes, Bart Selman

This research explores human computation systems as a multi-agent platform for coordinating human brain power. We are interested in the problem of designing human computation systems. In particular, we focus on the situation where developers cannot re-design the whole platform but can only make limited changes to the environments. We extend the framework of environment design to multiple agent in the context of human computation. To incorporate the collective information from multiple agents, we propose two approaches, agent type elicitation and collaborative filtering, under different assumptions. The formulation and algorithms provide solutions for developers in human computation systems to find the environment settings maximizing their goal functions. Multiagent Environment Design in Human Computation Chien-Ju Ho, Yen-Ling Kuo, Jane Yung-Jen Hsuhas 2 papers

In this paper we introduce and analyze social distance games, a family of non-transferable utility coalitional games where an agent's utility is a measure of closeness to the other members of the coalition. We study both social welfare maximisation and stability in these games from a graph theoretic perspective. We investigate the welfare of stable coalition structures, and propose two new solution concepts with improved welfare guarantees. We argue that social distance games are both interesting in themselves, as well as in the context of social networks. Social Distance Games Simina Brânzei, Kate Larsonhas 2 papers

In the application of multi-agent systems to real-world problems, agents often suffer from bounded rationality where agent reasoning is limited by 1) a lack of knowledge about choices, and 2) a lack of resources required for reasoning. To overcome the former, the agent uses sensing to refine its knowledge. However, sensing can also require limited resources, leading to inaccurate environment modeling and poor decision making. In this paper, we consider a novel and difficult class of this problem where agents must use stateful resources during sensing, which we define as resources whose state-dependent behavior changes over time based on usage. Specifically, such sensing changes the state of a resource, and thus its behavior, producing a phenomenon where the sensing activity can and will distort its own outcome. We term this the Observer Effect after the similar phenomenon in the physical sciences. Given this effect, the agent faces a strategic tradeoff between satisfying the need for 1) knowledge refinement, and 2) avoiding corruption of knowledge due to distorted sensing outcomes. To address this tradeoff, we use active perception to select sensing activities and model activity selection as a Markov decision process (MDP) solved through reinforcement learning where an agent optimizes knowledge refinement while considering the state of the resource used during sensing. Agent Sensing with Stateful Resources Adam Eck, Leen-Kiat Soh

In this paper, we propose that bounded rationality of another agent be modeled as errors the agent is making while deciding on its action. We are motivated by the work on quantal response equilibria in behavioral game theory which uses Nash equilibria as the solution concept. In contrast, we use decision-theoretic maximization of expected utility. Quantal response assumes that a decision maker is approximately rational, i.e., is maximizing its expected utility but with an error rate characterized by a single error parameter. Another agent's error rate may be unknown and needs to be estimated during an interaction. We show that this error rate can be estimated using Bayesian update of a suitable conjugate prior, and that it has a sufficient statistic of fixed dimension under strong simplifying assumptions. However, if the simplifying assumptions are relaxed, the quantal response does not admit a finite dimensional sufficient statistic, and a more complex update is needed. Modeling Bounded Rationality of Agents During Interactions Qing Guo, Piotr Gmytrasiewicz

We consider semi-autonomous agents that have uncertain knowledge about their environment, but can ask what action the operator would prefer taking in the current or in a potential future state. Asking queries can help improve behavior, but if queries come at a cost (e.g., due to limited operator attention), the number of queries needs to be minimized. We develop a new algorithm for selecting action queries by adapting the recently proposed Expected Myopic Gain (EMG) from its prior use in settings with reward or transition probability queries to our setting of action queries, and empirically compare it to the current state of the art. Comparing Action-Query Strategies in Semi-Autonomous Agents Robert Cohn, Edmund H. Durfeehas 3 papers, Satinder Singh

Virtual human, with realistic behaviors and social skills, evoke in users a range of social behaviors normally only seen in human face-to-face interactions. One of the key challenges in creating such virtual humans is to give them human-like conversational skills, such as turn-taking skill. In this paper, we propose a multimodal end-of-turn prediction model. Instead of recording face-to-face conversation data, we collect the turn-taking data using Parasocial Consensus Sampling (PCS) framework. Then we analyze the relationship between verbal and nonverbal features and turn-taking behaviors based on the consensus data and show how these features influence the time people use to take turns. Finally, we present a probabilistic multimodal end-ofturn prediction model, which enables virtual humans to make real-time turn-taking predictions. The result shows that our model achieves a higher accuracy than previous methods did. A Multimodal End-of-Turn Prediction Model: Learning from Parasocial Consensus Sampling Lixing Huang, Louis-Philippe Morency, Jonathan Gratchhas 2 papers

Serious games and other training applications have the requirement that they should be suitable for trainees with different skill levels. Current approaches either use human experts or a completely centralized approach for this adaptation. These centralized approaches become very impractical and will not scale if the complexity of the game increases. Agents can be used in serious game implementations as a means to reduce complexity and increase believability but without some centralized coordination it becomes practically impossible to follow the intended storyline of the game and select suitable difficulties for the trainee. In this paper we show that using agent organizations to coordinate the agents is scalable and allows adaptation in very complex scenarios while making sure the storyline is preserved the right difficulty level for the trainee is preserved. Scalable Adaptive Serious Games using Agent Organizations Joost Westra, Frank Dignumhas 3 papers, Virginia Dignumhas 3 papers

In power markets, the trade of reserve energy will become more important as more intermittent generation is traded. In this work, we propose a novel bidding mechanism for the integration of power and reserve markets. It adds expressivity to reserve bids and facilitates planning. Integrating power and reserve trade in electricity networks Nicolas Höning, Han Noot, Han La Poutré