Combinatorial search is the bedrock of artificial intelligence, powering everything from robotic pathfinding to automated theorem proving. However, algorithms like $A^*$ or Satisfiability Modulo Theories (SMT) solvers are only as effective as their heuristics—the mathematical compasses that guide them through exponential state spaces. Historically, designing these heuristics has been a manual bottleneck, requiring decades of human intuition and trial-and-error.
To overcome this limitation, a prominent research direction focuses on automated heuristic discovery. Instead of relying on human experts to hand-code domain-specific rules, these techniques allow systems to autonomously derive, learn, or compose search heuristics directly from problem descriptions and data.
The Logic of Abstraction and Transformation
How can a machine "invent" a heuristic from scratch? The most mathematically rigorous way is through problem abstraction. If you remove or relax certain constraints from a complex problem, the optimal solution to this simplified version is guaranteed to be less than or equal to the true optimal cost. Because it never overestimates the actual cost, this abstract solution functions as an admissible heuristic that guarantees optimality when used in algorithms like $A^*$.
Jack Mostow et al. pioneered this transformational approach with ABSOLVER, a system that takes a formal problem description and applies a catalog of algebraic transformations to abstract it. By automatically dropping constraints, ABSOLVER could re-derive classic human-designed heuristics (like Manhattan Distance for the 8-puzzle) and discover entirely new ones for complex domains like Rubik's Cube.
Building on this foundational concept, Armand Prieditis demonstrated that machine-discovered heuristics could systematically outperform human intuition, expanding significantly fewer states and reducing the effective branching factor of difficult combinatorial puzzles by multiple orders of magnitude.
To scale this process to massive state spaces, automated systems must navigate a fundamental space-time trade-off. As shown by the authors of A Space-Time Tradeoff for Memory-Based Heuristics, generating a wide variety of state-space abstractions allows an algorithm to systematically balance memory usage against search time. When a single global abstraction is too loose to provide strong guidance, more sophisticated structural decompositions can be discovered. For example, Aria Haghighi et al. introduced a method to automatically factor complex models into simpler, overlapping projections. By using linear programming to find the tightest possible lower bounds across these projections, the system constructs powerful admissible heuristics for high-dimensional tasks like bitext parsing.
Learning Search Strategies from Experience
While symbolic abstraction provides rigorous mathematical guarantees, another powerful paradigm treats heuristic discovery as an inductive learning problem. By practicing on problem instances, an agent can observe its own successes and failures to refine its search behavior.
Early systems established this loop by modifying discrete rule sets. Pat Langley developed SAGE.2, a framework that allows an automated agent to evolve from an exhaustive, blind searcher into an expert solver by optimizing its search rules based on practice behavior. To navigate the massive space of potential rules without human guidance, Stephen F. Smith utilized adaptive, evolutionary search algorithms to efficiently discover high-quality heuristics based on empirical performance.
Modern approaches supercharge this inductive loop by pairing classical search algorithms with deep learning and reinforcement learning (RL):
- Imitation Learning: Instead of hand-crafting features, a neural network can be trained to mimic an expensive, optimal planner. Markus Spies et al. embedded a trained neural network directly into Focal Search ($A^*_\omega$). This combination uses the network's "intuition" to accelerate multi-agent pathfinding while maintaining strict mathematical bounds on how far the solution can deviate from the optimum.
- Reinforcement Learning: In domains where optimal training data is unavailable, agents can learn via self-play or trial-and-error. Andrea Micheli et al. used RL to automatically synthesize search heuristics for temporal planning, training a neural network to estimate the downstream value of symbolic planning states.
- Strategy Synthesis: For discrete reasoning tools like SMT solvers, Mislav Balunovic et al. developed fastSMT, a system that automatically learns optimal solver strategies for specific problem domains, replacing the traditional, labor-intensive manual tuning process.
Compositionality and Negative Guidance
Automated discovery does not always require synthesizing a complex heuristic completely from scratch. Instead, effective guidance can be constructed by combining simple building blocks or by focusing on what not to do.
The authors of Automated Discovery of Composite SAT Variable-Selection Heuristics demonstrated that a system can successfully generate highly competitive heuristics for SAT solvers by automatically composing primitive, interpretable operations. This compositional approach allows the system to systematically explore a vast design space that would be impossible for a human engineer to map out manually.
┌────────────────────────────────────────────────────────┐
│ Automated Discovery │
└───────────────────────────┬────────────────────────────┘
│
┌─────────────┴─────────────┐
▼ ▼
┌───────────────────────────┐┌───────────────────────────┐
│ Positive Guidance ││ Negative Guidance │
│ "Where should we search?"││ "What should we avoid?" │
│ e.g., Composite Primitives││ e.g., BLOCKHEAD Rules │
└───────────────────────────┘└───────────────────────────┘
Furthermore, efficient search is as much about avoiding dead ends as it is about finding the goal. Dennis F. Kibler et al. explored this via "negative heuristics"—explicit rules designed to prevent a system from making obviously inefficient choices. By focusing on avoiding demonstrably poor decisions, forward-chaining systems can navigate massive state spaces with minimal wasted effort.
Overcoming Practical Bottlenecks
The shift from manual heuristic engineering to automated discovery addresses a critical bottleneck across diverse subfields of computer science.
In Answer Set Programming (ASP), Martin Gebser et al. highlighted that manual heuristic design requires a deep understanding of solver internals, creating a barrier for real-world applications and motivating the need for systems that can automatically learn domain-specific rules from solver runs.
In robotics, where symbolic logic intersects with continuous physical space, Caelan Reed Garrett demonstrated that relying on static, user-provided geometric samplers often fails to exploit the unique structure of a problem instance, requiring automated heuristics to guide high-level symbolic search toward valid continuous trajectories.
Even the strict requirement of admissibility can be relaxed and managed automatically. Ofir Marom et al. showed that by leveraging Bayesian uncertainty, a system can learn "likely-admissible" heuristics from data without requiring expensive, pre-existing optimal plans.
Ultimately, as synthesized by Roni Stern et al., the field is moving toward a unified paradigm of automated domain learning. By enabling solvers to independently discover problem properties and adapt their strategies, this research direction bridges the gap between general-purpose "black-box" algorithms and highly specialized, hand-tuned expert systems.
Key Foundational Work
Learning Effective Search Heuristics (1983) — contributed 1 concept elements to this direction.
Flexible Learning of Problem Solving Heuristics Through Adaptive Search (1983) — contributed 1 concept elements to this direction.
Don't Be Stupid (1981) — contributed 1 concept elements to this direction.