LLM2D
基于模式的图可达性逻辑重构
A Schema-aware Logic Reformulation for Graph Reachability
作者: Davide Di Pierro, Stefano Ferilli
发布日期: 10/4/2024
arXiv ID: oai:arXiv.org:2410.02533v1

摘要

图可达性是指理解图中两个不同点是否通过弧线连接,弧线通常带有语义信息。可达性在运动规划、路由等领域有着广泛的应用。为了避免传统深度优先和广度优先策略的复杂性(通常在逻辑语言中实现),提高可达性需要对关系进行结构化知识的了解。在某些情况下,图会通过其模式定义进行丰富,为每条弧线建立域和范围。引入模式感知的正式化来指导搜索,可以通过剔除无用路径并优先考虑原则上更早到达目标的路径,从而实现显著的改进。在本研究中,我们提出了一种策略,通过利用实例的高级概念化来自动排除和排序某些图路径。目标是获得图可达性场景的新的一阶逻辑重构,能够在时间、空间需求和回溯次数方面改进传统算法。实验结果表明,该方法在减少搜索策略中的回溯次数方面具有预期优势,从而节省了时间和空间。