Nonlinear Planning with Parallel Resource Allocation

Most nonlinear problem solvers use a least-commitment search strategy, reasoning about partially ordered plans. Although partial orders are useful for exploiting parallelism in execution, least-commitment is NP-hard for complex domain descriptions with conditional effects. Instead, a casual-commitment strategy is developed, as a natural framework to reason and learn about control decisions in planning. This paper describes how NOLIMIT reasons about totally ordered plans using a casual-commitment strategy, how it generates a partially ordered solution from a totally ordered one by analyzing the dependencies among the plan steps, and finally how resources are allocated by exploiting the parallelism embedded in the partial order. We illustrate our claims with the implemented algorithms and several examples. This work has been done in the context of the PRODIGY architecture that incorporates NOLIMIT, a nonlinear problem solver.