Approximation Properties of Planning Benchmarks
Malte Helmert, Robert Mattmüller, Gabriele Röger · 2006
Abstract. For many classical planning domains, the computationalcomplexity of non-optimal and optimal planning is known. However, little is known about the area in between the two extremes of findingsome plan and finding optimal plans. In this contribution, we provide a complete classification of the propositional domains from the firstfour International Planning Competitions with respect to the approximation classes PO, PTAS, APX, poly-APX, and NPO. 1 INTRODUCTION Considering the important role that benchmark domains such asL OGISTICS and SATELLITE play in evaluating the performance ofclassical planning algorithms, comparatively little is known about