Alternating Abduction and Planning over Temporal Dynamic Knowledge Graphs

원문 초록

Knowledge graphs change over time, but the effects of actions on them are only partly stated: the ontology entails further consequences, facts that an action needs are often unknown, and an action may make the graph inconsistent. We study these problems for Temporal Dynamic Knowledge Graphs (TDKGs), that is, SROIQ knowledge bases whose actions are rules with delete/insert templates and whose events lie on an intrinsic timeline. We present three tools that use a SROIQ reasoner only through a few operations: temporal projection, which plays the events along the timeline and is the exact test of plans; DDA (Direct-Derivation Abduction), which explains an observation by assuming its negation and negating what the reasoner newly derives; and APT (Abduction and Planning over TDKGs), which plans backwards from a goal, assumes the facts that the plan needs but nobody stated, and lets DDA explain the assumptions, each explanation becoming a new goal for a sub-plan, up to a depth bound. The same machinery synthesises action sequences that end in a chosen contradiction. We prove that projection is decidable and that the indirect effects of an action are exactly the entailments of the updated state; that DDA is sound, terminates and finds every single-assertion explanation; and that APT is sound and terminates, while bounded planning is decidable but 2NExpTime-hard. We compare the tools analytically with hitting-set abduction and classical planning, compare DDA with the abduction solver CATS on shared problems, and run them on six benchmarks. Five reasoners (HermiT, Konclude, Pellet, Openllet, JFact) return identical results. Their incremental modes answered some checks wrongly after removals and gave no speed-up; parallel calls help only when a single call is expensive.