A hybrid relaxed planning graph-LP heuristic for numeric planning domains
Andrew J. Coles, Maria Fox, Derek Long, Amanda J. Smith · 2008
Effective search control for numeric planning domains, in which appropriate numeric resource usage is critical to solv-ing the problem, remains an open challenge in domain-independent planning. Most real-world problems rely on metric resources such as energy, money, fuel or materials. Despite the importance of numbers, few heuristics have been proposed to guide search in such domains. Hoffmann’s ex-tended relaxation, implemented in Metric-FF, is one of the best general heuristics. We examine the behaviour of the Re-laxed Planning Graph (RPG) heuristic, used by Metric-FF, in numeric problems. While effective in problems with simple numeric interactions, it has two weaknesses when numeric reasoning is a fundamental part of solving the problem. We present a new heuristic for use in strongly numeric domains, using a Linear Program to capture numeric constraints as an adjunct to a relaxed planning graph. We demonstrate that an intelligent combination of these two techniques offers greatly improved heuristic guidance. 1