TL;DR
This paper introduces a method to automatically learn temporal plan preferences from user-annotated examples, simplifying the process of specifying complex goals in AI planning. By leveraging existing LTL formula learning techniques and exploring different plan generation strategies, they demonstrate that users can effectively define preferences with a manageable number of examples.
What Problem Does This Paper Address?
In many AI planning applications, users have preferences about the plans generated (e.g., "avoid visiting location X before Y," "ensure resource Z is always available"). While languages like PDDL3 support specifying these preferences, formalizing them can be incredibly difficult for users. Existing approaches often rely on reward functions, which can be hard to elicit, or require users to precisely define complex temporal logic formulas. This paper tackles the challenge of making preference specification more accessible by enabling users to learn these preferences from concrete examples of good and bad plans, rather than requiring them to write formal logic.
Methods
The core of the approach involves a loop:
- Plan Generation: Generate a diverse set of candidate plans for a given planning task. The paper explores four methods:
- TopK: Generates the k best plans by cost.
- TopKFil: TopK with an added filter to remove plan permutations.
- AgDiv (Agile Diverse Planning): Iteratively generates plans, forbidding reorderings of previously found ones to encourage diversity.
- RNDhFF (Randomized hFF): A greedy best-first search with randomized heuristic values, followed by a uniqueness filter.
- Plan Annotation: The user is presented with these generated plans and annotates them as "good" or "bad" with respect to a single temporal preference they are currently trying to define.
- LTL Formula Learning: Using the annotated "good" and "bad" plans as positive and negative examples, an LTLf (finite Linear Temporal Logic) formula learner is employed. The paper uses a SAT-based approach, adapted from Camacho & McIlraith [2019a], to find the smallest LTLf formula that perfectly distinguishes between the positive and negative examples.
The system then presents the learned formula(s) to the user. This process can be repeated for each preference the user wishes to define.
Datasets
The paper uses benchmark planning instances from existing work, specifically variants of Blocksworld, Nomystery, Rovers, and TPP, which are designed for resource-constrained planning. For generating hidden target formulas, they utilize LTL templates (e.g., "always," "sometimes," "sequence") and instantiate them with random facts from the action effects of each domain. They created a benchmark set of 1284 task-formula pairs.
Key Insights and Ideas
- Bridging the Gap: The most significant insight is that learning preferences from examples is a viable and potentially much easier alternative to manual formalization.
- Plan Generation is Crucial: The quality of the learned formula is highly dependent on the diversity and balance of the example plans provided. If the generated plans are all similar or only represent one type of outcome (e.g., all good or all bad), learning fails.
- "Good Enough" is Often Achievable: Even with realistic plan generation (where the generator doesn't know the target preference), the system can often learn formulas that are equivalent or closely related to the hidden target, especially for simpler preferences.
- Alternative Use Case: Plan Space Explication: Learned formulas that aren't identical to the target can still be valuable. They can reveal non-obvious dependencies between plan properties, offering a new way to understand and explain the structure of the plan space.
Key Results
- Effectiveness: For reasonable-sized target formulas, the approach can learn them effectively.
- Plan Generation Impact: The choice of plan generation method significantly impacts the success rate. TopKFil and RNDhFF showed better balancedness of positive/negative examples compared to TopK. AgDiv and RNDhFF performed best in terms of learning quality in the realistic (Genapp) setup.
- Number of Examples: The number of example plans needed to learn a formula varies, but the paper suggests that a manageable number (median around 10 for RNDhFF in the idealized setup) is often sufficient.
- Realistic vs. Idealized: There's a substantial performance gap between "realistic" plan generation (where the generator doesn't know the target preference) and "idealized" generation (where it does). This gap is a key area for future work.
Limitations and Future Work
- Plan Generation Bottleneck: The primary limitation is the performance gap between realistic and idealized plan generation. The current realistic methods struggle to produce balanced sets of examples for complex preferences, hindering learning.
- User Burden: While reduced, the user still needs to annotate plans. The number of annotations required can still be a burden, especially for complex preferences.
- Future Work:
- Alleviating the Gap: The authors suggest that incorporating even partial information about the target preference (e.g., which predicates are of interest) could significantly improve plan generation and thus learning quality.
- Interactive Learning: Interleaving plan generation, annotation, and formula learning could provide a more fluid user experience.
- Handling Noise: Extending the approach to be robust to noisy annotations (incorrectly labeled examples) would make it more practical.
Summary updated