A STRENGTHENED ALGORITHM FOR TEMPORAL REASONING ABOUT PLANS

Alien's interval algebra has been shown to be useful for representing plans. We present a strengthened algorithm for temporal reasoning abou t plans, which improves on straightforward applications of the existin g reasoning algorithms for the algebra. This is made possible by viewi ng plans as both temporal networks and hierarchical structures. The te mporal network view allows us to check for inconsistencies as well as propagate the effects of new temporal constraints, whereas the hierarc hical view helps us to get the strengthened results by taking into acc ount the dependency relationships between actions. We further apply ou r algorithm to the process of plan recognition through the analysis of natural language input. We show that such an application has two usef ul effects: the temporal relations derived from the natural language i nput can be used as constraints to reduce the number of candidate plan s, and the derived constraints can be made more specific by combining them with the prestored constraints in the plans being recognized.