Look-back Techniques for ASP Programs with Aggregates

• Autorzy: Faber W. , Leone N. , Maratea M. , Ricca F.
• Języki publikacji: EN

Abstrakty

EN

The introduction of aggregates has been one of the most relevant language extensions to Answer Set Programming (ASP). Aggregates are very expressive, they allow to represent many problems in a more succinct and elegant way compared to aggregate-free programs. A significant amount of research work has been devoted to aggregates in the ASP community in the last years, and relevant research results on ASP with aggregates have been published, on both theoretical and practical sides. The high expressiveness of aggregates (eliminating aggregates often causes a quadratic blow-up in program size) requires suitable evaluation methods and optimization techniques for an efficient implementation. Nevertheless, in spite of the above-mentioned research developments, aggregates are treated in a quite straightforward way in most ASP systems. In this paper, we explore the exploitation of look-back techniques for an efficient implementation of aggregates. We define a reason calculus for backjumping in ASP programs with aggregates. Furthermore, we describe how these reasons can be used in order to guide look-back heuristics for programs with aggregates. We have implemented both the new reason calculus and the proposed heuristics in the DLV system, and have carried out an experimental analysis on publicly available benchmarks which shows significant performance benefits

Słowa kluczowe

EN

Knowledge Representation and Reasoning; non-monotonic reasoning; answer set programming; heuristics; aggregates

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 4
• Strony: 379--413
• Opis fizyczny: Bibliogr. 40 poz., tab.

Twórcy

autor

Faber W.

autor

Leone N.

autor

Maratea M.

autor

Ricca F.

• Dep. of Math., University of Calabria Via P. Bucci, cubo 30b, 87036 Rende (CS), Italy,

Bibliografia

