Search-Guidance Mechanisms for Numeric Planning Through Subgoaling Relaxation

Abstract

Recently, a new decomposition based relaxation has been proposed for numeric planning problems. Roughly, this relaxation is grounded on the identification of regression-based necessary conditions for the satisfaction of sets of numeric subgoals. So far, it has been used to define novel heuristics that are able to provide great guidance in problems exhibiting a pronounced numeric structure. This paper investigates how to further exploit this relaxation; it does so by introducing the notion of the multi-repetition relaxed plan. The multi-repetition plan annotates actions with the number of times such actions need to be executed. We use this structure for different purposes: extraction of a concrete relaxed plan based heuristic, definition of subgoaling based helpful actions, and definition of what we call up-to-jumping actions. Up-to-jumping actions allow us to deeply leverage from the metric structure of the problem and devise an informed search strategy that can collapse several decision steps. We experimentally analyze a forward state space planner equipped with these novel mechanisms across several planning benchmarks, showing the benefit of the ideas presented in the paper.