We study plan synthesis for a variant of Knowledge and Action Bases (KABs), a rich, dynamic framework, where states are description logic (DL) knowledge bases (KBs) whose extensional part is manipulated by actions that possibly introduce new objects from an infinite domain. We show that plan existence over KABs is undecidable even under severe restrictions. We then focus on state-bounded KABs, a class for which plan existence is decidable, and provide sound and complete plan synthesis algorithms, which combine techniques based on standard planning, DL query answering, and finite-state abstraction. All results hold for any DL with decidable query answering. We finally show that for lightweight DLs, plan synthesis can be compiled into standard ADL planning.

Plan Synthesis for Knowledge and Action Bases / Calvanese, Diego; Montali, Marco; Patrizi, Fabio; Stawowy, Michele. - In: IJCAI. - ISSN 1045-0823. - STAMPA. - (2016), pp. 1022-1029. (Intervento presentato al convegno 25th International Joint Conference on Artificial Intelligence, IJCAI 2016 tenutosi a New York; United States).

Plan Synthesis for Knowledge and Action Bases

PATRIZI, FABIO
;
2016

Abstract

We study plan synthesis for a variant of Knowledge and Action Bases (KABs), a rich, dynamic framework, where states are description logic (DL) knowledge bases (KBs) whose extensional part is manipulated by actions that possibly introduce new objects from an infinite domain. We show that plan existence over KABs is undecidable even under severe restrictions. We then focus on state-bounded KABs, a class for which plan existence is decidable, and provide sound and complete plan synthesis algorithms, which combine techniques based on standard planning, DL query answering, and finite-state abstraction. All results hold for any DL with decidable query answering. We finally show that for lightweight DLs, plan synthesis can be compiled into standard ADL planning.
2016
25th International Joint Conference on Artificial Intelligence, IJCAI 2016
Computability and decidability; Data description
04 Pubblicazione in atti di convegno::04c Atto di convegno in rivista
Plan Synthesis for Knowledge and Action Bases / Calvanese, Diego; Montali, Marco; Patrizi, Fabio; Stawowy, Michele. - In: IJCAI. - ISSN 1045-0823. - STAMPA. - (2016), pp. 1022-1029. (Intervento presentato al convegno 25th International Joint Conference on Artificial Intelligence, IJCAI 2016 tenutosi a New York; United States).
File allegati a questo prodotto
File Dimensione Formato  
Calvanese_Postprint_Plan-synthesis_2016.pdf

accesso aperto

Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 351.3 kB
Formato Adobe PDF
351.3 kB Adobe PDF
Calvanese_Plan-synthesis_2016.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 818.23 kB
Formato Adobe PDF
818.23 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/913328
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? ND
social impact