Skip to main content
Download PDF
- Main
Coping with disjunctions in temporal constraint satisfaction problem
Abstract
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.
Main Content
For improved accessibility of PDF content, download the file to your device.
Enter the password to open this PDF file:
File name:
-
File size:
-
Title:
-
Author:
-
Subject:
-
Keywords:
-
Creation Date:
-
Modification Date:
-
Creator:
-
PDF Producer:
-
PDF Version:
-
Page Count:
-
Page Size:
-
Fast Web View:
-
Preparing document for printing…
0%