修订版报告：基于时间的约束传播算法：点与区间表示的对比与扩展
68 浏览量
更新于2024-08-25
收藏 202KB PDF 举报
"《约束传播算法在时间推理中的应用：修订报告》是Marc Vilain、Henry Kautz和Petervan Beek合作撰写的一篇论文，发表于1986年的AAAI会议上并在此基础上进行了修订。该报告关注的是计算科学领域，特别是人工智能中的时间推理问题。原始论文主要探讨了基于区间和点的两种时间表示方法在处理时间约束时的计算复杂性。
在基于区间的表示方法中，计算时间断言的后果被证明是计算上不可行的，因为涉及到复杂的区间操作和合并。相比之下，点表示法则显得更为有效，尽管它可能无法完全表达所有区间特性，但其处理简单的时间点关系的能力使得某些计算问题变得可解决。论文指出，之前关于点代数的一些错误陈述在修订版中得到了纠正，同时也引入了van Beek在1989年相关研究成果的深入分析。
时间推理在人工智能领域一直是一个持续的关注点，因为它对于构建能够理解和处理事件顺序、持续时间以及事件间依赖关系的智能系统至关重要。通过对比和改进这两种时间表示方法，该报告不仅展示了约束传播算法在处理时间约束时的不同策略，还探讨了如何有效地利用点表示法的可计算优势来优化问题求解过程。
总体来说，这篇修订报告为理解时间推理中的约束传播算法提供了一个深入而全面的视角，特别是在处理复杂时间逻辑时，强调了适当选择合适的时间表示方法对于算法性能和效率的重要性。对于从事人工智能、知识表示或规划领域的研究人员和开发者来说，这是一份极具价值的参考资料，可以帮助他们设计更有效的解决方案来处理动态和时间相关的任务。"
Constraint Propagation Algorithms
for Temporal Reasoning:
A Revised Report
Marc Vilain Henry Kautz Peter van Beek
The MITRE Corporation AT&T Bell Laboratories Dept. of Computer Science
Burlington Rd. 600 Mountain Ave. University of Waterloo
Bedford, Mass. 01730 Murray Hill NJ 07974 Waterloo, Ontario, Canada N2L 3G1
Abstract: This paper revises and expands upon a paper presented by two of the present authors at AAAI 1986
[Vilain & Kautz 1986]. As with the original, this revised document considers computational aspects of interval-
based and point-based temporal representations. Computing the consequences of temporal assertions is
shown to be computationally intractable in the interval-based representation, but not in the point-based one.
However, a fragment of the interval language can be expressed using the point language and benefits from the
tractability of the latter. The present paper departs from the original primarily in correcting claims made there
about the point algebra, and in presenting some closely related results of van Beek [1989].
The representation of time has been a recurring concern
of Artificial Intelligence researchers. Many represen-
tation schemes have been proposed for temporal
reasoning; of these, one of the most attractive is James
Allen's algebra of temporal intervals [Allen 1983]. This
representation scheme is particularly appealing for its
simplicity and for its ease of implementation with
constraint propagation algorithms. Reasoners based on
this algebra have been put to use in several ways. For
example, the planning system of Allen and Koomen
[1983] relies heavily on the temporal algebra to perform
reasoning about the ordering of actions. Elegant
approaches such as this one may be compromised,
however, by computational characteristics of the interval
algebra. This paper concerns itself with the
computational aspects of Allen's algebra, and of two
variants of a simpler algebra of time points.
Our perspective here is primarily computation-theoretic.
We approach the problem of temporal representation by
asking questions of complexity and tractability. In this
light, this paper establishes some formal results about
these temporal algebras. In brief these results are:
• Determining consistency of statements in the
interval algebra is NP-hard, as is determining the
deductive closure of these statements. Allen's
polynomial-time constraint propagation algorithm
for deductive closure is thus incomplete.
• We define a restricted form of the interval
algebra, concerned with measuring the relative
durations of events. This algebra can be
formulated in terms of a time point algebra
without disequality (≠). Allen's propagation
algorithm is sound and complete for this
fragment, and operates in O(n
3
) time and O(n
2
)
space.
• We also define a broader interval algebra
fragment, corresponding to the time point algebra
with ≠. A variant propagation algorithm performs
closure in this fragment in O(n
4
) time.
Throughout the paper, we consider how these formal
results affect practical Artificial Intelligence programs.
The Interval Algebra
Allen's interval algebra has been described in detail in
[Allen 1983]. In brief, the elements of the algebra are
relations that may exist between intervals of time.
Because the algebra allows for indefiniteness in
temporal relations, it admits many possible relations
between intervals (2
13
in fact). But all of these relations
can be expressed as vectors of definite simple relations,
of which there are only thirteen. The thirteen simple
A B
A BEFORE B
B AFTER A
A B
A MEETS B
B MET-BY A
A
B
A OVERLAPS B
B OVERLAPPED-BY A
A
B
A STARTS B
B STARTED-BY A
A
B
A DURING B
B CONTAINS A
A
B
A ENDS B
B ENDED-BY A
A
B
A EQUALS B
Figure 1: Simple Interval Relations
下载后可阅读完整内容，剩余9页未读，立即下载
2010-10-19 上传
2011-04-08 上传
2017-07-06 上传
2023-06-07 上传
2023-06-11 上传
2023-12-08 上传
2024-10-12 上传
2023-06-28 上传
2023-06-10 上传
weixin_38565221
- 粉丝: 6
- 资源: 946
我的内容管理
展开
最新资源
- 前端协作项目：发布猜图游戏功能与待修复事项
- Spring框架REST服务开发实践指南
- ALU课设实现基础与高级运算功能
- 深入了解STK：C++音频信号处理综合工具套件
- 华中科技大学电信学院软件无线电实验资料汇总
- CGSN数据解析与集成验证工具集：Python和Shell脚本
- Java实现的远程视频会议系统开发教程
- Change-OEM: 用Java修改Windows OEM信息与Logo
- cmnd：文本到远程API的桥接平台开发
- 解决BIOS刷写错误28：PRR.exe的应用与效果
- 深度学习对抗攻击库：adversarial_robustness_toolbox 1.10.0
- Win7系统CP2102驱动下载与安装指南
- 深入理解Java中的函数式编程技巧
- GY-906 MLX90614ESF传感器模块温度采集应用资料
- Adversarial Robustness Toolbox 1.15.1 工具包安装教程
- GNU Radio的供应商中立SDR开发包：gr-sdr介绍
