Experimenting with a temporal constraint propagation algorithm

Debasis Mitra

doi:10.1007/BF00117600

1996-01-01

PRE

Debasis Mitra *

Rasiah Loganantharaj

DOI：10.1007/BF00117600

原文链接

原文求助

摘要

En 中文

3-consistency algorithm for temporal constraint propagation over interval-based network, proposed by James Alien, is finding its use in many practical temporal reasoning systems. Apart from the polynomial behavior of this algorithm with respect to the number of nodes in the network, very little is known about its time complexity with respect to other properties of the initially given temporal constraints. In this article we have reported some of our results analyzing the complexity with respect to some structural parameters of the input constraint network. We have identified some regions, with respect to the structural parameters of the input network, where the algorithm takes much more time than it needs over other regions. Similar features have been observed in recent studies on NP-hard problems. Average case complexity of Alien's algorithm is also studied empirically, over a hundred thousand randomly generated networks, and the growth rate is observed to be of the order of quadratic with respect to the problem size (at least up to node 40, and expected to be lower above that). We have analyzed our data statistically to develop a model with which one can calculate the expected time to be consumed by the algorithm for a given input network.

Keyword:

3-consistency

experimental results

temporal reasoning

qualitative interval relations

complexity of propagation