×

zbMATH — the first resource for mathematics

A logic programming approach to knowledge-state planning. II: The DLV\(^\mathcal K\) system. (English) Zbl 1079.68619
Summary: In Part I of this series of papers [T. Eiter et al., “A logic programming approach to knowledge-state planning: semantics and complexity”, Tech. Rep. No. INFSYS RR-1843-01-11, Tech. Univ. Wien (2001); see also ACM Trans. Comput. Log. 5, No. 2, 206–263 (2004)], we have proposed a new logic-based planning language, called \(\mathcal K\). This language facilitates the description of transitions between states of knowledge and it is well suited for planning under incomplete knowledge. Nonetheless, \(\mathcal K\) also supports the representation of transitions between states of the world (i.e., states of complete knowledge) as a special case, proving to be very flexible. In the present Part II, we describe the DLV\(^\mathcal K\) planning system, which implements \(\mathcal K\) on top of the disjunctive logic programming system DLV. This novel planning system allows for solving hard planning problems, including secure planning under incomplete initial states (often called conformant planning in the literature), which cannot be solved at all by other logic-based planning systems such as traditional satisfiability planners. We present a detailed comparison of the DLV\(^\mathcal K\) system to several state-of-the-art conformant planning systems, both at the level of system features and on benchmark problems. Our results indicate that, thanks to the power of knowledge-state problem encoding, the DLV\(^\mathcal K\) system is competitive even with special purpose conformant planning systems,and it often supplies a more natural and simple representation of the planning problems.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68N17 Logic programming
Software:
PDDL; SATO; Graphplan
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bayardo, R.; Schrag, R., Using CSP look-back techniques to solve real-world SAT instances, (), 203-208
[2] Blum, A.L.; Furst, M.L., Fast planning through planning graph analysis, Artificial intelligence, 90, 281-300, (1997) · Zbl 1017.68533
[3] Bonet, B.; Geffner, H., Planning with incomplete information as heuristic search in belief space, (), 52-61
[4] Cimatti, A.; Roveri, M., Conformant planning via symbolic model checking, J. artificial intelligence res., 13, 305-338, (2000) · Zbl 0963.68195
[5] Eiter, T.; Faber, W.; Leone, N.; Pfeifer, G.; Polleres, A., Planning under incomplete knowledge, (), 807-821 · Zbl 0983.68539
[6] T. Eiter, W. Faber, N. Leone, G. Pfeifer, A. Polleres, A logic programming approach to knowledge-state planning: Semantics and complexity, Technical Report INFSYS RR-1843-01-11, TU Wien, 2001 · Zbl 1367.68301
[7] Eiter, T.; Leone, N.; Mateis, C.; Pfeifer, G.; Scarcello, F., The KR system : progress report, comparisons and benchmarks, (), 406-417
[8] E. Erdem, Applications of logic programming to planning: Computational experiments, unpublished draft, 1999, http://www.cs.utexas.edu/users/esra/papers.html
[9] Faber, W.; Leone, N.; Pfeifer, G., Pushing goal derivation in DLP computations, (), 177-191
[10] Ferraris, P.; Giunchiglia, E., Planning as satisfiability in nondeterministic domains, (), 748-753
[11] Finzi, A.; Pirri, F.; Reiter, R., Open world planning in the situation calculus, (), 754-760
[12] Gelfond, M.; Lifschitz, V., Classical negation in logic programs and disjunctive databases, New generation comput., 9, 365-385, (1991) · Zbl 0735.68012
[13] Gelfond, M.; Lifschitz, V., Representing action and change by logic programs, J. logic programming, 17, 301-321, (1993) · Zbl 0783.68024
[14] M. Ghallab, A. Howe, C. Knoblock, D. McDermott, A. Ram, M. Veloso, D. Weld, D. Wilkins, PDDL—The Planning Domain Definition language, Tech. Report, Yale Center for Computational Vision and Control, 1998, available at http://www.cs.yale.edu/pub/mcdermott/software/pddl.tar.gz
[15] Giunchiglia, E., Planning as satisfiability with expressive action languages: concurrency, constraints and nondeterminism, (), 657-666
[16] Giunchiglia, E.; Kartha, G.N.; Lifschitz, V., Representing action: indeterminacy and ramifications, Artificial intelligence, 95, 409-443, (1997) · Zbl 0894.68140
[17] Giunchiglia, E.; Lifschitz, V., An action language based on causal explanation: preliminary report, (), 623-630
[18] Giunchiglia, E.; Lifschitz, V., Action languages, temporal action logics and the situation calculus, ()
[19] Goldman, R.; Boddy, M., Expressive planning and explicit knowledge, (), 110-117
[20] Iocchi, L.; Nardi, D.; Rosati, R., Planning with sensing, concurrency, and exogenous events: logical framework and implementation, (), 678-689
[21] Kartha, G.N.; Lifschitz, V., Actions with indirect effects (preliminary report), (), 341-350
[22] Kautz, H.; Selman, B., Planning as satisfiability, (), 359-363
[23] Kushmerick, N.; Hanks, S.; Weld, D.S., An algorithm for probabilistic planning, Artificial intelligence, 76, 1-2, 239-286, (1995)
[24] Leone, N.; Rosati, R.; Scarcello, F., Enhancing answer set planning, (), 33-42
[25] Lifschitz, V., Foundations of logic programming, (), 69-127 · Zbl 0962.68026
[26] Lifschitz, V., Action languages, answer sets and planning, (), 357-373 · Zbl 0979.68517
[27] Lifschitz, V., Answer set planning, (), 23-37
[28] Lifschitz, V.; Turner, H., Splitting a logic program, (), 23-37
[29] Lifschitz, V.; Turner, H., Representing transition systems by logic programs, (), 92-106 · Zbl 0952.68132
[30] McCain, N.; Turner, H., Causal theories of actions and change, (), 460-465
[31] McCain, N.; Turner, H., Satisfiability planning with causal theories, (), 212-223
[32] McCarthy, J., Formalization of common sense. papers by John McCarthy edited by V. lifschitz, (1990), Ablex Norwood, NJ
[33] McCarthy, J.; Hayes, P.J., Some philosophical problems from the standpoint of artificial intelligence, (), 463-502, reprinted in [32] · Zbl 0226.68044
[34] McDermott, D., A critique of pure reason, Comput. intelligence, 3, 151-237, (1987), cited in [4]
[35] Niemelä, I., Logic programming with stable model semantics as constraint programming paradigm, Ann. math. artificial intelligence, 25, 3-4, 241-273, (1999) · Zbl 0940.68018
[36] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033
[37] M.A. Peot, Decision-theoretic planning, Ph.D. thesis, Stanford University, Stanford, CA, 1998
[38] Peot, M.A.; Smith, D.E., Conditional nonlinear planning, (), 189-197
[39] Pryor, L.; Collins, G., Planning for contingencies: A decision-based approach, J. artificial intelligence res., 4, 287-339, (1996)
[40] Reiter, R., On closed world data bases, (), 55-76
[41] Rintanen, J., Constructing conditional plans by a theorem-prover, J. artificial intelligence res., 10, 323-352, (1999) · Zbl 0916.68139
[42] Smith, D.E.; Weld, D.S., Conformant graphplan, (), 889-896
[43] Subrahmanian, V.; Zaniolo, C., Relating stable models and AI planning domains, (), 233-247
[44] Sussman, G.J., The virtuous nature of bugs, (), Chapter 3, pp. 111-117, originally written 1974
[45] Turner, H., Representing actions in logic programs and default theories: A situation calculus approach, J. logic programming, 31, 1-3, 245-298, (1997) · Zbl 0880.68010
[46] Ullman, J.D., Principles of database and knowledge base systems, vol. 1, (1989), Computer Science Press
[47] Weld, D.S.; Anderson, C.R.; Smith, D.E., Extending graphplan to handle uncertainty & sensing actions, (), 897-904
[48] Zhang, H., SATO: an efficient propositional prover, (), 272-275
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.