A Representation for Efficient Temporal Reasoning

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Temporal Resoning

It has been observed that the temporal reasoning component in a knowledge-based system is frequently a bottleneck. We investigate here a class of graphs appropriate for an interesting class of temporal domains and for which very efficient algorithms for reasoning are obtained, that of series-parallel graphs. These graphs can be used for example to model process execution, as well as various planning or scheduling activities. Events are represented by nodes of a graph and relationships are represented by edges labeled by <= or <. Graphs are composed using a sequence of series and parallel steps (recursively) on series-parallel graphs. We show that there is an 0(n) time pre-processing algorithm that allows us to answer queries about the events in O(1) time. Our results make use of a novel embedding of the graphs on the plane that is of independent interest. Finally we argue that these results may be incorporated in general graphs representing temporal events by extending the approach of Gerevini and Schubert.