Keywords

argumentation; artificial intelligence; computational complexity; incompleteness; inconsistency; non-monotonic formalisms; uncertainty

1.1 Background

In the area of artificial intelligence, one of the most important topics is to handle the uncertainty, incompleteness, and inconsistency of information. There are a lot of applications related to this topic, such as belief revision, decision-making, inter-agent communication, medical reasoning, legal reasoning, semantic web reasoning, trust computing and normative systems, etc.

When an agent is situated in an open and dynamic environment, since the world can be other than what it appears and the world changes [1], what the agent perceives is far from veridical and complete. As a result, the existing beliefs of an agent may conflict with some new information. So, belief revision is necessary for a rational agent to preserve the consistency of her knowledge. Related to belief revision, decision-making is a form of reasoning to determine actions. Given some available information about the current status of the world and the consequences of potential actions, there could be more than one alternative [2]. Since the available information may be incomplete and uncertain and different alternatives could not be selected simultaneously, conflicts may arise in the process of decision-making. For instance, in medical reasoning, knowledge can be uncertain and inconsistent [3], and more than one explanation for a medical hypothesis could be possible based on different medical studies [4]; in norm-governed systems, an agent may have several conflicting motivations, including internal desires and external obligations that are brought about by norms and policies [5].

In multi-agent systems, different agents interact with each other to achieve certain goals. When agents have competing claims on scarce resources (such as commodities, services, time, money, etc.), not all of them can be simultaneously satisfied. First, for those agents that have conflicting interests and a desire to cooperate, negotiation is an important coordination mechanism [6]. Due to the conflicting interests and uncertain information from the environment, how to formulate the mechanisms of negotiation is still an open problem. Second, for those agents that have opposite goals, argumentation is a form of reasoning for each agent to pursue her own goals. Legal argumentation is a typical example. It is adversarial and dialectic in nature [7]. Since argumentation schemes (a kind of generalized rules of inference) need not concern strict, abstract, necessarily valid patterns of reasoning, but can be defeasible, concrete and contingently valid, the conclusions of different schemes could be conflicting and defeasible [8].

In addition, for some practical reasoning systems in open and dynamic environments, such as semantic web [9] and trust computing [10], inconsistencies of information are also very common. For instance, in semantic web, domain ontologies established by different parties may conflict. In trust computing, both the information and its sources are uncertain. The conflicts among them are inevitable.

In order to treat with the uncertainty, incompleteness, and inconsistency of information, a number of research efforts have been made in the area of non-monotonic reasoning. In the 1980s, three non-monotonic formalisms (including default logic [11], circumscription [12] and autoepistemic logic [13]) were proposed. However, these formalisms are mainly suitable for epistemic reasoning. For practical reasoning and the reasoning in the process of multi-agent interaction, a more general non-monotonic formalism is needed. Meanwhile, from the perspective of implementation, the computational complexity problems of these formalisms are challenging. Furthermore, when considering the dynamics of systems (when new information is added to a system), the efficiency of computation is a great problem. This is because when a system is updated, any conclusions obtained previously could be overruled by some counter-arguments. So, for each modification, all existing conclusions should be recomputed. This is obviously inefficient.

1.2 The Notion of Argumentation

Due to the above-mentioned problems, in the past fifteen years, argumentation has been recognized as a non-monotonic formalism that is more general and natural than the traditional ones. In general, the study of argumentation may, informally, be considered as concerned with how assertions are proposed, discussed, and resolved in the context of disagreement [14].

The disagreement (inconsistency) may arise during the process of reasoning of an individual agent, or a set of agents interacting with each other. In different cases, the nature of inconsistency may vary. As mentioned above, in the process of epistemic reasoning (belief revision), the inconsistency of information is mainly due to the uncertainty and incompleteness of information. In the case of practical reasoning (decision-making, planning, etc.), an agent may have several motivations (desires, obligations, etc.). Due to the limitation of resources, the agent can not fulfil all of them, and the conflicts among different motivations arise. In means-end reasoning, there exist different options, which could be conflicting. In the case of inter-agent communication, such as negotiation and discussion, the interests, objectives, preferences or standpoints of different participants might be inconsistent.

Despite the fact that various arguments may have different internal structures and the nature of inconsistence between different kinds of arguments may vary, when evaluating the status of arguments, we may regard the attacks between arguments as abstract binary relations. Based on this idea, in 1995, Phan Ming Dung proposed an abstract argumentation theory, in which arguments are abstract entities, while the origins of attacks are also left unknown [15]. As a result, an argument system is simply represented as a directed graph (called a defeat graph), represented as , where denotes a set of arguments and denotes a set of attacks.

Since the status of arguments is evaluated in an abstract argumentation framework, while the representation of underlying knowledge, the construction of arguments and the identification of attacks are comparatively independent, an argumentation system can be conceived of a two-level architecture (Figure 1.1.), and its working process is composed of three steps. First, according to a set of underlying knowledge, a set of arguments are constructed and the attacks between them are identified, forming an argumentation framework. Second, given an argumentation framework, the status of arguments is evaluated (in terms of certain criteria), producing sets of extensions of arguments (each extension could be understood as a set of arguments that are acceptable together). Third, for each extension of arguments, the associated set of conclusions is identified.

