Introduction
Planning daily activities often involves balancing multiple constraints. For instance, a user might want to leave the office at 6:00 PM, have dinner at a specific Chinese restaurant, and catch a 7:30 PM movie. However, if the travel time and dining duration exceed the available window, the plan becomes "over-constrained." Traditional AI planning assistants typically address this by relaxing temporal constraints—suggesting the user eat faster or arrive late. This paper argues that such solutions are often undesirable or impossible (e.g., missing a flight). Instead, the authors propose Conflict-Directed Semantic Relaxation (CDSR), which allows the system to suggest semantically similar alternatives, such as switching to a closer restaurant of a different cuisine, to maintain a feasible schedule.
Conflict-Directed Semantic Relaxation (CDSR)
The CDSR algorithm extends the Controllable Conditional Temporal Problem (CCTP) framework. When a conflict is detected—such as the total duration of activities exceeding the time budget—the algorithm identifies the specific variables causing the bottleneck. Rather than just adjusting the start or end times, CDSR considers "weakening" the semantic requirements of the tasks.
A key innovation is the introduction of the SomethingElse (SthElse) variable. When the planner cannot find a valid schedule with the user's initial choices, it triggers this variable to explore the domain of semantically similar alternatives. This process is visualized in the search tree, where a conflict in the primary plan leads the algorithm to branch into alternative destination types.
Technical Implementation
The system bridges hard temporal logic with soft semantic similarity through several key components:
- Semantic Constraints via SPARQL: Tasks are defined not just by labels but by SPARQL queries that capture their underlying meaning. For example, a "Chinese Restaurant" is defined by its cuisine type in a knowledge base.
- Domain Relaxation: When a conflict occurs, the system can relax these SPARQL filters. For instance, if no Chinese restaurant fits the schedule, the system might relax the "Chinese" constraint to "Korean" if it finds a closer Korean restaurant that satisfies the temporal bounds.
- Word2Vec for Similarity: To ensure alternatives remain relevant, the system uses Word2Vec embeddings (trained on Google News) to calculate the cosine similarity between concepts. This prevents the AI from suggesting nonsensical swaps.
- Delayed Expansion: Querying large knowledge bases like Freebase is expensive. To maintain efficiency, the algorithm only performs semantic expansion after a candidate plan is dequeued for evaluation, a technique known as delayed expansion.
Evaluation and Results
The authors evaluated CDSR using six urban trip-planning scenarios involving nine participants. The system was tested across 54 sessions, where it successfully found feasible solutions in 52 cases. Notably, in 11 of these sessions, a traditional temporal-only planner would have failed entirely. By suggesting domain relaxations (e.g., changing the restaurant), CDSR preserved the overall structure of the user's evening.
User feedback indicated that while the system was highly flexible, the quality of alternatives was rated between 2 and 3 on a 5-point scale. This suggests that while Word2Vec captures general semantic similarity, it may not fully account for specific human preferences or the nuances of "substitutability" in dining and entertainment.
Conclusion and Future Work
CDSR demonstrates that treating the "what" and "where" of a plan as relaxable dimensions—much like "when"—significantly increases the robustness of automated assistants. Future work will focus on personalizing the similarity model to better reflect individual tastes and moving toward multi-objective optimization to better balance the trade-offs between time, cost, and semantic similarity.
Summary updated