Count-based Novelty Exploration in Classical Planning
This addresses the computational bottleneck in novelty search for classical planning, offering an incremental improvement for planning researchers and practitioners.
The paper tackles the problem of exponential growth in tuple counts needed for novelty exploration in classical planning by proposing a count-based novelty technique that uses a constant number of tuples based on frequency in the search tree, achieving competitive results in challenging benchmarks and significantly increasing instance coverage in dual configurations.
Count-based exploration methods are widely employed to improve the exploratory behavior of learning agents over sequential decision problems. Meanwhile, Novelty search has achieved success in Classical Planning through recording of the first, but not successive, occurrences of tuples. In order to structure the exploration, however, the number of tuples considered needs to grow exponentially as the search progresses. We propose a new novelty technique, classical count-based novelty, which aims to explore the state space with a constant number of tuples, by leveraging the frequency of each tuple's appearance in a search tree. We then justify the mechanisms through which lower tuple counts lead the search towards novel tuples. We also introduce algorithmic contributions in the form of a trimmed open list that maintains a constant size by pruning nodes with bad novelty values. These techniques are shown to complement existing novelty heuristics when integrated in a classical solver, achieving competitive results in challenging benchmarks from recent International Planning Competitions. Moreover, adapting our solver as the frontend planner in dual configurations that utilize both memory and time thresholds demonstrates a significant increase in instance coverage, surpassing current state-of-the-art solvers.