Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-06T10:10:18.988Z Has data issue: false hasContentIssue false

A review of current defeasible reasoning implementations

Published online by Cambridge University Press:  01 September 2008

DANIEL BRYANT
Affiliation:
Department of Computing, University of Surrey, Guildford, Surrey, UK; e-mail: [email protected], [email protected]
PAUL KRAUSE
Affiliation:
Department of Computing, University of Surrey, Guildford, Surrey, UK; e-mail: [email protected], [email protected]

Abstract

This article surveys existing practical implementations of both defeasible and argumentation-based reasoning engines and associated literature. We aim to summarize the current state of the art in the research area, show that there are many similiarities and connections between the various implementations and also highlight the differences regarding evaluation goals and strategies. An important goal of this paper is to argue for the need for well-designed empirical evaluations, as well as formal complexity analysis, in order to justify the practical applicability of a reasoning engine. There are indeed many challenges to be faced in developing implementations of argumentation. Not least of these is the inherent computational complexity of the formal models. We cover some of the ways these challenges have been addressed, and provide pointers for future directions in realizing the goal of practical argumentation.

Type
Articles
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alferes, J. J. & Pereira, L. M. 1996 Reasoning with Logic Programming. New York: Springer-Verlag.CrossRefGoogle Scholar
Amgoud, L. & Prade, H. 2004 Using arguments for making decisions: a possibilistic logic approach. In AUAI '04: Proceedings of the 20th conference on Uncertainty in artificial intelligence. Arlington, Virginia: AUAI Press, pp. 10–17.Google Scholar
Antoniou, G. 1997 Nonmonotonic Reasoning. MIT Press.CrossRefGoogle Scholar
Antoniou, G. & Bikakis, A. 2007 Dr-prolog: A system for defeasible reasoning with rules and ontologies on the semantic web. IEEE Transactions on Knowledge and Data Engineering 19(2), 233245.CrossRefGoogle Scholar
Antoniou, G., Billington, D., Governatori, G. & Maher, M. J. 2001 Representation results for defeasible logic. ACM Transactions on Computational Logic 2(2), 255287.CrossRefGoogle Scholar
Bench-Capon, T. J. M. 2003 Persuasion in practical argument using value-based argumentation frameworks. Journal of Logic Computation 13(3), 429448.CrossRefGoogle Scholar
Besnard, P. & Hunter, A.Elements of Argumentation. In preparation, 2008.CrossRefGoogle Scholar
Billington, D. & Rock, A. 2001 Propositional plausible logic: Introduction and implementation. Studia Logica 67(2), 243269.CrossRefGoogle Scholar
Bondarenko, A., Dung, P. M., Kowalski, R. & Toni, F. 1997 An abstract, argumentation-theoretic approach to default reasoning. Artificial Intelligence 93(1–2), 63101.CrossRefGoogle Scholar
Boolos, G., Burgess, J. & Jeffrey, R. 2002 Computability and Logic. Cambridge University Press.CrossRefGoogle Scholar
Bryant, D. & Krause, P. J. 2006 An implementation of a lightweight argumentation engine for agent applications. In Proceedings of 10th European Conference on Logics in Artificial Intelligence (JELIA06), vol. 4160 of LNAI. Springer, pp. 469–472.Google Scholar
Bryant, D., Krause, P. J. & Vreeswijk, G. 2006 Argue tuprolog: A lightweight argumentation engine for agent applications. In Proceedings of the 1st International Conference on Computational Models of Argument (COMMA06). IOS Press, pp. 27–32.Google Scholar
Capobianco, M. & Chesnevar, C. I. 1999 Introducing dialectical bases in defeasible argumentation. In Proceedings of the 6th Workshop on Aspectos Teoricos de la Inteligencia Artificial (ATIA), San Juan, Argentina, pp. 1–10.Google Scholar
Capobianco, M., Chesnevar, C. & Simari, G. 2004 An argument-based framework to model an agent's beliefs in a dynamic environment. In Proceedings of the First International Workshop on Argumentation in Multiagent Systems. AAMAS 2004.Google Scholar
Capobianco, M., Chesnevar, C. I. & Simari, G. R. 2005 Argumentation and the dynamics of warranted beliefs in changing environments. Autonomous Agents and Multi-Agent Systems 11(2), 127151.CrossRefGoogle Scholar
Causey, R. L. 1994 Evid: A system for interactive defeasible reasoning. Decision Support Sytems 11(2), 103131.CrossRefGoogle Scholar
Causey, R. L. 2003 Computational dialogic defeasible reasoning. Argumentation 17(4), 421450.CrossRefGoogle Scholar
Cayrol, C., Doutre, S. & Mengin, J. 2001 Dialectical proof theories for the credulous preferred semantics of argumentation frameworks. In ECSQARU '01: Proceedings of the 6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, London, UK: Springer-Verlag, pp. 668–679.Google Scholar
Cayrol, C., Doutre, S. & Mengin, J. 2003 On decision problems related to the preferred semantics for argumentation frameworks. Journal of Logic Computation 13(3), 377403.CrossRefGoogle Scholar
Cecchi, L. A., Fillottrani, P. R. & Simari, G. R. 2006 On the complexity of deLP through game semantics. In Dix, J. & Hunter, A. (eds.). Proceedings of the 11th International Workshop on Nonmonotonic Reasoning (NMR 2006). IfI Technical Report Series, Clausthal University, pp. 386–384.Google Scholar
Chesnevar, C. I. & Maguitman, A. G. 2004 Arguenet: an argument-based recommender system for solving web search queries. In Proceedings. 2004 2nd International IEEE Conference in Intelligent Systems, pp. 282–287.Google Scholar
Chesnevar, C. I., Maguitman, A. G. & Loui, R. P. 2000a Logical models of argument. ACM Computing Surveys, 32(4), 337383.CrossRefGoogle Scholar
Chesnevar, C. I., Simari, G. R. & Garca, A. J. 2000b Pruning search space in defeasible argumentation. In Proceedings of the Workshop on Advances and Trends in Search in Artificial Intelligence, pp. 40–47.Google Scholar
Chisholm, R. 1997 Theory of Knowledge. New Jersey: Prentice-Hall.Google Scholar
Cholewinski, P., Marek, V. W., Mikitiuk, A. & Truszczyński, M. 1999 Computing with default logic. Artificial Intelligence 112(1–2), 105146.CrossRefGoogle Scholar
Colmerauer, A., Kanoui, H., Roussel, P. & Pasero, R. 1973 Un systeme de communication homme-machine en francais. Technical report, Groupe de Recherche en Intelligence Artificielle, Universite d'Aix-Marseille II.Google Scholar
Covington, M. A. 2000 Logical control of an elavator with defeasible logic. IEEE Transactions on Automatic Control 45(7), 13471349.CrossRefGoogle Scholar
Denti, E., Omicini, A. & Ricci, A. 2001 tuProlog: A light-weight prolog for internet applications and infrastructures. In Symposium on Practical Aspects of Declarative Languages (PADL), 184198.Google Scholar
Denti, E., Omicini, A. & Ricci, A. 2005 Multi-paradigm java-prolog integration in tuProlog. Science of Computer Programming. 57(2), 217250.CrossRefGoogle Scholar
Dimopoulos, Y., Nebel, B. & Toni, F. 2000 Finding admissible and preferred arguments can be very hard. In Cohn, A. G., Giunchiglia, F. & Selman, B. (eds.). KR2000: Principles of Knowledge Representation and Reasoning, San Francisco: Morgan Kaufmann, pp. 53–61.Google Scholar
Dimopoulos, Y., Nebel, B. & Toni, F. 2002 On the computational complexity of assumption-based argumentation for default reasoning. Artificial Intellegence 141(1), 5778.CrossRefGoogle Scholar
Dimopoulos, Y. & Torres, A. 1996 Graph theoretical structures in logic programs and default theories. Theoretical Computer Science. 170(1–2), 209244.CrossRefGoogle Scholar
Dowling, W. F. & Gallier, J. H. 1984 Linear-time algorithms for testing the satisfiability of propositional horn formulae. Journal of Logic Programming 1, 267284.CrossRefGoogle Scholar
Dung, P. M. 1995 On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence 77(2), 321358.CrossRefGoogle Scholar
Dung, P. M., Kowalski, R. A. & Toni, F. 2006 Dialectic proof procedures for assumption based admissible argumentation frameworks. Artificial Intelligence 170(2), 114159.CrossRefGoogle Scholar
Dunne, P. E. & Bench-Capon, T. J. M. 2002 Coherence infinite argument systems. Artificial Intelligence 141(1), 187203.CrossRefGoogle Scholar
Gaertner, D. & Toni, F. 2007 Casapi—a system for credulous and sceptical argumentation. In Proceedings of First International Workshop on Argumentation and Nonmonotonic Reasoning, Arizona, USA.Google Scholar
Garcia, A., Gollapally, D., Tarau, P. & Simari, G. 2000 Deliberative stock market agents using jinni and defeasible logic programming. In In Proceedings of the ECAI Workshop on Engineering Societies in the Agents. Springer Verlag.Google Scholar
Garcia, A. & Simari, G. R. 1999 Parallel defeasible argumentation. Journal of computer science and technology special issue: Artificial intelligence and evolutive computation. 1(2), 4557.Google Scholar
Garcia, A. J. & Simari, G. R. 2004 Defeasible logic programming: an argumentative approach. Theory and Practice of Logic Programming 4(2), 95138.CrossRefGoogle Scholar
García, A. J., Rotstein, N. D. & Simari, G. R. 2007 Dialectical Explanations in Defeasible Argumentation. In Proceedings of the Ninth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU-07). Springer LNCS, pp. 295–307.Google Scholar
Garey, M. & Johnson, D. 1979 Computers and Intractability. New York: W. H. Freeman.Google Scholar
Gelfond, M. & Lifschitz, V. 1991 Classical negation in logic programs and disjunctive databases. New Generation Computing 9(3/4), 365386.CrossRefGoogle Scholar
Haenni, R. 2001 Cost-bounded argumentation. International Journal of Approximate Reasoning 26, 101127(27).CrossRefGoogle Scholar
Jakobovits, H. & Vermeir, D. 1999 Dialectic semantics for argumentation frameworks. In Proceedings of the 7th International Conference on Artificial Intelligence and Law. ACM Press, pp. 53–65.Google Scholar
Kowalski, R. 1979 Algorithm = logic + control. Communications of the ACM 22, 424436.CrossRefGoogle Scholar
Loui, R. & Simari, G. 1994 NATHAN (Spec13): Argues defeasibly in first-order logic. www.cs.cmu.edu/afs/cs/project/airepository/ai/areas/reasonng/defeasbl/nathan/0.html. Last accessed: 13th February 2007.Google Scholar
Loui, R. P., Norman, J., Olson, J. & Merrill, A. 1993 A design for reasoning with policies, precedents, and rationales. In ICAIL '93: Proceedings of the 4th International Conference on Artificial Intelligence and Law. New York, NY: ACM Press, pp. 202–211.Google Scholar
Loyd, J. 1984 Foundations of Logic Programming. Springer-Verlag.CrossRefGoogle Scholar
Maher, M. J., Rock, A., Antoniou, G., Billington, D. & Miller, T. 2001a Deimos. available from www.cit.gu.edu.au/arock/defeasible/Defeasible.cgi. Last accessed: 10 September 2006.Google Scholar
Maher, M. J., Rock, A., Antoniou, G., Billington, D. & Miller, T. 2001b Efficient defeasible reasoning systems. International Journal on Artificial Intelligence Tools, 10(4), 483501.CrossRefGoogle Scholar
Nudelman, E. 2005 Empirical Approaches to the Complexity of Hard Problems. PhD thesis, Stanford University, Stanford, CA.Google Scholar
Nute, D. 1988 Defeasible reasoning and decision support systems. Decision Support Systems 4(1), 97110.CrossRefGoogle Scholar
Nute, D. 1993 Defeasible prolog. In Proceedings of AAAI Fall Symposium on Automated Deduction in Nonstandard Logics, (Technical Report FS-93-01), pp. 105–112.Google Scholar
Nute, D. 1994 Defeasible logic. In Gabbay, D., Hogger, C. J. & Robinson, J. A. (eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 3: Nonmonotonic Reasoning and Uncertain Reasoning, Oxford: Oxford University Press, pp. 353–395.Google Scholar
Nute, D., Mann, R. I. & Brewer, B. F. 1990 Controlling expert system recommendations with defeasible logic. Decision Support Systems 6(2), 153164.CrossRefGoogle Scholar
Pollock, J. L. 1995 Cognitive Carpentry: A Blueprint for how to build a person. MIT Press, A Bradford Book, USA.CrossRefGoogle Scholar
Pollock, J. L. 1992 How to reason defeasibly. Artificial Intelligence 57(1), 142.CrossRefGoogle Scholar
Pollock, J. L. 1999 Rational cognition in OSCAR. In Workshop of Agent Theories, Architectures, and Languages, pp. 71–90.Google Scholar
Prakken, H. & Vresswijk, G. 2002 Logics for defeasible argumentation. In Gabbay, D. & Guenthner, F. (eds.), Handbook of Philosophical Logic, 2nd edn.The Netherlands: Kluwer Academic Publishers, pp. 218–319.Google Scholar
Rock, A. 2006a Deimos: A Query Answering Defeasible Logic System. www.cit.gu.edu.au/arock/defeasible/doc/Deimos-short.pdf Last accessed: 19th November 2006.Google Scholar
Rock, A. 2006b Phobos. Available from www.cit.gu.edu.au/arock/plausible/Plausible.cgi. Last accessed: 10 September 2006.Google Scholar
Rock, A. 2006c Phobos (Version 2): A Query Answering Plausible Logic System. www.cit.gu.edu.au/arock/plausible/doc/Phobos-short.pdf Last accessed: 19th November 2006.Google Scholar
Rock, A. & Billington, D. 2000 An implementation of propositional plausible logic. In Proceedings of 23rd Australasian Computer Science Conference, 2000. ACSC 2000. IEEE Press, pp. 204–210.Google Scholar
Russell, S. J. & Norvig, P. 2003 Artificial Intelligence: A Modern Approach, 2nd edn.Prentice HallGoogle Scholar
Schroeder, M. 1999 An efficient argumentation framework for negotiating autonomous agents. In MAAMAW '99: Proceedings of the 9th European Workshop on Modelling Autonomous Agents in a Multi-Agent World. London, UK: Springer-Verlag, pages 140–149.Google Scholar
Shortliffe, D. A. 1976 MYCIN: Computer-Based Medical Consultations. Elsevier.Google Scholar
Simari, G. & Loui, R. 1982 Mathematical treatment of defeasible reasoning and its implementation. Artificial Intelligence 53(2–3), 125157.CrossRefGoogle Scholar
Simari, G. R. 1989 A Mathematical Treatment of Defeasible Reasoning and its Implementation. PhD thesis, Washington University in Saint Louis.Google Scholar
Sun Microsystems. 2007 Welcome to NetBeans. Available from www.netbeans.org/ Last accessed: 10 September 2007.Google Scholar
Tarau, P. 1999 Jinni: Intelligent mobile agent programming at the intersection of java and prolog. In Proceedings of the Fourth International Conference on the Practical Application of Intelligent Agnets and Multi-Agents, London, UK, pp. 109–123.Google Scholar
Tolchinsky, P., Modgil, S., Cortes, U. & Sanchez-Marre, M. 2006 Cbr and argument schemes for collaborative decision making. In Proceedings of 1st International Conference on Computational Models of Argument (COMMA06). IOS Press.Google Scholar
Van Gelder, A., Ross, K. A. & Schlipf, J. S. 1991 The well-founded semantics for general logic programs. Journal of the ACM 38(3), 620650.CrossRefGoogle Scholar
Vreeswijk, G. 1993a IACAS: An Interactive Argumentation System—User Manual Version 1.0. http://citeseer.ist.psu.edu/195813.html. Last accessed: 19th November 2006.Google Scholar
Vreeswijk, G. 1993b Studies in Defeasible Argumentation. PhD thesis, Free University of Amsterdam, The Netherlands.Google Scholar
Vreeswijk, G. A. W. 1995 IACAS: an implementation of Chisholm's principles of knowledge. In The Proceedings of the 2nd Dutch/German Workshop on Nonmonotonic Reasoning, Utrecht., pp. 225–234.Google Scholar
Vreeswijk, G. A. W. 2006a Vreeswijk's Admissible Defence Sets. Available from www:cs:uu:nl/gv/code/grdadm/ Last accessed: 29 September 2006.Google Scholar
Vreeswijk, G. A. W. 2006b An algorithm to compute minimaly grounded and admissible defence sets. In Proceedings of 1st International Conference on Computational Models of Argument (COMMA06), IOS Press, pp. 109–120.Google Scholar
Vreeswijk, G. A. W. 2006c Argumentation System (AS). Available from www.cs.uu.nl/people/gv/code/AS/ Last accessed: 10 September 2006.Google Scholar