Best-First Width Search in the IPC 2018: Complete, Simulated, and Polynomial Variants (planner abstract)

Width-based search algorithms have recently emerged as a simple yet effective approach to planning. Best-First Width Search (BFWS) is one of the most successful satisficing width-based algorithms, as it strikes a good balance between an effective exploration based on a measure of state novelty and the exploitation provided by traditional goal-directed heuristics. Several conceptually interesting BFWS variants have recently been shown to offer state-of-the-art performance, including a polynomial-time BFWS planner which is incomplete but fast and effective, and a black-box BFWS planner that can plan efficiently with simulators, i.e. when the transition function of the problem is represented as a blackbox function. In this paper, we describe six BFWS planners involving these variations that we have entered into the 2018 International Planning Competition.