Parallel Non-Binary Planning in Polynomial Time

Christer Bäckström, Inger KleinIJCAI 1991

Introduction

In the field of AI planning, researchers often encounter a "complexity wall" where general-purpose planners, such as TWEAK, are undecidable or NP-hard. This computational burden makes them impractical for real-time industrial applications. However, many real-world domains, particularly in sequential control for assembly lines or chemical plants, do not require the full expressive power of general planners. This paper introduces a framework that is non-binary, parallel, and tractable, specifically tailored for these practical environments.

The SAS-PUS Problem Class

The authors define a new class of planning problems called SAS-PUS (Simplified Action Structures - Post-unique, Unary, Single-valued). The tractability of this class is achieved through three key structural restrictions:

  1. Post-unique: For any given state variable value, there is at most one type of action that can produce it. This eliminates the branching choices that typically lead to exponential search trees.
  2. Unary: Each action modifies exactly one state variable.
  3. Single-valued: If multiple actions require a specific variable value to persist during execution (a "prevail-condition"), that value must be the same for all such actions in the plan.

Methodology: Algorithm 4.1

The core contribution is Algorithm 4.1, which utilizes a BuildChain function to construct plans. Rather than exploring the entire state space, the algorithm identifies the necessary transitions for each variable and chains them together. It then computes a transitive closure to establish a partial ordering of actions, naturally identifying opportunities for parallel execution.

Table of actions for the LEGO car assembly, defining pre-conditions, post-conditions, and prevail-conditions.

Case Study: LEGO Car Assembly

The approach is validated using a simplified LEGO car factory model. The task involves assembling a car from three components: a chassis, a top, and wheels, each stored in separate locations. Three state variables represent the status of these components, each with multiple possible values.

Diagram of the LEGO car assembly process, illustrating the flow of components from storage to the workstation.

The action set includes six distinct operations, such as moving parts to the workstation and mounting them. The SAS-PUS constraints allow the planner to efficiently determine which parts can be moved simultaneously and the exact sequence required for assembly, producing a maximally parallel plan.

Results and Complexity

The algorithm is proven to run in $O(m^3n^3)$ time and $O(m^2n^2)$ space, where $m$ is the number of state variables and $n$ is the maximum number of values per variable. It is both sound and complete for the SAS-PUS class, guaranteed to find a minimal, maximally parallel plan if one exists. This demonstrates that by intentionally restricting action expressivity, planning moves from intractable to highly efficient.

Conclusion and Future Work

While SAS-PUS is powerful for sequential control, it has limitations, such as the unary constraint and single-valuedness. Future research aims to relax these restrictions to handle interdependent parallel actions and time-sensitive constraints while maintaining polynomial-time complexity.

Summary updated

BibTeX
@inproceedings{backstrom1991parallel,
  author = {Christer Bäckström and Inger Klein},
  title = {{Parallel Non-Binary Planning in Polynomial Time}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure