Knowledge Compilation for Nondeterministic Action Languages

Sergej Scheck (1) , Alexandre Niveau (1) , Bruno Zanuttini (1)

1 Equipe MAD - Laboratoire GREYC - UMR6072

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.

Domaines: Intelligence artificielle [cs.AI]

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⟩