Automatic Reductions from PH into STRIPS or How to Generate Short Problems with Very Long Solutions
Aldo Porco, Alejandro Machado, Blai Bonet · Proceedings of the International Conference on Automated Planning and Scheduling · 2013
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.