This paper presents the syntax and semantics of a simplified version of a logic-based agent-oriented programming language to implement agents with emotions. Four types of emotions are distinguished: happiness, sadness, anger and fear. These emotions are defined relative to agent's goals and plans. The emotions result from the agent's deliberation process and influence the deliberation process. The semantics of each emotion type is incorporated in the transition semantics of the presented agent-oriented programming language.
Mehdi Dastani, M. Birna van Riemsdijk, John-Jules Ch. Meyer
220 - 224
This paper presents three types of declarative goals: perform goals, achieve goals, and maintain goals. The integration of these goal types in a simple but extendable logic-based agent-oriented programming language is discussed and motivated. The computational semantics for each goal type is presented by means of a transition system. It is shown that the presented semantics of the goal types ensure some desirable and expected properties.
Alternating-offers is the most prominent negotiation protocol for automatic bilateral bargaining. Nevertheless, in most settings it is still not known how two fully rational agents should behave in the protocol. In this paper we study the finite-horizon alternating-offers protocol under one-sided uncertain deadlines. We make a novel use of backward induction in studying bargaining with uncertainty; we employ a “natural” system of beliefs and find, when it exists, the pertinent pure strategy sequential equilibrium. We further show, as an intrinsic limitation of the protocol, that for some parameter values there is no pure strategy sequential equilibrium, whatever system of beliefs is employed.
Azzurra Ragone, Tommaso Di Noia, Eugenio Di Sciascio, Francesco M. Donini
230 - 234
We propose a logic-based approach to automated oneshot multi-issue bilateral negotiation. We use logic in two ways: (1) a logic theory to represent relations among issues – e.g., logical implication – in contrast with approaches that describe issues as uncorrelated with each other; (2) utilities over formulas to represent agents having preferences over different bundles of issues. In this case, the utility assigned to a bundle is not necessarily the sum of utilities assigned to single elements in the bundle itself.We illustrate the theoretical framework and the one-shot negotiation protocol, which makes use of a facilitator to compute some particular Pareto-efficient outcomes. We prove the computational adequacy of our method by studying the complexity of the problem of finding Pareto-efficient solutions in a propositional logic setting.
The importance of defining a standard framework for agent communication languages (ACL) with a simple, clear, and a verifiable semantics has been widely recognized. This paper proposes a logic-based semantics which is social in nature. The basic idea is to associate with each speech act a meaning in terms of the commitment induced by that speech act, and the penalty to be paid in case that commitment is violated. A violation criterion based on the existence of arguments is then defined per speech act. Moreover, we show that the proposed semantics satisfies some key properties that ensure the approach is well-founded. The logical setting makes the semantics verifiable.
Existing approaches to knowledge representation and reasoning in the context of open systems either deal with “objective” knowledge or with beliefs. In contrast, there has been almost no research on the formal modelling of opinions, i.e., communicatively asserted ostensible beliefs. This is highly surprising, since opinions are in fact the only publicly visible kind of knowledge in open systems, and can neither be reduced to objective knowledge nor to beliefs. In this paper, we propose a formal framework for the representation of dynamic, context-dependent and revisable opinions and ostensible intentions as a sound basis for the external description of agents as obtained from observable communication processes. Potential applications include a natural semantics of communicative acts exchanged between truly autonomous agents, and a fine-grained, statement-level concept of trust.
Benoit Gaudou, Andreas Herzig, Dominique Longin, Matthias Nickles
245 - 249
One of the most important aspects of the research on agent interaction is the definition of agent communication languages (ACLs), and the specification of a proper formal semantics of such languages is a crucial prerequisite for the usefulness and acceptance of artificial agency. Nevertheless, those ACLs which are still mostly used, especially the standard FIPA-ACL, have a communication act semantics in terms of the participating agents' mental attitudes (viz. beliefs and intentions), which are in general undeterminable from an external point of view due to agent autonomy. In contrast, semantics of ACLs based on commitments are fully verifiable, but not sufficiently formalized and understood yet. In order to overcome this situation, we propose a FIPA-ACL semantics which is fully verifiable, fully formalized, lean and easily applicable. It is based on social attitudes represented using a logic of grounding in straightforward extension of the BDI agent model.
A common assumption for logic-based argumentation is that an argument is a pair 〈Φ, α〉 where Φ is a minimal subset of the knowledgebase such that Φ is consistent and Φ entails the claim α. Different logics are based on different definitions for entailment and consistency, and these give us different options for argumentation. For a variety of logics, in particular for classical logic, there is a need to develop intelligent techniques for generating arguments. Since building a constellation of arguments and counterarguments involves repeatedly querying a knowledgebase, we propose a framework based on what we call “contours” for storing information about a knowledgebase that provides boundaries on what is provable in the knowledgebase. Using contours allows for more intelligent searching of a knowledgebase for arguments and counterarguments.
Consider a community of simple autonomous robots freely moving in the plane. The robots are decentralized, asynchronous, deterministic without the common coordination system, identities, direct communication, memory of the past, but with the ability to sense the positions of the other robots. Existing results show the inability of gathering in this model and solve the gathering problem in the model extended by the multiplicity detection capability. However, the previous results rely on the fact that the robots are intially not moving. We prove that the gathering problem is unsolvable in the model with initial movement vectors even with the multiplicity detection capability.
We present a method to test a group of agents for (unwanted) emergent behavior by using techniques from learning of cooperative behavior. The general idea is to mimick users or other systems interacting with the tested agents by a group of tester agents and to evolve the actions of these tester agents. The goal of this evolutionary learning is to get the tested agents to exhibit the (unwanted) emergent behavior. We used our method to test the emergent properties of a team of agents written by students for an assignment in a basic MAS class. Our method produced tester agents that helped the tested agents to perform at their best and another configuration of our system showed how much the tested agents could hold their own against very competitive agents, which revealed breakdowns in the tested agents' cooperation.
Elise Bonzon, Marie-Christine Lagasquie-Schiex, Jérôme Lang, Bruno Zanuttini
265 - 269
Game theory is a widely used formal model for studying strategical interactions between agents. Boolean games  are two players, zero-sum static games where players' utility functions are binary and described by a single propositional formula, and the strategies available to a player consist of truth assignments to each of a given set of propositional variables (the variables controlled by the player.) We generalize the framework to n-players games which are not necessarily zero-sum. We give simple characterizations of Nash equilibria and dominated strategies, and investigate the computational complexity of the related problems.
Raz Lin, Sarit Kraus, Jonathan Wilkenfeld, James Barry
270 - 274
Many day-to-day tasks require negotiation, mostly under conditions of incomplete information. In particular, the opponent's exact tradeoff between different offers is usually unknown. We propose a model of an automated negotiation agent capable of negotiating with a bounded rational agent (and in particular, against humans) under conditions of incomplete information. Although we test our agent in one specific domain, the agent's architecture is generic; thus it can be adapted to any domain as long as the negotiators' preferences can be expressed in additive utilities. Our results indicate that the agent played significantly better, including reaching a higher proportion of agreements, than human counterparts when playing one of the sides, while when playing the other side there was no significant difference between the results of the agent and the human players.
Sana Moujahed, Olivier Simonin, Abderrafiâa Koukam, Khaled Ghédira
275 - 279
The facility positioning
Deployment, location and siting are used as synonyms
problem concerns the location of facilities such as bus-stops, fire stations, schools, so as to optimize one or several objectives. This paper contributes to research on location problems by proposing a reactive multiagent approach. Particularly, we deal with the p-median problem, where the objective is to minimize the weighted distance between the demand points and the facilities. The proposed model relies on a set of agents (the facilities) situated in a common environment which interact and attempt to reach a global optimization goal: the distance minimization. The interactions between agents and their environment, which is based on the artificial potential fields approach, allow us to locally optimize the agent's location. The optimization of the whole system is then obtained from a self-organization of the agents. The efficiency of the proposed approach is confirmed by computational results based on a set of comparisons with the k-means clustering technique.
While researchers have looked at many aspects of argumentation, an area often neglected is that of argumentation strategies. That is, given multiple possible arguments that an agent can put forth, which should be selected in what circumstances. In this paper, we propose a heuristic that implements one such strategy. The heuristic assigns a utility cost to revealing information, as well as a utility to winning, drawing and losing an argument. An agent participating in a dialogue then attempts to maximise its utility. We present a formal argumentation framework in which this heuristic may operate, and show how it functions within the framework. Finally, we discuss how this heuristic may be extended in future work, and its relevance to argumentation theory in general.
Terry Payne, Ester David, Nicholas R. Jennings, Matthew Sharifi
285 - 289
Public electronic displays can be used as an advertising medium when space is a scarce resource, and it is desirable to expose many adverts to as wide an audience as possible. Although the efficiency of such advertising systems can be improved if the display is aware of the identity and interests of the audience, this knowledge is difficult to acquire when users are not actively interacting with the display. To this end, we present BluScreen, an intelligent public display, which selects and displays adverts in response to users detected in the audience. Here, users are identified and their advert viewing history tracked, by detecting any Bluetooth-enabled devices they are carrying (e.g. phones, PDAs, etc.). Within BluScreen we have implemented an agent system that utilises an auction-based marketplace to efficiently select adverts for the display, and deployed this within an installation in our Department. We demonstrate, by means of an empirical evaluation, that the performance of this auction-based mechanism when used with our proposed bidding strategy, efficiently selects the best adverts in response to the audience presence. We bench-marked our advertising method with two other commonly applied selection methods for displaying adverts on public displays; specifically the Round-Robin and the Random approaches. The results show that our auction-based approach, that utilised the novel use of Bluetooth detection, outperforms these two methods by up to 64%.
An approach to handle the complex dynamics of a multi-agent system is based on distinguishing aggregation levels by structuring the system into parts or components. The behavior of every aggregation level is specified by a set of dynamic properties for components and interactions at that level, expressed in some (temporal) language. The dynamic properties of higher aggregation levels in principle can be logically related to dynamic properties of lower levels. This asks for identification and verification of such interlevel relations. In this article it is shown how this problem can be addressed using model checking techniques.
Sebastian Stein, Nicholas R. Jennings, Terry R. Payne
295 - 299
Service-oriented computing is a promising paradigm for highly distributed and complex computer systems. In such systems, services are offered by provider agents over a computer network and automatically discovered and provisioned by consumer agents that need particular resources or behaviours for their workflows. However, in open systems where there are significant degrees of uncertainty and dynamism, and where the agents are self-interested, the provisioning of these services needs to be performed in a more flexible way than has hitherto been considered. To this end, we devise a number of heuristics that vary provisioning according to the predicted performance of provider agents. We then empirically benchmark our algorithms and show that they lead to a 350% improvement in average utility, while successfully completing 5–6 times as many workflows as current approaches.
David C.K. Yuen, Andrew Byde, Nicholas R. Jennings
300 - 304
This paper investigates utility maximising bidding heuristics for agents that participate in multiple heterogeneous auctions, in which the auction format and the starting and closing times can be different. Our strategy allows an agent to procure one or more items and to participate in any number of auctions. For this case, forming an optimal bidding strategy by global utility maximisation is computationally intractable, and so we develop two-stage heuristics that first provide reasonable bidding thresholds with simple strategies before deciding which auctions to participate in. The proposed approach leads to an average gain of at least 24% in agent utility over commonly used benchmarks.
The traditional BDI agent has 3 basic computational components that generate beliefs, generate intentions and execute intentions. They run in a sequential and cyclic manner. This may introduce several problems. Among them, the inability to watch the environment continuously in dynamic environments may be disastrous and makes an agent less rational – the agent may endanger itself. Two possible solutions are by parallelism and by controlling and managing the 3 components in suitable ways. We examine a parallel architecture with three parallel running components which are the belief manager, the intention generator and the intention executor. The agent built with this architecture will have the ability of performing several actions at once. To evaluate the parallel BDI agent, we compare the parallel agent against four versions of sequential agents where the 3 components of the BDI agent are controlled and managed in different ways and different time resources are allocated to them. Experiments are designed to simulate agents based on the sequential and parallel BDI architectures respectively and the ability of the agents to respond to the same sequences of external events of various priorities are assessed. The comparison results show that the parallel BDI agent has quicker response, react to emergencies immediately and its behaviour is more rational.
Intention scheduling mechanism plays a critical role in the correct behaviour of BDI agents. For human-like agents, the independent intentions should be scheduled based on their priorities, which show the respective importance and urgency of the intentions. We propose to enrich the BDI agent architecture with 2 processing components, a PCF (Priority Changing Function) Selector and a Priority Controller. These enable a BDI agent to assign an initial priority value to an intention and change it with time according to the chosen PCF. The initial priority value reflects its urgency at the time of intention creation. The PCF selected defines how the priority should change with time. As an example, we design a function by simulating human behaviors when dealing with several things at the same time. The priority first increases with time according to the Gaussian function to simulate that people are more inclined to do something which has been on their mind for sometime. After a certain time, if the intention still does not get executed because of other higher priority intentions, its priority will decrease according to the Ebbinghaus forgetting curve. Experiment results show that with this mechanism, the agent can show some human-like characteristics when scheduling intention to execute. This can be used when simulating human-like agents.
We introduce a logical language with nullary operators min(n), for each non-negative integer n, which mean ‘the reasoner has at least n different beliefs’. The resulting language allows us to express interesting properties of non-monotonic and resource-bounded reasoners. Other operators, such as 'the reasoner has at most n different beliefs' and the operator introduced in [1, 4]: 'the reasoner knows at most the formulae φ1,…,φn′, are definable using min(n). We introduce several syntactic epistemic logics with min(n) operators, and prove completeness and decidability results for those logics.
In this paper, we show how to establish correctness and time bounds (e.g., quality of service guarantees) for multi-agent systems composed of communicating rule-based agents. The formal models of multi-agent systems we study are transition systems where each transition corresponds to either a rule firing or an act of communication by an agent. We present a complete and sound modal logic which formalises how the beliefs of communicating rule-based agents change over time. Using a simple example, we show how this logic can be used to specify temporal properties of belief change in multi-agent systems in a precise and realistic way, and how existing modal logic techniques such as model-checking can be used to state and verify properties of agents.
Recently I suggested that a cause is an event which, in its context of occurrence, is both necessary and sufficient for the effect. However this definition is only appropriate if there is a single potential cause of the effect. Consequently I suggest a generalization of the definition and discuss the resulting “Production Theory”. I suggest that this can be seen as a combination of a regularity theory in the Hume tradition and a dependence theory in the Lewis tradition, and argue that the Production Theory inherits the strengths of the component theories while avoiding their weaknesses.
This paper deals with merging multiple-source uncertain pieces of information, which are encoded by means of possibilistic networks. We first show that the merging of possibilistic networks having the same graphical structure can be easily achieved in polynomial time. When possibilistic networks have different graphical structures we show that their fusion can also be efficiently done by extending initial possibilistic networks into a same common structure. We then address two important problems: how to deal with cycles, and how to solve the subnormalization problem which reflects conflicts between sources?