Keywords

computational complexity; division-based method; dynamics of argumentation; semantics combination; semantics of argumentation

7.1 Introduction

According to the existing literature, most argumentation systems are dynamic [1–3], especially argumentation-based autonomous agents within a dynamic environment, including belief revision [4–9], deliberation [10–13], decision-making [14–18], and negotiation [19–23]. The existing research shows that in many argumentation systems, arguments and their attack relation evolve with the changing of underlying knowledge or information. For example, in [6,7], the authors formulated a system where an instantiated argumentation framework is based on the changing observations. So, at each time point, when observations change, the arguments and their attack relation change accordingly. In [4,24], within an argumentative system, when a new explanation is received, some strict rules are changed to defeasible rules, which gives rise to the changing of arguments and their attack relation. In [13,25], due to the dynamics of observations and inference rules, the argumentation frameworks for beliefs, goals and intentions, respectively, are dynamic. In [22,23], argumentation-based negotiation (ABN) agents perform reasoning with incomplete, uncertain and inconsistent information. Each agent’s theory (as an argumentation system) may evolve during a negotiation dialogue, i.e., if an agent receives an argument from another agent, it will add the new argument to its theory, and furthermore, new conflicts may arise between the original arguments of the agent and the ones that emerge after adding the received arguments to its theory [23]. In [26], when a collection of argumentation systems coming from different agents are merged (after consensual expansion of each argumentation system), the arguments and the attack relation of each argumentation system may change accordingly.

To illustrate the dynamics of argumentation systems, let us see a revised example from [6].

As shown in Example 7.1, when new observations arise, a set of arguments and/or attacks are added to the system. Meanwhile, in some other cases, when observations or rules of inference change, a set of arguments and/or attacks may be deleted from the system [25]. With the changing of arguments and/or attacks of an argumentation system, the status of some arguments changes, while that of others remains untouched. Now, one of the challenging problems is how to efficiently compute the dynamics of argumentation systems. When an argumentation system is modified, we may simply recompute the status of each argument afresh. However, this method is obviously inefficient, and in most of cases, difficult.

To cope with this problem, there have been a small number of efforts [16,27,28]. First, Boella et al studied the dynamics of argumentation by exploring the principles according to which the extension does not change when the set of arguments or the attacks between them are changed [27]. However, they have not considered how the extensions of an argumentation system evolve when new arguments are added or the old ones are removed. Second, Cayrol et al addressed the problem of revising the set of extensions of an abstract argumentation system, and studied how the extensions of an argumentation system may evolve when a new argument is received [28]. However, they restricted their study to the case of adding just one argument having only one interaction with an initial argument. Third, Amgoud et al used dynamics of argumentation in the decision-making of an autonomous agent [16]. They studied how the acceptability of arguments evolves when the decision system is extended by new arguments without computing the whole extensions. However, they also considered the situation where only one argument is added to the system. In addition, all of the current efforts have not taken the efficiency of computing the dynamics of argumentation into consideration.

According to the above analysis, a more general theory is needed to formulate the dynamics of an argumentation system, with the following three characteristics:

To realize this purpose, we introduce a division-based approach. The basic idea of this method is that when an argumentation framework is updated, we may only recompute the status of those arguments that are affected, while the status of those arguments that are unaffected can be obtained directly from the result of the previous computation. Based on the fundamental theories presented in Part III, the status of arguments that are affected and unaffected can be computed separately and then combined to form the semantics of the updated argumentation framework.

7.2 The Changing of an Argumentation Framework

As mentioned in the previous section, when a set of arguments and/or a set of attacks are added to (or deleted from) an argumentation framework, the status of affected arguments may change. However, if some arguments and attacks to be added are in the existing argumentation framework, or some arguments and attacks to be deleted are not in the existing argumentation framework, an addition (respectively a deletion) of them will not have any effects on the argumentation framework. So, for simplicity and without loss of generality, we suppose that the arguments and attacks to be added are not in the existing argumentation framework, while the arguments and attacks to be deleted are in the existing argumentation framework.

Let be the universe of arguments. For all and , let be the set of attacks (also called interactions) related to and of the form , or , in which and . Let be a set of attacks between the arguments in , and of the form , in which . An addition of an argumentation framework is defined as follows.

Meanwhile, let and be sets of attacks to be deleted. It holds that . A deletion of an argumentation framework is defined as follows.

Based on Definitions 7.1 and 7.2, an updated argumentation framework with respect to an addition or a deletion is syntactically defined as follows:

For simplicity, we use and to denote and , respectively.

7.3 The Division of an Updated Argumentation Framework

