- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper proposes a new approach to generate heuristic functions for Greedy Best-First Search (GBFS). Two approaches are presented, one where the planning process is modeled as an MDP where the actions are decisions to decide which planning node to expand next from the fringe. The second approach is inspired by the observations of the first one and consists of training a heuristic function using a novel supervised learning loss function that is based on the search experience generated by GBFS. Experiments show that the second approach allowed more planning instances to be solved on average, when comparing it against eight baselines.
Critical strengths
The paper presents a meaningful connection between RL and heuristic learning that can be used as a principled way to learn heuristics for symbolic planning. By modeling the problem of choosing the next node to expand as a sequential decision-making problem, the paper establishes a framework (independent of specific RL algorithms) that inspires a derivation and evaluation of a novel loss function used to train heuristic functions.
The evaluation includes a diverse set of baselines, both closer to the approach and classically used. Ten planning domains are evaluated and L_{po} has higher coverage in six out of ten domains, showing that it performs well in a range of problems. The proposed approaches also perform much better than other learned and traditional planning approaches. This provides encouraging empirical evidence of the practical value of the proposed learning objective. The authors also analyze the domain structures of cases where their approach is substantially better or worse than other approaches.
Critical weaknesses
None
Questions for authors
What explains the improvements of the proposed loss over existing ranking-based losses? Do you have an idea in which cases using the open lists encountered during search gives the approach a clear advantage?
2 comments
Thanks
Thank you for the explanation. I still think this is a good paper, and I would like to see it published.
answer to question
Thank you very much for the positive review.
We believe the improvements come from replaying the expansions as they were encountered during search. Lgbfs and its Lgbfssoftmax variant constrain only the states **at distance one(( from the best trajectory. Specifically at each step, the next state on the trajectory must be preferred over the other children of the states expanded so far. When the heuristic makes a mistake and expands a state off the trajectory (which during training can also happen because expansions are sampled from the policy) the children of that state enter the open list with heuristic values that the ranking losses have never constrained, and the search can keep expanding them. Lpo adds these open lists to the training set. A second effect is implicit weighting, as a mistake that costs many expansions contributes proportionally more to the loss.
When the search already follows the best trajectory, the ratio of expanded states to plan length is close to one (Figure 1 in the Appendix), the open lists seen by Lpo and Lgbfs coincide, and the two losses are identical, which is what we observe in five domains. The advantage appears when the search explores states far from the trajectory early in training, and in domains with dead ends or traps where one wrong expansion is followed by many more, such as Floortile and Transport, where Lpo is much better. The 0/1 ablation reported to Reviewer 2 supports this: Lpo keeps a 5 point lead over the ranking losses regardless of the target, so the gain comes from the loss rather than from the choice of the best node.