Resolving Over-Constrained Probabilistic Temporal Problems through Chance Constraint Relaxation

Peng Yu, Cheng Fang, Brian Charles WilliamsAAAI 2015 · DOI

Abstract

This paper introduces Conflict-Directed Chance-constraint Relaxation (CDCR), an algorithm designed to assist human operators in salvaging "impossible" schedules. By identifying specific logical conflicts in over-constrained probabilistic problems, CDCR suggests optimal trade-offs between extending mission deadlines and accepting slightly higher levels of risk.

Introduction

In high-stakes environments like deep-sea exploration, scheduling is a complex challenge defined by uncertainty. Underwater robots must navigate unpredictable currents, varying transit times, and hardware limitations. Traditional scheduling models often fail in these scenarios because they are "over-constrained"—the user’s requirements (e.g., "finish in 3 hours") and risk tolerance (e.g., "less than 5% chance of failure") are mathematically incompatible.

Example of a Chance-Constrained Probabilistic Simple Temporal Problem (cc-pSTP) for an underwater mission.

When a plan is impossible, human operators struggle to pinpoint the exact cause or determine how to fix it without compromising safety. CDCR acts as a decision aid that diagnoses the source of the risk and proposes minimal relaxations to make the plan feasible again.

Methodology

The CDCR algorithm operates on a Chance-Constrained Probabilistic Simple Temporal Problem (cc-pSTP) through several key phases:

  1. Grounding and Risk Allocation: The algorithm converts probabilistic durations (e.g., travel time following a Gaussian curve) into deterministic time windows by allocating a portion of the total allowed risk to each task. This transforms the probabilistic problem into a Simple Temporal Network with Uncertainty (STNU).
  2. Conflict-Directed Search: Rather than using brute-force search, CDCR employs "conflict learning." It checks the STNU for controllability—determining if a strategy exists to handle all outcomes. If a failure is detected, it extracts a "conflict," which is a specific set of logically incompatible constraints.
  3. Iterative Relaxation: Once a conflict is identified, the algorithm uses a non-linear optimizer (IPOPT) to find the most cost-effective resolution. This may involve relaxing a temporal constraint (adding time to a task) or relaxing the chance constraint (slightly increasing the allowed risk).
  4. Human-in-the-Loop Integration: The system functions as a mission advisor. If a human operator rejects a proposed resolution, that rejection is treated as a new constraint, and the algorithm searches for the next best alternative.

Evaluation and Results

The researchers evaluated CDCR using a mission simulator for underwater expeditions, testing 2,000 randomly generated scenarios with varying risk bounds and mission lengths. The algorithm was tested against both Normal (Gaussian) and Uniform probability distributions for task durations.

Runtime performance comparison between Normal and Uniform probability distributions as constraint complexity increases.

Key Findings

  • Efficiency: For problems with fewer than 100 constraints, CDCR typically found a resolution in under 30 seconds, making it viable for real-time mission planning.
  • Success Rates: The algorithm solved 1,640 cases with uniform distributions and 453 cases with normal distributions within the 30-second timeout.
  • Computational Bottlenecks: In tests involving normal distributions, solving the non-linear optimization for conflict resolution accounted for up to 90% of the total computation time. This highlights that while Normal distributions are more realistic for modeling natural phenomena, they significantly increase mathematical complexity.

Discussion and Future Work

The core innovation of this work is treating risk as a negotiable resource rather than a static limit. By leveraging STNU controllability checking, the algorithm can provide scientists with precise diagnoses of which tasks are causing scheduling conflicts.

However, limitations remain regarding scalability. Performance degrades as the number of constraints grows, particularly with non-linear probability distributions. Future research will focus on more efficient ways to handle non-linear chance constraints and exploring sophisticated methods for combining dependent risks beyond the conservative "union bound" approach.

Summary updated

BibTeX
@inproceedings{yu2015resolving,
  author = {Peng Yu and Cheng Fang and Brian Charles Williams},
  title = {{Resolving Over-Constrained Probabilistic Temporal Problems through Chance Constraint Relaxation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9652},
}
Figure