TL;DR
This paper introduces a novel framework for "sketch completion" in AI planning, allowing users to provide partial plan outlines (sketches) that the system then intelligently completes into full, executable plans. This approach bridges the gap between fully automated planning and user control, enabling more intuitive and collaborative plan generation.
What Problem Does This Paper Address?
Traditional AI planning systems typically require users to specify high-level goals, and the system then generates a complete plan from scratch. While effective, this approach offers little room for user influence beyond the initial goal definition. Users often want to guide the planning process, perhaps by sketching out a rough itinerary or a sequence of key actions, and then have the AI fill in the details. This is particularly relevant in domains like trip planning or military strategy, where user preferences and biases are crucial. The challenge is to interpret these user-provided "plan sketches," which can be incomplete, span multiple levels of abstraction, and contain underspecified tasks, and transform them into valid, compliant, and complete plans.
Methods
The paper proposes a two-phase approach for sketch completion:
- Interpretation Phase (Abductive Plan Recognition): This phase takes a user-supplied plan sketch (defined as a set of ground and non-ground tasks, called "anchors") and uses "abductive chains" to infer candidate high-level goals that the user might intend. An abductive chain represents a possible path from an anchor task to a goal through a sequence of operator schemas. The system identifies candidate goals by looking at the terminal nodes of these chains.
- Refinement Phase (Sketch-Compliant Task Refinement): Once candidate goals are identified, the system generates "plan skeletons." These skeletons encode the relationships between goals and anchors, essentially representing possible ways to achieve the intended goals while respecting the sketch. The core of this phase is a modified Hierarchical Task Network (HTN) planning process. Instead of purely top-down refinement, the system uses the plan skeletons to guide operator selection and ensure that the generated plan remains "compliant" with the original sketch. Compliance means that the sketch's elements are represented in the final plan.
Datasets
Not discussed in the paper. The paper uses a sample domain for illustration and mentions testing on a crisis action planning domain.
Key Insights and Ideas
- Plan Sketches as User Input: The core idea is to treat user-provided partial plans (sketches) as valuable input, not just high-level goals. This shifts the paradigm towards more interactive planning.
- Abductive Chains for Goal Inference: Using abductive chains to infer intended goals from sketch anchors is a clever way to bridge the gap between underspecified user input and concrete planning objectives.
- Plan Skeletons for Constraint Propagation: Plan skeletons act as a crucial intermediate representation, capturing the constraints imposed by the sketch and guiding the refinement process to ensure compliance.
- Sketch Compliance: The formal definition of "compliance" ensures that the generated plan respects the user's initial sketch, providing a measurable criterion for success.
- Balancing Automation and Control: The framework aims to provide a flexible middle ground, allowing users to exert significant influence without needing to specify every detail.
Key Results
The paper describes a prototype system implemented on top of the SIPE-2 planner. They tested it on a crisis action planning domain with 45 operator schemas and 7 abstraction levels.
- Computational Viability: The system successfully generated fully realized plans that incorporated sketch recommendations.
- Efficiency: For a specific test case where the sketch was designed to yield the same plan as an unassisted planner, the sketch completion process added only about 1% to the overall plan generation time. This suggests that the overhead of interpretation and skeleton generation is manageable.
- Qualitative Success: The system was able to handle sketches with tasks at mid-range abstraction levels and produce plans with hundreds of nodes.
Limitations and Future Work
- Goal Selection Bias: The paper acknowledges that identifying the intended goals from a set of candidate goals is a significant challenge. While they propose the concept of "IntendedGoals" functions, they don't commit to a specific bias (e.g., goal minimization, referentiality). Future work could explore various bias mechanisms.
- Exponential Bounds: The analysis mentions potential exponential bounds in the number of abductive chains and plan skeletons, though they argue practical performance is often better.
- User Interaction: While the system accepts sketches, the paper mentions interactive editing tools as a future direction. Further research could explore more sophisticated ways for users to interact with and refine the planning process.
- Generalization: While tested on a crisis action domain, further evaluation across a wider range of domains would be beneficial.
Summary updated