Exploiting Limited Interactions in Plan Optimization

Abstract

Past Planning systems have generally focused on structures capable of working in all domains (domain-independent planning) or on specific heuristics for a particular applied domain (domain-dependent planning). An alternate approach is to abstract the kinds of goal and subgoal interactions that occur in some set of related problem domains, and develop planning techniques capable of performing relatively efficiently in all domains in which no other kinds of interactions occur. In this paper we will demonstrate this approach on a particular formulation of multiple-goal planning problems. In particular, we demonstrate that for cases where multiple-goal planning can be performed by generating individual separate plans for each goal independently and then optimizing the conjunction, we can define a set of limitations on the allowable interactions between goals that allow efficient planning to occur where the restrictions hold. We further argue that these restrictions are satisfied across a significant class of planning domains. We present algorithms which are efficient for special cases of multiple-goal planning, propose a heuristic search algorithm that performs well in a more general case, and describe a statistical study that demonstrates the efficiency of this search algorithm.