Nested Preferences in Answer Set Programming

• Autorzy: Confalonieri R. , Nieves J.C.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we define a class of nested logic programs, called Nested Logic Programs with Ordered Disjunction (LPODs+), which makes it possible to specify conditional (qualitative) preferences by means of nested preference statements. To this end, we augment the syntax of Logic Programs with Ordered Disjunction (LPODs) to capture more general expressions. We define the LPODs+ semantics in a simple way and we extend most of the results of LPODs showing how our approach generalizes the LPODs framework in a proper way. We also show how the LPODs+ semantics can be computed in terms of a translation procedure that maps a nested ordered disjunction program (OD+-program) into a disjunctive logic program.

Słowa kluczowe

EN

answer set programming; preference handling; nested preferences

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 113, nr 1
• Strony: 19--39
• Opis fizyczny: Bibliogr. 33 poz., tab.

Twórcy

autor

Confalonieri R.

autor

Nieves J.C.

• Universitat Politecnica de Catalunya, Dept. Llenguatges i Sistemes Informatics, Edifici K2M, Despatx 201, C/ Jordi Girona Salgado 1-3, E - 08034 Barcelona, Spain,

Bibliografia

• [1] Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving, Cambridge University Press, 2003.
• [2] Benferhat, S., Brewka, G., Berre, D. L.: On the relation between qualitative choice logic and possibilistic logic, in: Proceedings of the 10th International Conference on Information Processing and Management of Uncertainty (IPMU 2004), 2004, 951-957.
• [3] Benferhat, S., Dubois, D., Prade, H.: Towards a Possibilistic Logic Handling of Preferences, Applied Intelligence, 14(3), 2001, 303-317.
• [4] Bertino, E., Mileo, A., Provetti, A.: PDL with Preferences, in: Proceedings of the Sixth IEEE International Workshop on Policies for Distributed Systems and Networks, 2005, 213-222.
• [5] Bosc, P., Pivert, O., Prade, H.: A Possibilistic Logic View of Preference Queries to an Uncertain Database, in: Proceedings of 19th IEEE International Conference on Fuzzy Systems (FUZZ-IEEE'10), 2010, 581-595.
• [6] Boutilier, C., Brafman, R. I., Domshlak, C., Hoos, H. H., Poole, D.: CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements, Journal of Artificial Intelligence Research, 21(1), 2004, 135-191.
• [7] Brewka, G., Benferhat, S., Le Berre, D.: Qualitative Choice Logic, Artificial Intelligence, 157(1-2), 2004, 203-237.
• [8] Brewka, G., Niemelä, I., Syrjänen, T.: Logic Programs with Ordered Disjunction, Computational Intelligence, 20(2), 2004, 333-357.
• [9] Brewka, G., Niemelä, I., Truszczyński,M.: Answer Set Optimization, in: Proceedings of 18th International Joint Conference on Artificial Intelligence, (IJCAI'03) (G. Gottlob, T. Walsh, Eds.), Morgan Kaufmann, 2003, 867-872.
• [10] Brewka, G., Niemelä, I., Truszczyński,M.: Preferences and Nonmonotonic Reasoning, AI Magazine, 29(4), 2008, 69-78.
• [11] Cabalar, P.: A Logical Characterisation of Ordered Disjunction, AI Communications, 24(2), 2011, 165-175.
• [12] Confalonieri, R., Nieves, J. C.: Nested Logic Programs with Ordered Disjunction, in: Proceedings of the 6th Latin American Workshop on Non-Monotonic Reasoning (LANMR'10) (M. Osorio, C. Zepeda, I. Olmos, J. L. Carballido, C.M. Jos`e Arrazola, Eds.), vol. 677 of CEUR Workshop Proceedings, CEUR-WS.org, 2010, 55-66.
• [13] Confalonieri, R., Nieves, J. C., Osorio, M., Vázquez-Salceda, J.: Possibilistic Semantics for Logic Programs with Ordered Disjunction, in: Proceedings of 6th International Symposium on Foundations of Information and Knowledge Systems, (FoIKS 2010) (S. Link, H. Prade, Eds.), vol. 5956 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, 2010, 133-152.
• [14] Confalonieri, R., Prade, H.: Answer Set Programming for Computing Decisions Under Uncertainty, in: Proceedings of the 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2011) (W. Liu, Ed.), vol. 6717 of Lecture Notes in Artificial Intelligence, Springer-Verlag, Berlin, Heidelberg, 2011, 485-496.
• [15] Confalonieri, R., Prade, H., Nieves, J. C.: Handling Exceptions in Logic Programming without Negation as Failure, in: Proceedings of the 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2011) (W. Liu, Ed.), vol. 6717 of Lecture Notes in Artificial Intelligence, Springer-Verlag, Berlin, Heidelberg, 2011, 509-520.
• [16] Costantini, S., Formisano, A.: Modeling preferences and conditional preferences on resource consumption and production in ASP, Journal of Algorithms, 64(1), 2009, 3-15.
• [17] Costantini, S., Formisano, A.: Weight Constraints with Preferences in ASP, in: Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR11) (J. Delgrande, W. Faber, Eds.), vol. 6645 of Lecture Notes in Artificial Intelligence, Springer-Verlag, Berlin, Heidelberg, 2011, 229-235.
• [18] van Dalen, D.: Logic and Structure, 3rd augmented edition edition, Springer-Verlag, Berlin, 1994.
• [19] Delgrande, J., Schaub, T., Tompits, H., Wang, K.: A classification and Survey of Preference Handling Approaches in Nonmonotonic Reasoning, Computational Intelligence, 20(2), 2004, 308-334.
• [20] Domshlak, C., Hüllermeier, E., Kaci, S., Prade, H.: Preferences in AI: An overview, Artifical Intelligence, 175(7-8),May 2011, 1037-1052.
• [21] Eiter, T., Gottlob, G.: On the computational cost of disjunctive logic programming: Propositional case, Annals of Mathematics and Artificial Intelligence, 15(3), 1995, 289-323.
• [22] Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases, New Generation Computing, 9(3/4), 1991, 365-386.
• [23] Janhunen, T.: On the Effect of Default Negation on the Expressiveness of Disjunctive Rules, in: Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning, (LPNMR'01) (T. Eiter, W. Faber, M. Truszczynski, Eds.), vol. 2173 of Lecture Notes In Computer Science, Springer-Verlag, London, UK, 2001, 93-106.
• [24] Kaci, S.: Working with Preferences: Less Is More, Springer-Verlag, 2011.
• [25] Kärger, P., Lopes, N., Olmedilla, D., Polleres, A.: Towards Logic Programs with Ordered and Unordered Disjunction, in: Proceedings of Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP2008), 24th International Conference on Logic Programming (ICLP 2008), 2008, 46-60.
• [26] Lifschitz, V., Tang, L. R., Turner, H.: Nested expressions in logic programs, Annals of Mathematics and Artificial Intelligence, 25(3-4), 1999, 369-389.
• [27] Osorio, M., Ortiz, M., Zepeda, C.: Using CR-Rules for evacuation planning, in: Proceedings of the IX Ibero-americanWorkshops on Artificial Inteligence (G. D. Ita-Luna, O. Fuentes-Chávez,M. Osorio-Galindo, Eds.), Puebla, Mexico, 2004, 56-63.
• [28] Osorio, M., Zepeda, C.: Minimal Extended Generalized Answer Sets and their Applications, in: Proceedings of the Workshop in Logic, Language and Computation (LoLaCOM06), Fifth Mexican Internantional Conference on Artificial Intelligence (R. Dávila, M. Osorio, C. Zepeda, Eds.), vol. 220 of CEUR Workshop Proceedings, CEUR-WS.org, 2006.
• [29] Osorio, M., Zepeda, C., Carballido, J. L.: Extended ordered disjunction programs to model preferences, Special issue of Journal Research on Computing Science: Advances in Computer Science and Applications, 53, 2011, 211-220.
• [30] Pearce, D., Sarsakov, V., Schaub, T., Tompits, H., Woltran, S.: A Polynomial Translation of Logic Programs with Nested Expressions into Disjunctive Logic Programs: Preliminary Report, in: Proceedings of the 18th International Conference on Logic Programming, (ICLP'02) (P. Stuckey, Ed.), vol. 2401 of Lecture Notes in Computer Science, Springer-Verlag, London, UK, 2002, 386-404.
• [31] Wilson, N.: Extending CP-nets with stronger conditional preference statements, in: Proceedings of the 19th national conference on Artifical Intelligence (A. G. Cohn, Ed.), AAAI'04, AAAI Press, 2004, 735-741.
• [32] Zepeda, C.: Evacuation Planning using Answer Set Programming, Ph.D. Thesis, Universidad De Las Américas Puebla and Institut National des Sciences Appliquées de Lyon, 2005.
• [33] Zepeda, C., Osorio, M., Nieves, J. C., Solnon, C., Sol, D.: Applications of preferences using answer set programming, in: Proceedings of the Answer Set Programming: Advances in Theory and Implementation Workshop (ASP 2005), Bath, UK, 2005, 318-332.