Eliminating Redundant Actions in Partially Ordered Plans A Complexity Analysis

Pascal Bercher, Conny Olz

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    9 Citations (Scopus)

    Abstract

    In this paper we study the computational complexity of postoptimizing partially ordered plans, i.e., we investigate the problem that is concerned with detecting and deleting unnecessary actions. For totally ordered plans it can easily be tested in polynomial time whether a single action can be removed without violating executability. Identifying an executable subplan, i.e., asking whether k plan steps can be removed, is known to be NP-complete. We investigate the same questions for partially ordered input plans, as they are created by many search algorithms or used by real-world applications in particular time-critical ones that exploit parallelism of non-conflicting actions. More formally, we investigate the computational complexity of removing an action from a partially ordered solution plan in which every linearization is a solution in the classical sense while allowing ordering insertions afterwards to repair arising executability issues. It turns out that this problem is NP-complete even if just a single action is removed and thereby show that this reasoning task is harder than for totally ordered plans. Moreover, we identify the structural properties responsible for this hardness by providing a fixed-parameter tractability (FPT) result.
    Original languageEnglish
    Title of host publicationProceedings International Conference on Automated Planning and Scheduling, ICAPS2019
    EditorsJ Benton, N Lipovetzky, E Onaindia, D Smith & S Srivastava
    Place of PublicationUnited States
    PublisherAAAI Press
    Pages310-319
    ISBN (Print)978-157735807-7
    DOIs
    Publication statusPublished - 2019
    Event29th International Conference on Automated Planning and Scheduling, ICAPS 2019 - Berkeley, United States
    Duration: 1 Jan 2019 → …

    Conference

    Conference29th International Conference on Automated Planning and Scheduling, ICAPS 2019
    Period1/01/19 → …
    OtherJuly 11-15 2019

    Fingerprint

    Dive into the research topics of 'Eliminating Redundant Actions in Partially Ordered Plans A Complexity Analysis'. Together they form a unique fingerprint.

    Cite this