Abstract
The study of formal nonmonotonic reasoning has been motivated to a large degree by the need to solve the frame problem and other problems related to representing actions. New efficient implementations of nonmonotonic reasoning, such as SMODELS and DLV, can be used to solve many computational problems that involve actions, including plan generation. SMODELS and its competitors are essential to implement a new approach to knowledge representation and reasoning: to compute solutions to a problem by computing the stable models (answer sets) of the theory that represents it. Marek and Truszczyński call this paradigm Stable model programming. We are trying to assess the viability of stable logic programming for agent specification and planning in realistic scenarios. To do so, we present an encoding of plan generation within the lines of Lifschitz’s Answer set planning and evaluate its performance in the simple scenario of Blocks world. Several optimization techniques stemming from mainstream as well as satisfiability planning are added to our planner, and their impact is discussed.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Apt, K.R., Bol, R.: Logic programming and negation: a survey. J. of Logic Programming 19/20 (1994)
Balduccini, M., Lanzarone, G.A.: Autonomous semi-reactive agent design based on incremental inductive learning in logic programming. In: Proc. of the ESSLI 1997 Symp. on Logical Approaches to Agent Modeling and Design, Utrecht University, pp. 1–12 (1997)
Baral, C., Gelfond, M.: Logic programming and knowledge representation. J. of Logic Programming 19/20 (1994)
Brignoli, G., Costantini, S., Provetti, A.: A Graph Coloring algorithm for stable models generation. Univ. of Milan Technical Report (1999) (submitted for publication)
Costantini, S., Provetti, A.: A new method, and new results, for detecting consistency of knowledge bases under answer sets semantics. Univ. of Milan Technical Report (1999) (submitted for publication)
Costantini, S.: Contributions to the stable model semantics of logic programs with negation. Theoretical Computer Science, 149 (1995)
Chen, W., Warren, D.S.: Computation of stable models and its integration with logical query processing. IEEE Trans. on Data and Knowledge Engineering 8(5), 742–747 (1996)
Cholewiński, P., Marek, W., Truszczyński, M.: Default reasoning system DeReS. In: Proc. of KR 1996, pp. 518–528. Morgan-Kaufman, San Francisco (1996)
Dimopoulos, Y., Nebel, B., Koehler, J.: Encoding Planning Problems in Nonmonotonic Logic Programs. In: Proc. of European Conference on Planning, pp. 169–181 (1997)
Dung, P.M.: On the Relation between Stable and Well-Founded Semantics of Logic Programs. Theoretical Computer Science, 105 (1992)
Eiter, T., Leone, N., Mateis, C., Pfeifer, G., Scarcello, F.: A deductive system for non-monotonic reasoning. In: Fuhrbach, U., Dix, J., Nerode, A. (eds.) LPNMR 1997. LNCS, vol. 1265, pp. 363–374. Springer, Heidelberg (1997)
Erdem, E.: Application of Logic Programming to Planning: Computational Experiments. In: Gelfond, M., Leone, N., Pfeifer, G. (eds.) LPNMR 1999. LNCS (LNAI), vol. 1730. Springer, Heidelberg (1999)
Faber, W., Leone, N., Pfeifer, G.: Pushing Goal Derivation in DLP Computations. In: Gelfond, M., Leone, N., Pfeifer, G. (eds.) LPNMR 1999. LNCS (LNAI), vol. 1730. Springer, Heidelberg (1999)
Fages, F.: Consistency of Clark’s completion and existence of stable models. In: Proc. of 5th ILPS conference (1994)
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Proc. of 5th ILPS conference, pp. 1070–1080 (1988)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Computing, 365–387 (1991)
Kautz, H., Selman, B.: Pushing the envelope: Planning, Propositional Logic and Stochastic Search. In: Proc. of AAAI 1996 (1996)
Lib99. Liberatore P., 1999. Algorithms and Experiments on Finding Minimal Models. Technical Report of University of Rome ”La Sapienza”
Lifschitz, V.: Answer Set Planning. In: Gelfond, M., Leone, N., Pfeifer, G. (eds.) LPNMR 1999. LNCS (LNAI), vol. 1730. Springer, Heidelberg (1999)
Marek, W., Truszczyński, M.: Stable models and an alternative logic programming paradigm. The Journal of Logic Programming (1999)
Niemelä, I., Simons, P.: Logic programs with stable model semantics as a constraint programming paradigm. In: Proc. of NM 1998 workshop (1998) (Extended version submitted for publication)
McCain, N., Turner, H.: Causal theories of actions and change. In: Proc. of AAAI 1997 Conference, pp. 460–465 (1997)
Saccà, D., Zaniolo, C.: Deterministic and Non-Deterministic Stable Models. J. of Logic and Computation (1997)
Simons, P.: Towards Constraint Satisfaction through Logic Programs and the Stable Models Semantics. Helsinki Univ. of Technology R.R. A:47 (1997)
Subrahmanian, V.S., Nau, D., Vago, C.: WFS + branch and bound = stable models. IEEE Trans. on Knowledge and Data Engineering 7(3), 362–377 (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Balduccini, M., Brignoli, G., Lanzarone, G.A., Magni, F., Provetti, A. (2000). Experiments in Answer Sets Planning. In: Cairó, O., Sucar, L.E., Cantu, F.J. (eds) MICAI 2000: Advances in Artificial Intelligence. MICAI 2000. Lecture Notes in Computer Science(), vol 1793. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10720076_9
Download citation
DOI: https://doi.org/10.1007/10720076_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67354-5
Online ISBN: 978-3-540-45562-2
eBook Packages: Springer Book Archive