Skip to main content

2016 | Buch

PRIMA 2016: Principles and Practice of Multi-Agent Systems

19th International Conference, Phuket, Thailand, August 22-26, 2016, Proceedings

herausgegeben von: Matteo Baldoni, Amit K. Chopra, Tran Cao Son, Katsutoshi Hirayama, Paolo Torroni

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

insite
SUCHEN

Über dieses Buch

This book constitutes the refereed proceedings of the 19th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2016, held in Phuket, Thailand, in August 22-26, 2016.

The 16 revised full papers presented together with two invited papers, 9 short papers and three extended abstracts were carefully reviewed and selected from 50 submissions. The intention of the papers is to showcase research in several domains, ranging from foundations of agent theory and engineering aspects of agent systems, to emerging interdisciplinary areas of agent-based research.

Inhaltsverzeichnis

Frontmatter
Erratum to: PRIMA 2016: Principles and Practice of Multi-Agent Systems
Matteo Baldoni, Amit K. Chopra, Tran Cao Son, Katsutoshi Hirayama, Paolo Torroni

Invited Papers

Frontmatter
Intercultural Collaboration and Support Systems: A Brief History
Abstract
At the beginning of the new millennium, we proposed the concept of intercultural collaboration where participants with different cultures and languages work together towards shared goals. Because intercultural collaboration is a new area with scarce data, it was necessary to execute parallel experiments in both in real fields as well as in research laboratories. In 2002, we conducted a one-year experiment with Japanese, Chinese, Korean and Malaysian colleagues and students to develop open-source software oriented towards machine translation. From this experiment, we understood the necessity of a language infrastructure on the Internet that could create customized multilingual environments for various situations. In 2006, we launched the Language Grid project to realize a federated operation of servers for language services. Using the Language Grid, we worked with a nongovernmental organization since 2011 to support knowledge communications between agricultural experts in Japan and farmers in Vietnam via their children. We observed that a large community emerged to utilize these nonmature machine translation technologies. During these experiences, by facing different types of difficulties, we gradually came to understand the nature of intercultural collaboration. Problems are wicked and not easily defined because of their nested and open networked origin. Fortunately, multiagent technologies can be applied to model and simulate intercultural collaboration so as to predict the difficulties and to prepare a better support systems. In this paper, we provide a brief history of the research and practice as regards intercultural collaboration and support systems.
Toru Ishida
Argumentation for Practical Reasoning: An Axiomatic Approach
Abstract
An argument system could be viewed as a pair of a set of argument and a binary attack relation between arguments. The semantics of argumentation rests on the acceptability of arguments and the structure of arguments and their attack relations. While there is a relatively good understanding of the acceptability of arguments, the same can not be said about their structure and attack relations. In this paper, we present an axiomatic analysis of the attack relations of rule-based argument systems by presenting a set of simple and intuitive properties and showing that they indeed determine an uniquely defined common attack relations for rule-based argument systems.
Phan Minh Dung

Regular Papers

Frontmatter
Argumentation-Based Semantics for Logic Programs with First-Order Formulae
Abstract
This paper studies different semantics of logic programs with first order formulae under the lens of argumentation framework. It defines the notion of an argumentation-based answer set and the notion of an argumentation-based well-founded model for programs with first order formulae. The main ideas underlying the new approach lie in the notion of a proof tree supporting a conclusion given a program and the observation that proof trees can be naturally employed as arguments in an argumentation framework whose stable extensions capture the program’s well-justified answer semantics recently introduced in [23]. The paper shows that the proposed approach to dealing with programs with first order formulae can be easily extended to a generalized class of logic programs, called programs with FOL-representable atoms, that covers various types of extensions of logic programming proposed in the literature such as weight constraint atoms, aggregates, and abstract constraint atoms. For example, it shows that argumentation-based well-founded model is equivalent to the well-founded model in [27] for programs with abstract constraint atoms. Finally, the paper relates the proposed approach to others and discusses possible extensions.
Phan Minh Dung, Tran Cao Son, Phan Minh Thang
Resistance to Corruption of General Strategic Argumentation
Abstract
[16, 18] introduced a model of corruption within strategic argumentation, and showed that some forms of strategic argumentation are resistant to two forms of corruption: collusion and espionage. Such a model provides a (limited) basis on which to trust agents acting on our behalf. However, that work only addressed the grounded and stable argumentation semantics. Here we extend this work to several other well-motivated semantics. We must consider a greater number of strategic aims that players may have, as well as the greater variety of semantics. We establish the complexity of several computational problems related to corruption in strategic argumentation, for the aims and semantics we study. From these results we identify that strategic argumentation under the aims and semantics we study is resistant to espionage. Resistance to collusion varies according to the player’s aim and the argumentation semantics, and we present a complete picture for the aims and semantics we address.
Michael J. Maher
Spread of Cooperation in Complex Agent Networks Based on Expectation of Cooperation
Abstract
This paper proposes a behavioral strategy called expectation of cooperation with which cooperation in the prisoner’s dilemma game spreads over agent networks by incorporating Q-learning. Recent advances in computer and communication technologies enable intelligent agents to operate in small and handy computers such as mobile PCs, tablet computers, and smart phones as delegates of their owners. Because the interaction of these agents is associated with social links in the real world, social behavior is to some degree required to avoid conflicts, competition, and unfairness that may lead to further inefficiency in the agent society. The proposed strategy is simple and easy to implement but nevertheless can spread over and maintain cooperation in agent networks under certain conditions. We conducted a number of experiments to clarify these conditions, and the results indicate that cooperation spread and was maintained with the proposed strategy in a variety of networks.
Ryosuke Shibusawa, Tomoaki Otsuka, Toshiharu Sugawara
Semantic Reasoning with Uncertain Information from Unreliable Sources
Abstract
Intelligent software agents may significantly benefit from semantic reasoning. However, existing semantic reasoners are based on Description Logics, which cannot handle vague, incomplete, and unreliable knowledge. In this paper, we propose \(\mathcal {S}\textsf {DL}\text {-}\textsf {Lite}\) which extends \(\textsf {DL}\text {-}\textsf {Lite}_{{R}}\) with subjective opinions to represent uncertainty in knowledge. We directly incorporate trust into the reasoning so that the inconsistencies in the knowledge can be resolved based on trust evidence analysis. Therefore, the proposed logic can handle uncertain information from unreliable sources. We demonstrate how \(\mathcal {S}\textsf {DL}\text {-}\textsf {Lite}\) can be used for semantic fusion of uncertain information from unreliable sources and show that \(\mathcal {S}\textsf {DL}\text {-}\textsf {Lite}\) reasoner can estimate the ground truth with a minimal error.
Murat Şensoy, Lance Kaplan, Geeth de Mel
A Collaborative Framework for 3D Mapping Using Unmanned Aerial Vehicles
Abstract
This paper describes an overview of a generic framework for collaboration among humans and multiple heterogeneous robotic systems based on the use of a formal characterization of delegation as a speech act. The system used contains a complex set of integrated software modules that include delegation managers for each platform, a task specification language for characterizing distributed tasks, a task planner, a multi-agent scan trajectory generation and region partitioning module, and a system infrastructure used to distributively instantiate any number of robotic systems and user interfaces in a collaborative team. The application focusses on 3D reconstruction in alpine environments intended to be used by alpine rescue teams. Two complex UAV systems used in the experiments are described. A fully autonomous collaborative mission executed in the Italian Alps using the framework is also described.
Patrick Doherty, Jonas Kvarnström, Piotr Rudol, Marius Wzorek, Gianpaolo Conte, Cyrille Berger, Timo Hinzmann, Thomas Stastny
Heuristics on the Data-Collecting Robot Problem with Immediate Rewards
Abstract
We propose the Data-collecting Robot Problem, where robots collect data as they visit nodes in a graph, and algorithms to solve it. There are two variations of the problem: the delayed-reward problem, in which robots must travel back to the base station to deliver the data collected and to receive rewards; and the immediate-reward problem, in which the reward is immediately given to the robots as they visit each node. The delayed-reward problem is discussed in one of the authors’ work. This paper focuses on the immediate-reward problem. The solution structure has a clustering step and a tour-building step. We propose Progressive Gain-aware Clustering that finds good quality solutions with efficient time complexity. Among the six proposed tour-building heuristics, Greedy Insertion and Total-Loss algorithms perform best when data rewards are different.
Zhi Xing, Jae C. Oh
Verifying Real-Time Properties of Multi-agent Systems via SMT-Based Bounded Model Checking
Abstract
We present a satisfiability modulo theories based bounded model checking (SMT-based BMC) method for timed interpreted systems (\(\mathrm{\mathbb {TIS}}\)) and for properties expressible in the existential fragment of a Real-Time Computation Tree Logic with epistemic components (RTECTLK). We implemented the standard BMC algorithm and evaluated it for two multi-agent systems: a timed train controller system and a timed generic pipeline paradigm. We used the Z3 solver.
Agnieszka M. Zbrzezny, Andrzej Zbrzezny
Balancing Rationality and Utility in Logic-Based Argumentation with Classical Logic Sentences and Belief Contraction
Abstract
Compared to abstract argumentation theory which encapsulates the exact nature of arguments, logic-based argumentation is more specific and represents arguments in formal logic. One significant advantage of logic-based argumentation over abstract argumentation is that it can directly benefit from logical properties such as logical consistency, promoting adherence of an argumentation framework to rational principles. On the other hand, a logical argumentation framework based on classical logic has been also reported of its less-than-desirable utility. In this work we show a way of enhancing utility without sacrificing so much of rationality. We propose a rational argumentation framework with just classical logic sentences and a belief contraction operation. Despite its minimalistic appearance, this framework can characterise attack strengths, allowing us to facilitate coalition profitability and formability semantics we previously defined for abstract argumentation.
Ryuta Arisaka, Ken Satoh
Individually Rational Strategy-Proof Social Choice with Exogenous Indifference Sets
Abstract
We consider a social choice problem where individual rationality is required. The status quo belongs to the outcome space, and the selected alternative must be weakly better than the status quo for everybody. If the mechanism designer has no knowledge of the alternatives, we obtain a negative result: any individually rational (IR) and strategy-proof (SP) mechanism can choose at most one alternative (besides the status quo), regardless of the preferences. To overcome this negative result, we consider a domain where the alternatives have a known structure, i.e., an agent is indifferent between the status quo and a subset of the outcomes. This set is exogenously given and public information. This assumption is natural if the social choice involves the participation of agents. For example, consider a group of people organizing a trip where participation is voluntary. We can assume each agent is indifferent between the trip plans in which she does not participate and the status quo (i.e., no trip). In this setting, we obtain more positive results: we develop a class of mechanisms called Approve and Choose mechanisms, which are IR and SP, and can choose multiple alternatives as well as the status quo.
Mingyu Guo, Yuko Sakurai, Taiki Todo, Makoto Yokoo
Offer Evaluation and Trade-Off Making in Automated Negotiation Based on Intuitionistic Fuzzy Constraints
Abstract
In automated negotiation, one of crucial problems is how a negotiating agent evaluates the acceptability of an offer. Most models mainly use two kinds of evaluation methods: (i) linear utility functions that depend on issues, and (ii) nonlinear utility functions that depend on crisp constraints. However, in real life, it is hard for human users to input so much and so accurate information that these evaluation methods require. To this end, this paper proposes a new approach for offer evaluation where human users are allowed to input indeterminate information. More specifically, we propose a framework of prioritised intuitionistic fuzzy constraint satisfaction problems for modelling agent’s goals. Moreover, we take both satisfaction degree and dissatisfaction degree into consideration when calculating an agent’s acceptability of an offer. Finally, we discuss how to make trade-offs via similarity measure based on intuitionistic fuzzy criteria functions.
Jieyu Zhan, Xudong Luo
Analyzing Topics and Trends in the PRIMA Literature
Abstract
This study investigates the content of the literature published in the proceedings of the International Conference on Principles and Practices of Multi-Agent Systems (PRIMA). Our study is based on a corpus of the 611 papers published in eighteen PRIMA proceedings from 1998 (when the conference started) to 2015. We have developed an unsupervised topic model, using Latent Dirichlet Allocation (LDA), over the PRIMA corpus of papers to analyze popular topics in the literature published at PRIMA in the past eighteen years. We have also analyzed historical trends and examine the strength of each topic over time.
Hoa Khanh Dam, Aditya Ghose
Sequence Semantics for Normative Agents
Abstract
We proposed a novel framework for the representation of goals and other mental-like attitudes in terms of degree of expected outcomes, where an outcome is an order of possible alternatives. The sequences of alternatives is modelled by a non-classical (substructural) operator. In this paper we provide a modal logic based axiomatisation of the intuition they propose, and we discuss some variants (in particular for the notion of social intention, intentions that are compliant with norms). Given that the outcome operator is substructural, we first propose a novel sequence semantics (a generalisation of possible world semantics) to model the outcome operator, and we prove that the axiomatisation is sound and complete with respect to the new semantics.
Guido Governatori, Francesco Olivieri, Erica Calardo, Antonino Rotolo, Matteo Cristani
Revenue Maximizing Markets for Zero-Day Exploits
Abstract
Markets for zero-day exploits (software vulnerabilities unknown to the vendor) have a long history and a growing popularity. We study these markets from a revenue-maximizing mechanism design perspective. We first propose a theoretical model for zero-day exploits markets. In our model, one exploit is being sold to multiple buyers. There are two kinds of buyers, which we call the defenders and the offenders. The defenders are buyers who buy vulnerabilities in order to fix them (e.g., software vendors). The offenders, on the other hand, are buyers who intend to utilize the exploits (e.g., national security agencies and police). Our model is more than a single-item auction. First, an exploit is a piece of information, so one exploit can be sold to multiple buyers. Second, buyers have externalities. If one defender wins, then the exploit becomes worthless to the offenders. Third, if we disclose the details of the exploit to the buyers before the auction, then they may leave with the information without paying. On the other hand, if we do not disclose the details, then it is difficult for the buyers to come up with their private valuations. Considering the above, our proposed mechanism discloses the details of the exploit to all offenders before the auction. The offenders then pay to delay the exploit being disclosed to the defenders.
Mingyu Guo, Hideaki Hata, Ali Babar
Distant Group Responsibility in Multi-agent Systems
Abstract
In this paper, we introduce a specific form of graded group responsibility called “distant responsibility” and provides a formal analysis for this concept in multi-agent settings. This concept of responsibility is formalized in concurrent structures based on the power of agent groups in such structures. A group of agents is called responsible for a state of affairs by a number of collective decision steps if there exists a strategy for the agent group to preclude the specified state of affairs in the given number of steps. Otherwise, the group is partially responsible based on its maximum contribution to fully responsible groups. We argue that the notion of distant responsibility is applicable as a managerial decision support tool for allocation of limited resources in multi-agent organizations.
Vahid Yazdanpanah, Mehdi Dastani
Competitive VCG Redistribution Mechanism for Public Project Problem
Abstract
The VCG mechanism has many nice properties, and can be applied to a wide range of social decision problems. One problem of the VCG mechanism is that even though it is efficient, its social welfare (agents’ total utility considering payments) can be low due to high VCG payments. VCG redistribution mechanisms aim to resolve this by redistributing the VCG payments back to the agents. Competitive VCG redistribution mechanisms have been found for various resource allocation settings. However, there has been almost no success outside of the scope of allocation problems. This paper focuses on another fundamental model - the public project problem. In Naroditskiy et al. 2012, it was conjectured that competitive VCG redistribution mechanisms exist for the public project problem, and one competitive mechanism was proposed for the case of three agents (unfortunately, both the mechanism and the techniques behind it do not generalize to cases with more agents). In this paper, we propose a competitive mechanism for general numbers of agents, relying on new techniques.
Mingyu Guo
Coalition Structure Formation Using Anytime Dynamic Programming
Abstract
The optimal coalition structure generation is an important problem in multi-agent systems that remains difficult to solve. This paper presents a novel anytime dynamic programming algorithm to compute the optimal coalition structure. The proposed algorithm can be interrupted, and upon interruption, uses heuristic to select the largest valued coalition from each subproblem of size x and picks the rest of the unassigned agent from other subproblem of size \(n- x\), where n is the total number of agents. We compared the performance of our algorithm against the only existing proposal in the literature for the optimal coalition structure problem that uses anytime dynamic programming using 9 distinct datasets (each corresponding to a different distribution). The empirical evaluation shows that our algorithm always generates better or, at least, as good a solution as the previous anytime dynamic programming algorithm.
Narayan Changder, Animesh Dutta, Aditya K. Ghose

