TL;DR
This paper introduces a novel method for learning "generalized potential heuristics" that work across all instances of a planning domain, not just a single problem. By using a mixed-integer programming approach on sample tasks, they automatically discover compact, interpretable heuristics that guarantee polynomial-time planning for any instance.
What Problem Does This Paper Address?
Classical AI planning systems can solve complex problems, but the plans they generate are typically specific to a single instance. Generalized planning aims to create solutions that are valid for an entire class of problems (a "domain"). This paper tackles the challenge of creating generalized heuristics – functions that guide search algorithms towards a goal. Existing heuristics are often instance-specific. The authors propose learning generalized heuristics that are "descending" and "dead-end avoiding," meaning they reliably guide greedy search algorithms to a solution in polynomial time for any instance within a given domain, without needing to be re-learned for each new problem.
Methods
The core of the paper is the development of "generalized potential heuristics." These are defined as weighted sums of "state features." These features are derived from concept languages (a subset of first-order logic) and represent properties like "the number of blocks that are clear" or "the distance from the robot to the nearest unvisited location."
The key innovation is an approach to learn these heuristics automatically. They formulate this learning problem as a Mixed Integer Program (MIP). The MIP is trained on a set of "training instances" and their reachable states. The objective is to find weights for the concept-based features such that the resulting heuristic is descending and dead-end avoiding across all observed states, while also minimizing the complexity of the features used (to encourage generalization).
Two variations of the learning approach are presented:
- Incremental Constraint Generation: This method starts with a small subset of states and iteratively adds more states (and corresponding constraints) if the current heuristic doesn't generalize. This helps to avoid the computational cost of expanding the entire state space of all training instances upfront.
- Refinement for Unseen States: If a learned heuristic leads a greedy search into a local minimum on a new instance (one not seen during training), this method refines the heuristic by adding new constraints to the MIP to correct the behavior for that specific problematic path.
Datasets
The paper evaluates their approach on several standard AI planning domains:
- Gripper: A robot moving balls between rooms.
- Miconic: An elevator transporting passengers.
- Spanner: An agent collecting spanners to tighten nuts.
- VisitAll: An agent visiting all locations in a graph.
- Logistics: Transporting packages between cities using trucks and planes.
The authors use "training instances" from these domains. They don't introduce new benchmarks but rather use existing domain encodings and generate training instances with reachable state spaces of up to 15,000 states.
Key Insights and Ideas
- Generalization is Key: The primary insight is that it's possible to learn heuristics that are truly domain-wide, not just problem-specific. This shifts the focus from solving individual problems to building reusable planning components.
- Concept Languages as Feature Factories: Using concept languages provides a principled way to define meaningful, interpretable, and generalizable state features that capture domain dynamics.
- MIP for Heuristic Synthesis: Formulating heuristic learning as a MIP is a powerful technique. It allows for the simultaneous optimization of multiple criteria (descending, dead-end avoiding, low complexity) and the incorporation of complex logical constraints.
- Complexity vs. Expressivity Trade-off: The choice of concept language and feature complexity is crucial. More expressive features can be more compact but lead to larger MIPs. The incremental and refinement approaches help manage this trade-off.
- Interpretable Heuristics: Even automatically learned heuristics often retain a degree of interpretability, which is valuable for understanding planning behavior.
Key Results
- The proposed approach successfully learns descending and dead-end avoiding generalized potential heuristics for the tested domains (Gripper, Miconic, Spanner, VisitAll).
- These learned heuristics were shown to generalize to unseen instances of the domains, enabling polynomial-time planning via greedy search.
- The incremental constraint generation method converged quickly (typically within 3 iterations) for the tested domains.
- For VisitAll, generalization was limited by the maximum graph diameter in the training instances, highlighting a potential area for future work.
- The learned heuristics often differed from manually designed ones but achieved similar or better performance with lower complexity.
Limitations and Future Work
- Limited Plan Length: The linear nature of the features and weights means the learned heuristics are best suited for domains where optimal plans are also linear in the number of objects. Domains requiring super-linear plans are not well-addressed.
- Detecting Unsolvability: The current heuristics are finite-valued and cannot inherently detect unsolvable instances. The authors suggest this is an orthogonal problem that could be addressed with separate mechanisms.
- Scalability: The MIP approach can become computationally expensive for domains with very complex features or a vast number of candidate features (e.g., Blocksworld and Logistics in their experiments).
- Interpretability Optimization: While learned heuristics are somewhat interpretable, optimizing directly for human interpretability is an open challenge.
- Future Work: The authors suggest deductive proofs of correctness for learned heuristics, exploring more expressive concept languages, improving feature selection, and scaling the approach to more complex domains. They also mention the possibility of combining finite and infinite heuristic values.
Summary updated