AAAI Publications, Twenty-Third International Conference on Automated Planning and Scheduling

Font Size: 
Automatic Reductions from PH into STRIPS or How to Generate Short Problems with Very Long Solutions
Aldo Porco, Alejandro Machado, Blai Bonet

Last modified: 2013-06-02


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.


Automated Planning, Translation, Complexity, Descriptive Complexity

Full Text: PDF