According to Formulas 7.1 and 7.2, with respect to a certain argumentation semantics , we may directly compute the extensions of and afresh, without considering previous information (the extensions of ). However, if the previous information is properly used, the complexity of computing the dynamics of argumentation might be decreased. If an argumentation semantics satisfies the criterion of directionality [29], then the status of an argument is affected only by the status of its defeaters, while the arguments which only receive an attack from have no effect on the state of . Based on this idea, we may infer that when a set of arguments and/or a set of attacks are added to (or deleted from) an argumentation framework, some arguments are directly or indirectly affected, while others remain unaffected. Therefore, if we can divide or into two parts: affected and unaffected, we need only to compute the status of affected arguments, while leaving the status of unaffected arguments unchanged. According to the theories presented in Chapters 4 and 5, the status of affected arguments can be computed in a conditioned sub-framework, and then combined with that of the unaffected ones, to form the semantics of the updated argumentation framework. Now, let us introduce the notion of dividing an updated argumentation framework.

The division of an updated argumentation framework is based on the notion of directionality of argumentation semantics [29,30]. Given an argumentation framework , for all , if there exists a directed path from to , i.e, is reachable from , then under the semantics that satisfies directionality, the status of may be affected by ; otherwise, is independent of . Based on this idea, the notion of reachability, as well as the notions of affected and unaffected between two arguments can be defined as follows:

According to Definition 7.4, the reachability relation is transitive, i.e., if is reachable from and is reachable from , then is reachable from .

Based on Definition 7.5, given a set of arguments , it is possible to identify the subset of that is affected by a set of arguments or by a set of attacks (interactions) , with respect to a set of attacks . In addition, we notice that the set of affected arguments related to an attack can be computed through , the attacked argument of . So, we will define the affected and unaffected arguments related to an attack by using the attacked argument of . Here, we use to indicate the attacked argument of , and to indicate a set of arguments, each of which is the attacked argument of an attack in .

Based on the concept of affected and unaffected arguments, we are ready to define the concept of the division of an updated argumentation framework. When an addition is added to (or a deletion is deleted from) an argumentation framework will be divided into three parts:

Formally, we first present the definition of the division of an updated argumentation framework with respect to an addition .

In this definition, the set of affected arguments contains those arguments in that are affected by and , as well as those arguments in . is the set of arguments in that are unaffected. The set of conditioning arguments contains those arguments in that attack the arguments in .

In order to ensure the correctness of the division defined in Definition 7.7, in this stage, we should verify that: (1) the union of affected arguments and the unaffected ones is equal to the set of arguments in the updated argumentation framework, i.e., (obvious), and (2) the union of attacks in three parts (affected, unaffected, conditioning) is equal to the set of attacks in the updated argumentation framework, which is formulated by the following lemma:

Similar to Definition 7.7, for the division of an argumentation framework with respect to a deletion, we have the following definition and lemma:

In this definition, the set of affected arguments in are those arguments in (i.e., ), that are affected by and . is the set of arguments that are unaffected. The set of conditioning arguments contains those arguments in that attack the arguments in .

After division, we will construct two sub-frameworks of the updated argumentation framework (respectively, ): an unconditioned sub-framework and a conditioned sub-framework. First, the unconditioned sub-framework of is , while the conditioned sub-framework of with respect to is constructed according to and as follows:

(7.5)

According to Definition 7.7, we may infer that: (i) , (ii) , and , such that attacks , and (iii) . In other words, is a conditioned sub-framework.

Similarly, we may construct two sub-frameworks of the updated argumentation framework : a unconditioned sub-framework , and a conditioned sub-framework with respect to , which is defined as follows:

(7.6)

According to Definition 7.8, we may infer that: (i) , (ii) , and , such that attacks , and (iii) . So, is also a conditioned sub-framework.

Finally, based on Lemmas 7.1 and 7.2, the following proposition shows the correctness of the division defined in Definitions 7.7 and 7.8, respectively.

7.4 Computing the Semantics of an Updated Argumentation Framework Based on the Division

Based on the concept of the division of an argumentation framework, we are now ready to compute the semantics of the two kinds of sub-frameworks described above and combine them to form the semantics of the updated frameworks and , respectively.

On the one hand, let be the set of extensions of an argumentation framework , under the argumentation semantics . According to the theory presented in Section 5.2, the set of extensions of the unaffected sub-framework with respect to an addition (respectively, with respect to a deletion ) can be obtained directly:

(7.7)

(7.8)

On the other hand, according to Definitions 4.8 and 4.9, the extensions of conditioned sub-frameworks are not computed directly. They are related to the status of the conditioning arguments. In other words, we should firstly construct two sets of partially assigned sub-frameworks:

(7.9)

(7.10)

And then, the extensions of the partially assigned sub-frameworks, i.e., and , can be obtained.

Based on the extensions of the two kinds of sub-frameworks, we obtain the extensions of by combining and , in which , and the extensions of by combining and , in which , in which .

(7.11)

(7.12)

7.5 An Illustrating Example

