Automatic Reductions from PH into STRIPS or How to Generate Short Problems with Very Long Solutions

Abstract

Recently, it has been shown how to automatically translate any problem in NP, expressed in the language of second-order logic, into a STRIPS planning problem. In this work, we extend this translation by considering decision problems in the polynomial-time hierarchy (PH) and not just NP. Since decision problems in PH require in general exponentially-long “certificates”, the plans (if any) for the resulting STRIPS problems may have exponential length. Besides explaining the novel translations, we present experimental results and discuss the challenges that such problems pose.