Merging Plans with Quantitative Temporal Constraints, Temporally Extended Actions, and Conditional Branches

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.