An analysis of conjunctive-goal planning

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science

Department dc:contributor.department

Computer Science

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1986

Author dc:creator

• Joslin, David Eugene

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en

Handle dc:identifier.uri

http://hdl.handle.net/10919/106109

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/106109