A BDI-based agent architecture for social competent agents

Abstract

In this work we suggest a Belief-Desires-Intentions mental model that provides agents with the social competence to capture and reason about their goals with respect to the goals of other agents/humans in the environment. The suggested architectural model would enable the implementation of generic social competent agents that would interact differently towards different groups.

We explore the agent’s behavior on the social spectrum by computationally describing the maximum attainable benefit when it belongs to different types of social groups. In addition, as the mental model requires the agent to have an ability to reason about group membership, which we prove to be NP-complete, we present a way to formulate the problem as a constraints satisfaction problem and evaluate possible heuristics to speed-up the search.

Keywords

Social agents agent architecture mental model

1. Introduction

In human society individuals are pursing their own interests while considering the impact of their actions on their surrounding. Accordingly, an important aspect of Social Intelligence is the ability to correctly capture the social structure and use it to navigate and achieve ones goals. In this work we suggest a mental model that provides agents with similar social capabilities. The model captures the entire social behavior spectrum [9], and provides design principles that will allow agents to reason and change their behavior according to their subjective perception of the cooperative/competitive nature of the society.

The main goal of the model it to assist software engineers with the implementation of generic social competent agents that would interact differently towards different groups. Such agents might, for instance, act cooperatively on some occasions, and on others they might reason (according to their beliefs) that competitive behavior should be applied to achieve their goals. Possible applications are quite obvious and span any autonomous agent (robot) that represents the interests of humans in virtual (physical) social environments. The model also intend to address a new class of important problems, where an agent can be part of different types of groups and acts accordingly (see [27]), thus it must consider how its actions affects other group members. Classifying different types of desires and behaviors is an important step in allowing it to do so.

Our model builds upon Bratman’s philosophical foundations of the Belief-Desire-Intention (BDI) model [4] that was developed to explain human practical reasoning. The model was proved to be highly applicable as a software model for developing bounded rational intelligent agents (e.g. [12]). However, while previous adaptation of the model described only specific parts of the social behavior spectrum (in particular joint and individual desires), in the first part of this work we aim to provide a formal model that spans the entire social spectrum, including relations that have not yet received any attention.

To do so we first extend the common Desires model to account for different relationship between desires. We then present the Social Behavior Activity (SBA) model, a BDI-based mental model that spans the social spectrum. The contribution of the SBA mental model is twofold: first, it provides a formal, valid theoretical foundation that could be used to explain and predict agent’s social behavior in realistic environment. Second, it serves as a set of design principles to guide the creation of agents that would be able to engage in behaviors that span the entire social spectrum.

Following the presentation of the model, we explore the agent’s behavior on the spectrum by computationally describing the maximum attainable benefit when it belongs to different types of social groups. The computational analysis provides a basis for building agents that are able to switch from competitive to cooperative interactions, or to individualistic behavior. The main goal of this analysis is to provide agents with the capabilities to reason about their different goals and to compute whether they should coordinate with the others, or form cooperative/competitive groups with them. Our analysis will define the different social groups and present a way to reason on them with the suggested mental architecture. In addition, as the mental model and social groups analysis require the agent to have an ability to reason about group membership, which we prove to be NP-complete, we also present a way to formulate the problem as a constraints satisfaction problem and evaluate possible heuristics to speed-up the search.

To summarize, our main contributions can be seen as the following:1

¹
This work extends the conference paper presented in [37].

The presentation of the Social Behavioral Activity (SBA) mental model for the construction of social competent agents. This mental model is an architectural framework that will allow engineering agents that have some reasoning capabilities about their social surroundings.

An analytical exploration of different social groups, which will allow an agent to decide which group to member (if any). As the above item is computationally expensive, we also present a reduction to the constraints satisfaction problem, and present and evaluate several heuristics to the group membership problem.

Following our presentation of the SBA model, we will explore its relationship to prior BDI models: SharedPlans (SP) [17], SharedActivity (SA) [18] and AdversarialActivity (AA) [38].

2. Related work

The social oriented multi-agent literature includes domain-specific algorithms that provide some adaptability to agents with different personalities or social behaviors. For example, in [21] the authors used a joint social welfare function and allowed agents to change the weight of their social tendency level. In [29] the authors used the Colored Trails game to study a model in which agents’ helpfulness is characterized in terms of cooperation and reliability. Another interesting approach in the form of a dependency graph that is used to describe and capture the relationships inside a multi-agent system environment was presented in [26], while another line of work that explores agents’ social interactions comes from agent-based simulation approach [8]. While these work provide some reasoning capabilities about the agents or the emergent dynamics of the multi-agent system, they do not consider the architectural aspect of agent design within the BDI framework, that is the main focus of this work.

Another related line of work is on group beliefs. These are usually defined as collectively intentional attitudes that are based on what the group members accept as the group’s belief [13,19,32]. Group beliefs, as oppose to individual beliefs (or mutual beliefs in our context), are attributed only to the collective. The fact that all the group members believe that A is not sufficient (or necessary) for a group belief in A. It is required for group belief that the group members take A to be true when they are acting in the group context, that is, that the individuals accept A when they are acting as group members. In our case we are dealing solely with individual beliefs (and mutual beliefs which are based on those) and the formation of different social groups does not require the adaptation of group beliefs to become members in that group.

Other works explore the notion of norms as a regulatory mechanism to agents’ behavior. However, norm-regulated environments may experience problems when norms associated with their agents are in conflict. For instance, actions that are forbidden in one social context, may, at the same time, also be permitted in another context. There are works that try to cope with these inconsistencies by presenting various mechanisms to detect and solve these contradictions (e.g. [35]). Nevertheless, we are not aware of any work in which these inconsistencies affect the agent decision regarding group membership.

BDI stands for Beliefs-Desires-Intentions. It is a model of human planning and decision making procedure that its philosophical foundations were developed by Bratman [4] as a way to explain how beliefs and desires (goals) should be connected to intentions. One of its main point was that a desire is idle until a plan is explicitly constructed to achieve it. In other words, until there is an explicit intention to pursue it.

Over the years, formal BDI based models of cooperation and teamwork activities have been extensively explored in multiagent worlds, producing various works on the problem’s philosophical foundations (e.g. [5,31]). These foundations were the main building blocks for different formal models, each with its own strengths and weaknesses (e.g. [17,22,36]). Part of these models followed with architectural works and implementations (e.g. [6,30]) which made an important proof of concept for the underlying models. More recently, with the advancements in agent-based programming solutions, new BDI-based practical abstract programming languages have emerged including 3APL [20], AgentsSpeak [25], and GOAL [7], which gave birth to several practical platform (see [2,3] for more information on these).

When interactions are guided by diverse interests, participants may have to overcome disagreements, uncooperative interactions, and even intentional attempts to damage one another. When these types of interactions occur, environments require appropriate behavior from the agents situated in them. Reviewing the BDI literature we can see that most works focus on the cooperative part of the social behavior spectrum [22], while other focus on various specific parts. For example, the Adversarial Activity model presented in [38] looks at the competitive part of the spectrum, while the Shared Activity model [18] disregards aggressive behavior. Additional work by Montagna et al. [23] did consider classification to “friends” and “enemies” in the formal language, however these are regarded as simplified predefined and static labels and are not connected to the agents’ set of desires. Jamroga et al. [34] extended ATL to facilitate game-like multi-agent reasoning capabilities, but still builds upon the classic structure of Desires.

The suggested framework in this work supports the full range of social interactions, from complete cooperation, through individualism, to zero-sum conflict.

3. The BDI language

The aim of our work is to be used as guidelines for the design of social competent agents that supports the full range of social interactions, from complete cooperation, through individualism, to zero-sum conflict. As such, while we have selected to use the SharedPlans formalism [17] as the underlying BDI based language, it is possible to use most of the above formal models [22,23,34] and augment the extended Desire model onto them.

3.1. Basic definitions

Our BDI formalism is derived from the one proposed in [14], and [15]. We have a basic propositional language L which is used by the agent to express beliefs about the world. We will simply assume that it contains the usual classical logic connectives ( $\land, \lor, \neg, \to, \leftrightarrow$ ), and their classical interpretation, together with the truth and falsity ( $⊤, ⊥$ ) constants, and the semantic entailment operator (⊢). F is the set of sentences of this language. We assume that the belief change operations $\dot{+}$ (revision) and $\dot{-}$ (contraction) have been defined for L [1].

Next, we assume a set $A = {1, 2, \dots, n}$ of agents. For each agent $i \in A$ we assume a finite set of actions, $A c_{i} = {α_{1}, α_{2}, \dots}$ . The set $A c_{i}$ represents the abilities of agent i. Agent i’s knowledge about how to bring about states of affairs in the environment is captured by a set of recipes $R_{i} = {⟨ α, φ ⟩ | α \in A c_{i} and φ \in L}$ , such that action α is executable if its preconditions are satisfied and the termination of α’s performance results in φ being true (see, e.g., [24] for discussion on the notion of “plan as recipe”). For every recipe $r = ⟨ α, φ ⟩$ , we assume there is a proposition $r_{α, φ} \in L$ . Intuitively, $r_{α, φ} \in L$ will be used to mean that: (1) the action α is executable, in that its preconditions are currently satisfied, and (2) the performance of α terminates and makes φ true. Only those recipes whose actions the agent believes can be executed are listed as beliefs using the propositions $r_{α, φ}$ . We will assume that in all recipes $⟨ α, φ ⟩$ , the formula φ is an atomic proposition.

