Introduction
In the field of Automated Planning, a "heuristic" serves as the compass that guides an agent toward its goal. Traditionally, researchers have treated the construction of these heuristics as a regression problem: "Predict exactly how many steps are left until the goal." However, recent research from MIT CSAIL suggests that we have been asking the wrong question. Instead of asking "How far?", we should be asking "Which way is better?"
This paper shifts the paradigm of learning planning heuristics from regression (predicting distance-to-goal) to learning to rank (predicting the relative order of states). By utilizing a RankSVM approach and novel features that capture temporal interactions between actions, the authors demonstrate significantly improved performance on complex planning benchmarks compared to traditional methods.
The Misalignment of Regression
Most modern planners utilize Greedy Best-First Search (GBFS). In this configuration, the planner maintains a list of potential next steps and always selects the one with the lowest heuristic value—the shortest estimated distance to the goal.
The core issue identified by the researchers is a misalignment between the learning objective and the search algorithm. Previous work used regression to train heuristics, aiming to minimize the Mean Squared Error (RMSE) between the predicted and actual distance. However, GBFS does not actually require precise distance estimates; it only requires that state A is ranked lower than state B if A is closer to the goal. A heuristic can have a high RMSE but still be a perfect guide if it consistently ranks the correct next state first.
Methodology: RankSVM and Pairwise Features
The authors propose two major innovations to bridge this gap:
- RankSVM for Planning: Instead of Ridge Regression, they employ a RankSVM formulation. This model is trained to maximize Kendall’s $\tau$, a statistic measuring the correlation between two rankings. It specifically penalizes the model when it flips the order of two states relative to their true distance-to-go.
- Pairwise Action Features: To describe a state to the learner, the researchers analyze the "relaxed plan" (an approximate plan ignoring certain constraints) generated by existing heuristics like FF or CEA. While standard approaches simply count action types, this new method examines pairs of actions and their temporal relationships in a Directed Acyclic Graph (DAG). By counting how often one action must precede another and identifying overlapping preconditions, the model captures complex "temporal spread" that simple counts miss.
Experimental Results
The researchers evaluated their approach using domains from the 2014 International Planning Competition (IPC) learning track, including Elevators, Transport, Parking, and No-mystery.
As shown in the table above, the results were definitive: RankSVM consistently outperformed Ridge Regression. In the Transport domain, the RankSVM learner solved 31 out of 35 problems, while the regression-based learner (FF RR Single) solved zero. Furthermore, the "Pairwise" features significantly outperformed "Single" action features, proving that the interaction between actions is vital for accurate ranking. While RankSVM is more computationally expensive to train, the resulting heuristics were so efficient that they solved problems with far fewer state expansions.
Key Insights and Limitations
- Ranking > Regression: The most critical takeaway is that RMSE is a poor proxy for search performance. A model that predicts distances accurately on average might still fail a search if it makes a ranking error at a critical junction.
- Leveraging the DAG: Treating the approximate plan as a graph rather than a "bag of actions" allows the learner to see the structure of the problem, such as realizing a robot must "move" before it can "pick."
- The Challenge of Dead-Ends: The authors noted one significant hurdle in the No-mystery domain, where learned heuristics performed slightly worse than standard ones. This domain is full of "dead-ends" (states from which the goal is unreachable). The researchers concluded that ranking is not enough to handle dead-ends; these states must be identified and avoided entirely.
Conclusion
By reframing heuristic learning as a ranking task, this research provides a more effective way to train planning agents. Future work suggests combining these ranking learners with dedicated dead-end detectors and exploring how to integrate features from multiple different base heuristics into a single, high-performance ranking model.
Summary updated