Simultaneous Heuristic Search for Conjunctive Subgoals

Lin Zhu, Robert Givan

We study the problem of building effective heuristics for achieving conjunctive goals from heuristics for individual goals. We consider a straightforward method for building conjunctive heuristics that smoothly trades off between previous common methods. In addition to first explicitly formulating the problem of designing conjunctive heuristics, our major contribution is the discovery that this straightforward method substantially outperforms previously used methods across a wide range of domains. Based on a single positive real parameter k, our heuristic measure sums the individual heuristic values for the subgoal conjuncts, each raised to the k'th power. Varying k allows loose approximation and combination of the previous min, max, and sum approaches, while mitigating some of the weaknesses in those approaches.Our empirical work shows that for many benchmark planning domains there exist fixed parameter values that perform well---we give evidence that these values can be found automatically by training. Our method, applied to top-level conjunctive goals, shows dramatic improvements over the heuristic used in the FF planner across a wide range of planning competition benchmarks. Also, our heuristic, without computing landmarks, consistently improves upon the success ratio of a recently published landmark-based planner FF-L.

Content Area: 16. Planning and Scheduling

Subjects: 1.11 Planning; 15.7 Search

Submitted: May 10, 2005

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.