Introduction
In classical AI planning, systems typically operate under the "closed-world assumption": any fact not explicitly stated in the current state is assumed to be false. While this simplifies computation, it fails to capture the nuances of real-world environments where background knowledge—or ontologies—can be used to infer hidden facts. For instance, an ontology might specify that any individual operating a machine is an employee, allowing a planner to infer "employee" status even if it isn't explicitly recorded in the database.
This research addresses the challenge of integrating expressive Horn Description Logics (DLs) into standard planning frameworks. By bridging the gap between open-world reasoning and closed-world planning, the authors enable more sophisticated domain modeling without sacrificing the efficiency of existing PDDL (Planning Domain Definition Language) solvers.
The Compilation Approach
The core contribution of this work is a novel compilation scheme that transforms an "explicit-input Knowledge and Action Base" (eKAB)—comprising a state, a set of actions, and an ontology—into a standard PDDL task. This allows the use of off-the-shelf planners to solve problems constrained by complex ontologies.
Key technical pillars of this approach include:
- Datalog-Rewritability: The authors demonstrate that if a DL's queries can be rewritten into Datalog with stratified negation, they can be mapped directly to PDDL's "derived predicates." This allows the planner to maintain a closed-world state while the derived predicates handle open-world inferences.
- Polynomial Rewriting for Horn-ALCHOIQ: A significant theoretical milestone is the development of a polynomial-sized Datalog rewriting for Horn-ALCHOIQ, one of the most expressive Horn logics. This ensures that the compiled PDDL files remain manageable in size.
- Complexity Boundaries: The research also establishes theoretical limits, proving a "no-go" theorem for the even more complex Horn-SROIQ. They show that polynomial-sized compilation for this logic is impossible unless there is an unlikely collapse in computational complexity theory.
Experimental Evaluation
The authors evaluated their "Horn" compiler against previous state-of-the-art specialized compilers (Cal16 and Bor21) using 125 instances from existing benchmarks and 110 new, more challenging instances designed to test expressive logics (e.g., Drones, Queens, and RobotConj).
As shown in the experimental results, the Horn compiler achieved 100% coverage, solving all 125 instances of the standard benchmarks. In contrast, previous methods like Bor21 struggled, particularly in the "Robot" domain. Furthermore, the Horn compiler demonstrated significantly lower planning times across most domains, often by several orders of magnitude.
Scalability and Discussion
A key insight from the study is that moving complexity from action definitions into the ontology can actually improve performance. In the "RobotConj" domain, which moves spatial logic into the ontology, the system scaled effortlessly to grid dimensions as large as 200x200.
The scalability analysis reveals that both compilation and planning times grow predictably (linearly or polynomially) with the problem size. This suggests that the added expressivity of Horn DLs acts as "syntactic sugar"—it makes domains easier for humans to model and more efficient for planners to process by simplifying individual action definitions.
Conclusion
This research successfully demonstrates that planning with expressive Horn Description Logics is not only theoretically sound but also practically superior to previous, more restrictive approaches. By leveraging general-purpose rewriters and PDDL derived predicates, the authors have provided a robust pathway for integrating open-world reasoning into mainstream AI planning. Future work remains to bridge the remaining theoretical gap for Horn-SHOIQ and to further optimize planners for the complex PDDL structures generated by these compilations.
Summary updated