时序动态知识图上的交替溯因与规划方法 APT
Alternating Abduction and Planning over Temporal Dynamic Knowledge Graphs
AI 导读
一篇 arXiv 论文针对时序动态知识图(TDKG,即带删除/插入规则动作的 SROIQ 知识库)中动作后果部分可知、所需事实未知及可能引发不一致的问题,提出三个工具:时序投影、DDA 溯因和 APT 规划。
正文 · 原文
Abstract: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: temporal projection, 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 sub-goal, up to a depth bound. The tools use a SROIQ reasoner only through a small contract, so they depend neither on a particular reasoner nor on a particular data structure; they are designed for a reasoner that processes added and removed axioms incrementally. Change is treated without modal operators, on one linear timeline and without possible worlds, so decidability of projection follows from that of SROIQ. We prove that indirect effects are exactly the entailments of the updated state, that DDA and APT are sound and terminate, and that bounded planning is 2NExpTime-hard and in 3ExpTime. We compare the tools with hitting-set abduction, the solver CATS and classical planning, and run them on six benchmarks and five reasoners with identical results.
| Subjects: | Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO) |
| Cite as: | arXiv:2607.27287 [cs.AI] |
| (or arXiv:2607.27287v4 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2607.27287 arXiv-issued DOI via DataCite |
Submission history
From: Amir Hossein Sharafi [view email]
[v1]
Wed, 29 Jul 2026 14:44:46 UTC (37 KB)
[v2]
Wed, 2 Sep 2026 14:50:41 UTC (35 KB)
[v3]
Mon, 9 Nov 2026 08:05:25 UTC (81 KB)
[v4]
Tue, 17 Nov 2026 07:07:06 UTC (91 KB)
来源:arXiv cs.AI · arxiv.org