ABSTRACT
This chapter presents an overview of how approximations and related techniques are used in automated planning. It focuses on classical planning problems, where states are conjunctions of propositions, all state information is known to the planner, all actions are instantaneous, and their outcomes are deterministic. The chapter provides some background on the classical planning problem and describes the main algorithmic approaches employed to solve this problem. It outlines several modern heuristic families underlying the success of classical planners built upon the planning-as-search approach. The chapter also describes incomplete and local search algorithms that sacrifice complete coverage of the search space to reduce computation time. It discusses approaches that reformulate the original planning problem into another combinatorial problem. The chapter explains approaches to identify structures that capture either independent or distinct subproblems of the original planning problem. It also outlines approximation and metaheuristics technique for more complex planning setting such as planning with time, resources, and uncertainty.
