Probabilistic approach improves representing uncertain temporal relationships
PAA: The Probabilistic Allen Algebra: A Generative and Complete Probabilistic Extension of Allen's Interval Relations
Artificial IntelligenceComputation and Language
Summary
Allen's interval algebra traditionally deals with time intervals using exact start and end points, but real-world timing is often uncertain and fuzzy. The authors develop a new probabilistic version that models time points and durations as statistical distributions, allowing for graded and uncertain expressions like "just before" or "roughly during." Their approach mathematically derives all the classic interval relations using probabilities instead of crisp rules, maintaining a consistent hierarchy and allowing more realistic temporal reasoning. They also provide open-source Python code to make this method accessible.
What this means in practice
- •For natural language processing teams: Represent and reason about vague temporal expressions in text with probabilistic interval relations.
- •For database management teams: Manage and query temporal data with uncertain or approximate intervals using a probabilistic algebra.
- •For event scheduling software teams: Employ probabilistic time interval reasoning to handle uncertain or flexible event boundaries for better scheduling.$Commercial implications: Enables development of scheduling tools that better handle uncertain or approximate timing, improving user experience and reliability.
Authors
Julian Eggert
Abstract
Allen's interval algebra is a qualitative calculus for temporal relations, but its thirteen base relations are crisp predicates over exact interval boundaries. This is inadequate for temporal information from language, perception, databases, or uncertain histories, where times, durations, and boundaries are uncertain and expressions such as "just before" or "roughly during" have graded meaning. We develop the probabilistic Allen algebra (PAA): a generative and complete extension in which relation probabilities are derived from distributions over interval boundaries rather than assigned as scores. Time points are Gaussian; intervals have Gaussian midpoints and truncated-Gaussian durations. Every relation is a boundary-ordering predicate in one common probability space: point-point relations reduce to error functions, and point-interval and interval-interval relations to multivariate Gaussian orthant probabilities induced by linear inequalities. Contact relations (meets, starts, finishes, equals) receive positive measure through a tolerance band, and under a single tolerance the thirteen relations form a true partition that recovers crisp Allen as the tolerance vanishes. The construction derives Allen's taxonomy rather than positing it: coarse predicates such as precedence, overlap, and containment are unions of leaves whose probabilities are leaf sums, and this hierarchy is preserved as intervals collapse to points and thirteen relations reduce to five and then three. Each relation further decomposes into correlation-aware temporal primitives in the spirit of CIDOC CRM. The algebra is scale-invariant and separates graded expressions such as "shortly before" from contact relations. All results are Monte-Carlo validated and shipped as an open, tested Python package.