Abstract
Automated planning for conjunctive goals is often hampered by harmful goal interactions, where achieving one goal inadvertently negates another. The Planning and Learning (PAL) system introduces a novel method for automatically deriving goal-ordering rules by analyzing planning failures. Unlike previous systems that rely on exhaustive search trees or static domain analysis, PAL examines "goal stacks" at the point of failure to generate general, correct control rules. Empirical evaluations demonstrate that PAL significantly reduces learning overhead and improves planning efficiency compared to state-of-the-art systems like PRODIGY/EBL.
Introduction
In automated planning, a "conjunctive goal" problem—where multiple objectives must be satisfied simultaneously—presents a significant challenge due to goal interactions. Planners require "goal ordering rules" to determine the optimal sequence of actions. Traditional approaches like Explanation-Based Learning (EBL) often produce overly specific, computationally expensive rules. Conversely, static analysis methods may overlook dynamic constraints, leading to over-generalization. PAL seeks a middle ground by learning robust rules from actual problem-solving traces without requiring extensive a priori domain knowledge.
The PAL System: Learning from Failure
The core innovation of PAL lies in its ability to learn from "unavoidable failures" during the planning process. When a planner reaches a dead-end, PAL retrieves the goal stacks from the leaf nodes. These stacks provide a concise history of the subgoals and operators that led to the impasse.
PAL identifies "determinants"—the specific state conditions that forced particular operator bindings. These failures are organized into Configuration trees (C-trees) and then generalized into Failure trees (F-trees) by replacing specific objects with variables. To ensure utility, PAL only retains "isolated" rules—those where the goals cannot be solved by the very operators that caused the initial failure.
Experimental Evaluation
PAL was evaluated using standard benchmarks from the PRODIGY test suite, including Blocksworld, Stripsworld (robot navigation), and Schedworld (machine scheduling). These domains were modified to emphasize multiple-goal problems, thereby forcing goal interactions.
Results and Discussion
Experimental results indicate that PAL is highly efficient. In the Blocksworld domain, PAL's learning overhead was approximately 0.43 seconds per rule, a stark contrast to the 40 seconds required by EBL. Furthermore, planners utilizing PAL-derived rules expanded fewer nodes and produced shorter, more optimal solutions.
Unlike static analysis tools, PAL successfully incorporates dynamic state information, such as a robot's location or the status of a door, making its rules more robust in complex environments. While PAL's rules are more general than those of EBL, they remain somewhat dependent on the training instances encountered. Future work may explore extending this methodology to $n$-goal interactions and further refining the representation of domain operators.
Conclusion
PAL demonstrates that analyzing failures at the leaf nodes of a search tree provides sufficient information to derive powerful control rules. By focusing on goal stack analysis and generalization, PAL offers a scalable and effective approach to managing goal interactions in complex planning domains.
Summary updated