Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các khung lập luận như là các bài toán thỏa mãn ràng buộc
Tóm tắt
Lập luận là phương pháp hứa hẹn cho lý luận có thể bị bác bỏ. Nó bao gồm việc biện minh cho mỗi kết luận hợp lý bằng các lập luận. Vì thông tin có sẵn có thể không nhất quán, một kết luận và sự phủ định của nó có thể đều được biện minh. Do đó, các lập luận được cho là xung đột. Vấn đề chính là làm thế nào để đánh giá các lập luận. Một số ngữ nghĩa đã được đề xuất cho mục đích đó. Những ngữ nghĩa quan trọng nhất là: ổn định, ưa thích, đầy đủ, cơ sở và có thể chấp nhận. Một ngữ nghĩa là một tập hợp các tiêu chí mà một tập hợp lập luận được gọi là mở rộng cần phải thỏa mãn để được chấp nhận. Các bài toán quyết định khác nhau liên quan đến những ngữ nghĩa này đã được định nghĩa (chẳng hạn như việc một khung lập luận có một mở rộng ổn định hay không). Cũng đã được chỉ ra rằng hầu hết các bài toán này là không thể giải quyết với thời gian hợp lý. Do đó, việc phát triển các thuật toán cho những bài toán này không phải là điều tầm thường và việc triển khai các hệ thống lập luận cũng không hề đơn giản. Gần đây, một số giải pháp cho vấn đề này đã được tìm ra. Ý tưởng là sử dụng một phương pháp giảm, trong đó một bài toán cho trước được chuyển đổi thành một bài toán khác như SAT hoặc ASP. Bài báo này theo đuổi hướng nghiên cứu này. Nó nghiên cứu cách mã hóa vấn đề tính toán các mở rộng của một khung lập luận (dưới mỗi ngữ nghĩa trước đó) dưới dạng một bài toán thỏa mãn ràng buộc (CSP). Việc mã hóa này rất quan trọng vì nó cho phép sử dụng các bộ giải rất hiệu quả (được phát triển bởi cộng đồng CSP) để tính toán các mở rộng. Các mã hóa của chúng tôi tận dụng các phép giảm hiện có đối với các vấn đề SAT trong trường hợp khung trừu tượng của Dung. Trong số các cách khác nhau để chuyển đổi một bài toán SAT thành một bài toán CSP, chúng tôi đề xuất cách phù hợp nhất trong bối cảnh lập luận. Chúng tôi cũng cung cấp các mã hóa trong trường hợp của hai họ khác của các khung lập luận: phiên bản bị ràng buộc của khung trừu tượng của Dung và khung lập luận dựa trên sở thích.
Từ khóa
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)