Actions and Programs over Description Logic Knowledge Bases: A Functional Approach

Knowing, Reasoning, and Acting: Essays in Honour of Hector J. Levesque. 2011.

We aim at reasoning about actions and about high-level programs over knowledge bases (KBs) expressed in Description Logics (DLs). This is a critical issue that has resisted good, robust solutions for a long time. In particular, while well-developed theories of actions and high-level programs exist in AI, e.g., the ones based on the Situation Calculus, these theories do not apply to DL KBs, since these impose very rich state constraints (all the intensional part of the ontology itself ). Here we propose a radical solution: we assume a Levesque's functional view of KBs and see them as systems that allow for two kinds of operations: ask, which returns the (certain) answer to a query, and tell, which produces a new knowledge base as the result of the application of an atomic action. In particular, we consider DL KBs formed by two components: a TBox, providing the intensional knowledge about the domain of interest, which we assume to be immutable over time; and an ABox, providing (incomplete) information at the extensional level, which we assume to be changed by atomic actions based on generic forms of instance level updates. The only requirement that we pose on such updates is that the resulting ABox is still expressible in the original DL language. We demonstrate the effectiveness of the approach by introducing Golog/ConGolog-like high-level programs on DL KBs, characterizing the notion of single-step executability of such programs, and devising nice methods for reasoning about sequences of actions generated by such programs. All our basic results are parametric wrt the specific DL language. Though for concreteness we present them using a particularly well behaved DL, namely DL-LiteA,id .

@incollection{book-levesque-2011,
   title = "Actions and Programs over Description Logic Knowledge Bases:  A
Functional Approach",
   year = "2011",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Riccardo Rosati",
   editor = "Gerhard Lakemeyer and Sheila A. McIlraith",
   booktitle = "Knowing, Reasoning, and Acting:  Essays in Honour of Hector
J. Levesque",
   publisher = "College Publications",
}