What Does it Take to Render h+(ΠC) Perfect?
Jörg Hoffmann, Marcel Steinmetz, Patrik Haslum · ANU Open Research (Australian National University) · 2014
It is well-known that h(Π) is perfect in the limit, i. e., we can always choose C so that h(Π) = h∗. But the proof is trivial (select C as the set of all conjunctions), and completely ignores the actual power of h(Π), basically pretending that h is the same as h. It is thus interesting to ask: Can we characterize the power of h(Π) more accurately? How large does C have to be, under which circumstances? We present first results towards answering these questions. We introduce a “direct” characterization of h(Π), in terms of equations, not employing a compilation step. We identify a first tractable fragment (similar to fork causal graphs) where size-2 conjunctions suffice to render h(Π) perfect. We present results comparing h(Π) to alternative partial delete relaxation methods (red-black planning and fluent merging). We finally present a number of wild speculations as to what might be interesting to investigate in the future. Disclaimer: We are enthusiastic about the research direction, but our work as yet raises far more questions than answers. We think that HSDIP is a great forum to discuss this big riddle, and we hope that other researchers may feel compelled to look at it.