Toward a mathematical theory of plan synthesis
Edwin Pednault · 1987
Planning problems generally have the following form: given a set of goals, a set of allowable actions and a descriptive of the current state of affairs, find a sequence of allowable actions that will bring about a state of affairs in which all of the desired goals are satisfied. This dissertation examines the question of how to solve planning problems efficiently. This question is addressed from a rigorous, mathematical standpoint, in contrast to the informal and highly experimental treatments found in most previous works. By introducing mathematical rigor, it has been possible to develop techniques that are capable of solving a much broader class of problems than has been considered in the past. For example, problems that involve time and context-dependent actions can be solved using the techniques that are presented. It has also been possible to unify and generalize many existing ideas in automatic planning, showing how they arise from first principles and how they may be applied to solve this broader class of problems. These ideas include means-ends analysis, opportunistic planning, goal protection, goal regression, constraint posting/propagation, and formal objects.