Optimizing temporal reasoning algorithms
LE3 .A278 2004
2004
Trudel, Andre
Acadia University
Master of Science
Masters
Computer Science
Many fields such as linguistics, philosophy, and Artificial Intelligence (AI) utilize temporal information. We examine temporal reasoning algorithms based on Allen's Interval Algebra (IA) and explore potential optimizations that yield empirical and practical computational improvements to van Beek and Manchak's algorithms, which are recognized as being among the leading methods in this field. In independent experiments, we validated their results for small networks. For large networks, those with 250 nodes or more, our algorithm using a fully generated and stored composition table outperforms all of van Beek's algorithms. The implication is that for problems involving small networks, clever heuristics are useful. As network size increases, the cost of computing the heuristics becomes greater than their usefulness. In this case, it is best to use our approach of a full composition table.
The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.
https://scholar.acadiau.ca/islandora/object/theses:2780
