Argumentation-based multi-agent distributed reasoning in dynamic and open environments

Abstract

This work presents an approach for distributed and contextualized reasoning in multi-agent systems, considering environments in which agents may have incomplete, uncertain and inconsistent knowledge. Knowledge is represented by defeasible logic with mapping rules, which model the capability of agents to acquire knowledge from other agents during reasoning. Based on such knowledge representation, an argumentation-based reasoning model that enables distributed building of reusable argument structures to support conclusions is proposed. Conflicts between arguments are resolved by an argument strength calculation that considers the trust among agents and the degree of similarity between knowledge of different agents, based on the intuition that greater similarity between knowledge defined by different agents implies in less uncertainty about the validity of the built argument. Contextualized reasoning is supported through sharing of relevant knowledge by an agent when issuing queries to other agents, which enable the cooperating agents to be aware of knowledge not known a priori but that is important to reach a reasonable conclusion given the context of the agent that issued the query. A distributed algorithm is presented and analytically and experimentally evaluated asserting its computational feasibility. Finally, our approach is compared to related work, highlighting the contributions presented, demonstrating its applicability in a broader range of scenarios, and presenting perspectives for future work.

1 Introduction

Distributed reasoning is a central aspect required by many applications proposed in the last decades, including mobile and ubiquitous systems, smart spaces and ambient intelligence systems [1,2,3]—and more recently the Internet of Things (IoT) [4, 5]—and the Semantic Web [6]. In these types of systems, distributed entities, called agents, are able to capture or receive information from their environment and from other agents, and are often able to derive new knowledge or making decisions based on the available knowledge.

We consider multi-agent systems (MAS) in environments in which agents may have imperfect knowledge, which may be incomplete, uncertain or inconsistent knowledge [7]. Incomplete knowledge concerns the possibility of an agent not having a complete knowledge about the environment and thus may require knowledge defined by other agents in order to reach conclusions. For example: assume a robot agent a that can feel the wind but is blind, and that has knowledge expressed by the following rule: “I may conclude that it is going to rain (conclusion) if it is windy (premise 1) and cloudy (premise 2)”. Agent a cannot reach the conclusion that it is going to rain by itself, because it cannot find the truth value of premise 2 by itself. But suppose there is another agent b. Then, a can ask b if it is cloudy. If b answers positively, then a is able to conclude that it is going to rain.

An agent can also have uncertain and/or conflicting knowledge due to imperfect sensing capabilities or badly intentioned or unreliable agents, which can lead to a global inconsistent state of knowledge. For example, an agent c has a damaged visual sensor. If a asks c whether it is cloudy or not, it is possible that c cannot inform correctly, thus returning an answer that contradicts the answer from agent b. Therefore, a has to decide which agent to believe when receiving both answers. Such decision could be based on a trust degree—or preference—an agent has to another.

Another concern in distributed settings, especially open, dynamic and knowledge-intensive ones, is seeking knowledge from arbitrary sources. For example, suppose d and e entered the environment very recently, so that a does not know what kind of knowledge they hold. Suppose again that a wants to know whether it is going to rain, but agents b and c, which previously used to answer about whether it is cloudy or not, have left the system. Then, the only way to know about it is asking the newcomer agents, d and e, even not knowing whether they hold such knowledge or not.

Furthermore, in many settings, agents have to reason based on heterogeneous knowledge with different degrees of certainty regarding the equivalence of pieces of information coming from different sources. Suppose d answers that there are clouds in the sky but e answers that it is overcast. Considering that the premise cloudy of a’s rule have a greater similarity to overcast (a sky covered with clouds) than with simply having clouds in the sky, a could give preference to e’s answer based on the similarity of the information. Another interesting and easy to understand example: suppose a drone robot is in front of an open window, but it does not know if he is able to pass through it only by its own knowledge. Than it asks other robots in the environment, one of which is a terrestrial robot that knows one can pass through an open door. Supposing the drone robot has learned beforehand that doors and windows are quite similar, it can possibly use the other robot’s knowledge to conclude that it can pass through that window.

Finally, a very important feature to have in distributed settings is enabling agents to share relevant information about their current situation, location, activity or object of interest when querying other agents. We call this kind of information focus. For example, suppose an agent f in a city distant from where a is. It looks at the sky and sees the clouds, and is also able to feel the wind, but it does not know if this means it is going to rain (it does not have the same rule as a). Thus, it asks other agents it knows. The only agent it is able to talk to at the moment is a, so it sends a message to a asking if it is going to rain. However, a, living in another city, is totally unaware of the weather conditions of f’s location. Then, f must send two rules without premises (i.e., facts) stating that there are clouds in the sky and it is windy in the location f is in. Therefore, when a receives the query, it is able to conclude that it is going to rain in f’s location, answering it to f. This is, in fact, a kind of contextual reasoning, as defined in classical work such as [8] and [9].

Structured argumentation is a prominent approach to formalize non-monotonic—or defeasible—reasoning by means of the construction and comparison of arguments for and against certain conclusions based on an underlying logic [10], enabling resolution of inconsistent knowledge between agents. Additionally, incomplete knowledge can be represented by means of mapping rules [1, 11], which enables agents to acquire knowledge from other agents in order to support a conclusion. However, there is no work based on argumentation that enables agents to acquire knowledge from arbitrary agents based on the similarity of different pieces of knowledge. Some related works, like the one presented by Bikakis et al. [1], assume that agents always know the exact source of a given piece of knowledge and that there is no possibility of knowledge being accepted based on its similarity. Furthermore, no work was found that proposes a solution for the problem of reasoning with focus knowledge not known a priori by the cooperating agents in a fully distributed setting. More details about related work are discussed in Sect. 6.

This paper presents a distributed reasoning approach, including the formal model and an operational algorithm that enable agents to build rule-based structured arguments for and against some conclusion in an open and dynamic environment setting. The distributed algorithm, its analytical and experimental evaluation, as well as further discussions compared to related works, have not been previously published. The formal model in an earlier stage of development was previously presented in [12], but this paper presents a revised version of it that defines some parts in a more straightforward and flexible way, in addition to useful definitions that enable a more natural connection with the presented algorithm. More specifically, the main differences regarding the formal model are the following: (i) the definitions of localization of focus rules and instantiation of il-literals; (ii) the definition of arguments has been simplified and now includes externally dependent arguments as external subarguments, as well as properties that are later used in other definitions; and (iii) the strength calculation formula now considers the concept of direct external subarguments and is based on a weighted average instead of summation. In summary, the previous work focused on the argumentation formalism and semantics, whereas the current work is focused on the operational and practical realization of distributed reasoning, by presenting a distributed algorithm, complexity issues, optimizations, experimental evaluation and further discussions.

In the model presented in this paper, agents may receive a query about the validity of a given piece of knowledge, but have incomplete knowledge, requiring them to issue new queries to other agents in order to answer the query. Each agent builds arguments based on its local available knowledge augmented with knowledge acquired from other agents, and the strengths of the arguments are calculated based on the trust among agents and the certainty regarding the similarity of the knowledge used to build them, enabling agents to make conclusions based on the comparison of such arguments. This way, reasoning is distributed among agents that concurrently build their arguments and then combine them to support conclusions. We also propose knowledge sharing in the context of a query, which enables agents to cooperate in reasoning about knowledge which is not known a priori by them, but is relevant for the agent that issued the query, achieving a kind of contextual reasoning. We therefore demonstrate that our approach enables knowledge representation and reasoning in scenarios that are not possible in related work.

Another relevant contribution regards the way the proposed algorithm builds self-explanatory tree-like argumentation-based structures, which enables not only their use in resolving conflicts and reaching conclusions, but also enables reusing them in other reasoning processes and possibly taking advantage of them for possible future features, such as explaining and learning. Precise representation of reasoning in the form of arguments also enables the use of a broader range of conflict resolution strategies, such as those that take advantage of the tree-like structure of arguments.

We also empirically demonstrate that our model can be viewed as a generalization of the proposal of Bikakis et al. [1] and that the conflict resolution strategy proposed in this work enables contextual reasoning that is more efficient than some of the strategies proposed in their approach [13].

Therefore, in summary, this paper presents four main contributions:

• Argumentation-based fully distributed reasoning model that takes advantage of knowledge acquired from arbitrary sources, relating pieces of knowledge based on their similarity, which enables its application in dynamic and open environments;

• Knowledge sharing in the scope of a query, enabling agents to be aware of relevant contextual knowledge from the point of view of the agent that issued the initial query.

• Strategy for resolving conflicts between arguments that takes into account the point of view of the agent that issued the query and the use of knowledge from indirectly queried agents.

• Operational self-explanatory argumentation-based structure building, which enables storing and reusing arguments for reasoning and possibly other future features such as explaining and learning.

Section 2 presents the formalization of our architecture, including agents and their knowledge representation formalism, as well as the formalization of query focuses and of the problem we are tackling. Section 3 presents the argumentation-based model of reasoning. Section 4 presents the distributed query answering algorithm that operationally realizes this reasoning model, as well as some properties of the algorithm and optimizations. Section 5 presents some experimental evaluations. Section 6 presents related work and discussion. Finally, conclusions and future work are presented.

2 Architecture and problem formalization

Before presenting the argumentation-based model and algorithm, it is necessary to present a concise multi-agent architecture—considering only the features that are relevant for this work—together with the rule-based knowledge representation (Sect. 2.1) and the problem formalization, including the proposed structures for queries and focus knowledge (Sect. 2.2).

2.1 Multi-agent architecture and rule-based knowledge representation

The following presents the definition of a MAS in our approach.

Definition 1

A distributed defeasible reasoning-based multi-agent system (DDRMAS) is defined as a tuple $\mathcal {S} = (Ags, F_Q)$, such that $Ags = \{a, b, c,\ldots \}$ is the set of agents at a given moment situated in the environment and $F_Q = \{\alpha , \beta , \gamma ,\ldots \}$ is a set of query focuses at a given moment.

$\triangle$

The set of query focuses $F_Q$ is necessary to enable the system to have a registry about the query focuses being considered at a given time. Query focuses will be detailed in Sect. 2.2.

The following presents the definition of an agent.

Definition 2

An agent $a \in Ags$ is defined as a tuple of the form $(KB_a, P_a, \Theta _a, st_a)$, such that:

• $KB_a$ is the agent’s knowledge base;

• $P_a: Ags \rightarrow [0,1]$ is a trust function, such that, given two agents b and c in Ags, if $P_a (b) > P_a (c)$, then a trusts b more than c. If $P_a (b) = P_a (c)$, then they are equally trustful.

• $\Theta _a: V^L \times V^L \rightarrow [0,1]$, such that $V^L$ is a vocabulary of literals, is a similarity function that maps pairs of literals to a number representing how similar they are;

• $st_a: [0,1]$ is a similarity threshold, used together with $\Theta _a$ to decide whether two literals are similar enough or not. $\triangle$

The trust function is used in the resolution of conflicts that may arise from the interaction between agents, as detailed in Sect. 3, and may result from various mechanisms, such as those related to Trust Theory [14] and dynamic preferences [15]. Therefore, the actual definition of such function is left open for the specific application developer.

The similarity function $\Theta _a$ and the similarity threshold $st_a$ are required to enable the matching of knowledge from different agents and will be formally defined in Definition 4. The process through which this similarity function is determined in each agent is also out of the scope of this work and may be defined by some learning process or expert knowledge.

As presented in Definition 3, knowledge bases are sets of rules composed of labeled literals (l-literals) p of the form $\langle D(p),L(p) \rangle$, where D(p) is called the definer of the l-literal p, and L(p) is a literal. The literal L(p) represents atomic information (x) or the negation of atomic information ($\lnot x$). For a literal x, its complementary literal is a literal corresponding to the strong negation of x, which can be denoted as $\sim x$. More precisely, $\sim x \equiv \lnot x$ and $\sim (\lnot x) \equiv x$. For any l-literal $p=\langle D(p),x \rangle$, the complementary l-literal is denoted as $\sim p=\langle D(\sim p),\sim x \rangle$.

