Alternation-Based Novelty Search

Abstract

One key decision for heuristic search algorithms is how to balance exploration and exploitation. In classical planning, the two strongest approaches for this problem are to alternate between different heuristics and to enhance heuristics with novelty measures. The most well-known planner using alternation is LAMA, which cycles between different open-lists that are ordered using different heuristics. The strongest novelty-based algorithms use best-first width search (BFWS), which prefers states that contain previously unseen combinations of atoms. Considerable effort has been put into trying to combine these two approaches, but so far, no combination has been able to significantly improve over the individual planners. In this paper, we explore the simple idea of using BFWS as just another open-list for LAMA. Our results show that adding even the strongest BFWS version to LAMA is detrimental. However, combining only parts of each approach yields a new state-of-the-art agile planner.