1991 · 27 citations · 8 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingParallel ComputationSequential Decision-makingPolynomial Time ComplexityPolynomial-time AlgorithmsState Variables
This paper formally presents a class of planning problems which allows non-binary state variables and parallel execution of actions. The class is proven to be tractable, and we provide a sound and complete polynomial time algorithm for planning within this class. This result means that we are getting closer to tackling realistic planning problems in sequential control, where a restricted problem representation is often sufficient, but where the size of the problems make tractability an important issue. 1 Introduction A large proportion of earlier papers about planning focus either on implementation of planners, or on representation problems, using logic or otherwise, and do not address computational issues at all. Among earlier work on planning complexity, Chapman [ 1987 ] has designed an algorithm, called TWEAK, which captures the essentials of constraint-posting nonlinear planners. TWEAK is proven correct, but does not always terminate. Chapman has proven that the class of problems...
8
Planning for conjunctive goals
David Chapman · Artificial Intelligence · 1987 · 1.1K citations · Full text
Planning as search: A quantitative approach
Richard E. Korf · Artificial Intelligence · 1987 · 368 citations
Reasoning about partially ordered events
Thomas Dean, Mark Boddy · Artificial Intelligence · 1988 · 120 citations