A comparison of point-based approaches to qualitative temporal reasoning

We address the problem of implementing general, qualitative, point-based te mporal reasoning. Given a database of assertions concerning relative occurr ences of points in tune, we are interested in various operations on this da tabase, including compiling the assertions into a representation that suppo rts efficient reasoning, determining whether a database is consistent, and computing the strongest entailed relation between two points. We begin by s pecifying a set of operations and their corresponding algorithms, applicabl e to general point-based temporal domains. We next consider a special-purpo se reasoner, based on series-parallel graphs, which performs very well in a temporal domain with a particular restricted structure. We discuss the not ion of a metagraph, which encapsulates local structure inside metaedges and uses special purpose algorithms within such local structures, to obtain a fast general point-based reasoner. That is, specifically, we use a very fas t, series-parallel graph reasoner to speed up general point-based reasoning . We also analyse the TimeGraph reasoner of Gerevini and Schubert. For purp oses of comparison, we have implemented four approaches: a generic point-ba sed reasoner, the generic point-based reasoner with a ranking heuristic, a reasoner based on series-parallel graphs, and a version of Gerevini and Sch ubert's TimeGraph reasoner. We compare these different approaches, as well as the original TimeGraph-II reasoner of Gerevini and Schubert, on differen t data sets. We conclude that the series-parallel graph reasoner provides t he best overall performance: our results show that it dominated on domains exhibiting structure, and it degraded gracefully when conditions were less than ideal, in that it did worse than the generic approach by only a consta nt factor in this case. (C) 2001 Elsevier Science B. V. All rights reserved .