3.2. BDI structures

Given the set of beliefs $B_{i}$ , desires $D_{i}$ , intentions $I_{i}$ , valuation function $v^{i}$ and cost function $c^{i}$ , A BDI structure for agent i is: $S_{i} = ⟨ B_{i}, D_{i}, I_{i}, v^{i}, c^{i} ⟩$ .

Beliefs – modeled in the conventional way and describe knowledge about the world or about other agents. $B_{i}$ stands for the beliefs of the agent, and it is a logical closure of a finite set of sentences. Formally, $B_{i} = {b \in L | B_{i}^{0} ⊢ b}$ , where $B_{i}^{0} \subset L$ is a finite set that represents the basis set of beliefs for i.

Desires – $D = D_{1} \cup D_{2} \dots \cup D_{n}$ , where $D_{i} \subset L$ represents the set of desires for agent i. We will use $d_{i}^{1}, \dots, d_{i}^{m}$ as elements in $D_{i}$ . We assert that desires will stay consistent by the belief revision operators.

Intentions – $I_{i}$ stands for the intentions of the agent i, where $I_{i} \subseteq R_{i}$ .

Valuation – Defined as $v^{i} : 2^{(D_{i})} \to R^{+}$ where $R^{+}$ is the set of positive real numbers.

Cost – Defined for a finite set of actions $c^{i} : 2^{(A c_{i})} \to R^{+}$ , which must satisfy the following condition: if $K \subseteq K^{'} \subseteq A c_{i}$ then $c^{i} (K^{'}) ⩾ c^{i} (K)$ .

We require that $v^{i}$ satisfies the following “monotonicity” condition: for $T_{i} \subseteq D_{i}$ , then $v^{i} (T_{i}) ⩽ v^{i} (D_{i})$ , and “additivity” condition: $v^{i} ({d_{i}^{1}, d_{i}^{2}}) = v^{i} (d_{i}^{1}) + v^{i} (d_{i}^{2})$ . In addition, we assert that the results of conflicting actions will be determined by nature: i.e. when two agents trying to achieve $d_{i}$ and $\neg d_{i}$ at the same time, only one of them will be instantiated, and their values will be the expected values, that is $v^{i} ({d_{i}, \neg d_{i}}) = \frac{1}{2} v^{i} (d_{i}) + \frac{1}{2} v^{i} (\neg d_{i})$ .2

²
Another option is to assume $v^{i} ({d_{i}, \neg d_{i}}) = - \infty$ . The appropriate assumption is dependent on the use of the model.

We extend the value function

v^{i}

to a function

{\bar{v}}^{i}

on all subsets X of L as follows:

