Merging separately generated plans with restricted interactions

Generating action sequences to achieve a set of goals is a computationally dicult task. When multiple goals are present, the problem is even worse. Although many solu-tions to this problem have been discussed in the literature, practical solutions focus on the use of restricted mechanisms for planning or the application of domain dependent heuristics for providing rapid solutions (i.e. domain-dependent planning). One previ-ously proposed technique for handling multiple goals eciently is to design a planner or even a set of planners (usually domain-dependent) that can be used to generate sep-arate plans for each goal. The outputs are typically either restricted to be independent and then concatenated into a single global plan, or else they are merged together using complex heuristic techniques. In this paper we explore a set of limitations, less restric-tive than the assumption of independence, that still allow for the ecient merging of separate plans using straightforward algorithmic techniques. In particular, we demonstrate that for cases where separate plans can be individually generated, we can dene a set of limitations on the allowable interactions between goal