Integrating AI planning with ontology reasoning ofers a promising approach to developing goal-driven planning systems that benefit from static domain knowledge. While AI planning guides a system via action sequences under closed-world assumptions, and ontology reasoning provides expressive static constraints under open-world semantics, combining the two introduces significant theoretical and practical challenges. This research explores novel frameworks for planning with ontologies, with a strong focus on description logics and classical planning. We aim to analyse the computational complexity and expressivity of such integrated systems, design compilations into existing planning formalisms, and develop practical algorithms where compilation is not possible. Building upon recent advancements in integrated formalism, known as eKABs planning, our latest work provides support for coherence update semantics, enabling planning with additional logical semantics requirements to facilitate the modelling process in practice. The project ultimately aims to bridge the gap between the theoretical richness of ontology reasoning and the practicality of planning algorithms, contributing foundational tools to both theory and real-world applications.
Artificial Intelligence (AI) planning and reasoning with ontology languages (ontology reasoning) are two
extensively studied research fields in symbolic AI and Knowledge Representation and Reasoning (KR).
While AI planning traverses a system’s internal states via a sequence of predefined actions to reach a
desired goal, ontologies are used to express static constraints during the system’s operations. In this
research, we consider the intersection of the two formalisms, which integrates current state-of-the-art
planning algorithms with reasoning over static data models, yielding great potential for applications
in real-world scenarios such as business process definitions, knowledge graphs, relational databases,
and operational planning/scheduling models [
Until now, theoretical aspects have been the focal point of research on integrating AI planning
and ontology reasoning. For instance, [
It’s necessary to clarify overlapping terms used in both fields to avoid confusion. We refer to reasoning
as static ontology reasoning in KR, domain as the description of a single planning or reasoning problem,
and state as a finite set of grounded first-order (FO) atoms (facts). We diferentiate between two semantics
of FO-formulas, namely open-world and closed-world assumptions. Specifically, in AI planning, a state
under the closed-world assumption fully describes a single FO interpretation over a fixed set of objects.
Contrarily, ontology reasoning employs open-world semantics where infinitely many interpretations
are considered over arbitrary sets of objects, as long as they are consistent with the observed state.
Ontology Reasoning. Generally, first-order logic (FOL) allows for modelling complex constraints
about unknown objects/facts under open-world semantics. However, this leads to reasoning in FOL being
undecidable and thus impractical for applications. To overcome this obstacle, we consider restricted
subsets of FOL, which include description logics (DLs), Datalog, and existential rules [
Example 1 demonstrates how an ontology expresses knowledge: Example 1. Axioms and facts in Blocks world ontology: on_block ⊑ on, ∃on_block− on_table ⊑ on, ∃on_table− Block ≡ ∃on, ∃on_block − ⊑ Block, funct on_block, ⊑ Table, Block ⊑ ¬Table, ⊑ Blocked, ∃on_block ⊑ ¬∃on_table, on_block(1, 2), on_table(3, ) This ontology expresses that 2 is blocked (Blocked(2)) since 1 is on 2 (on_block(1, 2)) and every block that has another block on top is blocked (∃on_block− ⊑ Blocked). Additionally, on_block(1, 3) cannot hold, since the on_block relation is functional (funct on_block).
In this project, we are interested in two main reasoning problems. The first one is to determine
whether an ontology is consistent, meaning it contains no contradictions. The second problem is to
decide if a query formula is entailed by the ontology, meaning it is satisfied in every interpretation of
the ontology. The following approaches address these problems: rewriting into closed-world reasoning
problems [
We will mainly focus on classical planning, in which one of the best candidates for computing
plans is heuristic search [
Besides classical planning, there are various planning formalisms with more expressive frameworks
[
Combined Formalism. In planning, a state is interpretable as an ABox, whereas a TBox can describe
its background knowledge. Exploiting these similarities, the most recent promising formalism for
combining classical planning with ontology reasoning is explicit-input Knowledge and Action Bases
(eKABs) [
Example 2. Consider the eKAB action move(, , ) that moves Block from position to . Its precondition is [on(, )] ∧ ¬[Blocked()] ∧ ¬[Blocked()], where the atoms in brackets are evaluated w.r.t. the ontology axioms (epistemic semantics). Its efects consist of ((), [Block()], ∅, {¬on_block(, )}), ((), [Table()], ∅, {¬on_table(, )}), ((), [Block()], {on_block(, )}, ∅), ((), [Table()], {on_table(, )}, ∅), which remove on_block(, ) when is entailed to be a Block, add on_table(, ) if is a Table, and so on. Efectively, it removes on(, ) and adds on(, ).
For example, the action is applicable for the substitution ↦→ 1, ↦→ 2, ↦→ 3, since on_block is included in on and neither Blocked(1) nor Blocked(3) are entailed. Then, it would remove on_block(1, 2) and insert on_block(1, 3), as Block(2) and Block(3) are entailed.
Research Goals. As mentioned previously, our primary goal is the investigation of distinct possibilities for integrating AI planning and reasoning, with DLs and classical planning as focal points. Under this context, we will establish the computational complexity of the concerned reasoning problems, which we will reinforce with implemented experiments in planning. Starting with eKABs, we will examine existing proposals on implementing reasoning in planning and strive to support more expressive logical frameworks. The study will include the evaluation of their relative expressivity, eficiency, and usefulness for modelling real-world applications. Even though compilation approaches can easily adopt preceding results and exploit state-of-the-art planning systems, the technique is not universally applicable due to the diferences in expressivity of the framework in observation. In such cases, we will instead design dedicated, integrated algorithms and study their properties. Summarily, the following are the main objectives of our research programme: (1) Complexity and expressivity analysis of combined planning and reasoning formalisms; (2) Where possible, designing eficient compilations of the formalisms in (O 1); (3) Development of integrated algorithms for more expressive planning over a background ontology (and vice versa).
In our latest work [
We could remove on(1, 2) to obtain a consistent state. However, since this fact is not explicitly present in the state (ABox), this operation doesn’t have any efect, and [on(1, 2)] would hold due to on_block(1, 2).
Even if we explicitly remove on_block(1, 2), we would lose that 2 is a block, i.e. we should add Block(2).
Example 3 illustrates that actions can cause three types of implicit efects: removing a fact requires (i) removing all stronger facts and (ii) adding previously implied facts to avoid losing information, whereas adding a fact requires (iii) removing any conflicting facts to ensure consistency.
Since the efects of the coherence update semantics coincide with the implicit efects listed in (i),
(ii), and (iii), we define a new semantics for eKAB that satisfies these requirements by applying the
coherence update semantics to all actions in a planning problem. The resulting planning task retains
favourable behaviours of the epistemic eKAB semantics for action conditions and of the coherence
update semantics for single-step updates between the states for DL-Lite. In particular, it is possible to
rewrite all operations into Datalog¬, and therefore into classical planning with PDDL derived predicates
[
We believe that our work’s main contribution to practical use lies in the ease of modelling for planning problems. In particular, explicitly dealing with the consequences of the background knowledge in every action can be avoided by simply encoding it in the ontology.
Admittedly, the coherence update semantics may not always be the most appropriate choice. For
instance, actions that completely remove a fact and its consequences from a state might fail under
the coherence update semantics due to (ii). Hence, we will also study combined semantics that allow
switching, e.g. between eKAB and the new semantics in future works via a special action that ignores
the implicit efects of the coherence update semantics. Nevertheless, such action might break the state’s
consistency, requiring additional repair mechanisms afterwards. Furthermore, we plan to provide
support for conjunction in DL-Lite. However, it is unclear whether a suitable update semantics can be
defined, since removing a conjunction involves a nondeterministic choice of which conjunct should
be removed. Lastly, in the case of large ontologies, it would be beneficial to use DL reasoners directly
instead of rewriting techniques, as they are optimised for dealing with such ontologies and can be
integrated with the planning system in a black-box manner.
3.1. Closely Related Work
The eKAB formalism was optimised and extended to support all Datalog¬-rewritable Horn DLs, via a
compilation into PDDL with derived predicates [
This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) in grant 540204715 and by the Swiss National Science Foundation (SNSF) as part of the project “Practical Planning with Ontologies” (PPO).
25–30