Learning to Rank for Synthesizing Planning Heuristics

Caelan Reed Garrett, Leslie Pack Kaelbling, Tomás Lozano-Pérez

Abstract: We investigate learning heuristics for domain-specific planning. Prior work framed learning a heuristic as an ordinary regression problem. However, in a greedy best-first search, the ordering of states induced by a heuristic is more indicative of the resulting planner's performance than mean squared error. Thus, we instead frame learning a heuristic as a learning to rank problem which we solve using a RankSVM formulation. Additionally, we introduce new methods for computing features that capture temporal interactions in an approximate plan. Our experiments on recent International Planning Competition problems show that the RankSVM learned heuristics outperform both the original heuristics and heuristics learned through ordinary regression.

Introduction

In automated planning, a heuristic function estimates the distance from a current state to the goal. Most modern planners rely on Greedy Best-First Search (GBFS), which expands the state with the lowest heuristic value. Traditionally, researchers have attempted to "learn" these heuristics by treating the task as a regression problem, aiming to minimize the Mean Squared Error (MSE) between predicted and actual goal distances.

However, for GBFS, the absolute numerical value of the heuristic is secondary to the ordering it induces. If a heuristic correctly identifies that State A is closer to the goal than State B, the planner will make the correct expansion choice regardless of whether the numerical distance estimates are accurate. This paper proposes shifting the paradigm from regression to learning-to-rank.

Methods

RankSVM for Planning

Instead of Ridge Regression (RR), which minimizes MSE, we utilize a RankSVM formulation. This approach optimizes for the Kendall rank correlation coefficient ($\tau$), measuring how well the predicted ranking matches the true ranking of states along a plan. This allows the learner to focus on local "which way is better" decisions, ignoring inconsistent absolute distance values across different problem instances.

Pairwise Action Features

To improve the model's predictive power, we move beyond simple action counts. We extract features from the Directed Acyclic Graph (DAG) produced by approximate planners (such as FastForward (FF) or Context-Enhanced Additive (CEA) heuristics):

  • Standard Features: Count occurrences of specific actions (e.g., "move") in the relaxed plan.
  • Pairwise Features: Count how often one action supports or precedes another in the DAG. This captures critical temporal dependencies—such as a "pick-up" necessarily preceding a "drop-off"—that simple heuristics often overlook.

To ensure high-quality training data, successful plans are post-processed using local search techniques to eliminate redundant steps that might introduce noise into the learning process.

Results

We evaluated our approach on four domains from the 2014 International Planning Competition (IPC) learning track: Elevators, Transport, Parking, and No-mystery.

Table 1: Performance comparison of various heuristic learning methods across four IPC domains. Note the significant coverage (Cov.) improvements for RankSVM (RSVM) variants over original heuristics and Ridge Regression (RR) baselines.

As shown in Table 1, the RankSVM approach significantly outperforms both the original heuristics and regression-based learners:

  • Superior Coverage: In the Transport domain, the original FF heuristic solved only 5 problems, while the RankSVM version with pairwise features (FF NN RSVM Pair) solved 31. In Parking, coverage jumped from 0 to 10.
  • Correlation vs. Accuracy: The data confirms that Kendall $\tau$ is a better predictor of success than RMSE. For instance, in Elevators, FF RSVM Single has a much higher RMSE (79.867) than FF RR Single (4.091), yet it achieves higher coverage (34 vs 22) because its ranking correlation ($\tau$) is superior.
  • Generalization: Models trained on small, easily solvable problems successfully generalized to much larger, complex problems that the training portfolio planner could not solve independently.

Conclusion

Framing heuristic synthesis as a ranking problem provides a more robust objective for search-based planning than traditional regression. While highly effective, the approach faces challenges in domains like No-mystery, where "dead-ends" (unreachable goals) are common. Future work will focus on integrating these learned ranking heuristics with specialized dead-end detectors and combining features from multiple base heuristics to create more powerful ensemble models.

Summary updated

Abstract

We investigate learning heuristics for domain-specific planning. Prior work framed learning a heuristic as an ordinary regression problem. However, in a greedy best-first search, the ordering of states induced by a heuristic is more indicative of the resulting planner's performance than mean squared error. Thus, we instead frame learning a heuristic as a learning to rank problem which we solve using a RankSVM formulation. Additionally, we introduce new methods for computing features that capture temporal interactions in an approximate plan. Our experiments on recent International Planning Competition problems show that the RankSVM learned heuristics outperform both the original heuristics and heuristics learned through ordinary regression.
BibTeX
@inproceedings{garrett2016learning,
  author = {Caelan Reed Garrett and Leslie Pack Kaelbling and Tomás Lozano-Pérez},
  title = {{Learning to Rank for Synthesizing Planning Heuristics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=ZioIOI1jKtM},
}
Figure