The Role of Benchmarks.

Given the theoretical hardness of classical planning, the chance of developing practically usable solution algorithms appears slim. However, modern planning systems developed since the 1990s such as Graphplan [14], SATPLAN [75-78], HSP [16] and FF [68] have demonstrated their ability to solve planning tasks of considerable size. Their efficiency, or - put a bit more carefully - their perceived efficiency is somewhat at odds with the theoretical hardness of planning. To understand why we can observe such good planner performance, we must consider the methods with which the performance of planning systems is evaluated. This is the topic of the following Sect. 1.1, which will lead us to a discussion of planning benchmarks in Sect. 1.2 and their theoretical properties in Sect. 1.3. In the penultimate Sect. 1.4, we briefly introduce a set of standard benchmarks. The chapter concludes with an overview of Part I in Sect. 1.5. [ABSTRACT FROM AUTHOR]