Argumentation frameworks as constraint satisfaction problems
Tóm tắt
Argumentation is a promising approach for defeasible reasoning. It consists of justifying each plausible conclusion by arguments. Since the available information may be inconsistent, a conclusion and its negation may both be justified. The arguments are thus said to be conflicting. The main issue is how to evaluate the arguments. Several semantics were proposed for that purpose. The most important ones are: stable, preferred, complete, grounded and admissible. A semantics is a set of criteria that should be satisfied by a set of arguments, called extension, in order to be acceptable. Different decision problems related to these semantics were defined (like whether an argumentation framework has a stable extension). It was also shown that most of these problems are intractable. Consequently, developing algorithms for these problems is not trivial and thus the implementation of argumentation systems not obvious. Recently, some solutions to this problem were found. The idea is to use a reduction method where a given problem is translated in another one like SAT or ASP. This paper follows this line of research. It studies how to encode the problem of computing the extensions of an argumentation framework (under each of the previous semantics) as a constraint satisfaction problem (CSP). Such encoding is of great importance since it makes it possible to use the very efficient solvers (developed by the CSP community) for computing the extensions. Our encodings take advantage of existing reductions to SAT problems in the case of Dung’s abstract framework. Among the various ways of translating a SAT problem into a CSP one, we propose the most appropriate one in the argumentation context. We also provide encodings in case two other families of argumentation frameworks: the constrained version of Dung’s abstract framework and preference-based argumentation framework.
Tài liệu tham khảo
Rahwan, I., Simari, G. (eds.): Argumentation in Artificial Intelligence. Springer (2009)
Amgoud, L., Cayrol, C.: A reasoning model based on the production of acceptable arguments. Ann. Math. Artif. Intell. 34, 197–216 (2002)
Amgoud, L., Devred, C., Lagasquie, M.: Generating possible intentions with constrained argumentation systems. Int. J. Approx. Reason. 52(9), 1363–1391 (2011)
Bench-Capon, T.J.M.: Persuasion in practical argument using value-based argumentation frameworks. J. Log. Comput. 13(3), 429–448 (2003)
Bennaceur, H.: A comparison between sat and csp techniques. Constraints 9, 123–138 (2004)
Bentahar, J., Maamar, Z.: Complexity results for argumentation-based agent communication. In: IEEE International Conference on Innovations in Information Technology, pp. 506–510 200 (2007)
Besnard, P., Doutre, S.: Checking the acceptability of a set of arguments. In: NMR, pp. 59–64 (2004)
Bistarelli, S., Santini, F.: A common computational framework for semiring-based argumentation systems. In: ECAI, pp. 131–136 (2010)
Bordeaux, L., Hamadi, Y., Zhang, L.: Propositional satisfiability and constraint programming: A comparative survey. ACM Comput. Surv. 38(4), 1–54 (2006)
Caminada, M.: Semi-stable semantics. In: Proceedings of the 1st International Conference on Computational Models of Argument (COMMA’06), pp. 121–130 (2006)
Castell, T., Fargier, H.: Propositional satisfaction problems and clausal csps. In: ECAI, pp. 214–218 (1998)
Cayrol, C., Doutre, S., Mengin, J.: On decision problems related to the preferred semantics for argumentation frameworks. J. Log. Comput. 13(3), 377–403 (2003)
Cooper, M.: An optimal k-consistency algorithm. Artif. Intell. 41(1), 89–95 (1989)
Coste-Marquis, S., Devred, C., Marquis, P.: Constrained argumentation frameworks. In: KR, pp. 112–122 (2006)
Creignou, N.: The class of problems that are linearly equivalent to satisfiability or a uniform method for proving np-completeness. Theor. Comput. Sci. 145(1 & 2):111–145 (1995)
Dechter, R., Meiri, I., Pearl, J.: Temporal constraint networks. In: KR, pp. 83–93 (1989)
Devred, C., Doutre, S., Lefèvre, C., Nicolas, P.: Dialectical proofs for constrained argumentation. In: COMMA, pp. 159–170 (2010)
Dimopoulos, Y., Nebel, B., Toni, F.: Preferred arguments are harder to compute than stable extensions. In: IJCAI’99, pp. 36–43 (1999)
Dimopoulos, Y., Nebel, B., Toni, F.: Finding admissible and preferred arguments can be very hard. In: KR’00, pp. 53–61 (2000)
Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77, 321–357 (1995)
Dung, P.M., Mancarella, P., Toni, F.: Computing ideal skeptical argumentation. Artif. Intell. 171, 642–674 (2007)
Dunne, P.: Computational properties of argument systems satisfying graph-theoretic constraints. Artif. Intell. 171(10–15), 701–729 (2007)
Dunne, P., Hunter, A., McBurney, P., Parsons, S., Wooldridge, M.: Inconsistency tolerance in weighted argument systems. In: AAMAS, pp. 851–858 (2009)
Dunne, P., Wooldridge, M.: Complexity of abstract argumentation. In: Rahwan, I., Simari, G. (eds.) Chapter 5 of Argumentation in Artificial Intelligence, pp. 85–104 (2009)
Egly, U., Gaggl, S., Woltran, S.: ASPARTIX: Implementing argumentation frameworks using answer-set programming. In: International Conference on Logic Programming, pp. 734–738 (2008)
Feder, T.: Network flow and 2-satisfiability. Algorithmica, 11(3), 291–319 (1994)
Freuder, E.: Temporal constraint networks. In: IJCAI, pp. 278–283 (1989)
Krom, M.: The decision problem for a class of first-order formulas in which all disjunctions are binary. eitschrift für Mathematische Logik und Grundlagen der Mathematik 13, 15–20 (1967)
Kumar, V.: Depth-first search. Encyclopaedia of Artificial Intelligence 2, 1004–1005 (1987)
Lifschitz, V.: Answer set programming and plan generation. Artif. Intell. 138, 39–54 (2002)
Mbarki, M., Bentahar, J., Moulin, B.: Specification and complexity of strategic-based reasoning using argumentation. Argumentation in Multi-Agent Systems. LNAI 4766, 142–160 (2006)
Nadel, B.: Some applications of the constraint satisfaction problem. Technical report, Wayne state university (1990)
Régin, J-C.: Generalized arc consistency for global cardinality constraint. In: Proceedings of the National Conference on Artificial Intelligence, pp. 209–215 (1996)
Rossi, F., van Beek, P., Walsh, T.: Handbook of constraint programming (foundations of artificial intelligence). Elsevier Science Inc. New York, NY, USA (2006)
Tsang, E.: Foundations of Constraint Satisfaction. Academic Press. ISBN 0-12-701610-4 (1993)
Walsh, T.: SAT v CSP. In: International Conference on Principles and Practice of Constraint Programming (CP 2000), pp. 441–456 (2000)
Westphal, M., Wolfl, S.: Qualitative csp, finite csp, and sat: Comparing methods for qualitative constraint-based reasoning. In: International Joint Conference on Artificial Intelligence, pp. 628–633 (2009)