Reference: Ginsberg, M. L. Possible Worlds Planning. 1986.
Abstract: The size of the search space is perhaps the most intractable of all the problems facing a general-purpose planner. Some planning methods (means-ends analysis being typical) address this problem by encouraging the system designer to give the planner domain-specific information (perhaps in the form of a difference table) to help govern this search. This paper presents a domain-independant approach to this problem based on the examination of possible worlds in which the planning goal has been achieved. Although a weak method, the ideas presented lead to considerable savings in many examples; in addition, the natural implementation of this approach has the attractive property that incremental efforts in controlling the search provide incremental improvements in performance. This is in contrast to many other approaches to the control of search or inference, which may require large expenditures of effort before any benefits are realized.
Notes: Working Paper.