New arc-consistency algorithm improves temporal constraint problem solving

Temporal Constraint Satisfaction Problems (TCSPs) have long challenged computer scientists seeking efficient ways to model time-dependent relationships in scheduling and planning. A new research paper introduces a refinement to how these problems are processed, potentially speeding up solution discovery across multiple applications.

The Problem with Unary Constraints#

TCSPs typically work by converting complex unary constraints into binary ones through the addition of an "origin of the world" reference variable. This transformation helps simplify the problem structure, but the resulting binary constraints haven't been fully optimized for existing consistency-checking algorithms. The gap lies in how researchers treat the constraints linking this origin variable to all other variables in the system.

A Fresh Approach to Consistency Checking#

The researchers propose binarized-domains Arc-Consistency (bdArc-Consistency), a new framework that reinterprets these special constraints as domain restrictions rather than traditional binary constraints. They present bdAC-3, an adapted version of Mackworth's classic AC-3 arc-consistency algorithm, designed specifically for this binarized-domain perspective.

The key insight: when a Simple Temporal Problem (STP)—a special case of TCSPs—satisfies bdArc-Consistency and maintains connectivity across all variables, its binarized domains reach a minimal state, meaning no further simplification is possible without losing valid solutions.

Practical Implementation and Testing#

Beyond the theoretical contribution, the work delivers two polynomial-time procedures that can extract solutions without backtracking once an STP meets these consistency criteria. The researchers demonstrate how these techniques integrate into broader TCSP solvers and job shop scheduling systems.

Experimental comparisons pit bdAC-3 against the existing ACSTP algorithm on standard test cases, while also evaluating different scheduling approaches. The team has released SWI-Prolog source code implementing these comparisons, and they provide an incremental version of bdAC-3 for systems requiring dynamic updates.

Why It Matters#

This work addresses a longstanding inefficiency in constraint programming: better filtering procedures during search reduce the number of dead-end branches explored. By tightening constraints earlier, solvers can spend less time on impossible configurations and more time finding actual solutions—a practical gain for fields ranging from AI planning to industrial scheduling.