Knowledge Compilation for Nondeterministic Action Languages - GREYC mad Access content directly
Conference Papers Year : 2021

Knowledge Compilation for Nondeterministic Action Languages

Sergej Scheck
  • Function : Author
  • PersonId : 1077482
Bruno Zanuttini
  • Function : Author
  • PersonId : 952903


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 NPDDL seq 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.
Fichier principal
Vignette du fichier
icaps2021.pdf (188.03 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03249126 , version 1 (03-06-2021)


  • HAL Id : hal-03249126 , version 1


Sergej Scheck, Alexandre Niveau, Bruno Zanuttini. Knowledge Compilation for Nondeterministic Action Languages. International Conference on Automated Planning and Scheduling, Aug 2021, Guangzhou, China. ⟨hal-03249126⟩
58 View
69 Download


Gmail Mastodon Facebook X LinkedIn More