Plan Reordering and Parallel Execution Ñ A Parameterized Complexity View

AAAI 2017

TL;DR

This paper dives into the computational complexity of planning problems, specifically how to optimize partial-order plans for more efficient execution. By applying parameterized complexity, the authors reveal which aspects of these problems make them computationally "hard" and which parameters allow for more tractable solutions, offering a more nuanced understanding than traditional NP-completeness results.

What Problem Does This Paper Address?

In artificial intelligence planning, a "plan" is a sequence of actions to achieve a goal. While a total-order plan specifies a strict sequence, a partial-order plan allows for flexibility, letting actions be executed in any order that respects dependencies. This flexibility is crucial for parallel execution, where independent actions can run simultaneously. However, finding the best partial-order plan, in terms of minimizing execution steps or maximizing parallelism, is computationally challenging.

Traditionally, problems like finding the minimum deordering (removing unnecessary ordering constraints) or minimum reordering (finding a new valid order) of a plan, and determining the minimum parallel execution length, have been shown to be NP-complete. This means that as the plan size grows, the time to find an optimal solution can explode exponentially. This paper tackles this by using a more refined analytical tool: parameterized complexity. Instead of just asking "is this problem hard?", parameterized complexity asks "is this problem hard with respect to a specific parameter (like the size of the plan, or the number of parallel actions)?". This allows for identifying scenarios where problems might be intractable in general but become manageable when certain aspects are small.

Methods

The core of this paper is the application of parameterized complexity theory to planning problems. The authors analyze several optimization problems related to partial-order plans, including:

  • Minimum Constrained Deordering (MCD) and Minimum Constrained Reordering (MCR): Finding a valid partial-order plan with the fewest ordering constraints (MCD) or a specific valid partial order (MCR) within a given size limit.
  • Parallel Plan Length (PPL): Determining the shortest possible execution time for a plan when actions can run in parallel, considering both ordering constraints and non-concurrency relations (which prevent certain actions from running simultaneously).
  • Parallel k-Processor Plan Length (PPLk): A variation of PPL where the number of available processors is limited to k.

They use standard parameterized complexity techniques, including:

  • Fixed-Parameter Tractability (FPT): Identifying problems that can be solved efficiently if a specific parameter is small, even if the overall problem instance is large. This is typically shown by providing algorithms with runtime $f(k) \cdot |I|^c$, where $f$ is a function of the parameter $k$ and $|I|$ is the instance size.
  • W-hardness: Demonstrating that a problem is likely intractable even when parameterized, meaning it's hard for small values of the parameter. They use reductions from known W-hard problems like DOMINATING SET and GRAPH K-COLORING.
  • Para-NP-hardness: Showing that a problem is NP-hard even when parameters are fixed to constants.

The authors analyze various parameters, including the size of the plan order ($n$), its height ($h$, longest chain), its width ($w$, largest antichain), the size of the non-concurrency relation ($n\#$), the maximum degree of the non-concurrency graph ($\Delta\#$), the desired parallel execution length ($lp$), and the number of processors ($k$).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not present experimental evaluations on specific datasets.

Key Insights and Ideas

  • Parameter Matters: The paper strongly emphasizes that the computational difficulty of plan optimization problems is highly dependent on the chosen parameter. What is intractable in general can become tractable (FPT) or remain intractable (W-hard) based on which aspect of the plan we focus on.
  • Non-concurrency is a Double-Edged Sword: The size of the non-concurrency relation ($n\#$) is a crucial parameter for parallel plan execution. While it adds constraints, it also makes the problem more tractable (FPT) when used as a parameter for PPL. However, for reordering and deordering problems involving parallel execution (MPR/MPD), it contributes to W-hardness.
  • Height vs. Width: The height of a plan order ($h$) is a more useful parameter for deordering than its width ($w$), as $h$ is directly related to the minimum parallel execution length.
  • k-Processor Scheduling is Harder: Limiting the number of processors ($k$) for parallel execution significantly increases the computational complexity, pushing problems into W[2]-hard and para-NP-hard categories, highlighting the challenge of resource-constrained scheduling.
  • Deordering vs. Reordering: Deordering problems (removing constraints) are often more tractable than reordering problems (finding new constraint sets), especially when considering parameters like the size of the non-concurrency relation.

Key Results

  • MCD (Minimum Constrained Deordering):
    • FPT when parameterized by the original order size ($n$).
  • W[2]-hard and in W[P] when parameterized by the desired order size ($n'$).
  • MCR (Minimum Constrained Reordering):
    • In W[P] when parameterized by the original order size ($n$).
  • W[2]-hard when parameterized by $\{n, h, h\}$ or $\{n, w, h\}$.
  • PPL (Parallel Plan Length):
    • FPT when parameterized by the size of the non-concurrency relation ($n\#$).
  • Para-NP-hard for most other parameter combinations.
  • MPD (Minimum Parallel Deordering):
    • FPT when parameterized by $\{n, n\#\}$.
  • MPR (Minimum Parallel Reordering):
    • In W[P] when parameterized by $\{n, n\#\}$.
  • W[2]-hard for several parameter combinations involving $\{h, h\}$ or $\{w, h\}$.
  • PPLk (Parallel k-Processor Plan Length):
    • FPT when parameterized by $\{lp, n\#, k\}$.
  • W[2]-hard when parameterized by $k$.
  • Para-NP-hard when parameterized by $\{n\#, \Delta\#, lp\}$.

Limitations and Future Work

  • Open Questions for Reordering: The paper notes that while MPD (deordering) is FPT with $\{n, n\#\}$, MPR (reordering) remains in W[P] with the same parameters. Precisely classifying MPR remains an open problem, as the number of reorderings is not bounded by $n$ in the general case, unlike deorderings.
  • Parameter Combinations: The authors suggest exploring other parameters for PPL, such as the clique number or treewidth of the non-concurrency graph, to gain further insights.
  • Interplay of Constraints: Identifying structural properties of both the partial order ($\prec$) and the non-concurrency relation ($\#$) considered together is highlighted as an interesting future direction.
  • k-Processor Optimization: A natural extension is to consider the k-processor parallel length as a criterion for plan optimization, building upon the PPLk results.
  • Practical Implications: While the paper provides theoretical insights, further work could explore how these parameterized complexity results can guide the development of more efficient practical planning algorithms.

Summary updated

BibTeX
@inproceedings{2017plan,
  title = {{Plan Reordering and Parallel Execution Ñ A Parameterized Complexity View}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
}
Figure