Journal Article

A Local Search Approach to Modelling and Solving Interval Algebra Problems

J. Thornton, M. Beaumont, A. Sattar and Michael Maher

in Journal of Logic and Computation

Volume 14, issue 1, pages 93-112
Published in print February 2004 | ISSN: 0955-792X
Published online February 2004 | e-ISSN: 1465-363X | DOI:
A Local Search Approach to Modelling and Solving Interval Algebra Problems

Show Summary Details


Local search techniques have attracted considerable interest in the artificial intelligence community since the development of GSAT and the min-conflicts heuristic for solving propositional satisfiability (SAT) problems and binary constraint satisfaction problems (CSPs) respectively. Newer techniques, such as the discrete Langrangian method (DLM), have significantly improved on GSAT and can also be applied to general constraint satisfaction and optimization. However, local search has yet to be successfully employed in solving temporal constraint satisfaction problems (TCSPs). This paper argues that current formalisms for representing TCSPs are inappropriate for a local search approach, and proposes an alternative CSP-based end-point ordering model for temporal reasoning. The paper looks at modelling and solving problems formulated using Allen's interval algebra (IA) and proposes a new constraint weighting algorithm derived from DLM. Using a set of randomly generated IA problems, it is shown that local search outperforms existing consistency-enforcing algorithms on those problems that the existing techniques find most difficult.

Keywords: Temporal reasoning, interval algebra, constraint satisfaction, local search

Journal Article.  0 words. 

Subjects: Computing ; Logic

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.