Automated planning is a core area within Artificial Intelligence that describes the development of a system through the application of actions [3]. A planning task is defined by an initial state, a set of actions with preconditions and efects on the current state, and a goal condition. States can be seen as finite first-order (FO) interpretations, and all conditions are specified by FO-formulas that are interpreted on the current state under closed-world semantics, i.e. absent facts are assumed to be false. A (ground) action is applicable if its precondition is satisfied in the current state w.r.t. an assignment of its variables. The objective is to select a sequence of applicable actions to reach the goal, called a plan. To facilitate expressive reasoning in the standard closed-world planning formalisms, logical theories under open-world semantics can be added to describe the possible interactions between objects of a domain of interest. Particularly, we are interested in Description Logics (DLs) and their application in reasoning about the individual states of a system. The main challenge is to reconcile the open-world nature of DLs and the closed-world semantics employed in classical planning. Explicit-input Knowledge and Action Bases (eKABs) combine planning with the description logic DL-Lite [4]. There, states (ABoxes) are interpreted using open-world semantics w.r.t. a background ontology (TBox) specifying intensional knowledge using DL-Lite axioms. The background ontology describes constraints on the state and entails additional facts that hold implicitly. Such a planning problem can be compiled into the classical planning domain definition language (PDDL) using query rewriting techniques [4].
on_block ⊑ on, ∃on_block− on_table ⊑ on, ∃on_table− on, ∃on_block−
⊑ Block, funct on_block, Implicitly, we know 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). On the other hand, we know that on_block(1, 3) cannot hold, since the on_block relation is functional (funct on_block).
Consider now the 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, this action 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, the action would remove on_block(1, 2) and insert on_block(1, 3), as Block(2) and Block(3) are entailed.
One property of this formalism is that action efects ignore implicit knowledge and only check whether the subsequent state is consistent with the TBox.
Example 2. The efect of the ground action move(1, 2, 3) is to add on_block(1, 3) to the state. In the eKAB formalism, this would make the state inconsistent, as argued previously.
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 would not afect the state at all, and [on(1, 2)] would continue to hold due to on_block(1, 2).
Moreover, even if we explicitly remove on_block(1, 2), we would lose the information that 2 is a block, which means that we should add Block(2) as well.
Example 2 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. Addressing
these challenges, the coherence update semantics was introduced for updating an ABox in the presence
of a DL-Lite TBox, where the updated ABox can be computed with a non-recursive Datalog¬ program
[
Here, we consider DL-Lite(ℋℱ ) [
The coherence update semantics [
Example 3. We express the efect of the action move(1, 2, 3) in Example 1 by the above update . Using coherence update semantics, we do not have to distinguish the type of 2 and can simply use del(on(1, 2)) instead. u is applied to an initial dataset containing the
To compute the efects of , a Datalog¬ program ℛ
assertions from as well as the translated update requests ins__request(⃗) (del__request(⃗)) for each
ins((⃗)) (del((⃗)) in [
First, the program ℛu translates the requests into direct insertion and deletion instructions: del_on(, ) ← ins_on_block(, ) ← ¬ on(, ), del_on_request(, )
on_block(, ), ins_on_block_request(, ) However, the first rule has no efect since on(1, 2) is not in the ABox. Instead, we have to remove on_block(1, 2) since on_block ⊑ on ∈ (cf. (i) from Example 2): del_on_block(, ) ←
on_block(, ), del_on_request(, ) Additionally, adding on_block(1, 3) also ensures that on_block(1, 2) gets deleted, since otherwise the functionality of on_block would be violated (cf. (iii)): del_on_block(, ) ←
on_block(, ), ins_on_block_request(, ), ̸= Finally, due to ∃on_block− ⊑ Block ∈ , the program retains the information Block(2) when on_block(1, 2) is deleted, by first deriving ins_block_closure (2) (cf. (ii)): ins_block_closure() ← del_on_block(, ), ¬Block(), ¬ins_block_request(), ¬del_block_request() This is then translated into an insertion operation if there are no conflicting requests that would cause an inconsistency (recall that Block ⊑ ¬Table ∈ ):
ins_block() ← ins_block_closure(), ¬ins_table_request() In summary, the above rules derive ins_on_block(1, 3), del_on_block(1, 2), and ins_block(2).
u checks whether the same tuple is requested to be added to on_block and
In addition, the program ℛ removed from on, as this is forbidden by the coherence semantics:
incompatible_update() ← ins_on_block_request(, ), del_on_request(, )
For planning, we lift the coherence update semantics to apply it to all actions in a planning problem. Our ceKAB semantics retains the favourable behaviours of the epistemic eKAB semantics for action conditions and of the coherence update semantics for single-step updates of DL-Lite ABoxes. In particular, it is possible to rewrite all operations into Datalog¬, and therefore into classical planning with derived predicates, in polynomial time.
A Polynomial Compilation Scheme for ceKABs. A compilation scheme translates a ceKAB
planning task to a PDDL task s.t. a plan for the ceKAB exists if a plan for the PDDL exists. Additionally,
if the translation is polynomially bounded in the size of the eKAB task, then the compilation scheme is
polynomial. We develop a polynomial compilation scheme by extending the known eKAB-to-PDDL
compilation from [
Deciding Plan Existence for ceKABs. The coherence plan existence problem decides whether a
plan exists for a DL-Lite ceKAB task. We study the complexity of the problem by means of a result by
Erol et al. [
Experimental Evaluation. We conduct a range of experiments to evaluate the feasibility of our
compilation and its performance compared to the pure eKAB semantics [
We use Downward Lab [
On most of the benchmarks, we observe that F̃︀F significantly outperforms FF in terms of memory
and CPU time due to the combinatorial explosion in the computation of the FF heuristic. In many
benchmark instances, heuristic search does not perform better than blind search, which indicates a weak
support for derived predicates in the heuristics in general. Compared to the original eKAB-to-PDDL
compilation [
In future work, we will try to extend ceKABs to support more expressive ontologies, and improve the planning performance by simplifying the Datalog¬ programs used in the compilations or by developing heuristics that better support the specific structure of the resulting 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).
The author(s) have not employed any Generative AI tools. [11] J. E. Doran, D. Michie, Experiments with the graph traverser program, Proceedings of the Royal
Society A 294 (1966) 235–259. [12] J. Hofmann, B. Nebel, The FF planning system: Fast plan generation through heuristic search, J.
Artif. Intell. Res. 14 (2001) 253–302. doi:10.1613/JAIR.855.