TL;DR
This paper introduces SCOPE, a system that combines explanation-based and inductive learning to automatically acquire search control rules for partial-order planners. By learning high-utility, generalized rules, SCOPE significantly speeds up planning performance in complex domains, outperforming purely explanation-based approaches.
What Problem Does This Paper Address?
Efficient automated planning, especially in complex domains, often relies on effective search control heuristics. Manually crafting these heuristics is a difficult and time-consuming task. While previous research has focused on learning control rules for linear, state-based planners, partial-order planners, which are generally more efficient, have received less attention in the learning context. Existing explanation-based learning (EBL) methods for control rule acquisition can produce overly specific rules that hinder performance. This paper addresses the challenge of learning effective, generalizable search control knowledge for partial-order planners.
Methods
SCOPE employs a novel multi-strategy learning approach by integrating Explanation-Based Generalization (EBG) with Inductive Logic Programming (ILP). The core idea is to leverage EBG to focus the inductive learning process.
- Example Analysis: The system first solves training problems using an existing partial-order planner (a Prolog implementation of UCPOP). It traces the planning process to generate "proof trees." These trees are then used to extract:
- Selection-decision examples: These record which plan refinements were successful and which led to backtracking.
- Generalized proof trees: These capture the background context explaining successful planning decisions, removing example-specific facts.
- Control Rule Induction: SCOPE uses a modified version of the FOIL algorithm (an ILP system) to learn control rules. Instead of a broad search for antecedents, SCOPE uses the generalized proof trees to guide FOIL's search, focusing on relevant background predicates and variable connections. This significantly improves the efficiency and utility of the learned rules. The learned rules are in the form of selection heuristics that direct the planner to choose appropriate plan refinements, reducing backtracking.
- Program Specialization: The learned control rules are then incorporated into the original planner. These rules act as guards, causing incorrect refinement applications to fail quickly, thereby pruning the search space.
Datasets
The paper evaluates SCOPE on two domains:
- Blocksworld: A classic AI planning domain involving stacking and unstacking blocks.
- Logistics Transportation: A domain where packages need to be delivered to different locations across cities.
For both domains, the authors generated random initial and final states to create problem sets. They trained SCOPE on example sets of increasing size and evaluated its performance on separate test sets. For a direct comparison with a related system, they used a specific blocksworld domain theory with 3-6 blocks and 3-4 goals, generating 100 training and 100 test problems.
Key Insights and Ideas
- Combining EBG and Induction is Key: The paper demonstrates that integrating EBG's ability to focus the search with ILP's capacity for generalization leads to more effective control rules than either method alone. EBG helps avoid the "utility problem" where overly specific or low-utility rules are learned.
- Partial-Order Planners Benefit from Learned Control: Unlike previous work that focused on linear planners, SCOPE shows that partial-order planners, which are generally more powerful, can also benefit significantly from learned search control.
- Guided Induction for Efficiency: By using generalized proof trees to constrain the inductive search (FOIL), SCOPE dramatically improves the learning process and the quality of the learned rules. This is a crucial innovation for handling the complexity of partial-order planning.
- High-Utility Rules Reduce Backtracking: The learned selection heuristics effectively guide the planner, preventing it from exploring unproductive branches of the search space and thus reducing costly backtracking.
Key Results
- Significant Speedup: In the blocksworld domain, SCOPE-modified planners were, on average, 11.3 times faster than the original planner. In the logistics domain, the speedup was 5.3 times faster.
- Improved Success Rate: SCOPE consistently produced modified planners that solved a higher percentage of test problems. In a comparative experiment, SCOPE achieved a 94% success rate compared to 69% for a purely EBL-based system.
- Better Speedup Ratio: SCOPE achieved a 2.86X speedup ratio in the comparative experiment, outperforming the EBL-based system's 1.47X.
- Guaranteed Soundness: The learned control rules do not affect the soundness of the planner; it remains guaranteed to find a correct solution if one exists. However, completeness is not strictly guaranteed, though a fallback mechanism is in place.
Limitations and Future Work
- Completeness Guarantee: While SCOPE aims for high utility, overly specialized rules could, in principle, make the planner incomplete. The authors address this by falling back to the original planner if the modified one fails to find a solution.
- Future Work:
- Investigate alternative information gain metrics for literal selection in the induction phase.
- Test SCOPE on more complex domains with features like conditional effects and universal quantification.
- Explore methods to improve plan quality (not just efficiency) by focusing learning on high-quality solutions.
Summary updated