keyword
search heuristics
Search heuristics are practical strategies, rules of thumb, or evaluation functions used in artificial intelligence and computational problem-solving to guide an algorithm through a large search space toward a goal. Rather than exhaustively evaluating every potential path, state, or hypothesis, a search heuristic estimates the cost, quality, or distance associated with candidate decisions, prioritizing the most promising avenues while pruning less viable ones. By trading the guarantee of an exhaustive search for increased computational efficiency, these techniques significantly reduce the time and memory needed to find effective solutions, making them fundamental to automated planning, machine learning induction, theorem proving, and complex optimization problems.
3 items
Planning in a Hierarchy of Abstraction Spaces
Earl D. Sacerdoti
Why you should read this
Introduces ABSTRIPS, an automated planning system that constructs a hierarchy of abstraction spaces by ranking operator preconditions, drastically reducing search complexity and demonstrating how hierarchical planning overcomes the combinatorial explosion in complex problem domains.
A problem domain can be represented as a hierarchy of abstraction spaces in which successively finer levels of detail are introduced. The problem solver ABSTRIPS, a modification of STRIPS, can define an abstraction space hierarchy from the STRIPS representation of a problem domain, and it can utilize the hierarchy in solving problems. Examples of the system's performance are presented that demonstrate the significant increases in problem-solving power that this approach provides. Then some further implications of the hierarchical planning approach are explored.
Added
2026-09-25
The CN2 Induction Algorithm
Peter Clark, T. Niblett
Why you should read this
Introduces the CN2 rule induction algorithm, which combines the noise-handling capabilities and efficiency of decision trees with the flexible if-then representation of the AQ algorithm to learn accurate, interpretable classification rules from imperfect data.
Systems for inducing concept descriptions from examples are valuable tools for assisting in the task of knowledge acquisition for expert systems. This paper presents a description and empirical evaluation of a new induction system, CN2, designed for the efficient induction of simple, comprehensible production rules in domains where problems of poor description language and/or noise may be present. Implementations of the CN2, ID3, and AQ algorithms are compared on three medical classification tasks.
Added
2026-09-24
STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving
Richard E. Fikes, Nils J. Nilsson
Why you should read this
Establishes the foundational logic-based representation of states, goals, and actions, defining the problem of automated planning.
We describe a new problem solver called STRIPS 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. STRIPS represents a world model as an arbitrary collection of first-order predicate calculus formulas and is designed to work with models consisting of large numbers of formulas. It employs a resolution theorem prover to answer questions of particular models and uses means-ends analysis to guide it to the desired goal-satisfying model.
Added
2026-01-27