Knowledge Compilation for Nondeterministic Action Languages

Authors

  • Sergej Scheck Normandie Université; UNICAEN, ENSICAEN, CNRS, GREYC
  • Alexandre Niveau Normandie Université; UNICAEN, ENSICAEN, CNRS, GREYC
  • Bruno Zanuttini Normandie Université; UNICAEN, ENSICAEN, CNRS, GREYC

DOI:

https://doi.org/10.1609/icaps.v31i1.15975

Keywords:

Conformant, Contingent And Adversarial Planning, Classical Planning Techniques And Analysis

Abstract

We 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.
ICAPS-21 Proceedings Cover

Downloads

Published

2021-05-17

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

Issue

Vol. 31 (2021): Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling

Section

Main Track