Conflict Directed Relaxation for Overconstrained Temporal Problems

16 concepts7 papers1 proposal

When a scheduling algorithm or a model checker returns "unsatisfiable," it often feels like a dead end. For a robot planning a mission or a designer verifying a timed system, knowing that a set of requirements is impossible is only half the battle. The more critical question is: why is it impossible, and what is the smallest change needed to fix it?

Research into conflict-directed relaxation moves beyond binary success or failure. Instead, it focuses on identifying the "surgical" adjustments—minimal changes to timing bounds or constraints—that restore feasibility to an overconstrained system.

The Anatomy of a Conflict

The core intuition behind this research is that in a large system of constraints, failure is rarely global. Usually, a specific, small subset of requirements is mutually inconsistent. In the context of temporal problems, Liffiton et al. describe these as Minimal Unsatisfiable Subsets (MUSes).

Think of a MUS as a logical bottleneck. If you have ten tasks to complete but only two of them overlap in a way that exceeds your total time budget, those two tasks form a conflict. By identifying these minimal sets, solvers can provide precise feedback. As Liffiton et al. argue, this provides the "surgical" information needed to fix a schedule rather than simply declaring it impossible.

In the domain of timed automata—mathematical models used to verify real-time systems—Gol et al. introduce a similar concept called the Minimal Sufficient Reduction (MSR). An MSR identifies the smallest set of timing constraints that, if relaxed or removed, would allow a system to reach a desired goal state. By isolating these critical constraints, designers can focus their tuning efforts on the specific parameters that impede system performance.

Surgical Relaxation Over Deletion

In traditional Boolean logic, a constraint is either kept or deleted. Temporal constraints are different: they are often defined by numeric intervals (e.g., "Task A must start between 5 and 10 minutes after Task B"). This numeric nature allows for a more nuanced approach than simple deletion.

The authors of these papers suggest that we can "nudge" constraints rather than removing them. For instance, Gerevini and Cristani demonstrated that strict inequalities (like $x < 5$) can be handled by applying a calculated "perturbation" value to transform them into non-strict constraints ($x \leq 5 - \epsilon$). This mathematical transformation allows solvers to find valid solutions for open intervals without losing precision.

When a conflict is identified, the goal is to find the minimum relaxation value—the smallest $\epsilon$—that resolves the inconsistency. Gol et al. extend this to safety specifications, identifying a "Minimal Guarantee" (MG). This is the smallest set of constraints that must be preserved to ensure safety. By relaxing the thresholds of these specific constraints rather than deleting them, the system remains robust while becoming feasible.

Real-world temporal problems are rarely static; they often involve uncertainty (e.g., how long a robot takes to travel) and risk. This introduces the challenge of dynamic controllability: the ability to adapt a schedule as events unfold.

When a probabilistic schedule is overconstrained, the conflict isn't just a logical contradiction; it's a threat to the probability of success. Yu et al. proposed Conflict-Directed Chance-constraint Relaxation (CDCR) to help operators navigate these trade-offs. Instead of an exhaustive search for a new plan, CDCR identifies the logical bottlenecks and suggests the best balance between extending deadlines and accepting a slightly higher risk of failure.

Building on this, Gao et al. developed algorithms that target only the constraints directly involved in a conflict to restore dynamic controllability. By focusing relaxation efforts on these specific points, the authors ensure that the resulting schedule retains the highest possible likelihood of success.

Why Conflict Direction Works

The efficiency of these methods stems from how they prune the search space. In an overconstrained plan, there are exponentially many ways to relax constraints. However, by generating conflicts early, solvers can ignore irrelevant parts of the problem.

Bhargava et al. show that faster conflict generation is the key to making temporal planning practical. By incrementally identifying the root causes of uncontrollability, their approach directs the search toward a valid relaxation much faster than general-purpose solvers. This shift from "searching for a solution" to "searching for the cause of failure" is what allows these systems to salvage complex, real-world plans that would otherwise be discarded as impossible.

Key Foundational Work

Identifying Conflicts in Overconstrained Temporal Problems (2005) — contributed 2 concept elements to this direction.
On Finding a Solution in Temporal Constraint Satisfaction Problems (1997) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_conflict_directed_search_44880d91,
  title = {conflict-directed search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conflict-directed-search/rdr_44880d91c22c4cf0b1ad1dac1a3aecec},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_conflict_directed_search_44880d91_v1,
  title = {conflict-directed search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conflict-directed-search/rdr_44880d91c22c4cf0b1ad1dac1a3aecec/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake