Planning and Complexity Malte Helmert Duration: Half-day Contact: Malte Helmert, helmert@informatik.uni-freiburg.de Planning is a hard problem. But just how hard, exactly? This tutorial investigates the hardness of planning from a number of angles to shed light on some of the most important formal questions surrounding the planning problem and its variants. Starting from classical complexity results for propositional STRIPS planning, we have a look at the perils of plan execution, get to know the price of uncertainty and find out how well we can cope with numbers. Encouraged (or discouraged?) by this news, we jump from general results to some specific planning domains, trying to discover just how close to optimality we can get.