Let us consider the following example.

Since abstract argumentation is comparatively independent of the underlying argument construction and comparison, it shows great promise as a theoretical tool for handling the various reasoning problems under the context of inconsistency. It is not only suitable for the reasoning of individual agents, but also for the interactions of multiple agents. As a result, argumentation is now regarded as a non-monotonic formalism for logical deduction, induction, abduction and plausible reasoning, and is promising to be applied to various applications, such as semantic web, recommender systems, trust computing, normative systems, social choice theory, judgment aggregation, law and medical, etc.

1.3 Motivations of this Book

Given an argumentation framework , a basic problem is to determine which arguments can be regarded as acceptable together. In order to resolve this problem, a lot of evaluating criteria (often called argumentation semantics) have been proposed. Some typical argumentation semantics include admissible, complete, preferred, grounded, stable, semi-stable, ideal and eager, etc. Each semantics stands for a set of criteria. For instance, a set of arguments is regarded as admissible, if it is conflict-free and it is able to defend each argument in it. Informally, we say that is conflict-free, it there exist no arguments such that attacks ; an argument is defended by , if for every argument that attacks then there exists an argument such that attacks . Definitions of some other semantics will be presented in the next chapter.

Under many semantics, determining the status of arguments is often not easy. It has been proved that many natural questions regarding argument acceptability are, in general, computationally intractable [16]. For this reason, in recent years, an increasing amount of work has been done on identifying tractable fragments of argumentation frameworks and developing more efficient algorithms [17,18]. However, how to efficiently compute the semantics of a generic argumentation framework is still an open problem.

In order to efficiently compute the semantics of a generic argumentation framework, the following two lines of work have been undertaken. The first line of work is on developing efficient approaches by exploiting existing sophisticated problem solvers that have been developed for other purposes. According to existing literature, the approaches based on propositional logic [19–22] and answer-set programming [23–25], respectively, have been widely studied. They are also called reduction-based approaches, which reduce an abstract argumentation problem into an instance of a different problem (SAT or ASP), delegating the burden of computation to existing systems. Thanks to the efficiency of the solvers for SAT or ASP problems, the corresponding argumentation problems could be resolved more efficiently. The second line of work is on establishing efficient approaches dedicated to argumentation, including labelling-based approaches [26–28] and dialogue games [26,29]. These approaches implement procedures for abstract argumentation from scratch, and therefore are called direct approaches. By adopting some specific techniques, the efficiency of direct approaches could be improved to some extent [27].

Although the above-mentioned two lines of work have made great efforts to improve the efficiency of computation, they all treat each argumentation framework as a monolithic entity, which may fundamentally restrict the improvement of efficiency. On the contrary, if we compute the status of arguments locally, then the computation may become easier. Let us consider the following three examples.

First, for most argumentation systems, changing of arguments and their attack relation is an intrinsic property of them. When an argumentation system is modified, if we recompute the status of each argument afresh, it is obviously inefficient. As a matter of fact, for each modification to an argumentation system, it is very common that only a part of arguments in the system are affected. Hence, if it is feasible to evaluate the status of those affected arguments locally, then the remaining arguments are not necessary to be considered.

Second, according to [16], although for some argumentation frameworks with special structures (such as acyclic, symmetric and bounded tree-width) there exist tractable algorithms, for a generic argumentation framework that might not belong to any tractable class, how to efficiently compute its semantics still remains unresolved. A promising solution is to decompose a general argumentation framework into a set of sub-frameworks, such that the status of each argument in a sub-framework could be computed locally. Given that the status of each argument is computed in a sub-framework, which might belong to some tractable class and has smaller size than that of the original argumentation framework, the execution time for evaluating the status of arguments might decrease.

Third, when querying the status of some arguments in an argumentation framework, we may only take into consideration a subset of arguments in the argumentation framework that are relevant to these arguments. In other words, the computation of the status of some arguments is performed locally.

From the above three examples, we observe that local computation could be an effective means to decrease the computation time in many situations. This is due to the following two reasons. In the first place, compared to the size of a whole argumentation framework, the size of a sub-framework is often smaller or much smaller. This idea has been adopted in divide-and-conquer algorithms, which have been recognized as an important algorithm design paradigm. In the second place, when an argumentation framework does not belong to any tractable class, some of its sub-frameworks might belong to some tractable classes.

Inspired by the above ideas, this book will introduce efficient approaches for computing the semantics of argumentation based on the theory of local computation.

1.4 The Structure of this Book

This book focuses on formulating efficient approaches for computing the semantics of abstract argumentation frameworks, and is divided into five parts. Besides this part for introduction, the contents of other four parts are as follows.