Early Innovation Short Papers

Frontmatter
Demand Response Integration Through Agent-Based Coordination of Consumers in Virtual Power Plants
Abstract
The transition towards an electricity grid based on renewable energy production induces fluctuation in electricity generation. This challenges the existing electricity grid design, where generation is expected to follow demand for electricity. In this paper, we propose a multi-agent based Virtual Power Plant design that is able to balance the demand of energy-intensive, industrial loads with the supply situation in the electricity grid. The proposed Virtual Power Plant design uses a novel inter-agent, multi-objective, multi-issue negotiation mechanism, to coordinate the electricity demands of industrial loads. Coordination happens in response to Demand Response events, while considering local objectives in the industrial domain. We illustrate the applicability of our approach on a Virtual Power Plant scenario with three simulated greenhouses. The results suggest that the proposed design is able to coordinate the electricity demands of industrial loads, in compliance with external Demand Response events.
Anders Clausen, Aisha Umair, Zheng Ma, Bo Nørregaard Jørgensen
A Multi Agent System for Understanding the Impact of Technology Transfer Offices in Green-IT
Abstract
We present a multi agent system simulating the complex interplay between the actors of innovation involved in the development of technology transfer for Green IT. We focus on the role and the influence of technology transfer offices on the individual objectives of each other actor (researchers, research facilities, companies). We analyse also their impact on several parameters, including sustainability.
Christina Herzog, Jean-Marc Pierson, Laurent Lefèvre
Modeling Organizational and Institutional Aspects in Renewable and Natural Resources Management Context
Abstract
Since 1990, there has been a striking increase in using multi-agent systems to study renewable resources management systems. The ultimate objective is to contribute to decisions support on resources management. The adopted strategic decisions are always joined with access to resources norms. However, the defined norms are statics and suppose that all agents are not autonomous and always obey to the underlying norms which do not reflect reality. In previous work, we proposed ML-MA [1], a multi-level multi-agent architecture to support renewable resources management systems modeling. In this work, we focus on the integration of normative aspects in our architecture. Our approach is illustrated using “Ouled Chehida” case study from Tunisian pastoral context.
Islem Hènane, Sameh Hadouaj, Khaled Ghédira, Ali Ferchichi
Generalising Social Structure Using Interval Type-2 Fuzzy Sets
Abstract
To understand the operation of the informal social sphere in human or artificial societies, we need to be able to identify their existing behavioural conventions (institutions). This includes the contextualisation of seemingly objective facts with subjective assessments, especially when attempting to capture their meaning in the context of the analysed society. An example for this is numeric information that abstractly expresses attributes such as wealth, but only gains meaning in its societal context. In this work we present a conceptual approach that combines clustering techniques and Interval Type-2 Fuzzy Sets to extract structural information from aggregated subjective micro-level observations. A central objective, beyond the aggregation of information, is to facilitate the analysis on multiple levels of social organisation. We introduce the proposed mechanism and discuss its application potential.
Christopher K. Frantz, Bastin Tony Roy Savarimuthu, Martin K. Purvis, Mariusz Nowostawski
Argumentation Versus Optimization for Supervised Acceptability Learning
Abstract
This paper deals with the question of how one should predict agent’s psychological opinions regarding acceptability statuses of arguments. We give a formalization of argumentation-based acceptability learning (ABAL) by introducing argument-based reasoning into supervised learning. A baseline classifier is defined based on an optimization method of graph-based semi-supervised learning with dissimilarity network where neighbor nodes represent arguments attacking each other, and therefore, the optimization method adjusts them to have different acceptability statuses. A detailed comparison between ABAL instantiated with a decision tree and naive Bayes, and the optimization method is made using each of 29 examinees’ psychological opinions regarding acceptability statuses of 22 arguments extracted from an online discussion forum. We demonstrate that ABAL with the leave-one-out cross-validation method shows better learning performance than the optimization method in most criteria under the restricted conditions that the number of training examples is small and a test set is used to select the best models of both methods.
Hiroyuki Kido
Towards Better Crisis Management in Support Services Organizations Using Fine Grained Agent Based Simulation
Abstract
Critical support service operations have to run 24 × 7 and 365 days a year. Support operations therefore do contingency planning to continue operations during a crisis. In this paper we explore the use of fine-grained agent-based simulation models, which factor in human-behavioral dimensions such as stress, as a means to do better people planning for such situations. We believe the use of this approach may allow support operations managers to do more nuanced planning leading to higher resilience, and quicker return to normalcy. We model a prototypical support operation, which runs into different crisis severity levels, and show for each case, a reasonable size of the crisis team that would be required. We identify two contributions in this paper: First, emergency planning using agent based simulations have mostly focused, naturally, on societal communities such as urban populations. There has not been much attention paid to study crisis responses within support services organizations and our work is an attempt to address this deficit. Second, our use of grounded behavioral elements in our agent models allows us to build complex human behavior into the agents without sacrificing validity.
Vivek Balaraman, Harshal Hayatnagarkar, Meghendra Singh, Mayuri Duggirala
Plan Failure Analysis: Formalization and Application in Interactive Planning Through Natural Language Communication
Abstract
While most robots in human robot interaction scenarios take instructions from humans, the ideal would be that humans and robots collaborate with each other. The Defense Advanced Research Projects Agency Communicating with Computer program proposes the collaborative blocks world scenario as a testbed for this. This scenario requires the human and the computer to communicate through natural language to build structures out of toy blocks. To formulate and address this, we identify two main tasks. The first task, called the plan failure analysis, demands the robot to analyze the feasibility of a task and to determine the reasons(s) in case the task is not doable. The second task focuses on the ability of the robot to understand communications via natural language. We discuss potential solutions to both problems and present prototypical architecture for the integration of planning failure analysis and natural language communication into an intelligent agent architecture.
Chitta Baral, Tran Cao Son, Michael Gelfond, Arindam Mitra
Automatic Evacuation Management Using a Multi Agent System and Parallel Meta-Heuristic Search
Abstract
An automatic evacuation management system taking advantage of a multi agent based mass evacuation simulator is proposed and prototyped. The aim of this system is to provide a stepping stone in the direction of automated evacuation managing. The proposed system is currently capable of identifying evacuation anomalies, proposing a mitigation strategy and providing feedback for human expert evaluation and query. All the pieces although seamlessly connected are independently developed. This allows their independent improvement and evaluation. This paper provides an overview of the developed automatic evacuation management system and all of its components, a demonstrative example, and discussion of its current limitations and future development direction. The demonstrative example shows increases of more than \(10\,\%\) in the evacuation throughput by using the proposed system.
Leonel Aguilar, Maddegedara Lalith, Tsuyoshi Ichimura, Muneo Hori
Dialectical Proof Procedures for Probabilistic Abstract Argumentation
Abstract
A dialectical proof procedure for computing grounded semantics of probabilistic abstract argumentation is presented based on the notion of probabilistic dispute tree. We also present an algorithm for top-down construction of probabilistic dispute trees.
Phan Minh Thang
Backmatter
Metadaten
Titel
PRIMA 2016: Principles and Practice of Multi-Agent Systems
herausgegeben von
Matteo Baldoni
Amit K. Chopra
Tran Cao Son
Katsutoshi Hirayama
Paolo Torroni
Copyright-Jahr
2016
Electronic ISBN
978-3-319-44832-9
Print ISBN
978-3-319-44831-2
DOI
https://doi.org/10.1007/978-3-319-44832-9