An Analysis of Conjunctive Goal Planning

摘要: This thesis develops a formal theory of planning, using simple paradigm planning that has been previously explored in work such as GPS, HACKER, STRIPS and NOAH. analyzes the goal interactions occur when is stated conjunction subgoals. In this analysis we assume problem finite state space, operators are reversible. Graph can be used to characterize these subgoal interactions. The entire space treated graph, each or subgoals defines subgraph. Each subgraph composed one more connected components. Solving by choosing component contains final necessary sufficient condition for solving any problem. worst case, analyzing shown no effective than enumerating searching. complexity proves complete algorithm solve all problems linear time. technique ordering analyzed, along with several extensions technique. While generalization possible, case generating order requires much computation brute-force search. A called capability analysis, derived from connect results, uses first-order logic find constraints must apply achieved. partial implementation counterfactual identify components world prevent remaining being