TLDR: A new research paper by Blai Bonet and Hector Geffner introduces a scalable symbolic AI method for learning general problem-solving policies. This approach, utilizing a hitting set algorithm and a novel ‘stratified policy’ concept, overcomes the traditional scalability limitations of symbolic AI while retaining its interpretability and correctness. The method, implemented through GENEX and WRAPPER algorithms, ensures policies are acyclic and can handle millions of states and hundreds of thousands of features, demonstrating strong performance across various planning domains and generalizing well to larger, unseen problems.
Artificial intelligence has made incredible strides in recent years, but teaching AI agents to solve complex planning problems efficiently and reliably remains a significant challenge. Imagine an AI that can not only find a solution for a single task, but learn a general strategy that works for an entire collection of similar problems, even if they involve different numbers of objects or varying initial conditions. This is the realm of ‘general policies’ in AI planning.
Traditionally, two main approaches have dominated this field: deep learning and symbolic methods. Deep learning excels at handling vast amounts of data and scaling up to complex scenarios, but the resulting policies can often be opaque – it’s hard to understand why the AI makes certain decisions, and their generalization to new, unseen situations isn’t always guaranteed. Symbolic methods, on the other hand, offer policies that are transparent, understandable, and provably correct. However, their major drawback has been a lack of scalability, limiting them to small training instances and feature sets.
A new research paper, titled Learning General Policies From Examples, by Blai Bonet and Hector Geffner, introduces a novel symbolic method that aims to bridge this gap. Their work proposes a way to learn general policies that combines the interpretability and correctness of symbolic AI with the scalability needed for real-world applications. This new approach can handle problems with millions of states and hundreds of thousands of features, a significant leap forward from previous symbolic methods.
The Core Innovation: Scalability and Structural Termination
The key to this breakthrough lies in two main areas. First, unlike prior symbolic methods that relied on computationally intensive techniques like SAT/ASP (Satisfiability/Answer Set Programming) solvers, the new method uses a hitting set algorithm. This algorithm is far more efficient and allows the system to process much larger datasets and feature pools.
Second, the researchers introduce a novel concept called ‘structural termination,’ which ensures that the learned policies are inherently acyclic. In simpler terms, this means the policy will always progress towards a goal and will not get stuck in infinite loops. This is a crucial property for reliable AI, and the paper’s ‘stratified policies’ are designed to guarantee this by organizing features in a way that ensures their values change a finite number of times along any trajectory.
How It Works: GENEX and WRAPPER
The new learning system consists of two main algorithms: GENEX and WRAPPER. GENEX (Generalization from Examples) is the core algorithm. It takes sets of ‘good’ (desired) and ‘bad’ (undesired) state transitions, along with a pool of features (descriptions of the state), and finds a stratified policy that includes the good transitions, avoids the bad ones, and is guaranteed to terminate.
The WRAPPER algorithm acts as a meta-learner around GENEX. It starts by using a classical planner to generate example plans for a small subset of training problems. It then feeds these examples to GENEX. If the resulting policy doesn’t solve all the training problems, WRAPPER identifies where the policy fails (e.g., gets stuck or reaches a dead end) and adds more ‘good’ or ‘bad’ transitions to the training set for GENEX to learn from. This iterative process continues until a robust general policy is found.
Also Read:
- Scalable Option Learning: Unlocking Large-Scale Training for Hierarchical AI
- CoreThink Unveils a New Symbolic Reasoning Layer for Enhanced LLM Performance
Impressive Results and Future Outlook
The experiments conducted on 34 standard planning domains demonstrate the effectiveness of this new approach. The system successfully found general policies for 20 of these domains, including some that were previously unsolvable by other symbolic methods. Crucially, the learned policies showed strong generalization capabilities, often solving instances significantly larger than those used for training, with high coverage and efficient execution.
While the WRAPPER algorithm is not always complete (meaning it might not find a policy even if one exists), this work represents a significant advancement in symbolic AI. It offers a powerful new tool for developing AI agents that can learn general, understandable, and reliable problem-solving strategies, opening doors for more robust and transparent AI applications in complex planning environments.
