A key capability of autonomous systems is to flexibly adapt to different environments and still act in a goal-directed way – even in unforeseen situations. Artificial Intelligence (AI) planning provides a powerful means to realize such behavior. It is a domain-independent reasoning technique that allows to derive – fully automatically – a sequence of actions that transforms a given initial state of a system into a desired state. A widely-used planning technique, in particular for real-world applications, is hierarchical planning.

We start with a study of the computational complexity of finding solutions to these problems and identify several restrictions that impact the hardness of hierarchical planning. Identifying potentially tractable problem classes enables the development of specialized solvers and search heuristics. Heuristics are an essential part of planning systems that are capable of finding solutions to complex planning problems quickly, which is of high importance for reactive autonomous systems. The design of state-of-the-art heuristics is illustrated by introducing the family of TDG heuristics for hierarchical planning. We show several examples on how AI planning enables the design of flexible, situation-adaptive autonomous systems. This includes personal assistants for setting up devices for home entertainment and assisting novice users with "Do it yourself" projects.