Merging Plans with Quantitative Temporal Constraints, Temporally Extended Actions, and Conditional Branches
Ioannis Tsamardinos, Martha E. Pollack, John F. Horty · 2000
We develop an algorithm for merging plans that are represented in a richly expressive language. Speci#cally,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 #nds 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 #rst, 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 byYang #1997# to suggest a potential resolution of the identi#ed con- #icts. Finally, the CSTN is again used to check whether the proposed resolution observes all the temporal constraints. Wehave implemented our approach, and we present preliminary experimental evidence about domain factors that in#uence its performa...