Ioannis Tsamardinos, Martha E. Pollack, and John F. Horty
We develop an algorithm for merging plans that are represented in a richly expressive language. Specifically, we are concerned with plans that have (i) quantitative temporal constraints, (ii) actions that are not instantaneous, but rather have temporal extent, and (iii) conditional branches. Given a set S of such plans, our algorithm finds a set of constraints that jointly ensure that the plans in S are mutually consistent, if such a set of constraints exists. The algorithm has three phases. In the first, it employs a new data structure, a conditional simple temporal network (CSTN), to identify con icts between the plans. Next, it uses an approach developed by Yang (1997) to suggest a potential resolution of the identified conicts. Finally, the CSTN is again used to check whether the proposed resolution observes all the temporal constraints. We have implemented our approach, and we present preliminary experimental evidence about domain factors that influence its performance.