Task-decomposition via plan parsing

Abstract

Task-decomposition planners make use of schemata that define tasks in terms of partially ordered sets of tasks and primitive actions. Most existing taskdecomposition planners synthesize plans via a topdown approach, called task reduction, which uses schemata to replace tasks with networks of tasks and actions until only actions remain. In this paper we present a bottom-up plan parsing approach to task-decomposition. Instead of reducing tasks into actions, we use an incremental parsing algorithm to recognize which partial primitive plans match the schemata. In essence, our approach exploits the observation that schemata are a convenient means for reducing search. We compile the schemata into a declarative search control language (like that used in machine learning research), which rejects plan refinements that cannot be parsed. We demonstrate that neither parsing nor reduction dominates the other on efficiency grounds and provide preliminary empirical results comparing the two. We not...