TL;DR
This paper tackles the "why" behind conflicting soft-goals in AI planning. It introduces a novel framework for explaining these conflicts by identifying minimal constraint relaxations that resolve them, offering actionable insights for users to understand and resolve trade-offs.
What Problem Does This Paper Address?
In AI planning, especially for complex tasks like robotic missions, we often deal with "soft-goals" – desirable outcomes that aren't strictly mandatory but improve the plan's quality. Sometimes, achieving multiple soft-goals simultaneously is impossible, leading to conflicts. Previous work identified these conflicts as minimal unsolvable subsets of soft-goals. However, this doesn't explain why these goals conflict. This paper addresses this gap by asking: what underlying constraints are causing these conflicts, and how can we relax them to resolve the conflict? Understanding this is crucial for users to make informed decisions about trade-offs.
Methods
The core of this paper is a framework for explaining soft-goal conflicts through constraint relaxations. They define a "relaxed task" as one where plans from the original task are still valid, but potentially more plans are now possible. They focus on two types of relaxations:
- Resource Constraint Relaxations: Increasing the initial amount of a consumed resource (like battery power).
- Time Constraint Relaxations: Widening time windows for actions (e.g., allowing an upload to happen earlier or later).
They then introduce two algorithms to efficiently compute these explanations:
- Internal Constraint Reuse (ICR): This algorithm iteratively computes explanations for increasingly relaxed tasks, reusing information (like solvable goal subsets) from less relaxed tasks to prune the search space.
- Search Space Reuse (SSR): This algorithm aims to reduce redundant computation by reusing the search frontier from previous relaxations, effectively building upon the exploration of more relaxed tasks.
The algorithms leverage the concept of Maximal Solvable Goal Subsets (MSGS) to efficiently check for solvability and prune the search space.
Datasets
The paper uses the IPC Rovers domain as a running example. For evaluation, they employ a benchmark suite consisting of:
- Resource-centric domains: Blocksworld, NoMystery, Rovers R, and TPP.
- Time-window domains: Parent's Afternoon, Rovers T, and Satellite.
These benchmarks are extensions of existing IPC domains, with relaxations applied to resource limits and time windows.
Key Insights and Ideas
- Explaining the "Why": The paper shifts the focus from what the conflict is (a set of goals) to why it exists (underlying constraint limitations).
- Minimal Relaxations as Explanations: Identifying the smallest change to constraints (e.g., adding 2 units of battery, or shifting a time window by 1 hour) that resolves a conflict provides a concrete and actionable explanation.
- Leveraging Relaxation Order: The concept of a "relaxation order" (a hierarchy of tasks from original to maximally relaxed) is key to efficiently computing explanations.
- Information Propagation is Crucial: Both ICR and SSR demonstrate that propagating information (like solvable goal subsets) across relaxations significantly improves performance compared to a baseline that recomputes everything from scratch.
- Complementary Algorithms: ICR and SSR show different strengths. ICR excels in resource-centric domains due to its stronger pruning, while SSR is more effective in time-constraint domains where relaxations are less impactful.
Key Results
- Theoretical Separation: Both ICR and SSR are theoretically shown to be exponentially faster than a baseline approach that doesn't propagate information. Furthermore, ICR is theoretically exponentially separated from SSR.
- Experimental Performance: Experiments on 7 domains show that ICR and SSR significantly outperform the baseline in terms of coverage (solving more instances).
- ICR shows a clear advantage in resource-constraint domains.
- SSR performs better in time-constraint domains.
- Coverage Improvements: Propagating MSGS (in ICR) improves coverage in 5 out of 7 domains compared to the baseline. SSR also shows improved coverage across multiple domains.
Limitations and Future Work
- Timeout and Memory Limits: Many instances were not solved due to time or memory limits, suggesting that further optimizations or parallelization might be needed, especially for tasks without a strict ordering.
- Automatic Relaxation Identification: The current approach assumes a predefined relaxation order. Future work could focus on automatically identifying the most relevant relaxations for a given conflict and user.
- Broader Application: Evaluating the approach in a real-world application setting is suggested.
- More Complex Relaxations: The paper mentions that reducing action durations is another potential relaxation strategy that was left for future work.
Summary updated