• [1] Alviano, M.: Efficient Recursive Aggregate Evaluation in Logic Programming, Intelligenza Artificiale. IOS Press, 2011, To appear.
• [2] Bayardo, R., Schrag, R.: Using CSP Look-back Techniques to Solve Real-world SAT Instances, Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-97), 1997.
• [3] Calimeri, F., Faber, W., Leone, N., Pfeifer, G.: Pruning Operators for Answer Set Programming Systems, Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR'2002), April 2002.
• [4] Davis, M., Logemann, G., Loveland, D.: A Machine Program for Theorem Proving, Communications of the ACM, 5, 1962, 394-397.
• [5] Dechter, R.: Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition, Artificial Intelligence, 41(3), 1990, 273-312.
• [6] Dechter, R., Frost, D.: Backjump-based backtracking for constraint satisfaction problems., Artificial Intelligence, 136(2), 2002, 147-188.
• [7] Dell'Armi, T., Faber,W., Ielpa, G., Leone, N., Pfeifer, G.: Aggregate Functions in DLV, Proceedings ASP03 - Answer Set Programming: Advances in Theory and Implementation (M. de Vos, A. Provetti, Eds.),Messina, Italy, September 2003, Online at http://CEUR-WS.org/Vol-78/.
• [8] Denecker,M., Vennekens, J., Bond, S., Gebser,M., Truszczynski,M.: The Second Answer Set Programming Competition, Proceedings of tre 10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR'09 (E. Erdem, F. Lin, T. Schaub, Eds.), 5753, Springer, 2009.
• [9] Faber, W.: Enhancing Efficiency and Expressiveness in Answer Set Programming Systems, Ph.D. Thesis, Institut f¨ur Informationssysteme, Technische Universität Wien, 2002.
• [10] Faber, W., Leone, N., Pfeifer, G.: Pushing Goal Derivation in DLP Computations, Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99) (M. Gelfond, N. Leone, G. Pfeifer, Eds.), 1730, Springer Verlag, El Paso, Texas, USA, December 1999.
• [11] Faber, W., Leone, N., Pfeifer, G.: Recursive Aggregates in Disjunctive Logic Programs: Semantics and Complexity, Proceedings of the 9th European Conference on Artificial Intelligence (JELIA 2004) (J. J. Alferes, J. Leite, Eds.), 3229, Springer Verlag, September 2004.
• [12] Faber, W., Leone, N., Pfeifer, G., Ricca, F.: On look-ahead heuristics in disjunctive logic programming, Annals of Mathematics and Artificial Intelligence, 51(2-4), 2007, 229-266.
• [13] Faber, W., Pfeifer, G., Leone, N.: Semantics and complexity of recursive aggregates in answer set programming, Artificial Intelligence, 175(1), 2011, 278-298.
• [14] Faber, W., Pfeifer, G., Leone, N., Dell'Armi, T., Ielpa, G.: Design and Implementation of Aggregate Functions in the DLV System, Theory and Practice of Logic Programming, 8(5-6), 2008, 545-580.
• [15] Faber, W., Ricca, F.: Solving Hard ASP Programs Efficiently, Logic Programming and Nonmonotonic Reasoning - 8th International Conference, LPNMR'05, Diamante, Italy, September 2005, Proceedings (C. Baral, G. Greco, N. Leone, G. Terracina, Eds.), 3662, Springer Verlag, September 2005, ISBN 3-540-28538-5.
• [16] Ferraris, P., Lifschitz, V.: Weight constraints as nested expressions, Theory and Practice of Logic Programming, 5(1-2), 2005, 45-74.
• [17] Gaschnig, J.: A General Backtrack Algorithm That Eliminates Most Redundant Tests, Proceedings of the Fifth International Joint Conference on Artificial Intelligence (IJCAI) 1977, 1977.
• [18] Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: On the Implementation of Weight Constraint Rules in Conflict-Driven ASP Solvers, Proceedings of 25th International Conference on Logic Programming (ICLP-09) (P. M. Hill, D. S. Warren, Eds.), 5649, Springer, 2009.
• [19] Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: clasp: A Conflict-Driven Answer Set Solver, Proceedings of the Ninth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'07) (C. Baral, G. Brewka, J. Schlipf, Eds.), 4483, Springer-Verlag, 2007.
• [20] Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-Driven Answer Set Solving, Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), Morgan Kaufmann Publishers, January 2007.
• [21] Gebser, M., Liu, L., Namasivayam, G., Neumann, A., Schaub, T., Truszczy´nski, M.: The First Answer Set Programming System Competition, 9th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR'07 (C. Baral, G. Brewka, J. Schlipf, Eds.), 4483, Springer Verlag, Tempe, Arizona,May 2007, ISBN 978-3-540-72199-4.
• [22] Gebser, M., Schaub, T., Thiele, S.: GrinGo : A New Grounder for Answer Set Programming, Logic Programming and Nonmonotonic Reasoning, 9th International Conference, LPNMR 2007, Tempe, AZ, USA, May 15-17, 2007, Proceedings (C. Baral, G. Brewka, J. S. Schlipf, Eds.), 4483, Springer, 2007.
• [23] Gelfond, M., Lifschitz, V.: Classical Negation in Logic Programs and Disjunctive Databases, New Generation Computing, 9, 1991, 365-385.
• [24] Giunchiglia, E., Lierler, Y., Maratea, M.: Answer Set Programming Based on Propositional Satisfiability, Journal of Automated Reasoning, 36(4), 2006, 345-377.
• [25] Giunchiglia, E., Narizzano, M., Tacchella, A.: Backjumping for Quantified Boolean Logic Satisfiability, Artificial Intelligence, 145, 2003, 99-120.
• [26] Lee, J., Meng, Y.: On Reductive Semantics of Aggregates in Answer Set Programming, Logic Programming and Nonmonotonic Reasoning-10th InternationalConference (LPNMR 2009) (E. Erdem, F. Lin, T. Schaub, Eds.), 5753, Springer Verlag, September 2009, ISBN 978-3-642-04237-9.
• [27] Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV System for Knowledge Representation and Reasoning, ACM Transactions on Computational Logic, 7(3), July 2006, 499-562.
• [28] Liu, L., Truszczyńki,M.: The Second Answer Set Programming Competition homepage, Since 2005, http://www.cs.uky.edu/ai/pbmodels/#Benchmark|region.
• [29] Manna, M., Ruffolo,M., Oro, E., Alviano, M., Leone, N.: The HiLeX System for Semantic Information Extraction, Transactions on Large-Scale Data and Knowledge-Centered Systems. Springer Berlin/Heidelberg, 2011, To appear.
• [30] Maratea,M., Ricca, F., Faber,W., Leone, N.: Look-Back Techniques and Heuristics in DLV: Implementation, Evaluation and Comparison to QBF Solvers, Journal of Algorithms in Cognition, Informatics and Logics, 63(1-3), 2008, 70-89.
• [31] Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an Efficient SAT Solver, Proceedings of the 38th Design Automation Conference, DAC 2001, ACM, Las Vegas, NV, USA, June 2001.
• [32] Pelov, N., Denecker, M., Bruynooghe, M.: Well-founded and Stable Semantics of Logic Programs with Aggregates, Theory and Practice of Logic Programming, 7(3), 2007, 301-353.
• [33] Prosser, P.: Hybrid Algorithms for the Constraint Satisfaction Problem., Computational Intelligence, 9, 1993, 268-299.
• [34] Ricca, F., Alviano, M., Dimasi, A., Grasso, G., Ielpa, S. M., Iiritano, S., Manna, M., Leone, N.: A Logic-Based System for e-Tourism, Fundamenta Informaticae, IOS Press, (105), 2010, 35-35.
• [35] Ricca, F., Faber,W., Leone, N.: A Backjumping Technique for Disjunctive Logic Programming, AI Communications - The European Journal on Artificial Intelligence, 19(2), 2006, 155-172.
• [36] Ricca, F., Grasso, G., Alviano, M., Manna, M., Lio, V., Iiritano, S., Leone, N.: Team-building with Answer Set Programming in the Gioia-Tauro Seaport, Theory and Practice of Logic Programming. Cambridge University Press, 2011, To appear.
• [37] Silva, J. P. M., Sakallah, K. A.: GRASP: A Search Algorithm for Propositional Satisfiability, IEEE Transaction on Computers, 48(5), 1999, 506-521.
• [38] Simons, P., Niemelä, I., Soininen, T.: Extending and Implementing the Stable Model Semantics, Artificial Intelligence, 138, June 2002, 181-234.
• [39] Son, T. C., Pontelli, E.: A Constructive Semantic Characterization of Aggregates in ASP, Theory and Practice of Logic Programming, 7, May 2007, 355-375.
• [40] Syrjänen, T.: Lparse 1.0 User's Manual, 2002, http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz.