A Hybrid Relaxed Planning Graph-LP Heuristic for Numeric Planning Domains

Andrew Coles, Maria Fox, Derek Long, Amanda Smith

Effective search control for numeric planning domains, in which appropriate numeric resource usage is critical to solving 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 extended relaxation, implemented in Metric-FF, is one of the best general heuristics. We examine the behaviour of the Relaxed 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.

Subjects: 1.11 Planning; 15.7 Search

Submitted: Jun 25, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.