TL;DR
This paper introduces novel techniques to improve generalized planning (GP), a field focused on creating programs that solve a range of planning problems. They propose "action novelty rank" to prune redundant program structures and "lifted helpful actions" to guide the search more effectively, leading to state-of-the-art performance on standard GP benchmarks.
What Problem Does This Paper Address?
Generalized Planning (GP) aims to generate a single "planning program" that can solve not just one specific planning problem, but an entire set of related problems. Think of it like writing a script that can handle variations of a task, like a robot arm picking up different sized boxes. Classical planning techniques, like heuristics and landmarks, have been adapted to help GP, but scaling GP to more complex scenarios remains a challenge. This paper tackles this by introducing new ways to make the search for these general plans more efficient and effective, specifically by addressing redundancy within generated programs and improving how the search is guided.
Methods
The core contributions of this paper lie in two main areas:
- Action Novelty Rank: This new concept quantifies how "novel" an action is within a planning program. If an action appears too frequently (exceeding a defined bound
v), the program is considered redundant and pruned. This is implemented in two new algorithms: - Novelty-Based BFS (BFS(v)): A best-first search that incorporates this novelty pruning.
- Novelty-Based Progressive PGP (PGP(v)): A progressive search variant that also uses novelty pruning, building upon existing state-of-the-art methods.
- Lifted Helpful Actions: Inspired by helpful actions in classical planning, this work extends the concept to GP. Instead of just looking at individual actions, they consider "action schemes" (templates for actions) and how they contribute to achieving goals across a set of instances. This helps prioritize actions that are genuinely useful for solving the broader GP problem.
- New Evaluation Functions and Structural Restrictions: The authors also propose new cost functions to guide the search and introduce structural restrictions on program generation (e.g., limiting certain actions in the first line, disallowing nested goto instructions) to further improve efficiency.
Datasets
The experiments were conducted on standard benchmarks for generalized planning, comprising:
- Eight STRIPS domains: These are symbolic planning domains.
- Six numerical domains: These domains involve numerical variables and states.
The paper does not introduce new benchmarks but focuses on evaluating their methods on existing ones.
Key Insights and Ideas
- Redundancy is a major bottleneck in GP: The concept of "action novelty rank" highlights that simply repeating actions excessively within a planning program can lead to inefficiency. Pruning these redundant structures significantly speeds up the search.
- Lifted helpful actions provide a more general guidance: By considering action schemes and their impact across multiple instances, lifted helpful actions offer a more robust way to guide the search compared to instance-specific helpful actions.
- Structural restrictions are crucial for scalability: Simple rules about how programs are constructed (e.g., what actions can start a program) can have a surprisingly large impact on search efficiency without sacrificing completeness.
- Low novelty bounds are surprisingly effective: The authors found that even very small bounds for action novelty (v=1 or v=2) were sufficient to solve many problems, indicating that GP problems often have inherent structures that can be exploited by novelty-based pruning.
Key Results
The paper demonstrates that their proposed algorithms, BFS(v) and PGP(v), significantly outperform the state-of-the-art in generalized planning.
- Improved Performance: BFS(v) and PGP(v) consistently matched or outperformed their baseline counterparts (BFS and PGP) in terms of search time and the number of expanded/evaluated nodes across various domains.
- Effectiveness of Novelty Pruning: The novelty-based pruning was shown to be highly effective, leading to substantial improvements, especially in domains like Select and Sorting where search time was reduced from hundreds of seconds to just a few.
- New Evaluation Functions: The novel evaluation functions (fha, fin, fen) integrated with existing heuristics also showed strong efficiency gains in specific domains.
- High Success Rate with Low Bounds: For many problems, a novelty bound of
v=1orv=2was sufficient to find solutions, demonstrating the power of this approach.
Limitations and Future Work
- Limitations:
- The paper notes that helpful actions can sometimes misguide the search if necessary actions are absent due to the open-world assumption over goals.
- In some specific cases (e.g., Corridor, Ontable, Spanner), the structural restriction of only allowing applicable actions in the first line prevented finding solutions, suggesting a need for more nuanced restrictions.
- Future Work:
- The authors suggest that other novelty-based search strategies and lifted HA extraction methods from classical planning could be adapted for GP.
- Exploring how to better handle situations where helpful actions might be misleading is also a potential avenue.
- Further investigation into the interplay between structural restrictions and evaluation functions for optimizing GP performance is implied.
Summary updated