An analysis of conjunctive-goal planning

Abstract

This thesis develops a formal theory of planning, using a simple paradigm of planning that has been previously explored in work such as GPS, HACKER, STRIPS and NOAH. This thesis analyzes the goal interactions that occur when the goal is stated as a conjunction of sub-goals. In this analysis we assume that the problem has a finite state space, and that operators are reversible.

Graph theory can be used to characterize these sub-goal interactions. The entire state space is treated as a graph, and each sub-goal or conjunction of sub-goals defines a subgraph. Each subgraph is composed of one or more connected components. Solving each sub-goal by choosing a connected component that contains a final goal state is a necessary and sufficient condition for solving any planning problem.

In the worst case, analyzing goal interactions is shown to be no more effective than enumerating the state space and searching. This complexity proves that no complete algorithm can solve all planning problems in linear time.

The technique of goal ordering is analyzed, along with several extensions to that technique. While a generalization of goal ordering is possible, in the worst case generating the goal order requires as much computation as solving the problem by a brute-force search.

A technique called capability analysis, derived from the connected component results, uses first-order logic to find the constraints that must apply as sub-goals are achieved. A partial implementation uses counterfactual logic to identify the components of a world state that prevent the remaining sub-goals from being achieved.