Eddie Schwalb

AAAI Conference 1997 Conference Paper

A New Unification Method for Temporal Reasoning with Constraints

• Eddie Schwalb

In this work we consider using logic programs to perform temporal reasoning. We identify some difficulties of combining constraint propagation and generalized resolution when temporal information is represented using tokens. We show that standard top-down evaluation (i. e. resolution) is incomplete due to the inability to unify constraints and ground terms. We present some syqtactic restrictions that enable temporal resolution. Under these restrictions, we propose a new unification method composed of constraint unification and token fusion algorithms. Incorporating them within a generalized resolution scheme render it, complete.

AIJ Journal 1997 Journal Article

Processing disjunctions in temporal constraint networks

• Eddie Schwalb
• Rina Dechter

Temporal constraint satisfaction problems (TCSPs) provide a formal framework for representing and processing temporal knowledge. Deciding the consistency of TCSPs is known to be intractable. We demonstrate that even local consistency algorithms like path-consistency (PC) can be exponential on TCSPs due to the fragmentation problem. We present two new polynomial approximation algorithms, Upper-Lower Tightening (ULT) and Loose Path-Consistency (LPC), which are efficient yet effective in detecting inconsistencies and reducing fragmentation. Our experiments on hard problems in the transition region show that LPC has the best effectiveness-efficiency tradeoff for processing TCSPs. When incorporated within backtrack search, LPC is capable of improving search performance by orders of magnitude.

TIME Conference 1996 Conference Paper

A Theory of Time and Temporal Incidence Based on Instants and Periods

• Lluís Vila
• Eddie Schwalb

Time is fundamental in representing and reasoning about changing domains. A proper temporal representation requires characterizing two notions: (1) time itself, and (2) temporal incidence, i. e. the domain-independent properties for the truth-value of fluents and events throughout time. There are some problematic issues, such as the expression of instantaneous events and instantaneous holding of fluents, the specification of the properties for the temporal holding of fluents, and the "dividing instant problem". This paper presents a theory of time and temporal incidence which is more natural than its predecessors and satisfactorily addresses the issues above. Our theory of time, called /spl Iscr//spl Pscr/ (Instants and Periods), is based on having instants and periods at equal levels. We define a theory of temporal incidence upon it, whose main original feature is the distinction between continuous and discrete fluents.

TIME Conference 1996 Conference Paper

Logic Programming with Temporal Constraints

• Eddie Schwalb
• Lluís Vila

Combines logic programming and temporal constraint processing techniques in a language called TCLP (Temporal Constraint Logic Programming), which augments logic programs with temporal constraints. Known algorithms for processing disjunctions in temporal constraint networks are applied. We identify a decidable fragment called Simple TCLP, which can be viewed as extending Datalog with limited functions to accommodate intervals of occurrence and temporal constraints between them. Some of the restrictions introduced by Simple TCLP are overcome by a syntactic structure which provides it with the benefits of reification. The latter allows quantification on temporal occurrences and relation symbols.

TIME Conference 1996 Conference Paper

Processing Disjunctions of Temporal Constraints

• Eddie Schwalb
• Rina Dechter

Describes new algorithms for processing quantitative temporal constraint satisfaction problems (TCSPs). In contrast to discrete CSPs, enforcing path consistency on TCSPs is exponential due to the fragmentation problem. We present an efficient polynomial constraint propagation algorithm, called "loose-path consistency" (LPC), which is shown to improve the performance of backtrack search algorithms by orders of magnitude. The tradeoffs between the effectiveness and efficiency of LPC are analyzed. We report the presence of a phase transition on this domain and perform an empirical evaluation on problems which lie in the transition region.

AAAI Conference 1994 Conference Paper

Temporal Reasoning with Constraints on Fluents and Events

• Eddie Schwalb

We propose a propositional language for temporal reasoning that is computationally effective yet expressive enough to describe information about fluents, events and temporal constraints. Although the complete inference algorithm is exponential, we characterize a tractable core with limited expressibility and inferential power. Our results render a variety of constraint propagation techniques applicable for reasoning with constraints on Auents.

ICML Conference 1993 Conference Paper

Compiling Bayesian Networks into Neural Networks

• Eddie Schwalb

AAAI Conference 1993 Conference Paper

Coping With Disjunctions in Temporal Constraint Satisfaction Problems

• Eddie Schwalb

Path-consistency algorithms, which are polynomial for discrete problems, are exponential when applied to problems involving quantitative temporal information. The source of complexity stems from specifying relationships between pairs of time points as disjunction of intervals. We propose a polynomial algorithm, called ULT, that approximates path-consistency in Temporal Constraint Satisfaction Problems (TCSPs). We compare ULT empirically to path-consistency and directional path-consistency algorithms. When used as a preprocessing to backtracking, ULT is shown to be 10 times more effective then either DPC or PC-2.