When a schedule with uncertain task durations becomes impossible to execute, a good repair system does more than report failure. It finds the small set of timing requirements that clash and proposes the cheapest loosening that makes the plan work again. When a human operator rejects one of these proposals, the best existing system records the rejection as a permanent "never offer this again" rule, called a nogood, and searches for something else. That works if the operator's priorities stay fixed. Over a long mission they rarely do. A deadline extension the operator refused at hour one may be exactly what they want at hour five. A system that keeps every past rejection will quietly rule out the repairs the operator now prefers. A system that forgets everything will keep re-proposing physically impossible fixes and lose the structure it has already learned.
We propose a repair loop for temporal plans under uncertainty in which each learned rule carries a record of why it exists. Rules that come from the physics of the plan, such as a negative cycle in the network of timing constraints, are never retracted. Rules that come from an operator rejection are tied to the specific preference comparison the rejection revealed. They are retracted only when that comparison is no longer believed to hold. The same preference belief then decides which constraint in a conflict to loosen, replacing the random choice used by current incremental checkers. The claim is narrow and testable. Under preference drift, retracting rules according to what they depend on should beat keeping them forever, wiping them, and decaying them uniformly over time, while staying fast enough for online repair.
Background and the gap
Three bodies of work supply the pieces. The first is conflict extraction for temporal networks. A Simple Temporal Network with Uncertainty (STNU) is a graph of events linked by timing bounds, some of whose durations are chosen by nature rather than by the scheduler. It is dynamically controllable if some execution strategy that reacts to observed durations always meets every bound. Faster Conflict Generation for Dynamic Controllability extracts the clashing constraints of an uncontrollable STNU in $O(n^3)$. Its incremental checker, RELAXIDC, reuses dependency structure across successive relaxations and runs 2.33 times faster on average over 15 relaxation steps. The authors also state that it picks which edge of the conflict to relax at random. We reuse their incremental checker and replace that random choice. Dynamic Control of Probabilistic Simple Temporal Networks adds directionality. Its MIN-LOSS DC method trims only the tail of a duration distribution that actually takes part in the conflict, which doubles execution success over symmetric trimming on the DREAM benchmark. We adopt directional trimming as one of the available relaxation moves. Both papers assume the deadlines and the costs of relaxing them are fixed. They supply our method, and they also mark the place where it departs: they never ask what the operator wants.
The second body of work is the closest prior system. Resolving Over-Constrained Probabilistic Temporal Problems through Chance Constraint Relaxation introduces Conflict-Directed Chance-constraint Relaxation (CDCR). CDCR trades deadline extensions against accepted risk and lets an operator reject proposals, adding each rejection as a monotonic nogood. Our proposal differs in three ways. Its nogoods can be retracted. It runs in the online execution loop rather than as an offline advisor. It avoids the general nonlinear solve that consumes up to 90% of CDCR's runtime under Gaussian durations, by restricting relaxations to a discrete menu of deadline extensions and directional tail trims.
The third body of work shows that preference drift is real and that naive handling fails. Right Now, Wrong Then discounts old preference data exponentially. It keeps reward accuracy above 60–70% after preferences flip, where stationary training falls to about 50–55%. The authors concede two limits: the right discount depends on an unknown drift budget, and the discount treats invariant facts and transient preferences the same way. Dynamic Adaptation to Preference Drift in Interactive Evolutionary Multi-Objective Optimization shows that wiping all history on drift makes search erratic. Its alternative, a detection-triggered reset, works better, but it relies on randomized evolutionary exploration and has no structural diagnosis. AcCoRD motivates the interactive side. Frontier language-model agents score as low as 0.09 on "triggered" preferences, which appear only after options are shown, and they fail to recognize unachievable constraint sets. These papers motivate the work and constrain its design: uniform decay and full reset are the designs to beat, not to reuse. Sarkar et al. further supports the premise that operators discover their preferences by reacting to proposals.
We deliberately do not build on the learned job-shop dispatchers (Residual Scheduling, MP-ASIL). They solve static deterministic problems, which their own authors acknowledge, and they produce no conflict explanations to attach preferences to.
Core Claim
Each relaxation move $m$ touches a constraint with a feature vector $\phi(m)$, for example which vehicle, which deadline, and whether the move extends time or accepts risk. The operator is modeled as having a utility weight vector $w_t$ that can change at unknown times. When the operator rejects move $m$ in favor of a move $m'$ they accept, or of continuing to wait, the system does not store "never $m$". It stores the comparison $w_t^\top(\phi(m') - \phi(m)) > 0$ together with the nogood it justifies. A Bayesian change-point posterior over $w_t$ is updated from every accept or reject. Each preference nogood $g$ remains active only while
$$ P\big(w_t^\top(\phi(m'_g) - \phi(m_g)) > 0 \mid \text{interactions up to } t\big) \ge \tau, $$
where $m_g$ and $m'_g$ are the rejected and preferred moves behind $g$ and $\tau$ is a retention threshold. Structural nogoods from negative cycles carry no such condition and are permanent. Retraction is therefore local. A shift in how much the operator cares about vehicle A's deadline revives only the nogoods whose comparisons involve that deadline. The remaining memory of what has already been explored is kept.
Within a conflict, the move proposed next is the one with the lowest expected utility loss under the current posterior, among moves not blocked by active nogoods. The checking of candidate moves is done incrementally with RELAXIDC.
The claim we will test is this. In drifting-operator settings, dependency-directed retraction reduces the number of proposals before acceptance and the regret against the operator's current true utility, compared with monotonic, wiped, and time-decayed memories. Structural nogoods prevent the infeasible re-proposals that a full wipe produces.
Research Program
We will build the system in three layers. The bottom layer is the existing machinery. It combines conflict extraction and incremental checking from Bhargava et al. with directional tail trimming from Gao et al., wrapped so that every candidate move is checked for restored controllability before it is ever shown to the operator.
The middle layer is the nogood store, with provenance tags and the retention test above. The preference posterior uses a linear utility with a Gaussian prior and a hazard-rate change-point model, as in Bayesian online change detection. Its main hyperparameter is the hazard rate. This hazard rate plays the role of NS-DPO's discount, and we will measure how sensitive results are to it, since sensitivity to that setting is exactly the weakness NS-DPO's authors report.
The top layer is the execution loop. Events are dispatched, durations are observed, and when controllability is lost the system extracts a conflict, proposes a move, and logs the operator's response.
No existing benchmark contains drifting operators, so we will build simulated operators on top of existing instances. A hidden weight vector drifts according to one of three schedules. Under sudden drift, the weights flip at a random time. Under gradual drift, they follow a random walk. Under triggered drift, the operator acquires a new concern only after a move touching that constraint is first proposed, mirroring AcCoRD's category. The simulated operator accepts a proposal when its current utility exceeds a reservation level, with logistic response noise.
The analysis component is a characterization of failure modes. We will count stale prunes, which are nogoods blocking the move the operator would currently prefer, and infeasible re-proposals, which are moves already known to be structurally useless. We will show which memory policy produces which failure.
Baselines
The naive reference point is a monotonic memory. Every rejection is a permanent nogood, as in CDCR Yu et al., and the next move is the cheapest one by a fixed cost. It runs on the same move menu and the same incremental checker. It should be optimal when there is no drift and degrade as drift grows. Matching it under no drift is a requirement for our method, not a success.
The full reset baseline clears all preference nogoods whenever any rejection contradicts the current model, which is the "fixed" reset of the iEMOA study. A second variant also clears structural nogoods, isolating the value of keeping them.
The uniform time decay baseline weights each nogood by $\gamma^{T-t}$ in the style of NS-DPO and drops it below a threshold. The discount $\gamma$ is tuned on held-out drift schedules with the same tuning budget we give our hazard rate.
The strongest competitor, and the key ablation, is tagged decay. It is uniform decay that exempts structural nogoods. It already captures the obvious fix of "don't forget the physics." Our proposal claims value beyond this baseline only through localized, evidence-triggered retraction.
On the relaxation-choice side, we compare random edge selection as in RELAXIDC against MIN-LOSS DC's probability-mass-loss criterion with no preference model. The second is the strongest existing method on the success-rate axis.
The strongest reported number available is MIN-LOSS DC's execution success rate of 0.46 on DREAM, against 0.22 for the SREA baseline, with 43ms runtime Gao et al.. CDCR solved 1,640 uniform-duration and 453 normal-duration cases within 30 seconds on its underwater simulator. We found no reported result on Lacuna for any method on these benchmarks with a drifting operator.
Beating the baselines would mean four things. First, success rate within noise of 0.46 on DREAM, since preference guidance must not cost controllability. Second, a statistically significant reduction in proposals-to-acceptance and in cumulative regret relative to tagged decay under sudden and triggered drift. Third, no loss relative to monotonic memory under zero drift. Fourth, per-repair latency that stays in the tens to hundreds of milliseconds.
Why not just…?
Why not just re-solve from scratch whenever the operator objects? Re-solving discards both the incremental checking state, which Bhargava et al. show is worth a 2.33× speedup over repeated relaxations, and the record of which repairs are structurally hopeless. The iEMOA study reports that wiping history makes search erratic. Our "full reset including structural nogoods" baseline is exactly this policy. If it matches our method on proposals-to-acceptance and latency, the provenance machinery is unnecessary, and we will report that.
Why not just decay old rejections over time and exempt the physical conflicts? This is the real threat, and it is why tagged decay is the central ablation rather than a straw man. Under steady gradual drift with a well-tuned $\gamma$, it may perform as well as our method. The predicted advantage of retraction is specific. It should appear under sudden and triggered drift, where only one or two preference dimensions change and uniform decay either forgets unchanged rejections too early or holds changed ones too long. It should also appear under mis-tuned discounts, which is NS-DPO's admitted weakness. We will sweep drift locality, defined as the fraction of weight dimensions that change, and report the crossover point. If no crossover exists, the claim fails.
Why not just let a language-model agent negotiate with the operator? AcCoRD finds that frontier agents reach perfect outcomes less than 30% of the time and fail to recognize unachievable constraint sets, which here means uncontrollable networks. Even so, a language model could serve as the dialogue front end that turns operator responses into comparisons. That is complementary to our method rather than a replacement, and we leave it out of scope.
Why not just use preference-blind MIN-LOSS DC? It maximizes the probability of successful execution, not the operator's acceptance. When those objectives align, it should be hard to beat. Our experiments report both axes so that any trade-off is visible rather than hidden.
Proposed Experiments
The primary testbed is DREAM: 540 instances with 21 events, where the reported 0.46 success rate anchors controllability. Transfer is tested on CAR-SHARING, which has 169 instances from real data, and on the AUV navigation STNUs used by Bhargava et al.. Each instance is paired with 20 simulated-operator seeds per drift schedule, and with a zero-drift control. Metrics are execution success rate, cumulative regret under the operator's current hidden utility, proposals until acceptance, counts of stale prunes and infeasible re-proposals, and per-repair wall-clock time.
The first decisive check is the zero-drift control. Our method must tie monotonic memory there, or the posterior is retracting rules it should keep. The second is the drift-locality sweep against tagged decay, which tests whether localized retraction adds anything beyond the obvious fix. The third is hazard-rate versus $\gamma$ sensitivity: our method should degrade more gracefully when its single hyperparameter is mis-set by a factor of four. The fourth is a misspecification test, in which the simulated operator uses a nonlinear utility the linear model cannot represent. This tells us whether retraction decisions remain useful when the preference model is wrong, which is the condition any real deployment will face.
References
- Faster Conflict Generation for Dynamic Controllability
- Dynamic Control of Probabilistic Simple Temporal Networks
- Resolving Over-Constrained Probabilistic Temporal Problems through Chance Constraint Relaxation
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- Dynamic Adaptation to Preference Drift in Interactive Evolutionary Multi-Objective Optimization
- AcCoRD: Evaluating User-Agent Collaboration Under Realistic User Preference Dynamics
- Evaluating Rule-based Programming and ReinforcementLearning for Personalising an Intelligent System
- Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem
- Towards Generalizable Multi-Policy Optimization with Self-Evolution for Job Scheduling