Synthesizing and Executing Plans in Knowledge and Action Bases

Diego Calvanese, Marco Montali, Fabio Patrizi, and Michele Stawowy

Proc. of the 29th Int. Workshop on Description Logics (DL 2016). Volume 1577 of CEUR Workshop Proceedings, http://ceur-ws.org/. 2016.

We study plan synthesis for a variant of Knowledge and Action Bases (KABs). KABs have been recently introduced as a rich, dynamic framework where states are full-fledged description logic (DL) knowledge bases (KBs) whose extensional part is manipulated by actions that can introduce new objects from an infinite domain. We show that, in general, plan existence over KABs is undecidable even under severe restrictions. We then focus on the class of state-bounded KABs, for which plan existence is decidable, and we provide sound and complete plan synthesis algorithms, through a novel combination of techniques based on standard planning, DL query answering, and finite-state abstractions. 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.


@inproceedings{DL-2016-kab-planning,
   title = "Synthesizing and Executing Plans in Knowledge and Action Bases",
   year = "2016",
   author = "Diego Calvanese and Marco Montali and Fabio Patrizi and
Michele Stawowy",
   booktitle = "Proc. of the 29th Int. Workshop on Description Logics
(DL 2016)",
   volume = "1577",
   series = "CEUR Workshop Proceedings, http://ceur-ws.org/",
}
pdf url