Now, let us consider the following example, which illustrates the process of computing the extensions of an updated argumentation framework based on the division. For simplicity and without loss of generality, we only discuss the case under preferred semantics.

7.6 Conclusions

In this chapter, we have introduced a division-based method for computing the dynamic semantics of argumentation. It has the following characteristics:

With the above two characteristics, this theory is expected to be very useful in various kinds of argumentation-based systems, especially belief revision [4–7,9], deliberation [10–12], decision-making [14,15,17,18], and negotiation [19–23], within agents and multi-agent systems. The reason is that in these systems, underlying knowledge and information are often uncertain, incomplete, inconsistent and ever-changing. As a result, the corresponding argumentation systems are dynamic by nature. So, the efficient division-based method will facilitate the development of these systems.

In recent years, dynamics of argumentation has attracted some research efforts. However, up to now, its concept is still unclear. Different researchers treated it from different perspectives.

First, in the area of dialectical argumentation, the dynamics of argumentation means that the dialectical process of argumentation may change with the variations of knowledge at different stages [31–33]. This concept focuses on how a position (or a claim) can be proved with respect to a theory which can be revised dynamically. Researchers in this area did not care about the status evolution of the whole set of arguments within an argumentation framework, but only considered whether a specific position (or a claim) is acceptable according to a dialectical proof procedure where two parties (proposer and opposer) are involved.

Second, other researchers paid more attention to how the whole set of arguments and attacks of an argumentation system changes with the changing of underlying information, or how the status of arguments of an argumentation system evolves upon the changing of arguments and attacks. On the one hand, in [6], Capobianco et al used potential arguments and the instances of them to treat with the knowledge changing in dynamic environment. When perceptions change dynamically, the instances of potential arguments and attacks among them vary accordingly. As a result, the status of arguments is changed. Sharing some basic ideas with [6], Rotstein et al introduced the notion of dynamics into the concept of abstract argumentation frameworks, by including the concept of evidence [7]. They proposed a concept of Dynamic Argumentation Framework (corresponding to potential arguments in [6]), from which a static instance can be obtained, according to a varying set of evidence (corresponding to perceptions in [6]). However, both of them have not considered how to dynamically compute the status of arguments without computing the whole set of arguments in each time point. On the other hand, some researchers have performed some works towards this issue. For example, Moguillansky et al studied the dynamics of argumentation based on the idea of classical belief revision, i.e., when an argument is added to a system, the revision operator will change the set of arguments, with an objective that the newly added argument is accepted [8]. Boella et al studied the dynamics of argumentation by exploring the principles where the extension does not change when an argument or an attack between them is changed, but without considering how to dynamically compute the status of arguments when the status of existing arguments is affected [27,34]. Baroni et al proposed a notion of directionality, which says that unattacked sets are unaffected by the remaining part of the argumentation framework as far as extensions are concerned [29,30], but without considering the dynamics of argumentation systems. Cayrol et al explored the impact of the arrival of a new argument on the outcome of an argumentation framework, by defining a typology of refinement (i.e. adding an argument), and defining principles and condition so that each type of refinement becomes a classical revision [28]. However, they did not focus on how to compute the status of arguments when an argumentation framework is expanded with a set of arguments or attacks. Amgoud and Vesic studied how the acceptability of arguments evolves when the decision system is extended by new arguments without computing the whole extensions [16]. Their theory is focused on the revision of a particular argument (a practical argument or an epistemic argument). On the contrary, we are more interested in the issue of how the status of all arguments in an argumentation framework changes when any variations arise.

Based on the above analysis, we may conclude that the division-based method is in line with [16,27–29], etc., but has the two characteristics (generality and efficiency) mentioned above.

References

1. Kakas A, Miller R, Toni F. An argumentation framework for reasoning about actions and change. In: Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning. 1999;78–91.

2. Bench-Capon TJM, Dunne PE. Argumentation in artificial intelligence. Artificial Intelligence. 2007;171(10–15):619–641.

3. Boella G, Pigozzi G, van der Torre L. Normative framework for normative system change. In: Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems. 2009;169–176.

4. Falappa MA, Kern-Isberner G, Simari GR. Explanations, belief revision and defeasible reasoning. Artificial Intelligence. 2002;141(1–2):1–28.

5. Capobianco M, Chesñevar CI, Simari GR. An argument-based framework to model an agent’s beliefs in a dynamic environment. In: Proceedings of the 1st International Workshop on Argumentation in Multi-Agent Systems. 2005;95–110.

6. Capobianco M, Chesñevar CI, Simari GR. Argumentation and the dynamics of warranted beliefs in changing environments. Journal of Autonomous Agents and Multi-Agent Systems. 2005;11(2):127–151.

