Studies in Action Planning - Algorithms and Complexity

The action planning problem is known to be computationally hard in the general case. Propositional planning is Pspace-complete and first-order planning is undecidable. Consequently, several methods to reduce the computational complexity of planning have been suggested in the literature. This thesis contributes to the advance and understanding of some of these methods. One proposed method is to identify restrictions on the planning problem which ensure tractability. We propose a method using a state-variable model for planning and define structural restrictions on the state-transition graph. We also present a planning algorithm that is correct and tractable under these restrictions as well as a map of the complexity results for planning under our new restrictions and certain previously studied restrictions. The algorithm is further extended to apply to a miniature assembly line. Another method that has been studied is state abstraction. The idea is to first plan for the most important g..