A KC Map for Variants of Nondeterministic PDDL - GREYC mad Access content directly
Conference Papers Year : 2022

A KC Map for Variants of Nondeterministic PDDL

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

Abstract

We study different languages for representing nondeterministic actions in planning from the point of view of knowledge compilation. Precisely, we consider succinctness issues (how succinct is the description of an action in each language?), and complexity issues (tractability or hardness of several queries and transformations which arise naturally in planning and belief tracking). We study an abstract, nondeterministic version of PDDL, nondeterministic conditional STRIPS, and the languages NPDDL_seq and NPDDL_not obtained by adding sequence and negation to nondeterministic PDDL. We show that these languages have different succinctness and different complexity for the most natural queries.
Nous étudions différents langages permettant de représenter des actions non-déterministes pour la planification automatique, du point de vue de la compilation de connaissances. Précisément, nous considérons la question de la concision des langages (quelle est la taille de la description d'une action dans chaque langage ?) et des questions de complexité (traitabilité ou dureté de plusieurs requêtes et transformations qui surviennent naturellement dans la planification et le suivi des croyances). Nous étudions une version abstraite et nondéterministe de PDDL, STRIPS conditionnel nondéterministe, et les langages NPDDL seq et NPDDL not obtenus en ajoutant séquence et négation à PDDL nondéterministe. Nous montrons que ces langages ont une concision et complexité différente pour les requêtes les plus naturelles.
Fichier principal
Vignette du fichier
JIAF_2022_paper_15.pdf (269.52 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03658932 , version 1 (04-05-2022)

Identifiers

  • HAL Id : hal-03658932 , version 1

Cite

Sergej Scheck, Alexandre Niveau, Bruno Zanuttini. A KC Map for Variants of Nondeterministic PDDL. 16es journées d'intelligence artificielle fondamentale (JIAF 2022), Jun 2022, Saint-Étienne, France. ⟨hal-03658932⟩
52 View
20 Download

Share

Gmail Facebook X LinkedIn More