TLDR: This research introduces “coherent eKABs (ceKABs),” a new formalism for automated planning that integrates background knowledge from DL-Lite ontologies with action effects using “coherence update semantics.” This ensures that implicit changes and consistency are automatically handled during planning. The authors show that ceKABs can be polynomially compiled into classical planning (PDDL), maintaining computational complexity, and demonstrate its practical feasibility through experiments, highlighting the importance of compilation variants and heuristics for performance.
Automated planning is a fundamental area within Artificial Intelligence, focusing on how a system can achieve a specific goal by applying a sequence of actions from an initial state. Traditionally, these planning systems operate under a “closed-world” assumption, meaning anything not explicitly stated as true is considered false. However, real-world scenarios often involve complex background knowledge, which is better represented using ontologies.
Ontologies, often interpreted under an “open-world” assumption (where something is only false if explicitly stated or derivable as false), provide a rich way to describe relationships and constraints between objects in a domain. Integrating this rich, open-world knowledge into closed-world planning systems presents a significant challenge: reconciling these two different ways of interpreting information.
One existing approach, called Explicit-input Knowledge and Action Bases (eKABs), combines planning with a type of ontology known as DL-Lite. In eKABs, the system’s state is interpreted with respect to a background ontology, which can infer additional facts implicitly. While eKABs allow for ontology-based action conditions, a key limitation arises with action effects. When an action changes the state, eKABs primarily operate on explicitly stated facts, often overlooking the implicit knowledge derived from the ontology. This can lead to inconsistencies or the loss of important information.
Consider a simple example: moving a block from one position to another. If the act of placing a block on another implicitly “blocks” the lower block, an eKAB system might only record the explicit move. If the original block was implicitly blocking another, and that implicit fact isn’t handled, the system could end up in an inconsistent state or lose track of the “blocked” status. This highlights the need for a more sophisticated way to handle action effects that respects the underlying ontology.
This is where “coherence update semantics” comes into play. This semantics, previously developed for single-step updates in DL-Lite ontologies, ensures that when a change occurs, the system automatically handles implicit effects. This means if you add a fact, any conflicting facts are removed to maintain consistency. Conversely, if you remove a fact, any stronger facts that implied it are also removed, and any previously implied facts that are no longer implied might need to be explicitly added to avoid losing information.
The research paper, titled “Automated Planning with Ontologies under Coherence Update Semantics,” introduces a new formalism called coherent eKABs (ceKABs). This approach extends eKAB planning by applying the coherence update semantics to action effects. Essentially, when an action is performed in a ceKAB system, it doesn’t just explicitly add or remove facts; it triggers a sophisticated update process that ensures the resulting state remains consistent with the ontology and accounts for all implicit changes.
The authors, Stefan Borgwardt, Duy Nhu, and Gabriele Röger, demonstrate that the complexity of this new formalism is no higher than previous approaches. They achieve this by showing that ceKAB planning tasks can be translated into classical planning problems (specifically, PDDL with derived predicates) using a polynomial compilation. This means that despite the added sophistication, the computational burden does not increase disproportionately.
Practical Implementation and Performance
To evaluate the feasibility and performance of their approach, the researchers implemented their ceKAB compilation and tested it against various benchmarks, including modified versions of classical planning problems like Blocks, Cats, and Robot. They compared its performance with the original eKAB semantics using the Fast Downward planning system.
Their experiments revealed that while supporting coherence update semantics adds some strain to the planning system, the compilation is practical. They explored different variants of their compilation and heuristic search strategies. Notably, a heuristic variant called ËœFF generally performed better, especially when combined with a Tseitin transformation, which simplifies logical conditions. This suggests that careful engineering of the compilation and the use of appropriate heuristics are crucial for practical performance.
Also Read:
- A New Framework for Temporal Reasoning with Constraints in Answer Set Programming
- KROMA: Enhancing Ontology Matching with Context-Aware Language Models
Future Directions
The paper concludes by discussing potential future work, such as extending this approach to more expressive description logics beyond DL-Lite. They also acknowledge that the coherence update semantics might not always be the most suitable choice for every scenario and suggest exploring combined semantics that allow switching between different update behaviors for specific operations. The challenges of improving heuristic search performance for derived predicates in planning systems are also highlighted as an area for further research.
This work represents a significant step forward in integrating rich ontological knowledge with automated planning, offering a more robust and semantically sound way to handle dynamic changes in complex domains. For more details, you can read the full research paper here.
