An Analysis of Conjunctive Goal Planning
| dc.contributor.author | Joslin, David E. | en |
| dc.contributor.author | Roach, John W. | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2013-06-19T14:36:57Z | en |
| dc.date.available | 2013-06-19T14:36:57Z | en |
| dc.date.issued | 1986 | en |
| dc.description.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 subgoals. 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 subgoal interactions. The entire state space is treated as a graph, and each subgoal or conjunction of subgoals defines a subgraph. Each subgraph is composed of one or more connected components. Solving each subgoal 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 connect component results, uses first-order logic to find the constraints that must apply as subgoals are achieved. A partial implementation uses counterfactual logic to identify the components of a world state that prevent the remaining subgoals from being achieved. | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier | http://eprints.cs.vt.edu/archive/00000041/ | en |
| dc.identifier.sourceurl | http://eprints.cs.vt.edu/archive/00000041/01/TR-86-34.pdf | en |
| dc.identifier.trnumber | TR-86-34 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/19904 | en |
| dc.language.iso | en | en |
| dc.publisher | Department of Computer Science, Virginia Polytechnic Institute & State University | en |
| dc.relation.ispartof | Historical Collection(Till Dec 2001) | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | An Analysis of Conjunctive Goal Planning | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |
Files
Original bundle
1 - 1 of 1