Scaling up Heuristic Planning with Relational Decision Trees

Tomás de la Rosa, Sergio Jiménez Celorrio, Raquel Fuentetaja, Daniel Borrajo

Abstract

Current evaluation functions for heuristic planning are expensive to compute. In numerous planning problems these functions provide good guidance to the solution, so they are worth the expense. However, when evaluation functions are misguiding or when planning problems are large enough, lots of node evaluations must be computed, which severely limits the scalability of heuristic planners. In this paper, we present a novel solution for reducing node evaluations in heuristic planning based on machine learning. Particularly, we define the task of learning search control for heuristic planning as a relational classification task, and we use an off-the-shelf relational classification tool to address this learning task. Our relational classification task captures the preferred action to select in the different planning contexts of a specific planning domain. These planning contexts are defined by the set of helpful actions of the current state, the goals remaining to be achieved, and the static predicates of the planning task. This paper shows two methods for guiding the search of a heuristic planner with the learned classifiers. The first one consists of using the resulting classifier as an action policy. The second one consists of applying the classifier to generate lookahead states within a Best First Search algorithm. Experiments over a variety of domains reveal that our heuristic planner using the learned classifiers solves larger problems than state-of-the-art planners.

Introduction

Automated planning involves finding a sequence of actions to transition from an initial state to a goal state. Modern planners predominantly rely on heuristic search, where mathematical functions estimate the distance to the goal. However, these planners often hit a "scalability wall" because computing heuristics is computationally expensive. In large or complex environments, planners may evaluate millions of nodes, many of which are irrelevant. While expert-defined Domain-specific Control Knowledge (DCK) can prune these searches, it is difficult to create. This research introduces ROLLER, a system designed to automatically learn search control knowledge from small, solvable problems to guide planners in much larger domains.

Methodology: The ROLLER Architecture

The ROLLER system treats search control as a relational classification task. Instead of analyzing the entire state space, which is often computationally prohibitive, ROLLER focuses on "helpful contexts."

The ROLLER learning architecture, showing the flow from training problems and PDDL domains to the generation of operator and binding classifiers.

Learning Search Control

As shown in the ROLLER architecture diagram, the system processes training problems and PDDL domains through an Example Generator. This generator produces operational and binding examples based on "helpful actions" (identified by the FF heuristic), remaining goals, and static environment facts.

These examples are fed into a Relational Classification Tool (specifically, an Inductive Logic Programming tool called TILDE) to build two types of relational decision trees:

  1. Operator Classifiers: These determine the type of action to perform (e.g., "stack" vs. "unstack").
  2. Binding Classifiers: These determine the specific objects involved in the action (e.g., "which block to stack").

Search Integration

The learned classifiers are integrated into the search process in two ways:

  • H-Context Policy: A depth-first search that treats the decision tree's output as a primary policy.
  • Lookahead-BFS: A hybrid approach where the policy generates "jumps" or lookahead states within a standard Best-First Search, combining learned intuition with traditional heuristic guidance.

Experimental Evaluation

The authors evaluated ROLLER across 10 diverse domains from the International Planning Competitions (IPC), including Blocksworld, Depots, Satellite, Rovers, Parking, and Storage. Training involved 30 small, randomly generated problems per domain, while testing focused on the 30 hardest problems from IPC sets.

Key Results

  • Scalability: ROLLER demonstrated superior scalability, solving 247 total test problems compared to 241 for LAMA-first and 188 for the standard FF planner. In the Blocksworld domain, it solved problems two orders of magnitude faster than LAMA.
  • Generalization: Policies learned on tiny problems (e.g., 8 blocks) generalized perfectly to massive problems (e.g., 100 blocks) that traditional planners could not solve.
  • Efficiency: The training phase is highly efficient, with decision tree learning taking less than 20 seconds for most domains.

Conclusion

ROLLER successfully bridges the gap between general-purpose heuristic planning and domain-specific control. By leveraging relational decision trees, it captures abstract concepts that generalize across problem sizes. While it faces challenges in "dead-end" heavy domains like Sokoban, its ability to provide massive speedups in standard benchmarks makes it a significant advancement in scalable automated planning. Future work will explore incorporating "landmarks" to improve guidance in domains with complex dependencies.

Summary updated

Abstract

Current evaluation functions for heuristic planning are expensive to compute. In numerous planning problems these functions provide good guidance to the solution, so they are worth the expense. However, when evaluation functions are misguiding or when planning problems are large enough, lots of node evaluations must be computed, which severely limits the scalability of heuristic planners. In this paper, we present a novel solution for reducing node evaluations in heuristic planning based on machine learning. Particularly, we define the task of learning search control for heuristic planning as a relational classification task, and we use an off-the-shelf relational classification tool to address this learning task. Our relational classification task captures the preferred action to select in the different planning contexts of a specific planning domain. These planning contexts are defined by the set of helpful actions of the current state, the goals remaining to be achieved, and the static predicates of the planning task. This paper shows two methods for guiding the search of a heuristic planner with the learned classifiers. The first one consists of using the resulting classifier as an action policy. The second one consists of applying the classifier to generate lookahead states within a Best First Search algorithm. Experiments over a variety of domains reveal that our heuristic planner using the learned classifiers solves larger problems than state-of-the-art planners.
BibTeX
@article{rosa2011scaling,
  author = {Tomás de la Rosa and Sergio Jiménez Celorrio and Raquel Fuentetaja and Daniel Borrajo},
  title = {{Scaling up Heuristic Planning with Relational Decision Trees}},
  journal = {J. Artif. Intell. Res.},
  year = {2011},
  url = {https://openreview.net/forum?id=hHVkfB2ECURb},
}
Figure