A least commitment approach to avoiding protection violations in nonlinear planning

We suggest one alternative approach to creating a valid plan in which all temporal constraints are mutually satisfiable and all preconditions for actions hold where required. While simultaneously maintaining information on the status of protection intervals for all required preconditions in the plan, our approach avoids premature imposition of temporal constraints to correct for protection violations. At the expense of additional bookkeeping, we adopt the least commitment strategy of attempting to correct those protection violations which can be corrected in only one way. By postponing choice as much as possible, we attempt to generate a search tree with fewer nodes. Since scheduling problems which arise in our planning context are inherently intractable, our approach does not rule out the possibility of extensive search. However, it might well be a preferable mechanism for a planner which adopts a general least commitment strategy.