TL;DR
This paper introduces ROLLER, a system that uses machine learning to automatically extract search control knowledge for heuristic planners. By building relational decision trees that capture "helpful contexts," the system can prioritize the best actions to take, allowing planners to solve massive problems—like 100-block Blocksworld tasks—orders of magnitude faster than state-of-the-art domain-independent planners.
What Problem Does This Paper Address?
Automated planning is the art of finding a sequence of actions to reach a goal. Most modern planners use heuristic search, where a mathematical function estimates the distance to the goal to guide the search.
However, these planners face a "scalability wall." Computing heuristics is computationally expensive, and in large or complex environments, the planner may evaluate millions of nodes, most of which lead nowhere. While experts can hand-code "Domain-specific Control Knowledge" (DCK) to prune these searches, doing so is tedious and requires deep expertise. The authors aim to bridge this gap by automatically learning how to "steer" the planner using experience from small, easy-to-solve problems.
Methods
The authors present the ROLLER system, which treats search control as a relational classification task.
- Helpful Contexts: Instead of looking at the entire state (which is too complex), ROLLER defines a "helpful context" for each state. This includes the set of "helpful actions" (identified by the FF heuristic), the remaining goals, and static facts about the environment.
- Two-Step Learning: ROLLER uses an off-the-shelf Inductive Logic Programming (ILP) tool called TILDE to build two types of relational decision trees:
- Operator Classifier: Decides which type of action to perform (e.g., "should I pick up a block or stack one?").
- Binding Classifier: Decides which specific objects to use for that action (e.g., "which block should I pick up?").
- Search Integration: These learned trees are used in two ways:
- H-Context Policy: A depth-first search that follows the decision tree's advice as a primary policy.
- Lookahead-BFS: A hybrid approach where the policy is used to generate "jumps" (lookahead states) within a standard Best-First Search, combining learned intuition with traditional heuristic guidance.
Datasets
The authors evaluated ROLLER across 10 diverse domains from the International Planning Competitions (IPC), including:
- Classic Benchmarks: Blocksworld, Depots, Satellite, and Rovers.
- Complex Logic Domains: Parking, Thoughtful (Solitaire), and Matching Blocksworld.
- Logistics: Storage and TPP.
For each domain, they trained the system on 30 small, randomly generated problems and tested it on the 30 hardest problems from the IPC evaluation sets.
Key Insights and Ideas
- Relational is Key: Standard machine learning (propositional) struggles with planning because the "features" change with every problem. By using Relational Decision Trees, ROLLER can learn abstract concepts like "a block that is part of a bad tower" regardless of the specific block ID.
- Learning from Quality: Not all solutions are equal. The authors found that learning from any valid solution introduces noise. They implemented a ranking system that prefers "least-commitment" solutions—those that leave the most options open—leading to much more robust control knowledge.
- Pruning via Heuristics: By only trying to learn from the "helpful actions" suggested by the FF heuristic, the learning space is drastically reduced, making it possible to learn effective policies in seconds rather than hours.
Key Results
- Massive Speedups: In the Blocksworld domain, ROLLER solved problems two orders of magnitude faster than LAMA (a top-tier planner).
- Superior Scalability: ROLLER solved 247 total test problems, compared to 241 for LAMA-first and 188 for the standard FF planner.
- Generalization: The system successfully learned policies on tiny problems (e.g., 8 blocks) that generalized perfectly to massive problems (100 blocks) that traditional planners couldn't touch.
- Efficiency: The training phase is remarkably fast; for most domains, learning the decision trees took less than 20 seconds.
Limitations and Future Work
- Domain Sensitivity: ROLLER struggled in domains like Sokoban or N-puzzle, where the specific trajectory to the goal is less important than complex numeric heuristics. In these "dead-end" heavy domains, action policies are often inaccurate.
- Plan Quality: While ROLLER is exceptionally fast at finding a solution, the resulting plans aren't always the shortest possible (optimal).
- Future Directions: The authors suggest incorporating "landmarks" (essential intermediate states) into the helpful context to provide better guidance in domains with complex dependencies. They also aim to explore how to automatically generate the most "informative" training problems rather than relying on random generation.
Summary updated