Technical Report No. 224 - Abstract

Malte Helmert, Robert Mattmüller, Gabi Röger
Approximation Properties of Planning Benchmarks

For many classical planning domains, the computational complexity of non-optimal and optimal planning is known. However, little is known about the area in between the two extremes of finding some plan and finding optimal plans. In this contribution, we provide a complete classification of the propositional domains from the first four International Planning Competitions with respect to the well-known approximation classes PO, APX, poly-APX, and NPO.