7. Rotstein ND, Moguillansky MO, García AJ, Simari GR. An abstract argumentation framework for handling dynamics. In: Proceedings of the 12th International Workshop on Non-Monotonic Reasoning. 2008;131–139.

8. Moguillansky MO, Rotstein ND, Falappa MA, García AJ, Simari GR. Argument theory change applied to defeasible logic programming. In: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. 2008;132–137.

9. Falappa MA, Kern-Isberner G, Simari GR. Belief revision and argumentation theory. In: Argumentation in Artificial Intelligence. 2009;341–360.

10. Amgoud L. A formal framework for handling conflicting desires. In: Proceedings of the 7th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty. 2003;552–563.

11. Modgil S, Luck M. Argumentation based resolution of conflicts between desires and normative goals. In: Proceedings of the 5th International Workshop on Argumentation in Multi-Agent Systems. 2009;19–36.

12. Gaertner D, Rodríguez-Aguilar JA, Toni F. Agreeing on institutional goals for multi-agent societies. In: Proceedings of the COIN@AAAI’08 Workshop. 2009;1–16.

13. Liao B, Huang H. An argumentation-based flexible agent with dynamic rules of inference. In: Proceedings of the 21st International Conference on Tools with Artificial Intelligence. 2009;284–291.

14. Kakas AC, Moraïtis P. Argumentation based decision making for autonomous agents. In: Proceedings the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems. 2003;883–890.

15. Fox J, Glasspool D, Grecu D, Modgil S, South M, Patkar V. Argumentation-based inference and decision making-medical perspective. IEEE Intelligent Systems. 2007;22(6):34–41.

16. Amgoud L, Vesic S. On revising argumentation-based decision systems. In: Proceedings of the 10th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty. 2009;71–82.

17. Amgoud L, Prade H. Using arguments for making and explaining decisions. Artificial Intelligence. 2009;173(3–4):413–436.

18. Matt P-A, Toni F, Vaccari J. Dominant decisions by argumentation agents. In: Proceedings of the 6th International Workshop on Argumentation in Multi-Agent Systems. 2010;42–59.

19. Parsons S, Sierra CA, Jennings NR. Agents that reason and negotiate by arguing. Journal of Logic and Computation. 1998;8(3):261–292.

20. Kraus S, Sycara K, Evenchik A. Reaching agreements through argumentation: a logical model and implementation. Artificial Intelligence. 1998;104(1–2):1–69.

21. Amgoud L, Parsons S, Maudet N. Argument, dialogue and negotiation. In: Proceedings of the 14th European Conference on Artificial Intelligence. 2000;338–342.

22. Rahwan I, Ramchurn SD, Jennings NR, McBurney P, Parsons S, Sonenberg L. Argumentation-based negotiation. Knowledge Engineering Review. 2003;18(4):343–375.

23. Amgoud L, Dimopoulos Y, Moraitis P. A general framework for argumentation-based negotiation. In: Proceedings of the 4th International Workshop on Argumentation in Multi-Agent Systems. 2008;1–17.

24. Falappa MA, García AJ, Simari GR. Belief dynamics and defeasible argumentation in rational agents. In: Proceedings of the 10th International Workshop on Non-Monotonic Reasoning. 2004;164–170.

25. Liao B, Huang H. ANGLE: an autonomous, normative and guidable agent with changing knowledge. Information Sciences. 2010;180(17):3117–3139.

26. Coste-Marquis S, Devred C, Konieczny S, Lagasquie-Schiex M, Marquis P. On the merging of Dung’s argumentation systems. Artificial Intelligence. 2007;171(10–15):730–753.

27. Boella G, Kaci S, van der Torre L. Dynamics in argumentation with single extensions: abstraction principles and the grounded extension. In: Proceedings of the 10th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty. 2009;107–118.

28. Cayrol C, de St-Cyr FD, Lagasquie-Schiex M. Revision of an argumentation system. In: Proceedings of the 11th International Conference on the Principles of Knowledge Representation and Reasoning. 2008;124–134.

29. Baroni P, Giacomin M, Guida G. SCC-recursiveness: a general schema for argumentation semantics. Artificial Intelligence. 2005;168(1–2):162–210.

30. Baroni P, Giacomin M. On principle-based evaluation of extension-based argumentation semantics. Artificial Intelligence. 2007;171(10–15):675–700.

31. D.V. Carbogim, Dynamics on Formal Argumentation, Ph.D Thesis, University of Edinburgh, 2000.

32. Prakken H. Relating protocols for dynamic dispute with logics for defeasible argumentation. Synthese. 2001;127(1–2):187–219.

33. Okuno K, Takahashi K. Argumentation system with changes of an agent’s knowledge base. In: Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence. 2009;226–232.

34. Boella G, Kaci S, van der Torre L. Dynamics in argumentation with single extensions: attack refinement and the grounded extension. In: Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems. 2009;1213–1214.