{\bar{v}}^{i} = \{\begin{matrix} v^{i} ({d \in D_{i} | X ⊢ d}) & if X ⊬ ⊥ \\ 0 & otherwise \end{matrix}

Additionally, where $I_{i}$ is a set of intentions, we assert $goals (I_{i}) = {φ | < α, φ > \in I_{i}}$ and $actions (I_{i}) = {α | < α, φ > \in I_{i}}$ . Where B is a set of beliefs and I is a set of intentions, we say that I is feasible in the context of B if $\forall ⟨ α, φ ⟩ \in I$ , $r_{α, φ} \in B$ , (i.e., the action part of every intention is believed to be executable). We write $feas (I, B)$ to denote the largest subset of I that is feasible in the context of B. Note that since B has a finite basis, $feas (I, B)$ must be finite.

Next, we defined a function ${ben}_{i} (I, B) \to R$ , the benefit that agent i would obtain from the set of intentions I if it were the case that beliefs B were correct: ${ben}_{i} (I, B) = {\bar{v}}^{i} (B \dot{+} \land {goals (feas (I, B))}) - c^{i} (actions (I) \cap A c_{i})$ . So, forexample: $b e n_{i} (I_{i}, B_{i})$ is the benefit that agent i would obtain from its own intentions $I_{i}$ under the assumption that its own beliefs, $B_{i}$ were correct. Similarly, ${ben}_{i} (I_{1} \cup \dots \cup I_{n}, B_{i})$ is the benefit that agent i would obtain from the intentions of all agents in the system, under the assumption that its own beliefs, $B_{i}$ were correct.

3.3. Desires model

Our formalization extends former BDI frameworks by providing the ability to reason whether one should be part of a social group $A$ , such that its intentions $I_{i}$ are adopted according to its beliefs about the states of the other members as well as their desires. Specifically, while previous BDI models only focused on cooperation while working solely with individual or joint desires, we take a new approach by differentiating between three types of desires that agent i may consider according to its relationship with some j:

Cooperative Desire ( $D_{i}^{c o p}$ ): $d \in D_{i}$ is i’s cooperative desire with respect to agent $j \in A$ , if $\exists_{j \neq i} d \in D_{j}$ .

Individual Desire ( $D_{i}^{i n d}$ ): $d \in D_{i}$ is an individual desire with respect to agent $j \in A$ , $i \neq j$ , if $\neg (d \in D_{j} \lor \neg d \in D_{j}$ ).

Competitive Desire ( $D_{i}^{c o m}$ ): $d \in D_{i}$ is i’s competitive desire with respect to agent $j \in A$ , if $\exists_{j \neq i} \neg d \in D_{j} .$

Running example.
Consider an academic department with three faculty members: Alice, Bob and Chen. Bob is already in a tenure track, while Alice and Chen have temporary positions. In addition, there is one newly available tenured position. Alice has three desires: (1) submitting a proposal. (2) winning an open tenured position in the department. (3) writing a paper. Bob’s desires are: (1) submit a proposal. (2) writing a paper. Chen’s desires are: (1) winning a tenured position in the department. (2) submitting a proposal.

Formally, the set of agents is ${A, B, C}$ . The Desires are ${d_{A}^{1}, d_{A}^{2}, d_{A}^{3}}$ for Alice, ${d_{B}^{1}, d_{B}^{2}}$ for Bob and ${d_{C}^{1}, d_{C}^{2}}$ for Chen. The valuation function for Alice is $v^{A} (d_{A}^{1}) = 5, v^{A} (d_{A}^{2}) = 12, v^{A} (d_{A}^{3}) = 10$ . The costs of the actions that brings about these desires (e.g. $⟨ α, d_{A}^{1} ⟩$ ) are $5, 8, 3$ respectively. The valuation function for Bob is $v^{B} (d_{B}^{1}) = 8, v^{B} (d_{B}^{2}) = 10$ , with action costs of $6, 6$ respectively. The valuation function for Chen is $v^{C} (d_{C}^{1}) = 8, v^{C} (d_{C}^{2}) = 6$ with actions costs of $5, 4$ .

Adding the information that the proposal desires are cooperative as all three are working jointly on the same proposal, i.e., $d_{A}^{1} = d_{B}^{1} = d_{C}^{2}$ . In a well-coordinated interaction only a single agent will spend the cost associated with this desire. In contrast, the position appointment is a competitive desire for Alice and Chen. As such, without coordination both will spend the cost of perusing the appointment, but only one will win. The others are individual desires.

The definitions of the different relations between goals yield the following: Proposition 1.
These properties satisfy the desire model:
Mutual Exclusion (with respect to a single agent) – $(D_{i}^{c o p} \cap D_{i}^{i n d}) = \emptyset$ . $(D_{i}^{c o p} \cap D_{i}^{c o m}) = \emptyset$ . $(D_{i}^{i n d} \cap D_{i}^{c o m}) = \emptyset$ .

Additivity – Let $D_{i}^{x}$ and $D_{i}^{y}$ be the set of desires from different types, then $v^{i} (D_{i}^{x} \cup D_{i}^{y}) = v^{i} (D_{i}^{x}) + v^{i} (D_{i}^{y})$ .

Containment – $D_{i}^{c o p} \subseteq D_{i}$ , $D_{i}^{i n d} \subseteq D_{i}$ , $D_{i}^{c o m} \subseteq D_{i}$ .

Self Desires – $D_{i} = D_{i}^{c o p} \cup D_{i}^{i n d} \cup D_{i}^{c o m}$ .

Proofs.
The Mutual Exclusion, that its existence can be seen from direct inspection of the definitions, provides the ability to ascribe the desire of agent i to one of the three types of desires. Mutual exclusion is with respect to a specific observable agent j. That is, agent’s i desire that is classified as a cooperative desire with respect to agent j, cannot be classified as an individualistic or a competitive desire towards j. The Additivity property, stating that the value of the union of desires is their individual sum, is a corollary of Mutual Exclusion. The Containment property is obvious from its definition. The Self Desires property is derived using propositions Mutual Exclusion and Containment; For every $d \in D_{i}$ , d can either be in some other agent’s set, in that case $d \in D_{i}^{c o p} \lor d \in D_{i}^{c o m}$ (depending on $v_{i}$ ), or it is not in some other agent’s set, hence $d \in D_{i}^{i n d}$ .

From the above basic properties we can see that agent i’s set of desires ( $D_{i}$ ) contains three types of desire relations: cooperative, individualistic and competitive desires. We define three types of action sets, where the actions in each set are part of the intentions that an agent adopts when trying to achieve the respective type of desire, as follows: $A_{C_{i}}^{b} = {α | < α, φ > \in I_{i}, φ \in D_{i}^{b}}$ , where $b \in {c o p, i n d, c o m}$ . □

4. The social behavior spectrum

Fig. 1.

Social behaviors spectrum.

Figure 1 describes a two-person preference model of the major interpersonal orientations that can occur between players. In this model [16], the player’s utility is defined on the horizontal axis, and the outcome of the “other” player is on the vertical axis. Each outcome increases monotonically along each axis, and the values reflect a linear combination of payoffs to both players. Multiple agents will be regarded as pairwise aggregation of the two-person model.3

Note that the behaviors on the left side of the graph are deliberately excluded from our work, since besides behaviors such as sacrifice or gifts, in which ones outcome is reduced, most of them are considered mental disorders (e.g. Masochism, Sado-Masochism).

To allow the description of different relationships between the agents’ desires, we now describe a set of behavioral axioms that correspond to the interpersonal orientations exhibited in the social behavior spectrum. The presented axioms, together with the mental state model presented later on, will constitute the design guidelines for the construction of social agents. In order to avoid describing a BDI framework from scratch, we build our presentation on a well-known framework, the SharedPlans [17], that provide all the operators and predicates for facilitating a joint activity.4

⁴

Nevertheless, our extension is general and can be used to extend any other model.

Next we present the main components of the SharedPlans formalism, but refer the reader to [17] for a complete description. The operator $Int.To (i, α, T_{n}, T_{α}, S)$ represents i’s intentions at time $T_{n}$ to do action α at time $T_{α}$ in the context of the BDI structure $S$ . The operator $Int.Th (i, prop, T_{n}, T_{prop}, S)$ representsi’s intention at time $T_{n}$ that a certain proposition $prop$ will hold at time $T_{prop}$ in the context of $S$ . The potential intention operators, Pot.Int.To(…) and Pot.Int.Th(…), are used to represent the mental state when an agent considers adopting an intention, but has not yet deliberated about its interaction with the other intentions it holds. The operator $B e l (i, f, T_{f})$ indicates i believes the statement expressed by formula f at time $T_{f}$ (we abuse notation with the formula f not really constituting the argument, but its name ‘f’). $M B (A, f, T_{f}$ ) represents Mutual Belief of the agents in $A$ . In addition, the operator $D o (i, α, T_{α})$ holds when i performs action α at time $T_{α}$ . The following are the five major social orientations:

A1. Altruistic act axiom In its purest form, an altruistic act is an action that improves the condition of the other, while not improving (and possibly worsening) your own condition. It appears to contradict the rational behavior assumption at the heart of classical economic theories. While rational behavior can lead to various problems when there is conflict between an individual’s interest and the perceived interest of the group (e.g., “the tragedy of the commons”), there are circumstances where the good of the group prevails, and individuals adopt “irrational” behavior for the sake of the collective. $\begin{array}{l} (\forall i, j \in A, S_{i}, S_{j}, ⟨ α, d ⟩ \notin I_{i}, d \notin D_{i}, T_{n}) \\ [Bel (i, {ML}_{alt} < {ben}_{i} (I_{i}, B_{i}) < 0, T_{n}) \land Bel (i, d \in \\ D_{j}, T_{n}) \to Pot.Int.To (i, α, T_{n}, T_{α}, S_{i})] \end{array}$

Agent i may consider adopting an intention to achieve an altruistic desire with respect to j, even if i does not obtain any benefit from attaining it (hence, altruism). The axiom states that an agent i will adopt an intention which achieves $d \in D_{j}$ if it believes that by performing it agent j will obtain a value, and that the decrease in its own benefit, due to the additional costs, will not be larger than some $M L_{a l t}$ constant.

It is important to note that as researchers still debate on the nature of altruistic behavior and whether they do provide some implicit benefit to its actuator, our definition does not consider these implicit benefits.

A2. Cooperative act axiom In a cooperative act, both parties share some effort to gain some benefit. In a pure cooperative scenario (such as the SharedPlan model [17]), the parties are members of the same group and attain part of their benefit from the group’s mutual utility function. In these situations, the parties have the incentive to use all of their resources in order to complete the joint goal. No member has any incentive to “save” some of its resources because the group’s utility is the main utility function. $\begin{array}{l} (\forall i, j \in A, S_{i}, S_{j}, ⟨ α, d ⟩ \notin I_{i}, d \in D_{i}, T_{n}) \\ [[Bel (i, d \in D_{j}, T_{n})] \land \\ case 1: “ j loses from achieving d itself” \\ [Bel (i, b e n_{j} (I_{j}, B_{i}) < 0, T_{n}) \\ \to Pot.Int.To (i, α, T_{n}, T_{α}, S_{i})] \oplus \\ case 2: “ j gets gains benefit from achieving d itself” \\ [Bel (i, {ben}_{j} (I_{j}, B_{i}) ⩾ 0, T_{n}) \\ \to Pot.Int.To (i, α, T_{n}, T_{α}, S_{i}) \lor \\ Pot.Int.Th (i, D o (j, α, T_{α}), T_{n}, T_{D o (.. .)}, S_{i}) \lor \\ Pot.Int.Th (i, D o ({i, j}, α, T_{α}), T_{n}, T_{D o (.. .)}, S_{i})]] \end{array}$

The formulation of the cooperative axiom is based on the theory presented in [18] that differentiate between a task and a treatment cooperative groups. Formally, an agent i may consider adopting an intention to achieve a cooperative desire with respect to j. This axiom states that if i believes that it shares the same desire with j, then there are two cases of cooperation. The first case states that i believes that j loses from completing the desire itself, then i may consider adopting an intention to achieve the desire. In the second case both agents, i and j, do not lose by performing α which achieves the desire (the α’s may be different), and there are three options. First, i may consider doing α by itself. Second, i may adopt a potential intention that α will be done by j. Third, α will be performed by i and j jointly.

A3. Individualistic act axiom Individualism is the case of showing no interest in the actions and utilities of others, while conducting actions that will maximize the individualist’s own utility value. This kind of social behavior is considered rational behavior in economic. $\begin{array}{l} (\forall i \in A, S_{i}, ⟨ α, d ⟩ \notin I_{i}, d \in D_{i}, T_{n}) \\ [Bel (i, b e n_{i} (I_{i}, B_{i}) ⩾ 0, T_{n}) \\ \to Pot.Int.To (i, α, T_{n}, T_{α}, S_{i})] \end{array}$

Formally, agent i may consider adopting an intention to achieve an individualistic desire when it believes that this desire does not belong to the other agent’s set of desires.

A4. Competitive act axiom There are situations in which increasing one’s utility will decrease the other’s, thus they are competitive interactions. The middle point of these interactions is pure competition, which occurs in zero-sum interactions. In these competitions, each party wants to complete a goal that directly conflicts with the goal of the other, and one’s gain is exactly the other’s loss. The competitive range also includes non-zero-sum encounters, in which the parties’ aggregate gains and losses can be more or less than zero (reflected in the ranges above and below the competition line). $\begin{array}{l} (\forall i, j \in A, S_{i}, S_{j}, ⟨ α, d ⟩ \notin I_{i}, d \in D_{i}, T_{n}) \\ [Bel (i, {ben}_{i} (I_{i}, B_{i}) ⩾ 0, T_{n}) \land Bel (i, (\exists_{(j \neq i)}) \neg d_{i} \in \\ D_{j}, T_{n}) \to Pot.Int.To (i, α, T_{n}, T_{α}, S_{i})] \end{array}$

Formally, agent i may consider adopting an intention to achieve a competitive desire with respect to j when it obtains a positive benefit from achieving the desire, even when i believes that agent j holds another desire, where when both desires will be achieved, agent i might lose.

A5. Aggressive act axiom In aggressive behavior, the agent’s only goal is to hurt the other party without trying to increase its own benefit. Such behavior can occur due to personal social and psychological circumstances. E.g, a player with no chance to win in an encounter might decide to focus his efforts on preventing one of the other competitors from winning, due to personal intrigues against him. This player might gain some benefit from its “vengeful” behavior, but no benefit will be gained with respect to the original goal. $\begin{array}{l} (\forall i, j \in A, S_{i}, S_{j}, ⟨ α, d ⟩ \notin I_{i}, d \notin D_{i}, T_{n}) \\ [Bel (i, M L_{a g g} < b e n_{i} (I_{i}, B_{i}) ⩽ 0, T_{n}) \land \\ Bel (i, \neg d \in D_{j}, T_{n}) \to Pot.Int.To (i, α, T_{n}, T_{α}, S_{i})] \end{array}$

Formally, agent i may consider adopting an intention to achieve an aggressive desire with respect to j, if it loses from achieving d, as long as member j also loses. The axiom states that an agent i will consider adopting the intention of performing α which may decrease its benefit up to some lower bound ${ML}_{agg}$ , if it believes that by achieving d j’s benefit will decrease as well, as $\neg d$ is in his set of desires.

5. Social behavior activity

The Social Behavior Activity model (SBA) describes the mental states of a member in a social interaction; these possible mental states span the spectrum as presented above, whereby the agent’s valuation of the desire relations affects its competitive/cooperative position on the spectrum. The SBA model defines a social behavior activity for a group of agents $A$ in the context of the BDI structure $S$ and profiles $P$ at time $T_{n}$ . We use the notation $P$ to represent the profiles of the members, and we use $P_{i}^{j}$ to denote i’s beliefs about j’s profile. The profile of a member is a domain dependent object that captures information that is known about the agents.5

⁵
As the profile definition is domain dependent, we refer the reader to [18] for an example of profile usage in an application.

The operator

member (i, A)

in the definition holds if i is a member of

A

, and

\max ()

is the maximum function. The Social Behavior Activity model is as follows:

$S B A (S, A, P, T_{n})$

$A$ mutually believes that all members are part of $A$ : $MB (A, (\forall i \in A) member (i, A), T_{n})$

Members of $A$ have (partial) beliefs about the profiles of the other agents: $(\forall i \in A) Bel (i, (j \in A) (\exists P_{i}^{j} \subseteq P), T_{n})$

$A$ mutually believes that either:

[all members of $A$ have the intention that they will attain the maximum positive difference between their and their opponent’s benefits: $\begin{array}{l} MB (A, f, T_{f}), f = (\forall i \in A) \\ Int . Th (i, \max (b e n_{i} (I_{1} \cup \dots \cup I_{n}, B_{i}) - (\forall_{j \neq i}) \\ b e n_{j} (I_{1} \cup \dots \cup I_{n}, B_{i})), T_{n}, T_{\max (\dots)}, S)] \oplus \end{array}$

[being a member obtains a better benefit value: $\begin{array}{l} MB (A, f, T_{f}), f = (\forall i \in A) \\ (b e n_{i} (I_{1} \cup \dots \cup I_{n}, B_{i}) ⩾ {ben}_{i} (I_{i}, B_{i}), T_{n}) \land \\ A has a mutual belief that each member has \\ an intention that the group be maintained: \\ MB (A, f, T_{f}), f = (\forall i \in A) \\ Int . Th (i, member (i, A), T_{n}, T_{member (.. .)}, S)] \end{array}$

First, SBA implies the ability of the agents to identify themselves as members of some social group (item 1) (an autonomous agent working in isolation will not be part of a social activity). Second, each individual in the group is characterized by life histories, development patterns, needs, goals, and behavior patterns. These characteristics might be known to some extent and are represented in each member’s profile. Thus, the members must have beliefs concerning a partial profile of the others (item 2). The profiles may be given explicitly or implicitly (e.g., learning the profile by observation, overhearing, etc.), and their exact structure is domain dependent. The third item represents two forms of mutual inter-group dependence. Dependence refers to the relation in which the benefit that one member obtains from its own behaviors is affected at least partly by the activities of another party. Mutual dependence (item 3) means that the benefits of all the parties are affected to some extent by the behaviors of the other members [9]. We differentiate (using exclusive or, ⊕) between two cases of mutual dependence: competitive ( ${SBA}_{a}$ ) and cooperative ( ${SBA}_{b}$ ) dependence. Proposition 2 (Consistency of Altruism).

(a) Agent i which his $S_{i}$ satisfies the mental states for ${SBA}_{a}$ (competitive social group) will not behave according to axiom A.1. (b) Agent i which his $S_{i}$ satisfies the mental states for ${SBA}_{b}$ (cooperative social group) might behave according to axiom A.1.

Proof.
(a) When i satisfies ${SBA}_{a}$ he believes to be in a competitive social group. Item 3.a in the mental state model dictates a mutual beliefs on a need to maximize the difference between his own benefit and the other members, which is inconsistence rationally with adopting an ${ben}_{i} (I_{i}, B_{i}) < 0$ intention. (b) When i satisfies ${SBA}_{b}$ he believes to be in a cooperative social group. Item 3.b in the mental state model dictates a mutual belief that $b e n_{i} (I_{1} \cup \dots \cup I_{n}, B_{i}) ⩾ {ben}_{i} (I_{i}, B_{i})$ . In order to satisfy that, i might need to adopt a ${ben}_{i} (I_{i}, B_{i}) < 0$ intention, to be consistent with the former condition. □
Proposition 3 (Consistency of Aggression).

(a) Agent i which his $S_{i}$ satisfies the mental states for ${SBA}_{b}$ (cooperative social group) will not behave according to axiom A.5. (b) Agent i which his $S_{i}$ satisfies the mental states for ${SBA}_{a}$ (competitive social group) might behave according to axiom A.5.

Proof.
(a) As the cooperative social group does not incentivize aggressive actions, a null-action will be always preferred to an aggressive action which lowers both his benefits. (b) It is intuitive to construct an example in which a “sacrificing” type of action will increase the gap in benefits, which is consistent with 3.1.

In a cooperative scenario ( ${SBA}_{b}$ ), agent i believes that there is some positive dependency between the benefit functions (Item 3.b), thus staying with the group will yield a higher benefit value than working alone. Therefore, when this holds the agent will need to adopt a belief that all members in the group (including itself) have the intention to remain group members (Item 3.b.i), and an aggressive behavior will not be possible (Proposition 3). On the other hand, in a competitive scenario ( ${SBA}_{a}$ ), the agents believe in a negative dependency between their benefits functions, which happens when there are competitive desires. In these situations, i will have the intention that the difference in benefits with each of the other members j will be maximized. The agent will acts according to axioms A.2–A.5, as aggressive act might exist to increase the benefits differences. It is easy to prove that altruistic actions are not valid in competitive groups (Proposition 2). □

6. Exploring the spectrum

In this section we will explore the spectrum by way of utility computation which will allow an agent to compute and find out which social group will be most beneficial for him, according to its beliefs about the desires’ relationships. This spectrum will allow him to reason about which group is expected to be most beneficial for himself, and adopt its intentions accordingly. We exemplify the various groups using the running example.

Maximum Individual Benefit: The maximum benefit that i may obtain while alone in the environment, ${Ben}_{i}^{ind} (I_{i}, B_{i})$ , can be defined as the values of the following set of desires: $\begin{array}{l} \forall φ \in goals (I_{i}), φ \in {D_{i}^{c o p} \cup D_{i}^{i n d} \cup D_{i}^{c o m}} & (1) \end{array}$

The agent’s total benefit as an individual when there is no other agent in the surrounding is composed of its own desires $D_{i}$ where $D_{i} = D_{i}^{cop} \cup D_{i}^{ind} \cup D_{i}^{com}$ and their relevant costs. Looking back at the example from page 7, we can compute the benefit values for the agents, had they were alone in the environment. Alice would have got ${Ben}_{A}^{ind} (I_{A}, B_{A}) = 0 + 4 + 7 = 11$ , Bob with ${Ben}_{B}^{ind} (I_{B}, B_{B}) = 2 + 4 = 6$ and Chen with ${Ben}_{C}^{ind} (I_{C}, B_{C}) = 3 + 2 = 5$ .

Maximum Benefit – Uncoordinated Social Group: An uncoordinated social group is one in which its members act alone according to their desires, but they are situated with other agents in the same environment. As such, their beliefs on the intentions of the other agents might influence their own intentions. We also assume that agents cannot be engaged in any sort of coordination activity. Given a Social Group $A$ , agents $i, j \in A$ , $i \neq j$ , the maximum total benefit of i in an Uncoordinated Social Group (USG), denoted as ${Ben}_{i}^{usg} (I_{i} \cup I_{j}, B_{i}$ ) is composed of: $\begin{array}{l} \forall φ \in goals (I_{i}), φ \in {D_{i}^{cop} \cup D_{i}^{ind} \cup D_{i}^{{com}^{'}}} \land \\ \forall α \in actions (I_{i}), α \in {C_{i}^{{cop}^{'}} \cup C_{i}^{ind} \cup C_{i}^{com}} & (2) \end{array}$

As seen before, when a rational agent is alone in its environment it selects the set of desires that maximizes its own benefit. Nevertheless, the same agent still follows the same set of desires, even as a part of an uncoordinated social group, as they are still the ones that optimize its benefit. However, as there are other agents in the environment, they can affect the agent in two ways: (1) positive impact – by achieving part of its desires from its set of cooperative desires ( $C_{i}^{{cop}^{'}} \subseteq C_{i}^{cop}$ is the subset that i performs by itself), thus decreasing i’s total cost to $c^{i} (C_{i}^{cop} ∖ C_{i}^{{cop}^{'}})$ . (2) negative impact – by achieving part of its competitive desires ( $D_{i}^{{com}^{'}} \subseteq D_{i}^{com}$ ), thus decreasing its total value from not receiving their benefits.

Proposition 4 (Benefits of uncoordinated social group).

If $(D_{i}^{c o m} = \emptyset) \lor (c^{i} (C_{i}^{cop} ∖ C_{i}^{{cop}^{'}}) ⩽ v^{i} (D_{i}^{com} ∖ D_{i}^{{com}^{'}}) - c^{i} (C_{i}^{{com}^{'}}))$ , then ${Ben}_{i}^{usg} ⩾ {Ben}_{i}^{ind}$ .

Proof.
In the first case, since the agent has no competitive desires, the total benefit from its desires can not increase due to other agents’ intentions, thus ${Ben}_{i}^{usg} = {Ben}_{i}^{ind}$ . The second case is when the positive impact (when other agents achieve i’s desires) is greater or equal to the negative impact, and ${Ben}_{i}^{usg} ⩾ {Ben}_{i}^{ind}$ .

The above proposition states that i is always better off being part of an uncoordinated social group, when it does not have competitive goals, or when it believes that the contribution of others to its cooperative desires will be greater than its loss from the competitive desires it will give. In the example we have a cooperative desire that is shared among all three agents, as such much effort is being spent without coordination. We also have a competitive desire between Alice and Chen, therefore without coordinating, the benefit will be computed as follows. ${Ben}_{A}^{usg} (I_{A}, B_{A}) = 0 + (0.5 * 4 - 0.5 * 8) + 7 = 5$ , Bob with ${Ben}_{B}^{usg} (I_{B}, B_{B}) = 2 + 4 = 6$ and Chen with ${Ben}_{C}^{usg} (I_{C}, B_{C}) = (0.5 * 3 - 0.5 * 5) + 2 = 1$ . □

Maximum Benefit – Coordinated Social Group: A coordinated social group is such that its members first coordinate their actions and intentions, in order to maximize their benefits. The agents may coordinate their cooperative desires as well as their competitive ones. A case of cooperative desires with coordination is equivalent to previous models (e.g., SharedPlans), where the group selects the best way to achieve the shared cooperative desire. In such cases, the agents may adopt a different set of coordinated cooperative actions, $C_{i}^{copN}$ than in cases where coordination is not possible. Similarly, the agent can negotiate its competitive desires with other members to optimize its benefit, and thus agree on a partial set of competitive desires $D_{i}^{{com}^{″}}$ (with the respective $C_{i}^{{com}^{″}}$ set). In such cases, i can be requested to give up some weak competitive desires that decrease the benefit of other agents, and accordingly it may exchange its set of individual desires in order to achieve only part of them ( $D_{i}^{{ind}^{″}} \subseteq D_{i}^{ind}$ with respective $C_{i}^{{ind}^{″}} \subseteq C_{i}^{ind}$ set). Given a social group $A$ , agents $i, j \in A, i \neq j$ , the maximum total benefit of i, as a member of a Coordinated Social Group (CSG), denoted as ${Ben}_{i}^{csg} (I_{i} \cup I_{j}, B_{i})$ is composed of: $\begin{array}{l} \forall φ \in goals (I_{i}), φ \in {D_{i}^{cop} \cup D_{i}^{{ind}^{″}} \cup D_{i}^{{com}^{″}}} \land \\ \forall α \in actions (I_{i}), α \in {C_{i}^{copN} \cup C_{i}^{{ind}^{″}} \cup C_{i}^{{com}^{″}}} & (3) \end{array}$
Proposition 5 (Benefits of coordination).

$\begin{array}{l} {Ben}_{i}^{csg} ⩾ {Ben}_{i}^{usg}, when \\ v^{i} ({D_{i}^{{com}^{″}}, D_{i}^{{ind}^{″}}}) - c^{i} ({C_{i}^{{com}^{″}}, C_{i}^{{ind}^{″}}, C_{i}^{copN}}) > \\ v^{i} ({D_{i}^{{com}^{'}}, D_{i}^{ind}}) - c^{i} ({C_{i}^{{com}^{'}}, C_{i}^{ind}, C_{i}^{{cop}^{'}}}) \end{array}$

Proof.
Trivial by simple arithmetic manipulations.

Proposition (5) justifies the need for strong negotiation skills in agents, as they may attain higher benefits from coordinating their actions. Going back to the example in this case (and the two that follow) we cannot know exactly which of the possible solutions will be agreed upon by the agents. It will also depend on the agents individual negotiation skills and strategic reasoning capabilities. If might be direct negotiations between the agents, or it might be that a central mechanism will be the reasoning side who simply dictates the agents which intentions to adopt, and which one to avoid. This will change according to the type of BDI agents in question. Nevertheless, we can assume that an optimal solution will not suddenly emerge due to computation limitation (we discuss this problem in depth in Section 7). One solution that might emerge is that Alice will drop its intention to be elected and will be the one who submits the proposal. As such, ${Ben}_{A}^{csg} (I_{A}, B_{A}) = 0 + 0 + 7 = 5$ , Bob with ${Ben}_{B}^{csg} (I_{B}, B_{B}) = 8 + 4 = 12$ and Chen with ${Ben}_{C}^{csg} (I_{C}, B_{C}) = 3 + 6 = 9$ . Two things to note about the coordinated solution: (1) all players are in not worse situation than before the coordination: $7 > 5$ , $9 > 6$ and $9 > 1$ . (2) The social welfare has doubled from $12$ to $28$ . □

Maximum Benefit – Cooperative Social Group: When i becomes a member in a Cooperative Social Group (CopSG), its total benefit will be composed of the coordinated social group components, together with the costs of the altruistic actions it contributed, $C_{i}^{alt}$ (which decreases its own benefit), and the altruistic actions that other agents performed to complete some of his desires, that will be denoted as $D_{j}^{alt}$ (increasing its benefit). Given a social group $A$ , agents $i, j \in A, i \neq j$ , the maximum total benefit of i as a Cooperative Social Group (CopSG) member, denoted as ${Ben}_{i}^{CopSG} (I_{i} \cup I_{j}, B_{i})$ is composed of: $\begin{array}{l} v^{i} (D_{i}^{cop} \cup D_{i}^{{ind}^{″}} \cup D_{i}^{{com}^{″}} ⋓_{\forall j} D_{j}^{alt}) - \\ c^{i} (C_{i}^{copN} \cup C_{i}^{{ind}^{″}} \cup C_{i}^{{com}^{″}} \cup C_{i}^{alt}) & (4) \end{array}$

As we noticed in the previous group type, when the agent is part of a coordinated group, Proposition 5 holds (otherwise a rational agent would leave the group). The next proposition states the basic condition in which the agent would prefer to “upgrade” the coordinated group to a cooperative one.
Proposition 6 (Benefits of cooperation).

if ${Ben}_{i}^{csg} ⩾ {Ben}_{i}^{usg}$ , then ${Ben}_{i}^{CopSG} ⩾ {Ben}_{i}^{csg}$ , when $v^{i} (D_{i}^{alt}) - c^{i} (C_{i}^{alt}) ⩾ 0$ .

Proof.
By aligning equations and canceling out $D_{i}^{{ind}^{″}}$ , $D_{i}^{cop}$ , $D_{i}^{{com}^{″}}$ terms with their respective actions.

The main condition in the above proposition is that the coordinated social group achieves a higher benefit for the agent, than the uncoordinated group. Otherwise, the question of whether to join a cooperative social group is not solely related to altruistic actions. □
Corollary 1.
If $({Ben}_{i}^{CopSG} ⩾ {Ben}_{i}^{csg}) \land ({Ben}_{j}^{CopSG} < {Ben}_{j}^{csg})$ , then $M L_{alt} = {Ben}_{i}^{CopSG} - {Ben}_{i}^{csg}$ .

In order for the social group to be cooperative, its group members must have a mutual belief that being part of the group will yield higher benefits for them (item 3.b). Therefore, corollary 1 states that when agent i wants to be in a cooperative social group with another agent j, but it believes that it is not beneficial for j to be in the group (as ${Ben}_{j}^{CopSG} < {Ben}_{j}^{csg}$ ), it will be willing to contribute altruistic desires with respect to j to “convince” it to be part of the group. However, this contribution will be bounded by $M L_{a l t}$ to prevent i from eventually losing.

Maximum Benefit – Competitive Social Group: In a similar way, when i is a member of a competitive social group (ComSG), its total benefit will comprise the sum of its own aggressive actions, together with the aggressive actions taken by j, and the benefit gained through cooperative desires that are performed by itself and other members. In addition, it will consider achieving only cooperative desires that will contribute more value to himself than to other agents ( $D_{i}^{{copN}^{'}}$ ). i’s total benefit also includes the set of its individual desires and the subset of competitive desires $D_{i}^{{comN}^{'}}$ . In this case, the main goal of i will be to maximize its benefit with respect to each j in its competitive group. Thus, $D_{i}^{{comN}^{'}}$ includes only the competitive desires that will cause a greater decrease in the benefit to others, thus some of the competitive desires in its original $D_{i}^{c o m}$ will not be part of $D_{i}^{c o m N^{'}}$ . Given a social group $A$ , agents $i, j \in A, i \neq j$ , the maximum total benefit of i as a Competitive Social Group (ComSG) member, denoted as ${Ben}_{i}^{ComSG} (I_{i} \cup I_{j}, B_{i})$ is composed of: $\begin{array}{l} v^{i} ({D_{i}^{{copN}^{'}} \cup D_{i}^{i n d} \cup D_{i}^{c o m N^{'}}} ∖ ⋓_{\forall j} D_{j}^{a g g}) - \\ ^{i} (C_{i}^{{copN}^{'}} \cup C_{i}^{i n d} \cup C_{i}^{c o m N^{'}} \cup C_{i}^{a g g}) & (5) \end{array}$

When examining the competitive social group, we can see that the situation worsens in terms of the agent’s total benefit as the benefit from the individual’s set of desires decreases, and new aggressive desires are added. Thus, we can conclude the following:
Corollary 2.
If $({Ben}_{i}^{ComSG} > {Ben}_{i}^{CopSG})$ then $\exists MD \in D_{i}^{com}$ s.t. $\begin{array}{rcl} d & = & \max ({ben}_{i} (I_{1} \cup \dots \cup I_{n}, B_{i}) \\ - (\forall j \in A, j \neq i) {ben}_{j} (I_{1} \cup \dots \cup I_{n}, B_{i})) . \end{array}$

In a competitive group, both $D_{i}^{c o m N^{'}}$ and $D_{i}^{{copN}^{'}}$ are subsets, thus receive lower or equal values. In addition, $⋓_{\forall j} D_{j}^{agg}$ are desires that further lower $A_{i}$ ’s benefit (by definition). As the total benefit is lower, only a “meta” set of desires ( $M D$ ) on the difference of the benefits values themselves can attain a higher total benefit.
7. To member or not to member?

Following the presentation of the $SBA$ model, it appears that a key ingredient is still missing in order to be able to practically use the model for architectural purposes. The missing ingredient appears in the $SBA$ ’s model in item 3.b under the proposition ${ben}_{i} (I_{i} \cup \dots \cup, I_{n}, B_{i}) ⩾ {ben}_{i} (I_{i}, B_{i})$ , that is a main query behind the question: to member or not to member (a cooperative group)? Given the vast amount of information that is needed the answer to this question relays on including the beliefs of the agent, his desires, his valuation and cost functions, and similar knowledge on the BDI structure of the other agents that member the group in question, it seems impractical to assume that an automated agent will be able to compute an answer. The following theorem shows that it is impractical to compute an optimal answer.

Theorem 1.
The individual agent’s task of computing whether to join a cooperative social group is NP-Complete.
Proof.
The reduction is to the Knapsack problem, where the set of n agents with individual payoff functions $p_{i}$ try to fill the knapsack with a subset of the k intentions, without any weight constraints.

Specifically, we can use the above problem as an instance of the 0-1 knapsack problem by trying to optimize the vector $v = {x_{1}, x_{2}, \dots, x_{k}}$ , where $x_{i} = 1$ if intention i is in the selected set, 0 otherwise. Instead of having a single $p_{i}$ vector, we have n such vectors and each agent’s original and individual set of intentions will be denoted as $v^{'} = {x_{1}, x_{2}, \dots, x_{k}}$ , where $x_{i} = 1$ if intention i is in the agent’s own individual set of intentions, 0 otherwise. The constraints are as follows:
$\sum_{i = 1}^{n} v p_{i} ⩾ \sum_{i = 1}^{n} v^{'} p_{i}$ (higher social welfare).

$(\forall i) v p_{i} ⩾ v^{'} p_{i} - ϵ$ (each individual is no worse than what he could have before minus some constant ϵ)

However, as the optimal solution is not accessible, oftentimes the agents will settle with some approximated solution that they can attain rather promptly, as a function of the available computational resources, and the requested precision. As human being in real life are able to get an approximated decision to the membership question using fast computed heuristic function [33], we might as well not aspire for an optimal solution, but settle with some approximated solution that bounded rational automated agents can get rather promptly, as a function of the available computational resources, and the requested precision. □

7.1. Membership as a CSP

In order to empirically evaluate the practicality of the membership query in real applications that the SBA model is directed to, we formulated the membership problem as a boolean constraints satisfaction problem: The set of agents, each with its own set of desires, for a total of N desires. Each of the N desires will be formulated as an individual node, that can get the value of 0 or 1 which signifies whether this desire will be fulfilled. Edges between nodes will model relationships between desires. The division to the cooperative, individualistic or competitive groups of desires, will be modeled as follows: (1) Cooperative desires – will be modeled with “or” constraint edges connecting the nodes. (2) Individual desires – are simply the nodes themselves. (3) Competitive desires – will be modeled with “exclusive or” constraint edge. A solution will be an assignment of values 1 or 0 to nodes s.t. the following constraints hold:

The local desires constraints are not violated.

Individual Benefit constraint: $(\forall i) v p_{i} ⩾ v^{'} p_{i} - ϵ$ .

Social Welfare constraint: $\sum_{i = 1}^{n} v p_{i} ⩾ \sum_{i = 1}^{n} v^{'} p_{i}$ .

Fig. 2.

Example graph representation.

Running example.

According to the previous example Alice has three desires ${d_{A}^{1}, d_{A}^{2}, d_{A}^{3}}$ , Bob’s desires are ${d_{B}^{1}, d_{B}^{2}}$ , and Chen’s desires are ${d_{C}^{1}, d_{C}^{2}}$ . The submit proposal desires are cooperative ${d_{A}^{1}, d_{B}^{1}, d_{C}^{2}}$ desire as all three are working jointly on the same proposal. The position appointment ${d_{A}^{2}, d_{C}^{1}}$ are competitive desires for Alice and Chen. The others are individual desires without any relationship among them. Let’s further assume the following costs/value functions to each of them: Alice costs $[5, 8, 3]$ , values $[5, 12, 10]$ , Bob costs $[6, 6]$ and values $[8, 10]$ and Chen costs $[5, 4]$ and values $[8, 6]$ . We can compute the Maximal Uncoordinated Benefit and get the following:6

⁶

Recall that we assume all parties have an equal chance of attaining competitive desires, and compute the expected benefit accordingly.

{Ben}_{A}^{ucg} = 5

{Ben}_{B}^{ucg} = 6

, and

{Ben}_{C}^{ucg} = 1

, and the total social welfare,

\sum_{i = 1}^{n} v p_{i} = 12

. A graph representation of the problem is depicted in Fig. 2. One solution for the above problem is

v^{'} = [d_{A}^{1}, \neg d_{A}^{2}, d_{A}^{3}, \neg d_{B}^{1}, d_{B}^{2}, d_{C}^{1}, \neg d_{C}^{2}]

, which results in respective individual benefits of: 7 for Alice, 12 for Bob, and 9 for Chen. The social welfare also increases to

\sum_{i = 1}^{n} v^{'} p_{i} = 28

7.2. Heuristic functions

The above solution is one of many existing solutions, and the small size of the problem (7 desires) constitutes a relatively easy problem to solve using brute-force search. However, for larger problems, bounded resources automated agents will need some heuristics to guide their search for a solution.7

⁷
Heuristics are often used in CSP type of problems to influence both the order of the evaluated variables and their values, to speed up the search.

As such, we suggest the following heuristic functions that are applicable to situations in which the agents commit their information to a third party (e.g. mediator or oracle) and get a solution that dictates which desires should be perused by the agents. This situation resembles a real life scenario in which the agents sit by the table and openly communicate and try to form a cooperative group, or situations in which a central principal, who have all the information, tries to coordinate their actions.

H1. Smallest number of desires

– This heuristic dictates searching first for a solution that satisfies the agent with the smallest number of desires. Obviously, less desires makes it easier to fully satisfies their goals.

H2. Largest number of competitive desires

– This heuristic tries to assign the agents with the largest number of competitive desires. The intuition here is that competitive desires provide more constraint as they always affect at least two agents.

H3. Smallest number of cooperative desires

– As cooperative desires are usually easier to assign (as at least two options are available), this function tries first to assign the agents that have the smallest amount of these.

H4. Maximize H1 + H3 − H2

– This function aggregates the rational behind the first three functions and dictates starting with the agent that maximizes the sum of $H 1$ and $H 3$ minus $H 2$ .

H5. Largest

{Ben}_{i}^{ucg}

value

– This function is very different from the previous four as it looks at the maximum benefit that an agent gets from being part of an uncoordinated social group. In other words, it will start by assigning the agent that would be in the best situation if such coordination effort would not take place at all.

In order to evaluate the usefulness of the suggested heuristics in guiding the search process, we used the ECLiPSe Constraint Logic Programming System. Our aim was to evaluate the different functions in 3 types of environments: cooperative, individualists, and competitive. The environments’ names describe them in terms of the proportions of the respective desires. Let us define $p c + p i + p m = 1$ to be a the probabilities distributions that characterizes an environment in terms of the probability of a single desire to be cooperative ( $p c$ ), individualistic ( $p i$ ) or competitive ( $p m$ ). An individualist environment is one in which, on average, the majority of the desires relations are individualistic. Specifically, we set the probabilities to be $p c = 0.15$ , $p m = 0.15$ and $p i = 0.7$ , in individualistic environment, and the cooperative/competitive environments were set with respective probabilities of $p c = 0.3$ or $p m = 0.3$ . We created 25 random instances to each of the environments using the following set of parameters: the number of agents was in the $[4, 6]$ range, the number of desires per agent was in the $[2, 7]$ range (therefore the problem sizes ranged from 8 to $42$ nodes). The costs/values numbers were in the $[1, 9]$ range. Each problem instance was solved using each of the suggested heuristics, and the solution time was recorded. Recall that we are interested in finding a solution, and not necessarily the optimal one, and there were instances in which a solution was not available. We used a 2.16 Ghz Intel Core 2 Due system with 2 GB of memory.

Fig. 3.

Simulations results.

The results depicted in Fig. 3, provide several insights on the behavior of the functions and the effect of the environment’s characteristics on the solution time. The y-axis is the time in minutes that it took before getting a solution to the problem. First, it is easy to see that competitive environments proved to be significantly more challenging than the other environments. One has to wait almost twice as long before getting the first solution. Second, it is easy to see that $H 4$ provides the best results in the first two environments and is equally effective to $H 2$ in the competitive environment. Finally, not surprisingly, a larger number of cooperative desires results in easier problem instances in terms of solution time. For sake of completeness, the average solution times when not using any heuristic function (and when solutions did exist) were: 104, 87.6 and 282.7 respectively. It is also interesting to observe that $H 5$ , which looked first at the agent who were better of without being coordinated, did not do as well as expected. It might be the case that ignoring the competition instead of trying to “manage” it is not the best course of action.

8. Relation with other BDI based models

The SharedPlans formalism, which we extend in this work, is a good exemplar of the golden age of BDI frameworks in the 90s. This formalism dictates all agents to have a joint utility function, thus describing a case of full cooperation. While joint group goal (or a “task group” as coined in the Psychology literature) is extremely important in multi-agent interactions, it obviously does not describe other forms of interactions. One example is a “treatment group” in which individuals are working on different goals, but can help or be helped by others. Such group describe well the interaction in a graduate students lab: each student is working on his own work, but mutual help still exist in various forms. Such form of interaction was describe using the SharedActivity notation in [18] and was exemplified in a touring museum domain. Another, more recent model was presented in [38]. The AdversarialActivity model presents a BDI framework for the competitive part of the spectrum.

It is of crucial importance to connect any newly presented formalism to older versions in order to conclude whether systems that implement any of the older frameworks, can be easily converted to include the new formalism. As such, we would like to show that the SBA model contains these three models. In other words, we show that the SBA can be regarded as a generalization of them without losing descriptive or behavioral power. We will show that through a series of containment relationships that show the following:

SharedPlans ⊆ SharedActivity ⊆ SocialBehaviorActivity

AdversarialActivity ⊆ SocialBehaviorActivity

To prove that a model is contained in another, we show that: (1) The definition of the first entails the definition of the second (i.e., an agent that holds mental states of the second model must also hold these mental states in the first); (2) All the axioms in the first model hold, and do not contradict the second model.

Theorem 2.
SharedActivity ⊆ SocialBehaviorActivity.
Proof.
This containment is quite obvious, as the definition of SA is equivalent to $S B A_{b}$ part of the SBA model, as clauses 1–4 in the SA model are identical to clauses 1, 3.b.i, 2, and 3.b in the SBA model, respectively. The helpful-behavior act and the cooperative act in the SA model are identical to A.1 and A.2 in the SBA model. Moreover, the union of A.3 and A.4 in the SBA model (individualism and competitive acts) are exactly the selfish act axiom from the SA model with their respective bounds in the cooperative case of the SBA model. □
Theorem 3.
SharedPlan ⊆ SharedActivity.
Proof sketch (complete proof in the Appendix).
To show definition entailment we suggest explicitly adding two axioms to the SP model that hold during rational behavior, but were implicit in the definition. The first axiom (N1) states that having a mutual belief by a group $A$ entails the ability of the agents to identify themselves as members of $A$ . The second axiom (N2) states that a group $A$ having some intention entails an intention by the group that the group will be maintained.

With those axioms in mind, it is easy to see that clause (0) of the partial SP model entails clause (1) of the ${SBA}_{b}$ model using axiom N1 above. In addition, axiom SP–A3 of the SP model together with N2 above entails clause (3.b) of the ${SBA}_{b}$ . Clause (2) of SBA requires a belief in a (partial) profile of other members;. Those parts are represented in the SP model by the meta-predicates CBA(…) (“can bring about”) and CBAG(…) (“can bring about group”). To prove that the ${SBA}_{b}$ model contains the axioms of the SP model, it is easy to see that an agent that acts according to the SP axiom is coherent with the SBA model. □
Theorem 4.
AdversarialActivity ⊆ SocialBehaviorActivity.
Proof.
The AdversarialActivity (AA) model reflects the interactions from a single agent point of view (agent $A_{a g}$ in the formulation) in order to clarify the model’s applicability. The following presentation gives the general version of the model, which quantifies over the point of view of the agent, and allows using any agent in A as the reference agent via substitution: $\begin{array}{l} A A (A, G_{A}^{}, T_{n}, w) \\ (1) (\forall A_{i} \in A) (\exists α \in C_{A_{i}}, T_{α}) \\ Int . Th (A_{i}, Achieve (G_{A_{i}}^{}, α), T_{n}, T_{α}, A A) \\ (2) (\forall A_{i}, A_{o} \in A) Bel (A_{i}, FulConf (G_{A_{i}}^{}, G_{A_{o}}^{}), T_{n}) \\ (3) (\forall A_{i}, A_{o} \in A) (\exists α_{o} \in C_{A_{o}}, T_{α}) \\ Bel (A_{i}, Int . Th (A_{o}, Achieve (G_{A_{o}}^{}, α_{o}), T_{n}, T_{α_{o}}, A A), T_{n}) \\ (4) (\forall A_{i, o} \in A) (\exists P_{A_{i}}^{A_{o}} \in P_{A_{i}}) \\ Bel (A_{i}, Profile (A_{o}, P_{A_{i}}^{A_{o}}), T_{n}) \end{array}$

Intuitively, AA models a zero-sum interaction while the SBA model is general and spans the whole individual-aggression range. The heart of the containment comes from clause 2 of the AA model. All A’s agents are in a $FulConf$ (full conflict) which (by definition) allows $Achieve (G_{A_{i}}^{}, α)$ to hold for only a single agent at a time. Using property 2 of the AA model (when $Achieve (G_{A_{i}}^{}, α)$ is true, agent $A_{i}$ has the maximum $eval$ value) and AA clause 1, we see that the intention that $Achieve (G_{A_{i}}^{}, α)$ holds implies the intention to attain higher utility than the others, which increases their difference in a zero-sum interaction as stated in clause 3.b.1 of the SBA model. In addition, clause 4 in the AA model describes the agent’s belief in the profile of the adversaries, which is exactly what is stated in clause 2 of the SBA model. □

9. Conclusions and future work

We presented the full social behavior spectrum as it has been modeled in social science research, and suggested the multiagent $Social Behavior Activity$ model as a formal theory that describes agents’ mental states and behavioral axioms across a range of behavioral possibilities. We explored the spectrum by providing a computational description of various social groups and the maximum achievable benefit for an agent. The findings of our social spectrum exploration show that usually it is worthwhile for an agent to be in some sort of cooperative or coordinated social group (depending on its negotiation skills), while in some cases it is also worthwhile taking altruistic actions in order to keep the social group intact. At the same time, being in a competitive social group is the worst option in most cases, unless there is a strict competition.

We then presented a way to tackle the “group membership” problem by remodeling the problem as a constraints satisfaction problem, and evaluated several heuristic functions to guide the search process on large problems. Regarding future research, we plan to implement the architecture in a simplified environment in which agents can be cooperative and competitive at different times. Our first step will be to implement an automated agent in the Du-Board game, and then continue to a more complex environment. This will allow us to empirically explore the benefits of using our architectural guidelines as a basis for the social agent’s design. Another limitation of our framework is the strong requirement for an explicit utility values and evaluation functions. Future iterations might tackle this by adding probabilistic values or fuzziness to the decision procedure.

Footnotes

Proof of containment relation

To show definition entailment we suggest explicitly adding two axioms to the SP model that hold during rational behavior, but were implicit in the definition. The first axiom states that having a mutual belief by a group $A$ entails the ability of the agents to identify themselves as members of $A$ . $\begin{array}{l} N 1 . MB (A, f, T_{f}) \Rightarrow \\ MB (A, (\forall A_{i} \in A) member (A_{i}, A), T_{f}) \end{array}$

The second axiom states that a group $A$ having some intention entails an intention by the group that the group will be maintained. $\begin{array}{l} N 2 . Int . Th (A, prop, T_{n}, T_{prop}, S) \Rightarrow \\ MB (A, (\forall A_{i} \in A) \\ Int . Th (A_{i}, member (A_{i}, A), T_{n}, T_{prop}, S), T_{n}) \end{array}$

With those axioms in mind, it is easy to see that clause (0) of the partial SP model $(MB (A, (\forall A_{j} \in A) Int . Th (A_{j}, D o (.. .), \dots), T_{p}))$ entails clause (1) of the ${SBA}_{b}$ model using axiom N1 above. In addition, axiom SP–A3 of the SP model: $\begin{array}{l} Bel (A, Int . Th (A, prop, T_{i}, T_{prop}, C_{prop}), T_{i}) \Rightarrow \\ Int . Th (A, prop, T_{i}, T_{prop}, C_{prop}) \end{array}$ together with N2 above entails clause (3.b) of the ${SBA}_{b}$ .

Clause (2) of SBA requires a belief in a (partial) profile of other members; the profile was defined as life histories, development patterns, needs, goals, and behavioral patterns. In the SP model, the agent’s intentions, capabilities and situations can be considered the profile. Those parts are represented in the SP model by the meta-predicates CBA(…) (“can bring about”) and CBAG(…) (“can bring about group”). Clause (1b1) of the partial SP definition entails FSP (“Full Shared Plan”) for selecting a recipe (using the Select_Rec_GR predicate), which in turn entails beliefs about the capabilities of the agent (i.e., about the CBA(…) and CBAG(…) meta-predicates).

Clause (3.b) of the ${SBA}_{b}$ states the necessity of mutual dependency. Thus, it remains to show that when the group’s members act according to the SP model, they have an MB that acting according to the SP generates better utility. However, the definition requires the agents to reconcile their intentions before adopting them, a process that causes the agents to perform the activities that generate the best possible utility [28].

To prove that the ${SBA}_{b}$ model contains the axioms of the SP model, we show that an agent that acts according to the SP axiom is coherent with the SBA model. It is important to note that since agents who act as a task group (modeled by the SP formalization) obtain part of their utility from the group, they have a stake in maximizing group utility. A greater group benefit means a greater share for each agent, which leads to greater individual utility. Therefore, only the Cooperation act axiom is relevant. There are 7 axioms in the SP model: axioms SP-A1 to SP-A5 state single-agent rational behavior and provide relations between intentions and belief in a single agent, and thus they must hold in the SA model. Moving on to SP-A6 and SP-A7, we encounter two axioms for the Int.Th(…) (“intention that”) predicate, which are clearly valid and do not conflict with any of the SA axioms. The final axiom SP-A7 is the one that provides a basis for helpful behavior in an SP context. Being derived from the SA Cooperation act axiom (SA-A2), it is easy to see that this axiom is coherent with the SA model.

References

[1]

C.E.

Alchourròn,

Gärdenfors and

Makinson, On the logic of theory change: Partial meet contraction and revision functions, Symbolic Logic 50 (1985), 510–530.

[2]

R.H.

Bordini and

Dastani, Multi-Agent Programming: Languages, Platforms and Applications,

Dix and

El Fallah Seghrouchni, eds, Multiagent Systems, Artificial Societies, and Simulated Organizations, Vol. 15, Springer, 2005.

[3]

R.H.

Bordini,

Wooldridge and

J.F.

Hübner, Programming Multi-Agent Systems in AgentSpeak Using Jason, Wiley Series in Agent Technology, John Wiley & Sons, 2007.

[4]

M.E.

Bratman, Intention, Plans and Practical Reason, Harvard University Press, Cambridge, MA, 1987.

[5]

M.E.

Bratman, Shared cooperative activity, The Philosophical Review 101(2) (1992), 327–341.

[6]

M.E.

Bratman,

D.J.

Israel and

M.E.

Pollack, Plans and resource-bounded practical reasoning, Computational Intelligence 4(4) (1988), 349–355.

[7]

Braubach,

Pokahr,

Lamersdorf and

Moldt, Goal representation for bdi agent systems, in: Second International Workshop on Programming Multiagent Systems: Languages and Tools,

R.H.

Bordini,

Dastani,

Dix and

El Fallah-Seghrouchni, eds, 2004, pp. 9–20, 7.

[8]

A.M.C.

Campos,

Dignum and

Dignum, From individuals to social and vice-versa, in: ESAW,

Artikis,

Picard and

Vercouter, eds, Lecture Notes in Computer Science, Vol. 5485, Springer, 2008, pp. 264–279.

[9]

V.J.

Derlega and

Grzelak, Cooperation and Helping Behavior Theories and Research, Academic Press, 1982.

10.

[10]

Dignum,

Koenig,

Kraus,

M.P.

Singh and

Wooldridge, in: 4th International Joint Conference on Autonomous Agents and Multiagent Systems AAMAS, July 25–29, 2005 Utrecht, The Netherlands. ACM, 2005, pp. 25–29.

11.

[11]

Fox and

Poole (eds), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI, Atlanta, Georgia, USA, July 11–15, 2010, AAAI Press, 2010.

12.

[12]

M.P.

Georgeff and

F.F.

Ingrand, Decision-making in an embedded reasoning system, in: Proceedings of the 11th International Joint Conference on Artificial Intelligence,

N.S.

Sridharan, ed., Morgan Kaufmann, August 1989, Detroit, MI, USA, 1989, pp. 972–978.

13.

[13]

Gilbert, Modelling collective belief, Synthese 73 (1987), 185–204.

14.

[14]

Grant,

Kraus,

Perlis, A logic based model of intention formation and action for multi-agent subcontracting, Artificial Intelligence 163(2) (2005), 163–201.

15.

[15]

Grant,

Kraus and

Wooldridge, Intentions in equilibrium, In Fox and Poole [11].

16.

[16]

D.W.

Griesinger and

J.W.

LivingstonJr., Towards a model of interpersonal motivation in experimental games, Behavioral Science 18 (1973), 173–188.

17.

[17]

B.J.

Grosz and

Kraus, Collaborative plans for complex group action, Artificial Intelligence 86(2) (1996), 269–357.

18.

[18]

Hadad,

G.A.

Kaminka,

Armon and

Kraus, Supporting collaborative activity, in: The National Conference on Artificial Intelligence (AAAI-2005), Pittsburgh, 2005, pp. 83–88.

19.

[19]

Hakli and

Negri, Reasoning about collectively accepted group beliefs, Philosophical Logic 40(4) (2011), 531–555.

20.

[20]

K.V.

Hindriks,

F.S.

De Boer,

Van der Hoek and

J.-J.C.

Meyer, Agent programming in 3apl, Autonomous Agents and Multi-Agent Systems 2(4) (1999), 357–401.

21.

[21]

L.M.

Hogg and

N.R.

Jennings, Socially intelligent reasoning for autonomous agents, IEEE Transactions on Systems, Man and Cybernetics — Part A 31(5) (2001), 381–399.

22.

[22]

H.J.

Levesque,

P.R.

Cohen and

J.H.T.

Nunes, On acting together, in: Proceedings of the 8th National Conference on Artificial Intelligence,

H.E.

Shrobe,

T.G.

Dietterich and

W.R.

Swartout, eds, Boston, Massachusetts, July 29 – August 3, 1990, AAAI Press / The MIT Press, 1990, pp. 94–99, 2 Volumes.

23.

[23]

Montagna,

Delzanno,

Martelli and

Mascardi, Bdiˆatl: An alternating-time BDI logic for multiagent systems, in: EUMAS 2005 - Proceedings of the Third European Workshop on Multi-Agent Systems,

M.P.

Gleizes,

G.A.

Kaminka,

Nowé,

Ossowski,

Tuyls and

Verbeeck, eds, Brussels, Belgium, December 7–8, 2005 Koninklijke Vlaamse Academie van Belie voor Wetenschappen en Kunsten, 2005, pp. 214–223.

24.

[24]

M.E.

Pollack, The uses of plans, Artificial Intelligence 57(1) (1992), 43–68.

25.

[25]

A.S.

Rao

AgentSpeak(L): BDI agents speak out in a logical computable language, in: Seventh European Workshop on Modelling Autonomous Agents in a Multi-Agent World,

van Hoe, ed., Eindhoven, The Netherlands, 1996.

26.

[26]

J.S.

Sichman and

Conte, Multi-agent dependence by dependence graphs, in: Proceedings of the First International Joint Conference on Autonomous Agents & Multiagent Systems, AAMAS, July 15–19, 2002, Bologna, Italy, ACM, 2002, pp. 483–490.

27.

[27]

Stone,

G.A.

Kaminka,

Kraus and

J.S.

Rosenschein, Ad hoc autonomous agent teams: Collaboration without pre-coordination, In Fox and Poole [11].

28.

[28]

Sullivan,

Glass,

Grosz and

Kraus, Intention reconciliation in the context of teamwork: An initial empirical investigation, in: Cooperative Information Agents III,

Klusch,

Shehory and

Weiss, eds, Lecture Notes in Computer Science, Vol. 1652, Springer, Berlin Heidelberg, 1999, pp. 149–162.

29.

[29]

Talman,

Hadad,

Gal and

Kraus, Adapting to agents’ personalities in negotiation, Dignum et al. [10], pp. 383–389.

30.

[30]

Tambe, Agent architectures for flexible, practical teamwork, in: Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI’97,

Kuipers and

B.L.

Webber, eds, July 27–31, 1997, Providence, Rhode Island, AAAI Press / The MIT Press, 1997, pp. 27–31.

31.

[31]

Toumela and

Miller, We-intentions, Philosophical Studies 53(3) (1988), 367–390.

32.

[32]

Tuomela, Group beliefs, Synthese 91(3) (1992), 285–318.

33.

[33]

Tversky and

Kahneman, Judgment Under Uncertainty: Heuristics and Biases, Cambridge University Press, 1982.

34.

[34]

van der Hoek,

Jamroga and

Wooldridge, A logic for strategic reasoning, Dignum et al. [10], pp. 157–164.

35.

[35]

Weber Vasconcelos,

M.J.

Kollingbaum and

T.J.

Norman, Normative conflict resolution in multi-agent systems, Autonomous Agents and Multi-Agent Systems 19(2) (2009), 124–152.

36.

[36]

Wooldridge and

N.R.

Jennings, The cooperative problem-solving process, Logic and Computation 9(4) (1999), 563–592.

37.

[37]

Zuckerman and

Hadad, Reasoning about groups: A cognitive model for the social behavior spectrum, in: IAT,

Boissier,

Bradshaw,

Cao,

Fischer and

M.-S.

Hacid, eds, IEEE Computer Society, 2011, pp. 125–132.

38.

[38]

Zuckerman,

Kraus and

J.S.

Rosenschein, The adversarial activity model for bounded rational agents, Autonomous Agents and Multi-Agent Systems 24(3) (2012), 374–409.

A BDI-based agent architecture for social competent agents

Abstract

Keywords

1. Introduction

1 This work extends the conference paper presented in [37].

3. The BDI language

3.1. Basic definitions

3.2. BDI structures

2 Another option is to assume v i ( { d i , ¬ d i } ) = − ∞ . The appropriate assumption is dependent on the use of the model.

5 As the profile definition is domain dependent, we refer the reader to [18] for an example of profile usage in an application.

Proposition 4 (Benefits of uncoordinated social group).

7 Heuristics are often used in CSP type of problems to influence both the order of the evaluated variables and their values, to speed up the search.

Footnotes

Proof of containment relation

References

¹
This work extends the conference paper presented in [37].

²
Another option is to assume $v^{i} ({d_{i}, \neg d_{i}}) = - \infty$ . The appropriate assumption is dependent on the use of the model.

⁵
As the profile definition is domain dependent, we refer the reader to [18] for an example of profile usage in an application.

⁷
Heuristics are often used in CSP type of problems to influence both the order of the evaluated variables and their values, to speed up the search.