# Expressivity of Planning with Horn Description Logic Ontologies (Technical Report)

arXiv: https://arxiv.org/abs/2203.09361 · HTML: https://mlsanity.com/paper/2203.09361/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 47 references that are in the map.
- First posted on arXiv 17 Mar 2022.

## Builds on (most cited first, 2 of 2)

- [Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy](https://mlsanity.com/paper/1401.5266/) (2014)
- [Model Comparison Games for Horn Description Logics](https://mlsanity.com/paper/1904.06919/) (2019)

## Built on by (most cited first, 4 of 4)

- [Planning for Temporally Extended Goals in Pure-Past Linear Temporal Logic: A Polynomial Reduction to Standard Planning](https://mlsanity.com/paper/2204.09960/) (2022)
- [Towards Ontology-Mediated Planning with OWL DL Ontologies (Extended Version)](https://mlsanity.com/paper/2308.08200/) (2023)
- [Current and Future Challenges in Knowledge Representation and Reasoning](https://mlsanity.com/paper/2308.04161/) (2023)
- [Automated planning with ontologies under coherence update semantics (Extended Version)](https://mlsanity.com/paper/2507.15120/) (2025)

## Abstract (arXiv)

State constraints in AI Planning globally restrict the legal environment states. Standard planning languages make closed-domain and closed-world assumptions. Here we address open-world state constraints formalized by planning over a description logic (DL) ontology. Previously, this combination of DL and planning has been investigated for the light-weight DL DL-Lite. Here we propose a novel compilation scheme into standard PDDL with derived predicates, which applies to more expressive DLs and is based on the rewritability of DL queries into Datalog with stratified negation. We also provide a new rewritability result for the DL Horn-ALCHOIQ, which allows us to apply our compilation scheme to quite expressive ontologies. In contrast, we show that in the slight extension Horn-SROIQ no such compilation is possible unless the weak exponential hierarchy collapses. Finally, we show that our approach can outperform previous work on existing benchmarks for planning with DL ontologies, and is feasible on new benchmarks taking advantage of more expressive ontologies. That is an extended version of a paper accepted at AAAI 22.