Speeding up problem solving by abstraction: a graph oriented approach
Artificial IntelligencePublished 1 August 1996
Robert C. Holte, Taieb. Mkadmi, Robert Zimmer, Alan MacDonald
Citations110
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
Experiments comparing these techniques on a variety of problems show that alternating opportunism (AltO) a variant of the new technique, is uniformly superior to all the others.
Abstract
This paper presents a new perspective on the traditional AI task of problem solving and the techniques of abstraction and refinement. The new perspective is based on the well-known, but little exploited, relation between problem solving and the task of finding a path in a graph between two given nodes. The graph oriented view of abstraction suggests two new families of abstraction techniques, algebraic abstraction and STAR abstraction. The first is shown to be extremely sensitive to the exact manner in which problems are represented. STAR abstraction, by contrast, is very widely applicable and leads to significant speedup in all our experiments. The reformulation of traditional refinement techniques as graph algorithms suggests several enhancements, including an optimal refinement algorithm, and one radically new technique: alternating search direction. Experiments comparing these techniques on a variety of problems show that alternating opportunism (AltO) a variant of the new technique, is uniformly superior to all the others.
Keywords
Computer Science
IEEE Transactions on Systems Science and CyberneticsA Formal Basis for the Heuristic Determination of Minimum Cost Paths
12,265 Citations1968Peter Hart, Nils J. Nilsson +1 more
How heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching is described and an optimality property of a class of search strategies is demonstrated.
Artificial IntelligenceStrips: A new approach to the application of theorem proving to problem solving
4,073 Citations1971Richard Fikes, Nils J. Nilsson
A new problem solver called STRIPS is described that attempts to find a sequence of operators in a space of world models to transform a given initial world model into a model in which a given goal formula can be proven to be true.
Principles of Artificial Intelligence
3,336 Citations1982Nils J. Nilsson
This classic introduction to artificial intelligence describes fundamental AI ideas that underlie applications such as natural language processing, automatic programming, robotics, machine vision, automatic theorem proving, and intelligent data retrieval.
Machine LearningVery Simple Classification Rules Perform Well on Most Commonly Used Datasets
1,798 Citations1993Robert C. Holte
On most datasets studied, the best of very simple rules that classify examples on the basis of a single attribute is as accurate as the rules induced by the majority of machine learning systems.
Artificial IntelligenceDepth-first iterative-deepening
1,549 Citations1985Richard E. Korf
A depth·first iterative·deepening algorithm is shown to be asymptotically optimal along all three dimmsions for exponential tree searches and is the only known algorithm that is capable of finding optimal solUtions to randomly generated instances of the Fif/un Puzzle within practical resource.
STRIPS: a new approach to the application of theorem proving to problem solving
1,479 Citations1971Richard Fikes, Nils J. Nilsson
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.
Computers and Thought
921 Citations1963Edward A. Feigenbaum, Julian Feldman
Elsevier eBooksGPS, A PROGRAM THAT SIMULATES HUMAN THOUGHT
817 Citations1988Allen Newell, Herbert A. Simon
This work shows that the techniques that have emerged for constructing sophisticated problem-solving programs also provide us with new, strong tools for constructing theories of human thinking that finally reveal with great clarity that the free behavior of a reasonably intelligent human can be understood as the product of a complex but finite and determinate set of laws.
Mathematical ProgrammingShortest paths algorithms: Theory and experimental evaluation
740 Citations1996Boris V. Cherkassky, Andrew V. Goldberg +1 more
An extensive computational study of shortest paths algorithms, including some very recent algorithms, is conducted, based on several natural problem classes which identify strengths and weaknesses of various algorithms.
DSpace@MIT (Massachusetts Institute of Technology)Systematic nonlinear planning
521 Citations1991David McAllester, David Rosenblitt
A simple, sound, complete, and systematic algorithm for domain independent STRIPS planning by starting with a ground procedure and then applying a general, and independently verifiable, lifting transformation.
Journal of the ACMKinodynamic motion planning
452 Citations1993Bruce R. Donald, Patrick Xavier +2 more
This work considers the simplified case of a point mass under Newtonian mechanics, together with velocity and acceleration bounds, and provides the first provably good approximation algorithm, and shows that it runs in polynomial time.
Artificial IntelligenceHeuristic search viewed as path finding in a graph
413 Citations1970Ira Pohl
A class of graph-searching procedures is described which uses a heuristic function to guide search, and a number of theoretical results for this model, and the intuition for these results, relate the efficiency of search to the accuracy of the heuristics used.
Randomized preprocessing of configuration for fast path planning
412 Citations2002Lydia E. Kavraki, J.-C. Latombe
This paper presents a new approach to path planning for robots with many degrees of freedom (DOF) operating in known static environments that is particularly attractive for many-DOF robots which have to perform many successive point-to-point motions in the same environment.
Artificial IntelligenceQuantitative results concerning the utility of explanation-based learning
368 Citations1990Steven Minton
This paper summarizes a set of experiments measuring the effectiveness of PRODIGY's EBL method (and its components) in several different domains.
Concept learning and the problem of small disjuncts
342 Citations1989Robert C. Holte, Liane Acker +1 more
Various approaches to this problem are evaluated, including the novel approach of using a bias different than the "maximum generality" bias, which prove partly successful, but the problem of small disjuncts remains open.
Artificial IntelligenceMacro-operators: A weak method for learning
295 Citations1985Richard E. Korf
The macro technique is a new kind of weak method, a method for learning as opposed to problem solving, and introduces a new type of problem structure called operator decomposability.
Elsevier eBooksOn Representations of Problems of Reasoning about Actions
268 Citations1981Saul Amarel
The chapter discusses a specific problem of transportation scheduling to evaluate the effects of alternative formulations of this problem on the expected efficiency of mechanical procedures for solving it and also to examine the processes that come into play when a transition takes place from a given problem formulation into a better one.
Artificial IntelligenceConcept learning and heuristic classification in weak-theory domains
255 Citations1990Bruce Porter, Ray Bareiss +1 more
This paper describes a successful approach to concept learning for heuristic classification that has been applied to the domain of clinical audiology and achieved a competence level equaling that of human experts and far surpassing that of other machine learning programs.
Proceedings of the Royal Society of London A Mathematical and Physical SciencesExperiments with the Graph Traverser program
205 Citations1966J. Doran, Donald Michie
An automatic method is described for the solution of a certain family of problems that depends upon the evaluation of intermediate states of the problem according to the extent to which they have features in common with the goal state.
International Joint Conference on Artificial IntelligenceSelectively generalizing plans for problem-solving
160 Citations1985Steven Minton
MORRIS is described, a heuristic problem solver that measures the utility of plan fragments to determine whether they are worth learning and comparing the performance of MORRIS to a less selective learning system.
IEEE Transactions on Pattern Analysis and Machine IntelligenceEnhanced iterative-deepening search
130 Citations1994A. Reinefeld, T.A. Marsland
The authors show that iterative-deepening searches can be greatly improved by exploiting previously gained node information, and their methods are faster and easier to implement than previous proposals.
Proceedings of the IRESteps toward Artificial Intelligence
115 Citations1961Marvin Minsky
The discussion is supported by extensive citation of the literature and by descriptions of a few of the most successful heuristic (problem-solving) programs constructed to date.
Artificial IntelligenceDownward refinement and the efficiency of hierarchical problem solving
107 Citations1994Fahiem Bacchus, Qiang Yang
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.
Using temporal logic to control search in a forward chaining planner
105 Citations1996Fahiem Bacchus, Froduald Kabanza
This work describes how natural domain information, of a “strategic” nature, can be expressed in a temporal logic, and then utilized to effectively control a forward-chaining planner.
Artificial IntelligenceToward a model of representation changes
103 Citations1980Richard E. Korf
The first steps in the development of a computer model of the process of changing representations in problem solving are presented, and a language for expressing representations and an interpreter for applying the transformations to representations have been developed.
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.
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.
International Joint Conference on Artificial IntelligenceFast recursive formulations for best-first search that allow controlled use of memory
72 Citations1989Anup K. Sen, A. Bagchi
Extensive runs on a variety of search problems, involving search graphs that may or may not be trees, indicate that MREC with M = 0 is as good as IDA* on problems such as the 15- puzzle for which IDA*, is suitable, while M REC with large M is as fast as A*, on problems for which node expansion time is not negligible.
ABTWEAK: abstracting a nonlinear, least commitment planner
68 Citations1990Qiang Yang, Josh Tenenberg
Artificial IntelligenceA structural theory of explanation-based learning
65 Citations1993Oren Etzioni
A theory which predicts and explains when EBL will work and why and suggests that a static analyzer of problem space definitions can match EBL's performance is presented.
Artificial IntelligencePerimeter search
58 Citations1994John Dillenburg, Peter Nelson
Analytical and experimental results are presented to show that perimeter search is more efficient than IDA∗ and A∗ in terms of time complexity and number of nodes expanded for two problem domains.
The Computer JournalDiscussion and correspondence: A note on the Towers of Hanoi problem
52 Citations1977Patrick J. Hayes
Information SciencesA result on the computational complexity of heuristic estimates for the A∗ algorithm
50 Citations1984Marco Valtorta
The performance of a new heuristic search algorithm that uses a formal representation that contains enough information to compute the heuristic evaluation function h(n), as defined in the context of A*, without requiring a human expert to provide it is analyzed.
Kluwer international series in engineering and computer scienceChange of Representation and Inductive Bias
49 Citations1990D. Paul Benjamin
A statistical approach to solving the EBL utility problem
44 Citations1992Russell Greiner, Igor Jurišica
PALO is presented, based on a mathematically rigorous form of utility analysis, that uses statistical techniques to determine whether the result of a proposed transformation will be better than the original system and includes empirical evidence that this approach can work effectively.
National Conference on Artificial IntelligenceIntegrating abstraction and explanation-based learning in PRODIGY
42 Citations1991Craig A. Knoblock, Steven Minton +1 more
This paper describes the integration of abstraction and explanation-based learning (EBL) in the context of the PRODIGY system and presents empirical results showing the effect of combining the two modules and describes the factors that influence the overall performance of the integrated system.
Artificial IntelligenceHeuristic search through islands
38 Citations1986P. P. Chakrabarti, S. Ghose +1 more
A heuristic search strategy via islands is suggested to significantly decrease the number of nodes expanded to ensure a suboptimal cost path (which may be optimal) and in extreme cases falls back to A∗.
Searching With Abstractions: A Unifying Framework and New High-Performance Algorithm 1
29 Citations1994Robert C. Holte, Chris Drummond +3 more
A common algorithmic framework encompassing the two main methods for using an abstract solution to guide search is presented, and the "alternating opportunism" technique produces shorter solutions than classical refinement with the same amount of search.
Kluwer international series in engineering and computer scienceA Theory of Abstraction for Hierarchical Planning
29 Citations1990Craig A. Knoblock
The paper formally defines hierarchical planning, shows that the technique can reduce an exponential search space to a linear one, and identifies the assumptions under which this analysis holds, and presents an algorithm for producing abstractions with the monotonicity property, a heuristic for evaluating abstraction spaces.
Artificial IntelligenceAlgorithms for searching explicit AND/OR graphs and their applications to problem reduction search
20 Citations1994P. P. Chakrabarti
Algorithm for finding out optimal cost solutions of an explicit AND/OR graph and how these algorithms can be incorporated in implicit graph search schemes like AO∗ so that they work for transformation rules which lead to graphs with cycles.
Generating effective admissible heuristics by abstraction and reconstitution
8 Citations1993Armand Prieditis, Bhaskar Janakiraman
This paper describes a method to reconstitute the abstracted details back into the solution to the Abstracted problem, thereby boosting accuracy while maintaining admissibility, and empirical results suggest that reconstitution can make a good admissible heuristic even better.
FigshareCharacterizing and Automatically Finding Primary Effects in Planning
7 Citations2018Eugene Fink, Qiang Yang
This paper presents a formal criterion for selecting useful primary effects, which guarantees planning efficiency, completeness, and optimality, and describes an inductive learning algorithm based on this criterion that automatically selects primary effects of operators.
Expert Systems with ApplicationsProceedings of the workshop on change of representation and problem reformulation
3 Citations1997Michael Lowry
This workshop was focused on analytic or knowledge-based approaches, as opposed to statistical or empirical approaches called 'constructive induction', and there is a potential for combining analytic and inductive approaches at a future date.
Routing heuristics for Cayley graph topologies
2 Citations2002Martin Hitz, Thomas A. Mueck
In this work, the Cayley graph model is used to generate and evaluate a large number of different interconnection topologies, and simulated annealing techniques are used to find accurate traversal heuristics for each candidate.
Expert Systems with ApplicationsBecoming reactive by concretization
1 Citations1997Armand Prieditis, Bhaskar Janakiraman
An incremental approach to constructing the action table through achieving goals with a hierarchical search system is described and it is shown how an implemented hierarchicalsearch system can completely reactive.
International Joint Conference on Artificial IntelligenceSearch methods using heuristic strategies
1 Citations1981Michael Georgeff
This paper examines algorithms for performing strategic search using both deterministic and nondeterministic strategies, and indicates how meta-level strategies can be used to guide the application of object level strategies, thus providing a hierarchy of strategic information.