Task-Decomposition via Plan Parsing

Anthony Barrett, Daniel S. WeldAAAI 1994

Abstract

Traditional hierarchical planning relies on top-down task reduction, which often struggles with expressive action languages and rigid search control. This paper presents UCPOP+PARSE, an algorithm that treats task-decomposition as a bottom-up parsing problem. By using decomposition schemata as a grammar to prune invalid plan refinements in a partial-order planner, the system achieves significant search space reduction and handles complex effects like conditional outcomes. Empirical results across multiple domains demonstrate substantial speedups and improved expressivity compared to traditional reduction-based planners.

Introduction

In AI planning, task-decomposition (Hierarchical Task Network or HTN planning) is essential for complex, real-world domains. It allows experts to provide "schemata"—recipes for breaking high-level tasks into sub-tasks. However, traditional planners use task reduction, recursively swapping abstract tasks for sub-networks until only primitive actions remain. This top-down approach faces two major hurdles:

  1. Expressivity Limits: It struggles with languages like ADL (Action Description Language) containing conditional effects, as preconditions may not be known until actions are fully instantiated.
  2. Rigid Search Control: Integrating task-decomposition with other search-control techniques is difficult because the reduction process is hard-coded into the planning loop.

Methods: Planning as Parsing

The authors propose UCPOP+PARSE, which reimagines task-decomposition as a parsing problem. The system integrates a sound and complete partial-order planner (UCPOP) with an incremental parser.

The UCPOP+PARSE algorithm integrates plan refinement with incremental parsing to prune the search space.

As shown in the algorithm above, the process follows these steps:

  • Initialization: Start with an initial plan $P$ and its corresponding parses.
  • Refinement: UCPOP adds primitive actions or links to satisfy goals.
  • Parsing: The decomposition schemata act as a grammar. The parser checks if the current network of actions can be parsed into the hierarchy. If a refinement results in a plan that cannot be parsed, that branch is pruned.

This "bottom-up" approach allows the schemata to act as a declarative "critic," guiding the planner toward valid hierarchical structures without the limitations of top-down reduction.

Evaluation and Results

The approach was evaluated on several domains, including the Briefcase Domain (with conditional effects), Tyreworld, and Process Planning.

A hierarchical decomposition tree illustrating how primitive actions are grouped into higher-level tasks like manage-contents and move-to.

Key empirical findings include:

  • Search Space Reduction: In the Tyreworld "Fix flat" problem, vanilla UCPOP failed after 5,000 plans, while UCPOP+PARSE found a solution in 702 plans.
  • Efficiency: For the "Saw a block" problem, parsing reduced CPU time from 135.3 seconds to 29.1 seconds.
  • Expressivity: Unlike traditional reduction planners, UCPOP+PARSE successfully handled conditional effects in the Briefcase domain by deferring commitment until actions were added to the plan.

Discussion

The core insight of this work is the duality of planning: task-decomposition is the intersection of valid solutions and plans generated by schemata. While reduction planners explore the "schema set," UCPOP+PARSE explores the "solution set" and uses schemata for pruning.

This framework offers a uniform way to combine task-decomposition with other control methods like the ALPINE abstraction algorithm. However, it does introduce parsing overhead and potential infinite loops with recursive schemata. Future work aims to automate schema generation through machine learning techniques like derivational analogy.

Summary updated

BibTeX
@inproceedings{barrett1994task,
  author = {Anthony Barrett and Daniel S. Weld},
  title = {{Task-Decomposition via Plan Parsing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure