Knowledge Compilation for Action Languages - GREYC mad Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Knowledge Compilation for Action Languages

Résumé

We study different languages for representing nondeterministic actions in automated 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 (how hard is it to decide whether a state is a successor of another one through some action described in one of these languages?). We study an abstract, nondeterministic version of PDDL, the language of NNF action theories, and DL-PPA, the dynamic logic of parallel propositional assignments. We show that these languages have different succinctness and different complexity of queries: DL-PPA is the most succinct one and NNF is the least succinct, and deciding successorship is already NP-complete for nondeterministic PDDL.
Nous étudions différents langages permettant de représenter des actions non déterministes pour la planification au-tomatique, du point de vue de la compilation de connais-sances. 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é (quelle est la complexité algorithmique de décider si un état est un successeur d'un autre pour une action décrite dans l'un de ces langages?). Nous étu-dions une version abstraite et nondéterministe de PDDL, le langage des théories d'actions en NNF, et DL-PPA, la logique dynamique des affectations propositionnelles par-allèles. Nous montrons que ces langages ont une concision différente, et une complexité de requête différente : DL-PPA est le plus concis et NNF le moins concis, et décider si un état est successeur d'un autre est déjà NP-complet pour PDDL nondéterministe.
Fichier principal
Vignette du fichier
jfpda2020.pdf (352.84 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02942877 , version 1 (22-10-2020)

Identifiants

  • HAL Id : hal-02942877 , version 1

Citer

Sergej Scheck, Alexandre Niveau, Bruno Zanuttini. Knowledge Compilation for Action Languages. Journées Francophones sur la Planification, la Décision et l’Apprentissage pour la conduite de systèmes (JFPDA 2020), Jul 2020, Angers, France. ⟨hal-02942877⟩
134 Consultations
64 Téléchargements

Partager

Gmail Facebook X LinkedIn More