Learning Neural Search Policies for Classical Planning

Paweł Gomoluch, Dalal Alrajeh, Alessandra Russo, Antonio Bucchiarone

Abstract

Heuristic forward search is currently the dominant paradigm in classical planning. Forward search algorithms typically rely on a single, relatively simple variation of best-first search and remain fixed throughout the process of solving a planning problem. Existing work combining multiple search techniques usually aims at supporting best-first search with an additional exploratory mechanism, triggered using a handcrafted criterion. In this paper, we introduce a parametrized search algorithm template which combines various search techniques within a single routine. The template's parameter space defines an infinite space of search algorithms, including, among others, BFS, local and random search. We then propose a neural architecture for designating the values of the search parameters given the state of the search. This enables expressing neural search policies that change the values of the parameters as the search progresses. The policies can be learned automatically, with the objective of maximizing the planner's performance on a given distribution of planning problems. We consider a training setting based on a stochastic optimization algorithm known as the cross-entropy method (CEM). Experimental evaluation of our approach shows that it is capable of finding effective distribution-specific search policies, outperforming the relevant baselines.

1. Introduction

In classical planning, the objective is to find a sequence of actions that transitions an initial state to a goal state. Modern planners predominantly utilize heuristic forward search, where a heuristic function estimates the distance from a given state to the goal. However, heuristics are often imperfect, leading to search pathologies such as plateaus and local minima. While many planners incorporate auxiliary mechanisms like random walks to escape these traps, these are typically governed by static, hand-crafted rules. This paper addresses the rigidity of such search algorithms by proposing a framework for learning dynamic search policies that adapt to the problem's structure and the search's progress.

2. Parametrized Search Template

We introduce a parametrized search template that unifies various search techniques into a single, flexible routine. The behavior of the search is controlled by six continuous parameters:

  • $\epsilon$: The probability of selecting a node at random from the open list, facilitating exploration.
  • $S$: The number of node expansions without heuristic improvement required to trigger a random walk.
  • $R$: The number of random walks performed upon triggering.
  • $L$: The length (number of steps) of each random walk.
  • $C$: The total number of steps in a cyclical global-local search strategy.
  • $c$: The fraction of steps within each cycle $C$ dedicated to local search.

By varying these parameters, the template can instantiate a wide spectrum of algorithms, ranging from standard Greedy Best-First Search (GBFS) to Iterated Local Search.

3. Neural Search Policies and Training

To dynamically adjust these parameters during search, we employ a Neural Search Policy (NSP). The NSP is a feed-forward neural network that takes the current "state of the search" as input and outputs the recommended parameter values. Input features include high-level metrics such as the current minimum heuristic value ($h_{min}$), the time elapsed, and the number of expansions since $h_{min}$ was last updated.

The policy weights are optimized using the Cross-Entropy Method (CEM), a gradient-free stochastic optimization technique. CEM iteratively samples a population of policies, evaluates their performance on a set of training problems, and iteratively refines the weight distribution toward the most successful candidates.

4. Experimental Evaluation

The proposed approach was evaluated across five domains from the International Planning Competition (IPC): Elevators, Floortile, No-mystery, Parking, and Transport. Training was conducted on generated problem sets, and the resulting policies were tested on unseen instances.

Training progress across five IPC domains. The y-axis represents the IPC score, showing consistent improvement as the CEM optimization proceeds over generations (x-axis).

The results indicate that learned NSPs significantly outperform traditional baselines. For instance, in the Transport domain, the NSP learned to prioritize local search ($c \approx 0.96$), which is highly effective for the logistics-based structure of the domain.

Detailed training progress for the Transport domain, showing the convergence of the IPC score.

In other domains, the NSP discovered unique strategies:

  • Elevators: The policy learned to trigger longer random walks only after prolonged stagnation.
  • Floortile: High exploration ($\epsilon$) was utilized early in the search to overcome misleading heuristic values.

Quantitatively, the NSP achieved an aggregate IPC score of 46.74, a substantial improvement over the 36.93 achieved by standard GBFS.

5. Conclusion

This work demonstrates the potential of learning dynamic search policies for classical planning. By parameterizing the search space and employing neural networks for real-time adaptation, we can discover sophisticated, domain-specific strategies that surpass hand-crafted heuristics. Future research will explore multi-heuristic policies and more advanced optimization techniques to further enhance planner performance.

Summary updated

Abstract

Heuristic forward search is currently the dominant paradigm in classical planning. Forward search algorithms typically rely on a single, relatively simple variation of best-first search and remain fixed throughout the process of solving a planning problem. Existing work combining multiple search techniques usually aims at supporting best-first search with an additional exploratory mechanism, triggered using a handcrafted criterion. A notable exception is very recent work which combines various search techniques using a trainable policy. That approach, however, is confined to a discrete action space comprising several fixed subroutines.In this paper, we introduce a parametrized search algorithm template which combines various search techniques within a single routine. The template's parameter space defines an infinite space of search algorithms, including, among others, BFS, local and random search. We then propose a neural architecture for designating the values of the search parameters given the state of the search. This enables expressing neural search policies that change the values of the parameters as the search progresses. The policies can be learned automatically, with the objective of maximizing the planner's performance on a given distribution of planning problems. We consider a training setting based on a stochastic optimization algorithm known as the cross-entropy method (CEM). Experimental evaluation of our approach shows that it is capable of finding effective distribution-specific search policies, outperforming the relevant baselines.
BibTeX
@inproceedings{gomoluch2020learning,
  author = {Paweł Gomoluch and Dalal Alrajeh and Alessandra Russo and Antonio Bucchiarone},
  title = {{Learning Neural Search Policies for Classical Planning}},
  booktitle = {ICAPS},
  year = {2020},
  url = {https://openreview.net/forum?id=ZbWjrTBoPvh},
}
Figure