Planning for multiple goals with limited interactions

A description is presented of the problem of finding an optimal global plan for a multigoal planning problem by combining plans that solve the individual goals. This problem arises in process planning, when one tries to combine the process plans for individual machinable features into a global process plan for the entire workpiece. It also arises in the planning of robot actions, when one tries to combine the plans for the handling of individual objects into a global plan. The problem can be shown to be NP-hard in general. However, if only one plan is available for each goal, then the problem can be solved in time O(n²) by imposing restrictions on the kinds of intergoal interactions involved. If more than one plan is available for each goal, the problem is still NP-hard even if these restrictions are satisfied but in the case described, a heuristic search algorithm has been developed which performs well