In Part II, some fundamental theories of argumentation as well as some existing approaches and algorithms for computing argumentation semantics are presented. For readers who are familiar with the area of computational argumentation, this part may be skipped.

In Part III, we introduce a theory of computation based on the idea of local computation. This part consists of two chapters. In Chapter 4, we first introduce the notion and the semantics of sub-frameworks. In Chapter 5, we formulate the relations between the semantics of an argumentation framework (global semantics) and that of a sub-framework (local semantics). This part lays a foundation for the subsequent part.

In Part IV, we formulate three approaches for efficient computation of argumentation from different perspectives. Specifically, Chapter 6 deals with the computation of the status of arguments in a static argumentation framework, Chapter 7 studies the computation of semantics of a dynamic argumentation system, and Chapter 8 deals with the computation of a part of arguments in an argumentation framework.

In Part V, we conclude the book and point out some future work.

References

1. Pollock JL. Perceiving and reasoning about a changing world. Computational Intelligence. 1998;14(4):498–562.

2. Amgoud L, Prade H. Using arguments for making and explaining decisions. Artificial Intelligence. 2009;173:413–436.

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

4. Grando MA, Moss L, Sleeman D, Kinsella J. Argumentation-logic for creating and explaining medical hypotheses. Artificial Intelligence in Medicine. 2013;58(1):1–13.

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

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

7. Bench-Capon T, Prakken H, Sartor G. Argumentation in legal reasoning. In: Rahwan I, Simari GR, eds. Argumentation in Artificial Intelligence. Springer 2009;363–382.

8. Verheij B. Dialectical argumentation with argumentation schemes: an approach to legal logic. Artificial Intelligence and Law. 2003;11(2–3):167–195.

9. Gómez SA, Chesñevar CI, Simari GR. ONTOarg: a decision support framework for ontology integration based on argumentation. Expert Systems with Applications. 2013;40(5):1858–1870.

10. Villata S, Boella G, Gabbay DM, van der Torre L. A socio-cognitive model of trust using argumentation theory. International Journal of Approximate Reasoning. 2013;54(4):541–559.

11. Reiter R. A logic for default reasoning. Artificial Intelligence. 1980;13(1–2):81–132.

12. McCarthy J. Circumscription–a form of non-monotonic reasoning. Artificial Intelligence. 1980;13(1–2):27–39.

13. Moore RC. Semantical considerations on nonmonotonic logic. Artificial Intelligence. 1985;25(1):75–94.

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

15. Dung PM. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence. 1995;77(2):321–357.

16. Dunne PE. Computational properties of argument systems satisfying graph-theoretic constraints. Artificial Intelligence. 2007;171(10–15):701–729.

17. Coste-Marquis S, Devred C, Marquis P. Symmetric argumentation frameworks. In: Proceedings of the Eighth European Conference Symbolic and Quantitative Approaches to Reasoning with Uncertainty. 2005;317–328.

18. Dvořák W, Pichler R, Woltran S. Towards fixed-parameter tractable algorithms for argumentation. In: Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning. 2010;112–122.

19. Arieli O, Caminada M. A general QBF-based formalization of abstract argumentation theory. In: Proceedings of the Fourth Conference on Computational Models of Argument. 2012;105–116.

20. Besnard P, Doutre S. Checking the acceptability of a set of arguments. In: Proceedings of the 10th International Workshop on Non-Monotonic Reasoning. 2004;59–64.

21. Dvořák W, Järvisalo M, Wallner JP, Woltran S. Complexity-sensitive decision procedures for abstract argumentation. In: Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning. 2012;54–64.

22. Egly U, Woltran S. Reasoning in argumentation frameworks using quantified boolean formulas. In: Proceedings of the First Conference on Computational Models of Argument. 2006;133–144.

23. Egly U, Gaggl SA, Woltran S. Answer-set programming encodings for argumentation frameworks. Argument & Computation. 2010;1(2):147–177.

24. Nieves JC, Osorio M, Cortés U. Preferred extensions as stable models. Theory and Practice of Logic Programming. 2008;8(4):527–543.

25. Wakaki T, Nitta K. Computing argumentation semantics in answer set programming. In: Proceedings of the 22nd Annual Conference of the Japanese Society for Artificial Intelligence. 2008;254–269.

26. Modgil S, Caminada M. Proof theories and algorithms for abstract argumentation frameworks. In: Rahwan I, Simari GR, eds. Argumentation in Artificial Intelligence. Springer 2009;105–132.

27. Nofal S, Dunne PE, Atkinson K. On preferred extension enumeration in abstract argumentation. In: Proceedings of the Fourth Conference on Computational Models of Argument. 2012;205–216.

28. Verheij B. A labeling approach to the computation of credulous acceptance in argumentation. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence. 2007;623–628.

29. Thang PM, Dung PM, Hung ND. Towards a common framework for dialectical proof procedures in abstract argumentation. Journal of Logic and Computation. 2009;19(6):1071–1109.