Foundations And Applications Of Generalized Planning

Research in the field of Automated Planning is largely focused on the problem of constructing plans or sequences of actions for going from a specific initial state to a goal state. The complexity of this task makes it desirable to find generalized plans which can solve multiple problem instances from a class of similar problems. Most approaches for constructing such plans work under two common constraints: (a) problem instances typically do not vary in terms of the number of objects, unless theorem proving is used as a mechanism for applying actions, and, (b) generalized plan representations avoid incorporating loops of actions because of the absence of methods for efficiently evaluating their effects and their utility. Approaches proposed recently address some aspects of these limitations, but these issues are representative of deeper problems in knowledge representation and model checking, and are crucial to the problem of generalized planning. Moreover, the generalized planning problem itself has never been defined in a manner which could unify the wide range of representations and approaches developed for it. This thesis is a study of the fundamental problems behind these issues. We begin with a comprehensive formulation of the generalized planning problem and an identification of the most significant challenges involved in solving it. We use an abstract representation from recent work in model checking to efficiently represent situations with unknown quantities of objects and compute the possible effects of actions on such situations. We study the problem of evaluating loops of actions for termination and utility by grounding it in a powerful model of computation called abacus programs. Although evaluating loops of actions in this manner is undecidable in general, we obtain a suite of algorithms for doing so in a restricted class of abacus programs, and consequently, in the class of plans which can be translated to such abacus programs. In the final sections of this thesis, these components are utilized for developing methods for solving the generalized planning problem by generalizing sample plans and merging them together; by using classical planners to automate this process and thereby solve a given problem from scratch; and also by conducting a direct search in the space of abstract states