Knowledge Compilation for Nondeterministic Action Languages
Keywords:Conformant, Contingent And Adversarial Planning, Classical Planning Techniques And Analysis
AbstractWe study different languages for representing nondeterministic actions in planning from the point of view of knowledge compilation. Precisely, we consider succintness issues (how succinct is the description of an action in each language?) and complexity issues (tractability or hardness of several queries which arise naturally in planning and belief tracking). We study an abstract, nondeterministic version of PDDL, nondeterministic conditional STRIPS, the language NNFAT of NNF action theories, and the language NPDDLseq obtained by adding a sequence operator to nondeterministic PDDL. We show that these languages have different succinctness and different complexity even for the most natural queries.
How to Cite
Scheck, S., Niveau, A., & Zanuttini, B. (2021). Knowledge Compilation for Nondeterministic Action Languages. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 308-316. https://doi.org/10.1609/icaps.v31i1.15975