Plan Reordering and Parallel Execution - A Parameterized Complexity View

Meysam Aghighi, Christer BäckströmAAAI 2017 · DOI

Introduction

Automated planning traditionally focuses on generating a sequence of actions to reach a goal. However, these "total-order" plans are often suboptimal for real-world execution, where multiple agents or parallel processes can operate simultaneously. Converting a linear sequence into a "partial-order" plan—a process known as plan relaxation—allows for concurrency and increased flexibility.

While finding the optimal relaxation is known to be NP-complete, this paper investigates whether specific problem parameters allow for efficient solutions. By applying the lens of parameterized complexity, the authors identify which characteristics of a plan make optimization tractable, moving beyond the standard "hard" or "easy" binary.

Problem Formulations

The research focuses on three primary computational challenges associated with plan relaxation and parallelization:

  1. Minimum Constrained Deordering (MCD): Finding a subset of the original plan's constraints to reach a target size while maintaining validity.
  2. Minimum Constrained Reordering (MCR): Finding any valid partial order of a specific target size, not necessarily by subsetting the original constraints.
  3. Parallel Plan Length (PPL): Seeking the shortest possible execution time for a plan, given a "non-concurrency" relation—a set of rules defining which actions cannot be executed simultaneously.

Methodology: Parameterized Complexity

Rather than viewing problem difficulty solely as a function of total input size ($n$), the authors utilize the Parameterized Complexity framework. This approach decomposes the difficulty of a problem based on specific input parameters ($k$):

  • FPT (Fixed-Parameter Tractable): Problems that can be solved in time $f(k) \cdot n^{O(1)}$. If the parameter $k$ is small, the problem is efficiently solvable even if the total input is large.
  • W[2]-hard: Problems that are likely not solvable efficiently, even when the parameter $k$ is small.

As a theoretical study, the authors rely on mathematical proofs and reductions from classical problems like Dominating Set, Graph Coloring, and Precedence Constrained Scheduling to categorize these planning problems.

Key Insights and Complexity Results

The Gap Between Original and Desired Size

A significant finding of the paper is the asymmetry between deordering and reordering. MCD is found to be FPT when parameterized by the size of the original plan order ($n_\prec$). This suggests that simplifying an existing small plan is computationally manageable. Conversely, MCR is W[2]-hard when parameterized by the desired target size ($n_{\prec'}$). This indicates that searching for a small, valid partial order within a large space of possibilities remains difficult, even if the target size itself is small.

The Role of Non-Concurrency

In the context of parallel execution (PPL), the authors identify the "non-concurrency relation" ($n_\#$) as a critical parameter. This relation represents the number of action pairs that are forbidden from running at the same time. The study proves that PPL is FPT with respect to the size of this relation. This is a "magic" parameter: if the number of conflicting action pairs is low, the shortest parallel execution can be found efficiently, regardless of the total number of actions in the plan.

Resource Constraints and the Processor Bottleneck

The complexity shifts when moving from an idealized "infinite processor" model to a realistic scenario with a fixed number of processors ($k$). The authors demonstrate that restricting the number of agents makes the parallel execution problem significantly harder (para-NP-hard). This confirms that resource scheduling is a primary driver of complexity. Even with small plan lengths or low non-concurrency degrees, the introduction of a processor limit ($PPL_k$) often removes the possibility of FPT algorithms unless the number of processors is also treated as a parameter.

Conclusion and Future Directions

This research provides a theoretical "map" for plan optimization. By identifying parameters like the non-concurrency relation and original plan size, the authors highlight specific conditions under which plan relaxation is tractable.

While the paper provides the mathematical foundation, it does not implement these FPT algorithms on real-world benchmarks. The authors suggest that future work should explore structural parameters, such as the treewidth of the non-concurrency graph, which might reveal further tractable sub-cases. Additionally, extending the analysis to actions with varying durations remains a vital area for study, as allowing actions of different lengths (e.g., lengths 1 and 2) makes the scheduling problem much harder, even with only two processors.

Summary updated

BibTeX
@inproceedings{aghighi2017plan,
  author = {Meysam Aghighi and Christer Bäckström},
  title = {{Plan Reordering and Parallel Execution - A Parameterized Complexity View}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11025},
}
Figure