The definer D(p) can be either a direct reference to an agent $a \in Ags$ (in which case the l-literal is called a concrete labeled literal, or cl-literal) or a symbol @ meaning that any known agent in Ags may define the l-literal (in which case the l-literal is called a schematic labeled literal, or sl-literal).

Definition 3

A knowledge base $KB_a$ is a set of rules of the form

$$\begin{aligned} r_{ai}: \langle a, x \rangle \hookleftarrow Body(r_{ai}) \end{aligned}$$

where $r_{ai}$ is the rule identifier, $a \in Ags$, $i \in \mathbb {N}^+$, $\langle a, x \rangle$ is a cl-literal which is the head of the rule, and Body(r) is a set of l-literals, also called body, representing a conjunction of l-literals. The symbol $\hookleftarrow$ is a placeholder for either $\leftarrow$, indicating a strict rule, or $\Leftarrow$, indicating a defeasible rule.

$\triangle$

A rule with empty body, i.e., when $|Body(r)| = 0$, is called a factual rule throughout this paper.

The set of l-literals in a KB is called its vocabulary, denoted $V^L = V^{CL} \cup V^{SL}$, where $V^{CL}$ is the set of cl-literals and $V^{SL}$ is the set of sl-literals, such that $V^{CL} \cap V^{SL} = \emptyset$. Such sets are also closed under negation, i.e., when $\langle D(p), x \rangle \in V^L$, then $\langle D(p), \sim x \rangle \in V^L$.

A strict rule is a rule $r_{ai}:\langle a,x \rangle \leftarrow Body(r_{ai})$ such that for every l-literal $\langle D(p),y \rangle \in Body(r_{ai})$, $D(p)=a$, i.e., all l-literals are local cl-literals, since they are defined locally by the very agent a. Similarly, a local defeasible rule is a rule $r_{ai}:\langle a,x \rangle \Leftarrow Body(r_{ai})$ such that for every l-literal $\langle D(p),y \rangle \in Body(r_{ai})$, $D(p)=a$. The difference is that strict rules cannot be defeated, i.e., they represent absolute truth in the system and are interpreted by classical logic.

An important assumption is that the subset of strict rules in a KB cannot have cycles nor inconsistencies. The maintenance of such consistency is left to a human specialist or by some belief revision/update mechanism, which is out of the scope of this work. On the other hand, defeasible rules have the interesting property of tolerating contradictory rules and chains of rules that lead to infinite cycles or self-defeating lines of reasoning. The way DDRMAS handle such cases is further explained in Sects. 3 and 4.

A mapping defeasible rule is a rule $r_{ai}:\langle a,x \rangle \Leftarrow Body(r_{ai})$ such that for every l-literal $\langle D(p),y \rangle \in Body(r_{ai})$, $D(p) \in Ags$ and there exists at least one l-literal $\langle D(p),y \rangle \in Body(r_{ai})$ s.t. $D(p) \in Ags {\setminus } \{a\}$, i.e., l-literals in the body may also be defined by other agents, in which case they are called foreign cl-literals. This is what enables agents to function with incomplete knowledge, requiring them to cooperate with other agents to reach conclusions. The intuition of a mapping rule denoted by $r_{ai}:\langle a,x \rangle \Leftarrow \langle b,y \rangle$ is the following: “If a knows that agent b concludes y, then a considers it a valid premise to conclude x if there is not any adequate contrary evidence”.

A schematic rule is a rule $r_{ai}:\langle a,x \rangle \Leftarrow Body(r_{ai})$ such that for every l-literal $\langle D(p),y \rangle \in Body(r), D(p) \in Ags \cup \{@\}$, and there exists at least one l-literal $\langle D(p),y \rangle \in Body(r)$ s.t. $D(p)=@$, i.e., l-literals may be defined by the own agent (local cl-literals), other specific agents (foreign cl-literals) or by an arbitrary agent (sl-literal). The intuition of a schematic rule denoted $r_{ai}: \langle a,x \rangle \Leftarrow \langle @,y \rangle$, is the following: “If a knows that some agent concludes a literal similar enough to y, then a considers it a valid premise to conclude x if there is not any adequate contrary evidence”.

An sl-literal can be bound (or instantiated) to any cl-literal that is similar enough to it. This enables to support a broad range of scenarios, especially those involving approximate reasoning. For example, suppose a scenario in which knowledge is represented by means of an OWL ontology [16]. In this case, a similarity function could be based on axioms that use the owl:sameAs property. Other examples could include lexical similarity, such as WordNet [17], which could be used in scenarios involving speech or text recognition, and other syntactic and semantic matchmaking processes, such as Larks [18].

Therefore, we define a similarity function between l-literals, as well as the concepts of similarity threshold, similar enough and similarity degree, which are all related.

Definition 4

A similarity function $\Theta _a: V^{L} \times V^{L} \rightarrow [0,1]$ is such that a greater similarity between p and q results in a greater $\Theta _a(p, q)$ value. Given a similarity threshold $st_a \in [0,1]$, two l-literals p and q are similar enough if $\Theta _a(p, q) \ge st_a$. Given two identical l-literals, the similarity between them will always be 1, i.e., $\forall p \in V^L, \Theta (p,p) = 1$.

$\triangle$

The similarity function can be used to define the concept of instantiated l-literal (il-literal), which includes the information of the similarity between two l-literals. The il-literals are particularly useful in the definition of arguments in Sect. 3, and are specially used to express that an sl-literal can be instantiated to a given cl-literal based on the similarity of their inner literal. Definition 5 defines an il-literal.

Definition 5

Given an l-literal $q = \langle D(q), x \rangle$, a cl-literal $q' = \langle b, x' \rangle$, a similarity function $\Theta _a$ and a similarity threshold $st_a$, where $a, b \in Ags$, such that $\Theta _a(q, q') \ge st$ (i.e., q and $q'$ are similar enough), the function $Inst_a(q, q')$ defines an instantiated l-literal (il-literal) as:

$$\begin{aligned} Inst_a(q, q') = \langle b, x', \Theta _a(q, q') \rangle \end{aligned}$$

$\triangle$

Example 1

This is inspired by an example given by Antonis Bikakis in his thesis [19]. Suppose there are five mushroom hunters collecting mushrooms in a natural park, each one in possession of a mobile device with a personal agent: Alice’s a, Barb’s b, Charles’s c, Dennis’ d and Eric’s e. The goal of mushroom hunting for every agent is to help their users to collect edible mushrooms. The mental states, including the knowledge bases, and the trust function of each of these agents are presented in Fig. 1.

Fig. 1

Agents’ definitions for Example 1

Alice’s (a) has some knowledge about some species, such as the death cap, which it knows is not edible (rule $r_{a1}$). Suppose also that a and b share the same knowledge that, if a mushroom is edible, then they can collect it, and if it is not edible, they cannot. They are also willing to take into account the opinion of any known agent about the edibleness of a mushroom, i.e., if any agent states that a mushroom is edible, then they are willing to accept it to be true if there is no adequate contrary evidence. Such knowledge is thus presented both in $KB_a$ (rules $r_{a2}$ and $r_{a3}$) and in $KB_b$ (rules $r_{b2}$ and $r_{b3}$). Barb’s (b) also believes that an object is not edible if it has a volva (rule $r_{b1}$).

Charles’ (c) believes that a mushroom is edible if it is an amanita velosa (rule $r_{c1}$), but it cannot describe a mushroom of this species. Therefore, it is willing to accept that the mushroom is an amanita velosa if any other agent states that a mushroom is similar enough to an amanita velosa.

Dennis’ (d) believes that an object is not edible if it is an amanita (rule $r_{d1}$). However, Dennis does not know anything about amanitas’ characteristics; thus, a sl-literal is also used in the body of the rule.

Finally, Eric’s (e) believes that a mushroom is a springtime amanita if it has some properties, such as having a volva and a pale brownish cap ($r_{e1}$). Actually, springtime amanita is the same as amanita velosa, but we assume the agents in the system are not so certain about it. Therefore, the agents consider a similarity degree of 0.8 between them; thus, the il-literal $\langle e, spa(M), 0.8 \rangle$ can be instantiated based on $\langle @, avl(M) \rangle$ and $\langle e, spa(M) \rangle$. Similarly, a springtime amanita is a type of amanita, and the agents consider a similarity degree of 0.4 between them. Therefore, the il-literal $\langle e, spa(M), 0.4 \rangle$ can be instantiated based on $\langle @, am(M) \rangle$ and $\langle e, spa(M) \rangle$. The similarity degree between every l-literal with lexically identical literals is defaulted to 1. Therefore, $\langle c, ed(M), 1 \rangle$ can be instantiated based on $\langle @, ed(M) \rangle$ and $\langle c, ed(M) \rangle$, and in a similar way $\langle d, \lnot ed(M), 1 \rangle$ can be instantiated based on $\langle @, \lnot ed(M) \rangle$ and $\langle d, \lnot ed(M) \rangle$.

It is important to note that this example also considers that each agent has total trust in itself; therefore $P_a(a) = P_b(b) = P_c(c) = P_d(d) = P_e(e) = 1$. There may be cases in which this does not occur (i.e., there may be agents that do not fully trust in themselves), but for the present example this will be the case for the sake of simplicity in the next steps.

2.2 Query, focus knowledge and problem formalization

An agent $a_0 \in A$ (which we call emitter agent) is able to issue queries to itself or to other agents. When an agent emits an initial query, which results in subsequent queries to other agents (which we call cooperating agents), it is necessary that every such agent becomes aware of specific knowledge related to the focus of the initial query. This is a key feature to enable effective contextual reasoning, because it nourishes the reasoning ability of the cooperating agents with the possibility of considering relevant—and possibly not known a priori by these agents—information in the context of the emitter agent, which may be related to its current object of interest, activity, situation or location. The following defines what a query focus is and introduces the concept of focus knowledge.

Definition 6

A query focus for an l-literal p is a tuple $\alpha = (p, a_0, KB_{\alpha }^{\mathcal {F}})$, such that $\alpha$ is the unique identifier of the query, a is the agent that created the query and $KB_{\alpha }^{\mathcal {F}}$ is the focus knowledge base of $\alpha$.

$\triangle$

Definition 7

A focus knowledge base $KB_{\alpha }^{\mathcal {F}}$ is a set of defeasible rules and focus rules of the form $r^{\mathcal {F}}_{\alpha i}: Head(r^\mathcal {F}_{\alpha i}) \Leftarrow Body(r^\mathcal {F}_{\alpha i})$, s.t. $\exists p \in \{Head(r^\mathcal {F}_{\alpha i})\} \cup Body(r^\mathcal {F}_{\alpha i})$ s.t. $p = \langle \mathcal {F}, x \rangle$, i.e., at least one of the l-literals of the rule is a focus labeled literal (fl-literal).

$\triangle$

The idea of fl-literals in the format $\langle \mathcal {F},x \rangle$ is that such knowledge must be temporarily interpreted by each cooperating agent as if it was a locally defined cl-literal, i.e., as if each agent defined it. For example, if an agent b receives a query with the following rule $r^\mathcal {F}_1: \langle \mathcal {F}, y_1 \rangle \Leftarrow$, it should interpret the rule as if it was $\langle b, y_1 \rangle \Leftarrow$. When the processing of the query is ended, the rule is discarded if it does not originally belong to the knowledge base of b. It is important to note that focus knowledge bases only have defeasible rules (which can also be mapping rules and schematic rules). This is because focus strict rules would require a mechanism to avoid introducing cycles and contradictions to the subset of strict rules of a KB.

It is important to note the difference between an sl-literal and an fl-literal. The first one is used to represent that an agent requires knowledge defined by an arbitrary external source, which has to be found by querying other agents. The former is used to represent knowledge that was shared with the agent in a way that the agent must consider it as a temporarily locally defined knowledge in order to answer a question in a better informed way.

Therefore, it is useful to define a localization function for focus rules, which requires defining the localization of fl-literals, as presented in definitions 8 and 9.

Definition 8

(Localization of fl-literals) Given an fl-literal $p=\langle \mathcal {F}, x \rangle$ and an agent a, the localization function of p in agent a is denoted $Loc(p, a) = \langle a, x \rangle$.

$\triangle$

Definition 9

(Localization of focus rules) Given a focus rule $r^\mathcal {F}: Head(r^\mathcal {F}) \Leftarrow Body(r^\mathcal {F})$, a function $Loc\_Rule$ that defines a localized rule for a given agent a based on $r^\mathcal {F}$ is defined as:

$$\begin{aligned} Loc\_Rule(r^{\mathcal {F}}, a) = r_a^\mathcal {F}: Loc(Head(r^\mathcal {F}), a) \Leftarrow \{ Loc(q, a) \ | \ q \in Body(r^\mathcal {F})\} \end{aligned}$$

$\triangle$

For convenience, it is useful to state some additional definitions. The local extended knowledge base of an agent a, denoted $KB_{a\alpha } = KB_a \cup KB_{a\alpha }^{\mathcal {F}}$, where $KB_{a\alpha }^{\mathcal {F}} = \{Loc\_Rule(r^\mathcal {F}, a) \ | \ r^\mathcal {F} \in KB_{\alpha }^{\mathcal {F}}\}$, represents the local knowledge of a single agent augmented with the focus knowledge of a query focus $\alpha$. Therefore, the global extended knowledge base given a current query focus $\alpha$ is defined as $KB_{\mathcal {S}\alpha } = \bigcup _{a}^{Ags} KB_{a\alpha }$. Similarly, $V^L_{a\alpha }$ and $V^L_{\mathcal {S}\alpha }$, respectively, denote the local extended vocabulary of an agent a and the global extended vocabulary.

Given these definitions, it is possible to formalize the problem we are solving: “Given an agent a with a query focus $\alpha = ( p, a_0, KB_\alpha ^\mathcal {F})$ for an l-literal p in a system $\mathcal {S}$, a wants to know whether l-literal p is a logical consequence of $KB_{\mathcal {S}\alpha }$ or not”. This is a subproblem of the following problem: “Given a system $\mathcal {S}$ considering a query focus $\alpha = ( p, a_0, KB_\alpha ^\mathcal {F})$, which l-literals in $KB_{\mathcal {S}\alpha }$ are its logical consequences?”. In our approach, as further explained in Sects. 3 and 4, it is possible that an l-literal p in $KB_{\mathcal {S}\alpha }$ may be a logical consequence ($KB_{\mathcal {S}\alpha } \models p$)—i.e., p has a true truth-value—or may not be a logical consequence ($KB_ {\mathcal {S}\alpha } \not \models p$)—i.e., p has a false truth-value. However, it may be not possible to assert that p is a logical consequence or not, which happens specially when there are fallacious arguments (like circular and self-defeating arguments). In these cases, an undec truth-value is assigned to p, as presented in Sect. 4.

It is important to note that the definition of a global extended KB concerns only the formalization of the model and the problem: in practice, it is not necessary for agents to operationally perform a union of their KBs, as it would result in a centralized solution. The operational solution presented in this paper (Sect. 4) consists of each agent collaborating to construct arguments based on its own local extended KB, and then sending such arguments to other agents in order to generate larger arguments that enable answering the query presented.

Example 1.1

Given the scenario previously presented, suppose that, at some moment, Alice finds a mushroom $m_1$ with the following characteristics: It has a volva and a pale brownish cap. Thus, a asks itself a query, such that:

$$\begin{aligned} {\begin{matrix} p=\langle a, col(m_1) \rangle \quad \alpha = (p, a, KB_{\alpha }^{\mathcal {F}}) \quad KB_{\alpha }^{\mathcal {F}} = \{ r_{\alpha 1}^{\mathcal {F}}, r_{\alpha 2}^{\mathcal {F}}\}\\ r_{\alpha 1}^{\mathcal {F}}: \langle \mathcal {F}, hv(m_1) \rangle \Leftarrow \qquad r_{\alpha 2}^{\mathcal {F}}: \langle \mathcal {F}, pbc(m_1) \rangle \Leftarrow \end{matrix}} \end{aligned}$$

(1)

where $\alpha$ is a new query focus whose focus knowledge base contains the rules that represent the mushroom’s characteristics.

When receiving its own query, a cannot reach a conclusion based only on its own knowledge. Thus, it has to query other agents. In each query to another agent, it includes the same query focus $\alpha$, in order to enable the agents to reason effectively about the mushroom perceived. Therefore, each agent applies the function $Loc\_Rule$ for every focus rule received. For example, when e receives the query, it temporarily defines internally the rules $\langle e, hv(m_1) \Leftarrow$ and $\langle e, pbc(m_1) \Leftarrow$. Given this focus, a will conclude that Alice can collect the mushroom $m_1$ because of the argument generated from b with the help of e (see $r_{c1}$ and $r_{e1}$), though b alone (see $r_{b1}$) and d with e (see $r_{d1}$ and $r_{e1}$) state that it is not edible. The reason for this decision is based on the strength calculation of the arguments generated by each agent and is further discussed in Sect. 3.

Example 1.2

Suppose that, simultaneously to the query focus $\alpha$ from Example 1.1, Barb finds a mushroom ($m_2$) which she knows is a death cap, and wants to know if she should collect it or not. Therefore, its agent emits to itself a query with the following query focus:

$$\begin{aligned} {\begin{matrix} p: \langle b, col(m_2) \rangle \quad \beta = (p, b, KB_{\beta }^{\mathcal {F}}) \quad KB_{\beta }^{\mathcal {F}} = \{r_{\beta 1}^{\mathcal {F}}\} \\ r_{\beta 1}^{\mathcal {F}}: \langle \mathcal {F}, dc(m_2) \rangle \Leftarrow \end{matrix}} \end{aligned}$$

(2)

In this case, a new focus rule, $\beta$, is originated from Barb. It is important to note that, in this case, the focus knowledge from query focus $\alpha$ is not included. As presented in Sect. 3, Barb will decide not to collect $m_2$, since Alice’s agent will answer the query indicating that $m_2$ is not edible.

3 Argumentation-based model

This section is divided into two subsections. Section 3.1 presents the argumentation-based structures built as part of the reasoning process. Section 3.2 presents how different arguments are compared in order to enable conflict resolution.

3.1 Argumentation-based structure

This section presents how arguments are derived from the local extended KB of each agent given a query focus. An argument $A \in Args_{\mathcal {S}\alpha }$, such that $Args_{\mathcal {S}\alpha }$ is the set of arguments that can be generated from a knowledge base $KB_{\mathcal {S}\alpha }$ is an n-ary tree derived from the chaining of rules of $KB_{\mathcal {S}\alpha }$.

Definition 10 formally presents an argument, as well as a set of functions that capture its elements and properties.

Definition 10

(Argument) Given a global extended knowledge base $KB_{\mathcal {S}\alpha }$, an argument $A \in Args_{\mathcal {S}\alpha }$ based on a rule $r: p \hookleftarrow Body(r) \in KB_{\mathcal {S}\alpha }$ such that $p = \langle a,x \rangle$, with $a \in Ags$, is a n-ary tree whose root node is labeled as p. Given $n = |Body (r)|$, if $n = 0$, then the tree has an only child node labeled $\top$, which is a leaf node. If $n > 0$, then the tree has n child nodes, each one corresponding to an l-literal $q = \langle D(q), y \rangle$ such that $q \in Body (r)$, and each of the child nodes is either labeled as:

• (I) q, if $D(q) = a$ (i.e., q is a local cl-literal) and there exists a rule $r'$ s.t. $Head(r') = q' = \langle a, y \rangle$, or

• (II) $Inst_a(q,q')$, if $D(q) \ne a$ (i.e., it is either a foreign cl-literal or an sl-literal) and there exists a rule $r'$ s.t. $Head(r') = q' = \langle D(q'), y' \rangle$, where $D(q') \in Ags$ (i.e., $q'$ is not an sl-literal) and $\Theta (q,q') > st$ (i.e., q and $q'$ are similar enough, or identical).

A node is additionally labeled with a “!” mark in case it introduces a fallacious subargument—either a cyclic or self-defeating subargument. Therefore, given a potential node labeled q, the node is labeled q! if there exists an ancestral node $q_{orig}$ s.t. $D(q) = D(q_{orig})$ and either: $\Theta (q, q_{orig}) > st$ (cyclic argument), or $\Theta (q, \ \sim q_{orig}) > st$ (self-defeating argument). A fallacious node is always a leaf node.

Each node not labeled with “!” is the root of a subargument of A, which is another argument defined recursively according to this definition.

Each tree edge is labeled with the identifier of the rule used to derive the argument, which can also be referred by Rule(A).

$\triangle$

Note that the definition avoids the existence of infinite trees or cyclic graphs by creating fallacious leaf nodes when a cycle or self-defeat is detected. A cycle occurs when a literal that is similar enough to a literal in an ancestral node in the tree is found. Cycles, if not detected and interrupted, would lead to a cyclic graph instead of a finite tree. Furthermore, marking a node as fallacious and making it a leaf node enables us to identify an argument that is fallacious, such that it could not be used to justify a conclusion. A self-defeating argument occurs when a literal that is similar enough to the complement of a literal in an ancestral node in the tree is found. Such is another kind of fallacious argument that could not be used to justify a conclusion, therefore it is convenient to also mark the node when it appears and make it a leaf node of the argument.

For convenience, some functions that enable retrieving components and features of an argument are presented as follows:

• Conc(A) refers to the conclusion of an argument A, which is the l-literal that labels its root node.

• Subs(A) refers to the set of proper subarguments of an argument A. A proper subargument of an argument A, denoted $A'$, is a proper subtree of the tree that represents the argument A. Proper subarguments are simply called subarguments throughout the text.

• $ExSubs(A) \subseteq Subs(A)$ refers to the set of external subarguments of an argument A, i.e., the subarguments of A whose conclusions are il-literals. Formally: $B \in ExSubs(A)$ iff $B \in Subs(A)$ and $Conc(B) = \langle b, x, \theta \rangle$, s.t. $b \in Ags$, $x \in V$ and $\theta \in [0,1]$.

• $DExSubs(A) \subseteq ExSubs(A)$ refers to the set of direct external subarguments of an argument A, which are the external subarguments of A that are not external subarguments of another external subargument of A. Formally, $B \in DExSubs(A)$ iff $B \in ExSubs(A)$ and s.t. $B \in ExSubs(C)$.

• Prem(A) refers to the set of premises of an argument A, which are all the nodes of an argument except its root and the nodes labeled with $\top$.

  If $Prem(A)=\emptyset$, then A is a base argument. The premises can be expressed as the conclusions of the proper subarguments of an argument, i.e., $Prem(A) = \{q \ | \ q=Conc(B), B \in Subs(A)\}$.

• $Fall(A) \in \{true,false\}$ indicates whether an argument is fallacious (true) or not (false). A not fallacious argument is called a valid argument. An argument is fallacious if any of its l-literals is a fallacious leaf node. Formally, $Fall(A) = true$ iff $\exists q! \in A$ s.t $q \in V^L_{\mathcal {S}\alpha }$.

• $Type(A) \in \{strict,defeasible\}$ indicates whether an argument is strict or defeasible. A strict argument is based on a strict rule, and each of its subarguments is also strict. A defeasible argument is either based on a defeasible rule or at least one of its subarguments is defeasible. Formally, $Type(A) = strict$ iff $Type(Rule(A)) = strict$ and $\forall B \in Subs(A)$, $Type(Rule(B)) = strict$; and $Type(A) = defeasible$ iff $Type(Rule(A)) = defeasible$ or $\exists B \in Subs(A)$ s.t. $Type(Rule(B)) = defeasible$.

An argument is conventionally named based on the agent that defines it, and the query focus is used in the name as a superscript, given the possibility of having multiple query focuses. For example, if the conclusion of an argument is defined by an agent a in a query focus $\alpha$, then the argument will be called $A_i^\alpha$, with $i \in \mathbb {N}^+$. If it is an argument defined by an agent b in a query focus $\beta$, it will be called $B_i^\beta$.

A graphical representation is given in the examples to follow (see Fig. 2). We opted to represent the edges as if they were directed to the conclusion of the argument, so as to remind the rules’ arrows. We also use doubled lines to represent edges from arguments based on defeasible rules in order to differentiate them from arguments based on strict rules. The inline representation follows a notation similar to tree parenthesis notation, but with a $\leftharpoonup$ arrow indicating the separation between conclusion and premises. Therefore, an argument is denoted $(\ldots )$. A base argument with conclusion p is $( p \leftharpoonup \top )$. An argument with conclusion p with two subarguments is $( p \leftharpoonup (\ldots ), (\ldots ))$.

Continuation of Example 1.1

Figure 2a shows the derived arguments that conclude $\langle a, col(m_1) \rangle$ and $\langle a, \lnot col(m_1) \rangle$. In addition to these, arguments based on the rules $r_{b2}$ e $r_{b3}$ can also be derived, but they are omitted since they are almost identical to arguments $A_1^\alpha$, $A_2^\alpha$ and $A_3^\alpha$. The labels of the edges were also omitted since it is easy to see which arguments are derived from which rules (see Fig. 1 and Eq. 1).

Fig. 2

Set of arguments of Example 1.1 (a) and 1.2 (b)

Some properties of the arguments are exemplified as follows: $Conc(A_1^\alpha ) = \langle a, col(m_1) \rangle$; $Conc(A_2^\alpha ) = Conc(A_3^\alpha ) = \langle a, \lnot col(m_1) \rangle$; $Conc(C_1^\alpha ) = \langle c, ed(m_1), 1 \rangle$; $Subs(A_1^\alpha ) = ExSubs(A_1^\alpha ) = \{ C_1^\alpha , E_1^{\alpha }, E_{1}^{\alpha '}, E_1^{\alpha ''} \}$; $DExSubs(A_1^\alpha ) = \{ C_1^\alpha \}$; $Prem(A_1^\alpha ) = \{ \langle c, ed(m_1), 1 \rangle , \langle e, spa(m_1), 0.8 \rangle , \langle e, hv(m_1) \rangle , \langle e, pbc(m_1) \rangle \}$; $Fall(A_1^\alpha ) = false$; $Type(A_1^\alpha ) = defeasible$.

Note that from schematic rule $r_{a2}$ the argument $A_{1}^{\alpha }$ is formed by instantiating the sl-literal $\langle @, ed (m_1) \rangle$ with the conclusion of $C_{1}^{\alpha }$. Similarly, $A_{2}^{\alpha }$ and $A_{3}^{\alpha }$ are formed from the rule $r_{a3}$, having its sl-literals instantiated with the conclusions of the subarguments $B_{1}^{\alpha }$ and $D_{1}^{\alpha }$, respectively. The arguments $B_{1}^{\alpha }$, $E_{1}^{\alpha }$ and $E_{2}^{\alpha }$ are simply originated from their local rules and the localized focus rules.

Argument $C_{1}^{\alpha }$ is based on $r_{c1}$ and formed by instantiating the sl-literal $\langle @, avl(m_1) \rangle$ with the head of $r_{e1}$, from which the subargument $E_{1}^{\alpha }$ is created.

It is interesting to note that without sharing and localizing the focus knowledge of the query focus $\alpha$, none of these arguments could be derived, since b and e would not be aware of the mushroom $m_1$ and its characteristics. This demonstrates how a kind of contextualized reasoning is allowed in DDRMAS.$\square$

Continuation of Example 1.2

From query focus $\beta$, the arguments derived are shown in Fig. 2b.

In this case, argument $B_{1}^{\beta }$ is based on $r_{b1}$ by instantiating the sl-literal $\langle @,\lnot ed(m1)\rangle$ with the conclusion of $A_{1}^{\beta }$, which is based on $r_{a1}$. Once more, this is only possible because $r^\mathcal {F}_{\beta 1}$ is shared with the query focus $\beta$, making agent a aware of the fact that $m_2$ is a death cap.

It is interesting to note that this set of arguments is different from the arguments derived with query focus $\alpha$ and that both the queries do not interfere with each other.$\square$

Example 2

This brief example presents a case where both cyclic and self-defeating arguments occur. Suppose the following global KB:

$$\begin{aligned} \begin{aligned} r_{a1}: \langle a, x \rangle \Leftarrow \langle @, y \rangle ; \quad r_{a2}: \langle a, \lnot x \rangle \Leftarrow \langle @, z \rangle \\ r_{b1}: \langle b, y' \rangle \Leftarrow \langle @, x \rangle ; \quad r_{c1}: \langle c, y'' \rangle \Leftarrow \langle @, \lnot x \rangle ; \quad r_{b2}: \langle b, zz \rangle \Leftarrow \end{aligned} \end{aligned}$$

(3)

Suppose also the following $\Theta _a$ function: $\Theta _a(\langle a, y \rangle , \langle b, y' \rangle ) = \Theta _a(\langle a, y \rangle , \langle c, y'' \rangle ) = 0.9$ and $\Theta _a(\langle a, z \rangle , \langle b, zz \rangle ) = 0.6$. All the agents have total trust in each other (i.e., $P_a(b) = P_a(c) = 1$). Suppose also a query focus $\gamma$ with $KB^\mathcal {F}_\gamma = \emptyset$. Then, the following arguments can be generated.

$$\begin{aligned} \begin{aligned} A^\gamma _1 = (\langle a, x \rangle \leftharpoonup (\langle b, y', 0.9 \rangle \leftharpoonup \langle a, x \rangle !)) \\ A^\gamma _2 = (\langle a, x \rangle \leftharpoonup (\langle c, y'', 0.9 \rangle \leftharpoonup \langle a, \lnot x \rangle !)) \\ A^\gamma _3 = (\langle a, \lnot x \rangle \leftharpoonup (\langle b, zz, 0.6 \rangle \leftharpoonup \top )) \end{aligned} \end{aligned}$$

(4)

Note that, in this case, $Fall(A^\gamma _1) = true$ and $Fall(A^\gamma _2) = true$, since both arguments are fallacious.

3.2 Comparison of arguments and conflict resolution

To resolve conflicts between arguments with contradictory conclusions, we use argumentation semantics. In this work, we use an adapted version of the argumentation semantic for Defeasible Logic (DL) proposed by [20] and extended by [1]. A defeat relation between arguments is proposed, from which the notions of acceptable, justified and rejected arguments are derived. This work extends the mentioned semantic specifically by defining an argument strength calculation which is used in the defeat relation. All other definitions remain true to the original ones and are only briefly presented in Sect. 4.

Definitions 11 and 12 present the attack and defeat relations:

Definition 11

(Attack) An argument $A_i$ attacks a (local or distributed) defeasible argument $A_j$, denoted $A_i \mathcal {A} A_j$, iff their conclusions are complementary. Formally, let $\mathcal {A} \subset Args \times Args$ be the relation. Then $A_i \mathcal {A} A_j$ iff $Conc(A_i)=p$ and $Conc(A_j)=\sim p$.

$\triangle$

Definition 12

(Defeat) An argument $A_i$ defeats an argument $A_j$, denoted $A_i \mathcal {D} A_j$, iff $A_i$ attacks $A_j$, and $A_j$ is not stronger than $A_i$. Formally, let $\mathcal {D} \subset Args \times Args$ be the relation and $StArg: Args \rightarrow [0,1]$ be an argument strength function. Then, $A_i \mathcal {D} A_j$ iff $A_i \mathcal {A} A_j$ and $StArg(A_i) \ge StArg(A_j)$.

$\triangle$

Definition 13 presents the definition of the strength of an il-literal, which is then used in the definition of strength of an argument (Definition 14).

Definition 13

(Strength of an il-literal) The strength of an il-literal $q_{inst} = (b, x, \theta )$ from the point of view of an agent a is $StIL (q_{inst}, a) = P_a(b) \times \theta$.

$\triangle$

Definition 14

(Argument Strength) $StArg: Args \rightarrow [0,1]$ is a function on an argument A to values between 0 and 1, where 0 is the smallest possible strength value and 1 is the greatest possible strength value, defined as follows:

$$\begin{aligned} {\begin{matrix} &{}StArg (A) \\ &{}\quad ={\left\{ \begin{array}{ll} \begin{aligned} P_{[D(Conc(A))]}(D(Conc(A))) \qquad \qquad \quad &{} \quad \text {if } DExSubs(A) = \emptyset \\ \frac{\displaystyle \sum _{A' \in DExSubs(A)} StIL(Conc(A'),D(Conc(A))) \times StArg(A')}{\displaystyle \vert DExSubs(A) \vert } &{} \quad \text {if } DExSubs(A) \ne \emptyset \end{aligned} \end{array}\right. } \end{matrix}} \end{aligned}$$

(5)

$\triangle$

The base case of the argument strength formula occurs when there are no external subarguments. In this case, the strength is simply given by the trust the agent that defines the conclusion of the argument (D(Conc(A))) has in itself. For example, if $D(Conc(A)) = a$, and $P_a(a) = 1$, then $StArg(A) = 1$.

The strength of an il-literal defines the basic element to calculate the strength of an argument. Intuitively, it can be said that the strengths of the il-literals represent the strengths of the bindings between the chained arguments coming from different agents, which are represented by external subarguments (see Definition 10 and Example 1.1). This strength considers not only the similarity degree ($\theta$) between the knowledge defined by each different agent, but also the trust an agent has in each other ($P_a(b)$).

Considering that, the strength of an argument consists of a weighted average, by means of summing the strengths of its direct external subarguments multiplied by the strength of the il-literals that bind the argument to each direct external subargument, all divided by the amount of direct external subarguments. This way, the strength of an argument is a function of the strengths of its direct external subarguments, which are arguments derived by other agents (see Definition 10). In other words, the similarity between knowledge from different agents and the trust between the agents is what defines the strength of an argument.

An interesting feature of this formula is that it “weakens” an argument when there is indirect trust between agents, which makes agents more skeptical to “third-party” arguments, i.e., arguments that are external subarguments, but not direct external subarguments. This is because the calculus recursively depends on the strength of the direct external subarguments of the argument A (DExSubs(A)), inducing the multiplication of the strengths of the il-literals that are the conclusions of these subarguments. Since the range of the il-literals and argument strength function is [0, 1], it then follows that the strength values corresponding to these indirect dependencies, when multiplied, result in reduced values when they are less than 1. This characteristic is formalized in Corolary 1 and demonstrated through the example that follows.

Corollary 1

(The strength of arguments based on indirect trust tends to be lower than the strength of arguments based on direct trust) Let a, b and c be three agents, such that $0< P_a(b) < 1$, $P_a(b) = P_a(c) = P_b(c)$ and $P_a(a) = P_b(b) = P_c(c) = 1$. Let $A_1 = (\langle a, x \rangle \leftharpoonup C_1)$, $C_1 = (\langle c, z, 1 \rangle \leftharpoonup \top )$, $A_2 = (\langle a, x \rangle \leftharpoonup B_1)$, $B_1 = (\langle b, y, 1 \rangle \leftharpoonup C_1)$ be four arguments. Notice that $A_1$ is based only on a direct trust between a and c, whereas $A_2$ is based on an indirect trust from a to b, then from b to c. The strength of $A_1$ will be greater than the strength of $A_2$, i.e., $StArg(A_1) > StArg(A_2)$.

Proof

$StArg(A_1) = StIL(\langle c, z, 1 \rangle , a) \times StArg(C_1) = P_a(c) \times 1 \times 1 = P_a(c)$ and $StArg(A_2) = StIL(\langle b, y, 1 \rangle , a) \times StArg(B_1) = P_a(b) \times 1 \times StIL(\langle c, z, 1 \rangle , b) \times StArg(C_1) = P_a(b) \times P_b(c) \times 1 \times 1 = P_a(b) \times P_b(c) = P_a(b)^2$. As $P_a(c) = P_a(b)$, then $StArg(A_1) = P_a(b)$. Finally, as $0< P_a(b) < 1$, then it follows that $P_a(b)^2 < P_a(b)$, thus $StArg(A_2) < StArg(A_1)$. $\square$

Continuation of Example 1.1

As illustrated in Fig. 2, there are some defeasible arguments with contradictory conclusions: $A_{1}^\alpha$ vs. $A_{2}^\alpha$ and $A_{3}^\alpha$. That means they attack each other: $A_{1}^\alpha$ attacks $A_{2}^\alpha$ and $A_{3}^\alpha$ and vice versa. One can therefore calculate the strengths of these arguments and conclude that $A_{1}^\alpha$ is stronger than $A_{2}^\alpha$ and $A_{3}^\alpha$, thus defeating both, while $A_{2}^\alpha$ and $A_{3}^\alpha$ do not defeat $A_{1}^\alpha$.

$$\begin{aligned} StArg(A_{1}^\alpha )= & {} \frac{StIL(\langle c, ed(m_1),1 \rangle ,a) \times StArg(C_{1}^\alpha )}{1}\\= & {} P_a(c) \times 1 \times \frac{StIL(\langle e, spa(m_1),0.8 \rangle ,c) \times StArg(E_{1}^\alpha )}{1}\\= & {} 0.6 \times P_c(e) \times 0.8 \times P_e(e) = 0.6 \times 1 \times 0.8 \times 1 = 0.48\\ StArg(A_{2}^\alpha )= & {} \frac{StIL(\langle b, \lnot ed(m_1), 1 \rangle ,a) \times StArg(B_{1}^\alpha )}{1}\\= & {} P_a(b) \times 1 \times P_b(b) = 0.4 \times 1 = 0.4\\ StArg(A_{3}^\alpha )= & {} \frac{StIL(\langle d, \lnot ed(m_1), 1 \rangle ,a) \times StArg(D_{1}^\alpha )}{1} \\= & {} P_a(d) \times 1 \times \frac{StIL(\langle e, spa(m_1), 0.4 \rangle ,d) \times StArg(E_{1}^\alpha )}{1} \\= & {} 0.2 \times P_d(e) \times 0.4 \times P_e(e) = 0.2 \times 1 \times 0.4 \times 1 = 0.08 \end{aligned}$$

It is interesting to note, in this case, that although $A_1^\alpha$ was calculated as stronger, it still had a relatively low strength value due to the indirect dependence of $A_1^\alpha$ to $E_1^{\alpha }$, as it was necessary to multiply the trust of Alice in Charles (0.6) to the similarity of 0.8 between springtime amanita ($spa(m_1)$) and amanita velosa ($avl(m_1)$. Charles’ perfect trust in Eric (1) kept the strength from going even lower. In contrast, in the case of $A_2^\alpha$, although Alice’s trust in Barb is less than 0.4, the argument has not much less strength than $A_1^\alpha$, since it only depends directly on a subargument defined by another agent.

Therefore, in this case, $A_1^{\alpha } \mathcal {D} A_2^{\alpha }$ and $A_1^{\alpha } \mathcal {D} A_3^{\alpha }$, but and .$\square$

4 Distributed query answering algorithm

This section presents a distributed algorithm for evaluating queries between agents based on the proposed knowledge representation and argumentation-based model.

This algorithm produces results based on the ambiguity-blocking semantics for defeasible logic (DL) proposed by [20] and extended by [1]. The reader is referred to these papers in order to have a deeper understanding of such semantics, but it is important to briefly define the concepts of “justified”, “supported”, “undercut” and “rejected” arguments. The set of justified arguments is incrementally and monotonically built, starting with strict arguments, then arguments that are not defeated or are defended by the already justified arguments, and so on until no further arguments can be justified. An argument A is justified if it is strict, or if: (1) it is not fallacious, (2) it is supported by a set of already justified arguments J, and (3) every argument that defeats A is undercut by the set of justified arguments J (i.e., A is defended by J). An argument A is supported by a set of arguments J if every subargument of A is in J. An argument A is undercut by a set of arguments J if there is an argument B which is supported by J that defeats a subargument of A. Finally, an argument A is rejected if it is not strict and either a subargument of A is already rejected, or A is defeated by an argument supported by the set of justified arguments.

The specific reasoning problem that is solved by the algorithm is stated as follows: Given a DDRMAS $\mathcal {S}$ and a query focus $\alpha$ for an l-literal p sent to agent a, compute the truth value of p based on whether justified arguments exist for some l-literal similar enough to p or not. The algorithm produces an answer with three components: (i) a truth-value $tv_p \in \{true, false, undec\}$ for the l-literal p queried; (ii) a set of arguments that conclude l-literals similar enough to p; and (iii) a set of arguments that conclude l-literals similar enough to $\sim p$. This way, the agent that receives an answer also receives the arguments that support and refute p, so that it can perform conflict resolution from its own point of view.

The truth-value true implies that there exists an argument for a l-literal $p'$ similar enough to p which is justified in $KB_{\mathcal {S}\alpha }$ (the global extended knowledge from system $\mathcal {S}$ with focus knowledge from the query $\alpha$), false implies that all arguments for every $p'$ similar enough to p are rejected in $KB_{\mathcal {S}\alpha }$, and undec implies that there are not any argument for any $p'$ similar enough to p that is justified, but there are arguments for some $p'$ similar enough to p that are neither justified nor rejected in $KB_{\mathcal {S}\alpha }$. This last case occurs when there are fallacious arguments involved.

The arguments in the algorithm have the same structure as the arguments presented in Sect. 3, having, in addition, three Boolean labels: J, indicating that the argument has already been identified as justified; R, indicating that the argument has already been identified as rejected; and SuppJ, indicating that the argument is supported by a set of justified arguments. These three properties play a fundamental role in comparing the sets of arguments for and against p, in order to correctly implement the DL semantics [1, 20]. In fact, such labels (or flags) enable the implementation of the DL semantics in a labeling-based fashion, similar to [21], which proposes labeling semantics for abstract argumentation frameworks. In summary, instead of incrementally building the sets of justified and rejected arguments, this labeling-based approach traverses an argument in a post-order fashion labeling each argument as SuppJ, J or R. When all arguments are labeled, we gather the set of J-labeled arguments as the justified arguments, and the set of R-labeled arguments as the set of rejected arguments.

It is also assumed that each argument has a numeric property St, referring to the strength of the argument, whose default value is 0, but that is modified throughout the execution of the algorithm by calculating the strength of the argument using the StArg function.

The presentation of the algorithm will be divided into two sections. Section 4.1 presents the main procedure Query, and Sect. 4.2 presents the auxiliary function $Find\_Def\_Args$, which corresponds to a good part of the algorithm as a whole, and therefore is presented separately in order to facilitate reading and understanding. Finally, Sect. 4.3 presents some analytical evaluation of the algorithm as well an approach to optimize it.

4.1 Procedure Query

Each agent implements the same algorithm, which also defines a basic messaging protocol that allows them to collaborate effectively. The main procedure, Query, presented in Algorithm 1 in Appendix A, is called when an agent a receives a message of the form $Query(p, \alpha , hist_p)$ from an agent $a_0$. This can be considered an “Ask” speech act emitted by $a_0$, where: p is the l-literal queried; $\alpha = (p,a',KB^\mathcal {F}_\alpha )$ is the query focus; and $hist_p$ is a list of l-literals already evaluated during the query processing, which allows to avoid infinite loops by detecting the occurrence of fallacious arguments. The query result is returned to $a_0$ as a message in the format $Ans(p, \alpha , tv_p, Args_p, Args_{\sim p})$, where: $tv_p$ is the truth value of p; $Args_p$ is a set of arguments that support the conclusion p; and $Args_{\sim p}$ is a set of arguments that support the conclusion $\sim p$.

The algorithm can be divided into 6 (six) main steps:

• 1. Extended local KB creation given query focus $\alpha$ (line 3)

• 2. Search for l-literals $p'$ similar to p in the extended local KB (lines 4 and 5)

• 3. Checking and handling of cycles and self-destructive rule chains (lines 6 and 7)

• 4. Local strict answer search for each similar l-literal $q'$ (lines 8 to 15)

• 5. Local or distributed defeasible answer search for each similar l-literal $q'$ (lines 16 to 22)

• 6. Comparison between arguments and calculation of the truth-value based on the strengths of defeasible sets of arguments for and against the conclusion of each similar l-literal $q'$ (lines 23 to 26)

Figure 3 presents an activity diagram that illustrates the execution of these steps.

Fig. 3

Activity diagram for the Query algorithm

Step 1 defines the local extended KB, $KB_{a\alpha }$, as defined in Sect. 2. This enables the agent to consider not only its own knowledge, but also an augmented knowledge considering the focus knowledge received in the query.

Step 2 iterates over $KB_{a\alpha }$ searching for any rule with head $p'$ such that p and $p'$ are similar enough. This enables to consider literals by similarity, as described earlier.

Step 3 verifies whether $p'$ or $\sim p'$ are not in $hist_p$. If any of these is the case, then a cycle or self-defeat is detected. The algorithm then creates a fallacious argument consisting of a unique leaf node labeled $p'!$.

Steps 4 to 6 are executed iteratively or in parallel, for each $p'$. It is interesting that it can be made in parallel because it mainly consists in querying other agents asynchronously.

Step 4 tries to build local strict arguments based on strict rules of the agent. This step works as a depth first algorithm traversing the strict rules of the agent trying to activate each rule in the chain of rules, as a classic logic proof finder. A pseudocode is presented in Algorithm 2 in Appendix A.

Step 5 tries to build defeasible arguments, both for $p'$ and $\sim p'$. This is done by means of a helper function called $Find\_Def\_Args$, which is responsible for sending queries to other agents for each literal in the body of the rules with head $p'$. It is also responsible for incrementally building distributed arguments (arguments that have external subarguments). Section 4.2 details it a bit further. Furthermore, in step 5 it is verified whether local strict answers have been found (lines 19 to 22). If this is the case, every opposite argument is marked as rejected, since a strict argument defeats every opposite argument and is not defeated by them.

Step 6 takes all the defeasible arguments generated for and against $p'$ and compares them. Its pseudocode is presented in the $Compare\_Def\_ Args$ function in Algorithm 3, Appendix A. This step implements most part of the DL semantics by checking the Boolean flag SuppJ and R and setting J and R accordingly, and, based on these flags, decide the truth-value $tv_{p'}$. At this point, i.e., after $Find\_Def\_Args$ was called, SuppJ—and also R for the case in which some subargument is marked as rejected, which means the argument has been undercut—have already been previously set in the $Find\_Def\_Args$ (step 4), when arguments are built and every subargument are checked whether they are justified or rejected, as explained in Sect. 4.2, step 4.

A brief explanation of step 6 is given as follows. The variable $tv_{p'}$ is set as undec as default. Then, a set of not undercut (already rejected by the existence of rejected subarguments) arguments for both $p'$ and $\sim p'$ is defined (line 3). This is done because undercut arguments cannot be used to prevent an argument from being justified: even if an undercut argument defeats another argument, this last one has already been defended by the argument that defeated the first one. Next, for each not undercut argument A:

• (i) if A is supported by justified arguments and there does not exist any not undercut argument B that defeats A, then A is marked as justified (J) and the truth value is set to true, since a single justified argument for $p'$ is sufficient for accepting such conclusion.

• (ii) if there exists an opposite argument $B \in Args_{\sim p'}$ that is supported by justified arguments and defeats A, then A is marked as rejected (R).

Finally, if none of the arguments in $Args_{p'}$ have been found as justified and all of them have been rejected (or $Args_{p'}$ is empty, which simply means there is no argument for $p'$), then $tv_{p'}$ is set to false. However, it is possible that there are arguments that are not justified nor rejected, in which case $tv_{p'}$ remains undec (this happens specifically when the argument is fallacious and is not defeated by an argument supported by the justified arguments).

Continuation of Example 1.1

Below is a brief simulation of the processing of Query for $\langle a,col(m_1) \rangle$.

• Agent a emits the query $Query(p=\langle a,col(m_1) \rangle ,\alpha =(p,a,\{r^\mathcal {F}_{\alpha 1},r^\mathcal {F}_{\alpha 2}\}),hist_p=[])$ to a

  • Expected result: $Ans(\langle a, col(m_1) \rangle , \alpha , true, \{A_1^\alpha \}, \{A_2^\alpha , A_3^\alpha \})$

  • Explanation:

    • Step 1: $KB_{a\alpha }$ is created by localizing the focus rules $r^\mathcal {F}_{\alpha 1}$ and $r^\mathcal {F}_{\alpha 2}$, therefore including the rules $r^\mathcal {F}_{\alpha a1}: \langle a, hv(m_1) \rangle \Leftarrow$ and $r^\mathcal {F}_{\alpha a2}: \langle a, pbc(m_1) \rangle \Leftarrow$.

    • Step 2: Only one similar l-literals is found: $p' = \langle a,col(m_1) \rangle$.

    • Step 3: Neither $p'$ nor $\sim p'$ is in $hist_p$.

    • Step 4: No local strict argument can be built for $p'$, since there are no strict rules with head $p'$.

    • Step 5:

      • $Find\_Def\_Args(p',\ldots )$ returns $Args_{p'} = \{A_1^\alpha \}$. $A_1^\alpha$ and all of its subarguments are marked as SuppJ (supported by justified arguments).

      • $Find\_Def\_Args(\sim p',\ldots )$ returns $Args_{\sim p'} = \{A_2^\alpha , A_3^\alpha \}$. All arguments are marked as SuppJ. The process for this call to $Find\_Def\_Args$ is detailed in Sect. 4.2.

    • Step 6: As $A_1^\alpha$ is marked as SuppJ and no other argument defeats it (i.e., and ), then $A_1^\alpha$ is marked as J (justified), and, as $A_1^\alpha \mathcal {D} A_2^\alpha$ and $A_1^\alpha \mathcal {D} A_3^\alpha$, then both $A_2^\alpha$ and $A_3^\alpha$ are marked as R (rejected). Also $tv_p = true$ is returned (see Algorithm 3 in Appendix A for details).

$\square$

Continuation of Example 2

Below is a brief simulation of the processing of Query for $\langle a,x \rangle$.

• Agent a emits the query $Query(p=\langle a,x \rangle ,\gamma =(p,a,\{\}),hist_p=[])$ to a

  • Expected result: $Ans(\langle a, x \rangle , \gamma , undec, \{A_1^\gamma , A_2^\gamma \}, \{A_3^\gamma \})$

  • Explanation:

    • Step 1: $KB_{a\gamma }$ is created, but there are no focus rules, thus there are no changes in the agent’s KB.

    • Step 2: Only one similar l-literals is found: $p' = \langle a, x \rangle$.

    • Step 3: Neither $p'$ nor $\sim p'$ is in $hist_p$.

    • Step 4: No local strict argument can be built for $p'$, since there are no strict rules with head $p'$.

    • Step 5:

      • $Find\_Def\_Args(p',\ldots )$ returns $Args_{p'} = \{A_1^\gamma , A_2^\gamma \}$. None of the arguments have been marked as SuppJ, as they are fallacious (their fallacious leaf arguments are created at line 6 of Query, Algorithm 1, Appendix A). They are also not marked as R (rejected), because their subarguments are not defeated. The process for this call to $Find\_Def\_Args$ is detailed in Sect. 4.2.

      • $Find\_Def\_Args(\sim p',\ldots )$ returns $Args_{\sim p'} = \{A_3^\gamma \}$. All arguments are marked as SuppJ.

    • Step 6: Both $A_1^\gamma$ and $A_2^\gamma$ are not defeated by $A_3^\gamma$ (i.e., $A_1^\gamma$ and $A_2^\gamma$) because their strength is greater (note the similarity degrees of their il-literals, and remember that the trust is 1 for every pair of agents in this example). However, both are not marked as SuppJ, since they are fallacious, thus they cannot be marked as J (justified). They are also not marked as R, since they are not defeated. Therefore, $tv_p = undec$ (undecided) (see Algorithms 1 and 3 in Appendix A for details).

$\square$

4.2 Function $Find\_Def\_Args$

The function $Find\_Def\_Args$ is presented in Algorithm 4 in Appendix A. It receives a literal $p'$, the extended knowledge base $KB_{a\alpha }$ created in the Query procedure, the query context $\alpha$ and the history $hist_p$.

The procedure is split in 4 (four) steps:

• 1. Update $hist_p$ by adding $p'$ to it (line 3)

• 2. Send queries for every l-literal q that exists in the body of each r with head $p'$ (lines 4 to 10)

• 3. Filter the results received for each q for the queries and add them as possible subarguments for an argument for $p'$ (lines 11 to 16)

• 4. Build argument for $p'$ based on the possible subarguments, for each different rule for $p'$ (lines 17 to 28)

Figure 4 presents an activity diagram that illustrates these steps.

Fig. 4

Activity diagram for the $Find\_Def\_Args$ algorithm

Step 1 is self-explanatory.

Step 2 consists of iterating over each rule r with head $p'$ in $KB_{a\alpha }$, and for each rule r, iterate over each l-literal q in the body of r in order to send new queries, aiming to try to build argument for each q. This iteration can also be done in parallel, which is interesting since the query messages are sent asynchronously. In this step, when an sl-literal is found, the query is sent in a broadcast manner to every agent in the system. Otherwise, if a cl-literal is found, the query is sent only to the agent D(q). The code for querying agents is illustrated in Algorithm 5, Appendix A.

Step 3 is executed when answers are received. If no arguments are found for q, the algorithm goes to the next rule and discards all the results for the current rule (lines 11 and 12). This is because an argument for $p'$ based on a rule r cannot be built if one of its body members cannot be activated. Next, the arguments received are filtered in order to avoid an “explosion” of subarguments. This is done by eliminating fallacious arguments if valid ones were found (lines 13 and 14) and then getting the argument that has the greatest strength multiplied by the strength of the il-literal in its conclusion from the point of view of the current agent (a)—which is part of the argument strength calculation (line 15). This way, only the subargument that will contribute with the greatest strength possible is considered. This is reasonable when considering that the goal is to find the best arguments to support a conclusion, thereby avoiding the generation of a lot of irrelevant arguments that could impose unnecessary overhead over the MAS. This can also be viewed as a kind of pruning of irrelevant arguments: fallacious subarguments are irrelevant when valid ones exist, and multiple subarguments for the same conclusion can be pruned by leaving only the one that provides the most benefit.

Step 4 is executed after the answers for each q in the body of a given rule r is received. It takes the possible subarguments and builds arguments for $p'$ based on them. It is actually in this step that an sl-literal is instantiated to an il-literal (see lines 20 and 21). Also, for each argument $A_{p'}$ built, if every subargument is marked as justified (J), then $A_{p'}$ is marked as supported by justified arguments (SuppJ, lines 14 and 15). On the other hand, if there exists any subargument which is marked as rejected (R), then $A_{p'}$ is also marked as rejected (lines 16 and 17). This also means $A_{p'}$ is considered as undercut, i.e., it cannot be used to prevent another argument from being justified, even if it defeats the other argument, as explained in Sect. 4.1, step 6. Finally, is in this step that the strength of the argument is calculated by means of StArg (Sect. 3), in line 18.

Continuation of Example 1.1

Below is a brief simulation of the processing of the call $Find\_Def\_Args(p' = \langle a,\lnot col(m_1) \rangle , KB_{a\alpha },\alpha ,hist_p=[])$

• Expected result: $Args_{p'} = \{A_2^\alpha , A_3^\alpha \}$

• Explanation:

  • Step 1: A new list $hist_{p'}$ is created by adding $p'$ to $hist_p$. Thus $hist_{p'} = [p']$.

  • Step 2: A single rule $r_{a3}$ (see Fig. 1) is found with head $p'$. This rule has a single body member $q = \langle @, \lnot ed(m_1) \rangle$. Therefore, queries for q are sent to every agent (a, b, c, d and e). The query has the form $Query(\langle @, \lnot ed(m_1) \rangle , \alpha , hist_p=[\langle a,\lnot col(m_1) \rangle ])$.

  • Step 3: The queries for b and d return $tv_p = true$, and, respectively, the arguments $B_1^\alpha$ and $D_1^\alpha$ with their subarguments (see Fig. 2), all of them marked as J (justified), since they are not defeated. The same query is also sent to a, c and e, but they return $tv_p=false$ and no arguments, since there are no rules with head $p'$ in these agents’ KBs. Therefore $B_1^\alpha$ and $D_1^\alpha$ are stored as possible subarguments for arguments for $p'$.

  • Step 4: The argument $A_2^\alpha$ is created with subargument $B_1^\alpha$ and the argument $A_3^\alpha$ is created with subargument $D_1^\alpha$. As both subarguments are marked as J (justified), then both new arguments are marked as SuppJ (supported by justified). Finally, both arguments for $p' = \langle a, \lnot col(m_1) \rangle$ are returned. For details, see Algorithm 4 in Appendix A.

$\square$

Continuation of Example 2

Below is a brief simulation of the processing of the call $Find\_Def\_Args(p' = \langle a,x \rangle , KB_{a\gamma },\gamma ,hist_p=[])$

• Expected result: $Args_{p'} = \{A_1^\gamma , A_2^\gamma \}$

• Explanation:

  • Step 1: A new list $hist_{p'}$ is created by adding $p'$ to $hist_p$. Thus $hist_{p'} = [\langle a,x \rangle ]$.

  • Step 2: A single rule $r_{a1}$ is found with head $p'$. This rule has a single body member $q = \langle @, y \rangle$. Therefore, queries for q are sent to every agent (a, b and c). The query has the form $Query(\langle @, y \rangle , \gamma , hist_p=[\langle a,x \rangle ])$.

  • Step 3: The queries sent to b and c return $tv_p = undec$. In summary, when b and c receive the query, the rules $r_{b1}$ and $r_{c1}$ are found to have similar enough literals as heads. However, when traversing the bodies of these rules, the literal x is found, which is in $hist_p$. Therefore, the fallacious leaf arguments given in the example are created, and then they are used as subarguments to build $A_1^\gamma$ and $A_2^\gamma$. The respective possible subarguments $B_1^\gamma$ (with conclusion $\langle b, y', 0.9 \rangle$) and $C_1^\gamma$ (with conclusion $\langle c, y'', 0.9 \rangle$) are then created and stored (see the rules and arguments in Example 2).

  • Step 4: The arguments $A_1^\gamma$ and $A_2^\gamma$ are created with the subarguments $B_1^\gamma$ and $C_1^\gamma$, respectively. As both subarguments are neither marked as J (justified) nor R (rejected), then both new arguments are not marked with any of these labels as well. For details, see Algorithm 4 in Appendix A.

$\square$

4.3 Complexity issues and optimization

It is important to note that the algorithm as presented thus far would have exponential complexity in the worst case. Suppose the following global KB:

$$\begin{aligned}{} & {} r_{a1}: \langle a, x_1 \rangle \Leftarrow \langle @, x_2 \rangle , \langle @, x_3 \rangle , \langle @, x_4 \rangle ; \qquad r_{b1}: \langle b, x_2 \rangle \Leftarrow \langle @, x_3 \rangle , \langle @, x_4 \rangle \\{} & {} r_{c1}: \langle c, x_3 \rangle \Leftarrow \langle @, x_4 \rangle ; \qquad r_{d1}: \langle d, x_4 \rangle \Leftarrow \end{aligned}$$

Figure 5 presents a call tree, considering only the queries that reach the $Find\_Def\_Args$ stage (step 5 of the Query algorithm), which leads to recursive calls to the procedure Query. Cases in which the queries do not reach this stage do not induce recursion on the agents’ knowledge base rules, namely: when the queried agent does not have any similar l-literal in its knowledge base, or when the l-literal which was queried or its complement is in the history $hist_p$. For simplicity, therefore, the complexity analysis criterion used is the number of calls to Query that reach the $Find\_Def\_Args$ stage.

Fig. 5

Call tree for the worst case when $n=3$

Each edge of the call tree presented in Fig. 5 is labeled in the form $\langle a\rangle \rightarrow \langle b \rangle : \langle p \rangle$, where $\langle a\rangle$ is the agent that submitted the query, $\langle b \rangle$ is the agent that received the query, and $\langle p \rangle$ is the l-literal being queried. Each vertex is labeled as the l-literal $\langle p \rangle '$ that was found to be similar enough to p, and for which an answer will be sought.

It is easy to see that the il-literals $\langle b, x_2, 1\rangle$, $\langle c, x_3, 1 \rangle$ and $\langle d, x_4, 1 \rangle$ will be generated from this setup, constituting the set of premises of the arguments. Therefore, it is possible to induce that the number of queries that reach the stage of $Find\_Def\_Args$ for an arbitrary number of premises n in the arguments is asymptotically $O(2^n)$. The demonstration is straightforward and will not be presented for the sake of space and convenience.

As to the number of messages, complexity is even greater considering the number of messages that each agent sends for each sl-literal and to each known agent. This is because, in each of the queries, represented by the edges in the call tree, as shown in Fig. 5, one must consider that the agent actually sends query messages to each known agent.

Therefore, the number of messages exchanged has an asymptotic complexity of $O(|Ags|\times 2^n)$ in the worst case.

Therefore, it is clear that the algorithm as presented thus far is not computationally feasible. However, we present an optimization strategy that enables it to achieve polynomial time complexity: a cache memory that allows storing and reusing arguments previously generated in the context of the same query focus. This memory, referred as $C_{\alpha }[p']$, is individual and local to each agent, and mapped to each specific query focus $\alpha$ and by each l-literal $p'$ that is similar enough to a queried l-literal p.

A record $C_{\alpha }[p']$ in agent a can store a null value ($\bot$), a future (as explained below), or the actual set of arguments for and against p built in a previous query. Each time an agent a reaches steps 4 and 5 of the Query algorithm, it first checks whether $p'$ (the l-literal which was found to be similar enough to the l-literal queried) has not been previously received in the same query focus by checking the value of $C_{\alpha } [p']$. If this is the case and the answer has already been returned, it proceeds to use that answer. If the argument is still not found—that is, the agent is still in the middle of processing to build it—the thread gets waiting until an answer is received. This is achieved through the concept of future (or promise) [22]. In simple terms, a future is an object that acts as a proxy for an initially unknown result because the calculation of its value has not yet been completed. Many parallel threads may wait until the value of this object is set. When this happens, they are notified, so they are able to capture the value and resume their execution.

The benefits of this simple caching mechanism are made clearer when observing what would happen in the case presented when using this caching mechanism. Figure 6 shows what would be the call tree for this case with the optimization presented.

Fig. 6

Call tree for the worst case scenario when $n=3$ with the caching mechanism

Note that only $n + 1 = 4$ queries make it to the $Find\_Def\_Args$ stage in this case, since there is no need to repeat the same query processing for $\langle @, x_3 \rangle$ and $\langle @, x_4 \rangle$, as in the version without cache. Therefore, it can be induced that the number of calls to Query that get to the $Find\_Def\_Args$ stage is now proportional to the number of premises, reducing the time complexity to O(n). It is easy to think of the intuition for it: there will be as many queries as there are l-literals to query about as the algorithm traverses the agents’ rules, similar to a depth-first tree traversal.

As to the number of messages, it is also reduced. For the worst case scenario with $n=3$, only $3 \times 3 = 9$ messages are sent by a to each of the agents b, c and d ($|Ags| - 1 = 3$) about each of the sl-literals in the rule body $r_{a1}$ ($n=3$). Then there will be $2 \times 3 = 6$ messages, corresponding to the two sl-literals in the body of $r_{b1}$, which must also be sent to the 3 other agents. Then there will be $1 \times 3 = 3$ messages sent by c, corresponding to the single sl-literal in the body of $r_{c1}$ sent to the 3 other agents. Therefore, $(3 \times (3+2+1)) \times 2 = 36$ messages are exchanged, including the query and reply messages. Generally speaking, the number of messages $m = [(|Ags| - 1) \times \sum _{i=1}^{n} i)] \times 2$ = $[(|Ags| - 1) \times ( n \times (1+n)/2)] \times 2 = (|Ags|-1) \times (n^2 + n)$. Therefore, the number of messages exchanged with optimization based on cache is $O(|Ags| \times n^2)$.

In an average case, however, the number of messages tends to be less. Let m be the number of sl-literals and k the number of foreign cl-literals. Assuming that each sl-literal occurs only once in the entire extended knowledge base—unlike the worst case, where they are repeated—then for each sl-literal, $(| Ags|-1)\times 2$ messages are sent, counting query and reply messages. Furthermore, for each foreign cl-literal, 2 messages are sent, one query and one reply. Therefore, the total number of messages sent is $M = m\times (|Ags|-1)\times 2 + k \times 2$. Therefore, the asymptotic complexity for the number of messages in this average case is $O(|Ags| \times m + k)$.

As to the total size of arguments generated, the cache mechanism enables it to be reduced, given that arguments already generated in memory can be just reused by reference. In fact, the maximum total size of arguments ends up being proportional to the amount of rules in the system combined with the similarity rate between literals, i.e., the amount of sl-literal in the body of the rules that are similar enough to the head of other rules. In other words, the more rules with premises that are similar enough to conclusions of other rules, the more arguments will be built, but no argument is built more than once.

Another point of interest of this caching mechanism is that it illustrates how DDRMAS allows reusing previously generated arguments. In this case, it was used to enable a better performance. However, the same arguments could be stored and reused in other features, such as those related to explanation and learning.

5 Experimental evaluation

In order to ensure the computational feasibility and performance, as well as emphasize DDRMAS’s potential for real applications, an implementation of the model was developed, as well as some testing scripts. The implementation was done using the Python programming language.¹ All the experiments were run using the Python 3.10.9 interpreter in an AMD Ryzen 3 5400u in Ubuntu 22.04.2 LTS. A simple class diagram is presented in Fig. 7.

Fig. 7

Class diagram for the implemented system

Three testing scripts were developed: (i) a script that creates and performs queries in randomized systems; (ii) a script that implements the worst case presented in Sect. 4.3; and (iii) a script that implements the worst case presented for the contextual defeasible logic (CDL) model [13], in order to enable some comparison with DDRMAS.

The randomized script creates a random system taking the following parameters:

• Number of agents (|Ags|);

• Total number of distinct literals ($|L_\mathcal {S}|$);

• Total number of distinct rules ($|KB_{\mathcal {S}}|$);

• Maximum size of rules’ body (MaxB);

• Number of focus rules (FKBSize);

• Percentage of sl-literals throughout the rules (PerSL);

• Percentage of pairs of literals with high similarity (PerSim);

• Whether the system has cycles or not (AllowsCycles);

The rules are generated based on random l-literals for their head and body. All rules are defeasible. Each rule has a body of size varying between and including 0 and MaxB, evenly distributed. The generated rules are randomly and uniformly distributed among the agents. Redundant or self-conflicting rules are discarded, since they do not add any new information, and such kinds of rules can be easily filtered on a real scenario. For example, rules like $B \Leftarrow A, A$, or $B \Leftarrow A, \sim A$ are removed; and when a rule $B \Leftarrow A$ exists, then $B \Leftarrow A, C$ is not relevant, therefore discarded. This does not impose any new assumption on the DDRMAS system, because mechanisms to remove such redundant rules can be executed in parallel and independently of the DDRMAS query system.

The intuition for this random script is getting statistical data that possibly gives insights about features and weaknesses of DDRMAS. Therefore, different settings were run by a number TimesRun and the following data was captured from these executions: (i) total of arguments generated ($|Args_{\mathcal {S}\alpha }|$); (ii) total of messages exchanged (|Msgs|); (iii) sizes of messages exchanged (SizesMsgs); and (iv) times of execution (T).

Table 1 presents some results. Only the cases in which at least one argument was generated are accounted (note the WithArgs line), in order to consider only the cases in which rules have been activated during reasoning.

Table 1 Results of the experiments with the randomized system generator

It is interesting to note that the number of arguments, number of messages and sizes of messages are quite reasonable when compared to the amount of agents, literals and rules. Only the number of messages tends to be a little greater when there are more agents, but this is expected, as discussed in Sect. 4.3. It would be necessary to find out the impact of the number of messages in real world applications in order to have further insights on the necessity of optimizing it and how it could be mitigated.

It is also evident that the allowance of cycles increases the amount of arguments generated, even with the existence of the mechanism that avoids infinite loops by creating fallacious arguments that behave as leaf nodes. This happens because, when the script is run with $AllowsCycles=False$, it discards rules that would introduce fallacious arguments. If there are no fallacious arguments, when trying to build some arguments, the algorithm ends up not reaching neither a fallacious leaf node nor a factual rule, thus many arguments are never really built.

As for the script that implements the worst-case scenario presented in Section 4.3, it was executed with the following inputs and obtained the following results: $|Ags| = |L_\mathcal {S}| = 20 \ \rightarrow \ |Args_{\mathcal {S}\alpha }| = 20; |Msgs| = 7220; T = 143.96 \ ms; Max(SizesMsgs) = 19; Avg(SizesMsgs) = 0.36$. These results confirm the analytical complexity analysis presented in Sect. 4.3.

In order to enable a comparison with the most similar related work, we modeled CDL’s worst case presented in [13] in DDRMAS. This was done by considering the absence of sl-literals, i.e., all body members of rules are concrete l-literals. This setting consists of $n+1$ agents $\{a_0, a_1,\ldots , a_n\}$, such that $a_0$ has the following rules:

$$\begin{aligned} {\begin{matrix} r_{{a_0}1}: \langle a_0, x_0 \rangle \Leftarrow \langle a_2, x_2 \rangle , \langle a_3, x_3 \rangle , \ldots , \langle a_n, x_n \rangle \\ r_{{a_0}2}: \langle a_0, x_0 \rangle \Leftarrow \langle a_1, x_1 \rangle , \langle a_3, x_3 \rangle , \ldots , \langle a_n, x_n \rangle \\ \ldots \\ r_{{a_0}[n/2]}: \langle a_0, x_0 \rangle \Leftarrow \langle a_1, x_1 \rangle , \ldots , \langle a_{n/2-1}, x_{n/2-1} \rangle , \langle a_{n/2+1}, x_{n/2+1} \rangle ,\ldots , \langle a_n, x_n \rangle \\ r_{{a_0}[n/2+1]}: \langle a_0, \lnot x_0 \rangle \Leftarrow \langle a_1, x_1 \rangle , \ldots , \langle a_{n/2}, x_{n/2} \rangle , \langle a_{n/2+2}, x_{n/2+2} \rangle ,\ldots , \langle a_n, x_n \rangle \\ \ldots \\ r_{{a_0}n}: \langle a_0, \lnot x_0 \rangle \Leftarrow \langle a_1, x_1 \rangle , \langle a_2, x_2 \rangle , \ldots , \langle a_{n-1}, x_{n-1} \rangle \\ \end{matrix}}\nonumber \\ \end{aligned}$$

(6)

The other agents all have a single factual rule each. For example, $a_1$ has the rule $\langle a_1, x_1 \rangle \Leftarrow$, $a_2$ has $\langle a_2, x_2 \rangle \Leftarrow$, and so on.

The results for $|Ags| = |L_\mathcal {S}| = 100$ are the following: $|Args_{\mathcal {S}\alpha }| = 198; |Msgs| = 19404; T = 721.68 \ ms; Max(SizesMsgs) = Max(SizesMsgs) = 1$. The number 100 for the agents/literals was chosen because 100 is the maximum amount of agents that Bikakis et al. tested with in their experiment [13]. It is interesting to note that, in their case, they could not run their most complex strategy for conflict resolution (Complex Mapping Sets)—which uses all the context information possible—for more than 40 agents because it exceeded memory usage in their setup, and for 40 agents their experiment took $207828 \ ms$ to execute. This shows that our approach for conflict resolution enables an efficient context reasoning, with the addition of considering some nuances related to the indirect dependencies among agents, as explained in Sect. 3.2.

This also demonstrates that CDL systems can be modeled on DDRMAS—by simply using only cl-literals, and not sl-literals or focus rules—but not the other way around—for example, the mushroom hunt scenario, which requires considering knowledge from arbitrary sources and contextual/focus rules, which are features not provided in CDL. Therefore, DDRMAS can be seen as a kind of generalization of CDL. The main differences between CDL and DDRMAS are further detailed and discussed in Sect. 6.

6 Related work

This section presents some related work. The ones that are most similar are those based on defeasible logic (DL) and multi-context systems (MCS). Governatori et al. [20] present an argumentation-based semantics for DL, enabling reasoning in the presence of possibly conflicting defeasible rules in a knowledge base. Bikakis et al. [1] extends this model, calling it contextual defeasible logic (CDL), including the possibility of distributed knowledge bases with a querying algorithm to enable multiple agents to discover the truth-value of a literal. However, they do not propose ways to enable agents to use knowledge from arbitrary agents, i.e., it is assumed that all agents know which agent defines each knowledge, which is not realistic in many scenarios (the mushroom hunting scenario being an example, since it cannot be modeled in CDL). There is also no proposal for handling knowledge from different agents based on similarity, assuming that all agents share the same vocabulary, which also assumes there is a centralized entity that standardizes such vocabulary. Therefore, the defeat relation, which is the base for conflict resolution between arguments, is defined only in terms of preferences (trust) among agents. Furthermore, sharing contextual knowledge in queries, which is also a requirement for scenarios like the mushroom hunting one, is not proposed in their work.

Furthermore, we empirically observed in Sect. 5 that DDRMAS can be seen as a kind of generalization of CDL in the sense that CDL systems can be modeled on DDRMAS, but not the other way around. The mushroom hunters scenario, for example, requires the existence of sl-literals and similarity-based matching of literals to model knowledge coming from arbitrary sources, and the existence of shared focus rules to model a kind of contextual reasoning that requires temporary knowledge sharing between agents. Therefore, such scenario is not possible in CDL, given that it does not propose features to model these requirements.

In [13], Bikakis et al. propose different strategies for CDL in order to take advantage of the trust that multiple agents have in each other, which enables achieving similar results to the strength calculation proposed in this work. However, such strategies are not proposed using tree-like structures for arguments, therefore lacking the flexibility of proposing forms of conflict resolution based on the structure of arguments—for example, by means of a formula, as is done in DDRMAS. The most complete strategy proposed by them, called Complex Mapping Sets (CS), uses the trust among all the agents involved on achieving a given conclusion, but does not penalize indirect trust between them, as is done in the argument strength formula used in DDRMAS, which takes advantage of the tree-like structure of arguments. Furthermore, it was demonstrated in Sect. 5 that the worst case presented in [13] is feasible and efficient in DDRMAS for a great number of literals and agents. This is a relevant contribution, given that DDRMAS’s default conflict resolution approach also uses all context information and relations between agents—except the irrelevant arguments which are discarded in step 3 of the $Find\_Def\_Args$ algorithm, as explained in Sect. 4.2—which are materialized in the arguments built during reasoning.

An approach with goals related to this work is presented in [23], proposing multi-agent argumentation-based reasoning with argument strength determined by the credibility of information sources. One notable capability is that the strength of an argument is not absolute but may vary from one context to another through special rules known as backing and detracting rules. These rules enable reasoning about the strength of arguments. For instance, a detracting rule could cast doubt on an agent’s credibility in a specific context, allowing the agent to dismiss information even if it comes from a more credible source. However, the approach does not consider strength calculation in the same way as in the present work (i.e., as a formula that considers the tree-like structure of arguments) neither provides ways to share contextual knowledge between agents in the context of an isolated query. The idea of backing and detracting rules is nonetheless appealing in the context of the present work and may be considered for future works.

Other relevant work in the field are the structured argumentation approaches DeLP (defeasible logic programming) [24] and ASPIC+ [25]. None of them proposes distributed knowledge bases with a query algorithm in the same fashion as proposed in this work. Furthermore, there is no solution to deal with knowledge coming from arbitrary agents and matched by similarity. In [26], DeLP presents a similar idea to the query focus, called contextualized query, which is a query that includes knowledge relevant to help answering it. Such query must be issued to a node called DeLP-Server. However, such approach is restricted to a client–server query answering fashion, and does not propose a form of distributed reasoning with interrelated knowledge from different agents in a peer-to-peer manner as proposed in this work. As to ASPIC+, it proposes a framework for DL that can take advantage of extension-based semantics, like those proposed by Dung [27], but also does not propose an architecture for multi-agent reasoning.

The argumentation-based multi-agent system (ArgMAS) [28] presents a DeLP-based framework that supports collaboration between agents, which allows combining the knowledge bases of different agents in order to produce arguments. Therefore, this approach presents a way of reasoning with interrelated knowledge bases, although it does not use the concept of bridge/mapping rules. Instead, agents in an agent alliance construct partial arguments that contain sets of free literals, that is, sets of literals that are not yet supported by other arguments. From there, a meta-agent runs a backward-chaining algorithm trying to construct a complete argument based on the partial arguments. However, this proposal has some relevant differences compared to the present work: (i) Collaboration between agents is restricted to a predefined set of agents belonging to the same alliance, while in DDRMAS an agent can collaborate with any other agent, without the need of an alliance being created; (ii) an agent can only participate in one alliance at a time, while our work allows an agent to participate in the reasoning of multiple query focuses simultaneously; (iii) the complete arguments are generated by a meta-agent, which centralizes a good part of the reasoning, and not by the individual agents in a totally distributed manner, as proposed in DDRMAS; and (iv) the correspondence between the literals of different agents is defined only by the exact correspondence, that is, a partial argument with a free literal x is chained to a literal that exactly concludes the value x, not being made a matching based on similarity. In addition, the work does not present ways of sharing focus in queries.

Similar work is also found in the field of MCS, which is a kind of formalization for systems composed of multiple knowledge bases that are interrelated by means of their vocabularies. However, no work was found that solved all the problems mentioned in the present work, and only one is based on argumentation-based semantics [1]. Furthermore, most of the approaches on MCS propose a conflict resolution based on the concept of repair [29], which modifies the knowledge bases to maintain a conflict-free global state. The present work, on the other hand, proposes conflict resolution at query time, i.e., conflicts are detected when arguments are built and then confronted to each other, which also does not necessarily imply in updating the knowledge bases, but only in giving the most reasonable answer given some criteria (in our case, trust among agents and knowledge similarity). Therefore, different from repairing, DDRMAS proposes maintaining a possibly inconsistent global state, resolving them when conflicting knowledge is used, with the benefit of allowing agents to maintain different views about the environment and to be able to more faithfully execute a type of contextual reasoning in which there are conclusions that are valid in certain contexts but not in others.

Dao-Tran et al. [30] proposes the dynamic distributed multi-context system (DDMCS), which includes the use of schematic bridge (mapping) rules with a similarity function, and a backtracking algorithm to enumerate all possible substitutions (instantiations) of schematic bridge atoms (similar to the sl-literals of this work) in a distributed environment, in order to instantiate a concrete SMC, from which equilibria—possible sets of admissible beliefs—can be calculated. Therefore, DDMCS theoretically requires the pre-instantiation of a concrete SMC for each new change in the system, which may involve each existing knowledge base, as there are dependencies between them. This could result in unnecessary overhead in highly dynamic environments. Furthermore, some sort of centralized entity would be needed to instantiate and assign these “instantiated knowledge bases” to each agent. The approach of the present work (DDRMAS), on the other hand, does not require any centralized action in response to changes. When an agent needs to query other agents about an sl-literal, it simply sends a message in broadcast to the other agents, without even needing to know each existing agent in the system specifically. Agents arriving at the environment can simply send a broadcast message to introduce themselves. Agents leaving the environment can also send this type of message to let other agents know of their absence. In cases in which this is not possible (for example, an agent abruptly removed from the system), when such an agent is queried by another agent, some communication service or broker could simply return a communication error. Changes in agents’ knowledge also do not require any intervention in DDRMAS. When an agent with updated knowledge is queried, it will simply use its current knowledge.

7 Conclusions and Future Work

A comprehensive and flexible model, which allows modeling and implementing scenarios with distributed agents, with the possibility of incomplete and conflicting knowledge bases, as well as a form of contextualized reasoning, was presented. A formalization of knowledge bases and queries, as well as the formalization of arguments that can be generated from them, is presented. It is also proposed a distributed algorithm that allows the processing of queries according to the underlying argumentation semantics. It was analytically and experimentally demonstrated that the model is computational feasible and that it presents contributions and advantages when compared to related work.

Future work includes proposing models for explanation and learning based on the argument structures generated in the reasoning process. This way, agents could explain the decisions they made, as well as adapt their rules based on the arguments received from other agents.

Alternative forms of argument strength calculation can also be proposed and tested. Some ideas in this respect include: (i) joint argument strength for a given literal, i.e., considering the sum of strengths of all the arguments for and against a given literal; (ii) a naiver strength calculation that considers all arguments, including external subarguments of subarguments, equal to direct external subarguments; (iii) a more arrogant strength calculation that does not take into account the strength calculation using the trust function of the agent that generates the argument, but only the trust function of the argument that issued the query; and (iv) a more skeptical strength calculation, that uses the min operation instead of summation, such that only the strength of the weaker subargument is used to derive the strength of an argument. More details about these different strength calculations, as well as comparisons and properties, will be presented in future work.

Further investigation on the relation of DDRMAS to existing argumentation models could also be realized. In fact, it is possible to prove that a DDRMAS system can be transformed to a Governatori’s DL system, but not the other way around, demonstrating that DDRMAS inherits DL properties, but also extends it. This demonstration was not included in this paper on account of its already considerable length. Furthermore, it could also be fruitful to compare DDRMAS to other models, such as DeLP and ASPIC+, and investigating whether it is possible to adapt DDRMAS to use different argumentation semantics. New kinds of rules, such as the detracting and backing rules proposed by [23], which enable reasoning about the strength of arguments, could also be studied and integrated to our approach.

Another interesting line of future work would be to implement applications based on DDRMAS in order to demonstrate its usefulness in real world scenarios, as well as software frameworks in different programming languages to facilitate the development of such applications.

Algorithm pseudocodes

Algorithm 1

Pseudocode for the Query procedure.

Algorithm 2

Pseudocode for the $Local\_Strict\_Ans$ function.

Algorithm 3

Pseudocode for the $Compare\_Def\_Args$ function.

Algorithm 4

Pseudocode for the $Find\_Def\_Args$ function.

Algorithm 5

Pseudocode for the $Query\_Agents$ procedure.