Downward refinement and the efficiency of hierarchical problem solving
Artificial IntelligencePublished 1 November 1994
Fahiem Bacchus, Qiang Yang
Citations107
SJR quartileQ1
SJR score1.84
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The case when the DRP fails is examined, and an analytical model of search complexity parameterized by the probability of an abstract solution being refinable is provided, which provides a more accurate picture of the effectiveness of hierarchical problem solving.
Abstract
Analysis and experiments have shown that hierarchical problem solving is most effective when the hierarchy satisfies the downward refinement property (DRP), whereby every abstract solution can be refined to a concrete-level solution without backtracking across abstraction levels. However, the DRP is a strong requirement that is not often met in practice. In this paper we examine the case when the DRP fails, and provide an analytical model of search complexity parameterized by the probability of an abstract solution being refinable. Our model provides a more accurate picture of the effectiveness of hierarchical problem solving. We then formalize the DRP in Abstrips-style hierarchies, providing a syntactic test that can be applied to determine if a hierarchy satisfies the DRP. Finally, we describe an algorithm called Highpoint that we have developed. This algorithm builds on the Alpine algorithm of Knoblock in that it automatically generates abstraction hierarchies. However, it uses the theoretical tools we have developed to generate hierarchies superior to those generated by Alpine. This superiority is demonstrated empirically.2 2 Parts of Section 2 have previously appeared at AAAI-92 [4], and parts of Section 3 have previously appeared at IJCAI-91 [3].
Keywords
Computer Science
Journal of the Franklin InstituteAn introduction to probability theory and its applications
29,966 Citations1958
Artificial IntelligencePlanning in a hierarchy of abstraction spaces
1,163 Citations1974Earl D. Sacerdoti
Examples of the ABSTRIPS system's performance are presented that demonstrate the significant increases in problem-solving power that this approach provides, and some further implications of the hierarchical planning approach are explored.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)A Structure for Plans and Behavior
1,160 Citations1977Earl D. Sacerdoti
Progress to date in the ability of a computer system to understand and reason about actions is described, and the structure of a plan of actions is as important for problem solving and execution monitoring as the nature of the actions themselves.
Where the really hard problems are
1,021 Citations1991Peter Cheeseman, Bob Kanefsky +1 more
It is shown that NP-complete problems can be summarized by at least one "order parameter", and that the hard problems occur at a critical value of such a parameter.
Artificial IntelligencePlanning with constraints (MOLGEN: Part 1)
814 Citations1981Mark Stefik
This paper presents an approach to hierarchical planning, termed constraint posting, that uses constraints to represent the interactions between subproblems and is illustrated with a computer program that plans gene-cloning experiments in molecular genetics.
International Joint Conference on Artificial IntelligenceGenerating project networks
624 Citations1977Austin Tate
The planner (NONLIN) and the Task Formalism (TF) used to hierarchically specify a domain are described, which can aid in the generation of project networks.
CERN Document Server (European Organization for Nuclear Research)Practical Planning: Extending the Classical AI Planning Paradigm
517 Citations1988David E. Wilkins
Archives of Internal MedicineContemporary Approaches to Creative Thinking.
502 Citations1963Louis L. Lunsky
In the spring of 1958 six scientists gathered at the University of Colorado to consider the problem of creative thinking, its conditions, and how it can be fostered.
Atherton Press eBooksThe processes of creative thinking.
472 Citations2011Allen Newell, James Shaw +1 more
It is concluded that problem solving creative when the problems solved are relatively new and difficult, and what has been learned about problem solving by simulating certain human prblem solving pro cesses with digital computers is summarized.
Artificial IntelligenceAll I know: A study in autoepistemic logic
371 Citations1990Hector J. Levesque
This research attempts to show how some of these patterns of reasoning can be captured using only the classical notions of logic, by extending a logic of belief so that it is possible to say that only a certain proposition is believed.
Artificial IntelligenceDomain-independent planning Representation and plan generation
370 Citations1984David E. Wilkins
A domain-independent planning program that supports both automatic and interactive generation of hierarchical, partially ordered plans is described, and an improved formalism makes extensive use of constraints and resources to represent domains and actions more powerfully.
Artificial IntelligencePlanning as search: A quantitative approach
364 Citations1987Richard E. Korf
It is presented that planning can be viewed as problem-solving search using subgoals, macro-operators, and abstraction as knowledge sources and an analysis of abstraction concludes that abstraction hierarchies can reduce exponential problems to linear complexity.
Artificial IntelligenceTheorem proving with abstraction
143 Citations1981David A. Plaisted
The use of abstractions permits the advantages of set-of-support strategies to be realized in arbitrary complete non set- of-support resolution strategies.
Automatically generating abstractions for problem solving
80 Citations1991Craig A. Knoblock
A major source of inefficiency in automated problem solvers is their inability to decompose problems and work on the more difficult parts first, which can be addressed by employing a hierarchy of abstract problem spaces to focus the search.
Artificial IntelligenceSearching for an optimal path in a tree with random costs
80 Citations1983Richard M. Karp, Judea Pearl
It is shown that for p 1/2, every algorithm which guarantees finding an exact cheapest path, or even a path within a fixed cost ratio of the cheapest, must run in exponential average time.
Characterizing abstraction hierarchies for planning
73 Citations1991Craig A. Knoblock, Josh Tenenberg +1 more
This paper provides a crisp formalization of ABSTRIPS-style abstraction, and defines the refinement relationship between solutions at different levels of the abstraction hierarchy, crucial to developing efficient search strategies with this type of hierarchical planning.
Elsevier eBooksAbstraction in Planning
71 Citations1991Josh Tenenberg
This thesis explores the use of abstraction in planning in order to simplify the task of reasoning about the effects of an agent's actions within a complex world by ignoring details and including only those aspects of primary importance.
ABTWEAK: abstracting a nonlinear, least commitment planner
68 Citations1990Qiang Yang, Josh Tenenberg
Search reduction in hierarchical problem solving
68 Citations1991Craig A. Knoblock
This paper shows analytically that hierarchical problem solving can reduce the size of the search space from exponential to linear in the solution length and identifies a sufficient set of assumptions for such reductions in search.
Abstract theorem proving
42 Citations1989Fausto Giunchiglia, Toby Walsh
The generality of the framework is tested by formalizing and analyzing some work done in the past; its efficacy by giving a procedure which solves the false proof problem by avoiding the use of inconsistent abstract spaces.
International Joint Conference on Artificial IntelligenceAn efficient robot planner which generates its own procedures
39 Citations1973Laurent Siklóssy, J. Dreussi
LAWALY is a LISP program which solves robot planning problems given an axiomatic description of its capabilities in some world, and generates her own procedures to embody these capabilities.
Rare & Special e-Zone (The Hong Kong University of Science and Technology)The downward refinement property
33 Citations1991Fahiem Bacchus, Qiang Yang
Working within a semantics for ABSTRIPS-style abstraction, a semantic condition sufficient for guaranteeing its presence in an abstraction hierarchy is developed and a set of sufficient and polynomial-time checkable syntactic conditions that can be used for checking a hierarchy for the downward refinement property are provided.
An expected-cost analysis of backtracking and non-backtracking algorithms
28 Citations1991Colin McDiarmid, Gregory Provan
The general guideline that backtracking becomes attractive when there is the possibility of "dead-ends" or prohibitively costly outcomes is suggested.
Abstraction in problem solving and learning
28 Citations1993Amy Unruh, Paul S. Rosenbloom
The expected value of hierarchical problem-solving
20 Citations1992Fahiem Bacchus, Qiang Yang
This model predicts a phase boundary where abstraction provides no benefit: if the probability that an abstract solution can be refined is very low or very high, search with abstraction yields significant speed up, however, in the phase boundary area where the probability takes on an intermediate value search efficiency is not necessarily improved.
Elsevier eBooksAn Analysis of ABSTRIPS
17 Citations1992Craig A. Knoblock
A reconstruction and analysis of the algorithm used in ABSTRIPS shows that the method for constructing abstractions implicitly assumes that the preconditions that are determined to be details will be independent, and can degrade the performance of the planner.
Elsevier eBooksA Critical Look at Knoblock's Hierarchy Mechanism
15 Citations1992David E. Smith, Mark A. Peot
It is shown that Knoblock's method, and more generally, the principle of ordered monotonicity, can produce hierarchies that perform arbitrarily poorly and a technique is proposed based on evaluating the number of potential solutions to different possible subgoals in a plan.