TL;DR
This paper introduces significantly faster algorithms for explaining why a proposed plan doesn't satisfy user preferences, extending the previous framework to handle more expressive temporal logic properties (LTLf) with minimal overhead. This advancement makes plan-space explanation more practical and applicable to a wider range of real-world planning problems.
What Problem Does This Paper Address?
When automated planners generate plans, especially in complex domains like production planning or disaster recovery, it's often difficult for humans to articulate their preferences upfront. This leads to an iterative process where planners suggest candidate plans, and users provide feedback. A crucial part of this interaction is explaining why a suggested plan fails to meet a user's implicit preferences.
Eifler et al. (2020) proposed a framework for this using "plan-property dependencies." A plan property is essentially a condition a plan might satisfy (e.g., "use less than 100 energy units"). A dependency states that if a plan satisfies a set of properties X, it cannot satisfy a set of properties Y. This allows for explanations like, "You can't achieve properties X because you'd have to give up properties Y."
The core challenge addressed by this paper is twofold:
- Efficiency: Eifler et al.'s original algorithms for computing these dependencies were computationally expensive, limiting their practical use.
- Expressivity: The original framework was restricted to simple goal facts and "action-set" properties (which check if certain actions are used). This is insufficient for many real-world temporal preferences, such as "deliver package A before package B."
Methods
The paper presents two main algorithmic contributions for computing plan-property dependencies, specifically focusing on finding "minimal unsolvable goal subsets" (MUGS), which are the core of these dependencies.
- Symbolic Search for MUGS: This approach leverages Binary Decision Diagrams (BDDs) to represent the entire reachable state space of a planning problem. By building a BDD of all states reachable within the cost bound, the solvability of any goal subset can be tested very efficiently. This method essentially performs a single, comprehensive search, avoiding redundant planning calls.
- Explicit State-Space Search with Pruning: This method uses a more traditional explicit state-space search but incorporates advanced pruning techniques. It maintains a set of "maximal solvable goal subsets" found so far and uses heuristics (specifically, critical-path heuristics like $h_{max}$ and $h_{\mathcal{C}, \mathcal{L}}$) to identify states from which no "new" solvable goal subsets can be reached. This pruning significantly reduces the search space.
Additionally, the paper extends the framework to handle Linear Temporal Logic (LTLf) properties. This involves:
- Compiling LTLf formulas into property automata (NFAs).
- Integrating these automata into the planning task, effectively transforming LTLf properties into goal facts that the MUGS algorithms can process. This compilation is done in a way that allows for continued search even if an automaton doesn't reach an accepting state, which is crucial for soft goals.
Datasets
The evaluation uses benchmarks from the International Planning Competition (IPC) and extensions thereof. Specifically:
- IPC benchmarks modified with plan-cost bounds: These are standard planning problems where a cost limit is imposed, making them relevant to oversubscription planning.
- Benchmarks extended with action-set (AS) properties: These are domains where preferences are expressed using Eifler et al.'s original AS property formalism.
- Newly generated instances for LTLf evaluation: The authors created larger instances by increasing the number of objects and hard goals to test the scaling behavior of LTLf properties with respect to the number of properties analyzed. These instances included both AS properties and LTLf properties not expressible as AS properties.
Key Insights and Ideas
- Symbolic search is a powerful tool for MUGS: By representing the entire reachable state space with BDDs, the problem of checking solvability for numerous goal subsets becomes dramatically more efficient. This is a significant departure from Eifler et al.'s meta-search approach.
- Heuristic-guided pruning is effective for explicit search: The paper demonstrates how to adapt sophisticated heuristics to prune states that cannot lead to novel solutions, making explicit search viable for MUGS computation.
- LTLf compilation is surprisingly efficient: Extending the framework to LTLf, a much more expressive language, incurs minimal computational overhead compared to using AS properties when the LTLf properties could be expressed as AS properties. This suggests that the LTLf compilation machinery is well-integrated.
- LTLf properties introduce scaling challenges, but remain feasible: While scaling to a large number of LTLf properties is harder than with AS properties, the framework remains effective for a moderate number of temporal properties, making it applicable to more realistic scenarios.
- New algorithms significantly outperform previous ones: The proposed algorithms (both symbolic and explicit search) show dramatic improvements in coverage and speed over Eifler et al.'s original methods.
Key Results
- Dramatic performance improvements: The new algorithms (symbolic and explicit search with $h_{max}$) significantly outperform Eifler et al.'s methods on MUGS computation. For IPC benchmarks with cost bounds, coverage increased by 163% (for $x=0.25$) and 165% (for $x=0.75$) for the explicit search method.
- Complementary strengths: The symbolic and explicit search methods show complementary strengths across different domains, suggesting a hybrid approach could be even more powerful.
- Competitive results for cardinality-optimal OSP: As a side effect, the algorithms can find cardinality-optimal plans (maximizing the number of satisfied soft goals), outperforming the state-of-the-art OSP solver [Katz et al., 2019].
- LTLf extension is practical: When evaluating LTLf properties, the overhead compared to AS properties is minimal. Scaling to up to 4-5 LTLf properties is feasible, with performance degrading gracefully as the number of properties increases.
Limitations and Future Work
- Scaling with LTLf properties: While feasible for a moderate number of LTLf properties, scaling to a very large number remains a challenge. The paper notes that the worst-case number of MUGS is exponential in the number of properties.
- Future Directions:
- Temporal Planning: Extending the framework to handle temporal planning problems.
- Deeper Explanations: Answering "why" questions about the entailment itself, not just the dependency.
- Automatic Property Identification: Developing methods to automatically identify relevant plan properties for a given task or user.
- Case Studies: Applying the framework to real-world applications.
Summary updated