Abstract
Constraint Acquisition (CA) is a vital technique for automating the modeling of complex scheduling and planning problems. However, qualitative constraints—which describe temporal and spatial relationships—often present a "modeling bottleneck" due to their disjunctive nature and the resulting combinatorial explosion in learning algorithms. This paper introduces GEQCA (Generic Qualitative Constraint Acquisition), a framework that leverages the mathematical properties of qualitative calculus and background knowledge to significantly reduce the query burden on human users. Experimental results demonstrate that GEQCA outperforms existing state-of-the-art methods, particularly in sparse real-world scenarios.
Introduction: The Modeling Bottleneck
Constraint Programming is a powerful tool for solving industrial scheduling problems, yet it requires experts to translate requirements into formal logic. Constraint Acquisition aims to democratize this process by allowing non-experts to "teach" the system through interaction. A significant challenge arises with qualitative constraints, such as "Task A happens during Task B" or "Region X overlaps Region Y." These relationships are often "fuzzy" and disjunctive, making them difficult for standard learning algorithms to acquire efficiently without overwhelming the user with questions.
Qualitative Constraints and Allen's Algebra
Qualitative reasoning typically relies on algebras like Allen’s Interval Algebra, which defines a set of Jointly Exhaustive and Pairwise Disjoint (JEPD) relations between intervals.
Because these relations are JEPD, exactly one basic relation must hold between any two entities. GEQCA exploits this property: ruling out one relation (a "no" answer from the user) immediately narrows the search space for others.
The GEQCA Framework
The authors introduce several innovations to make qualitative acquisition practical:
- Qualitative Queries: The system asks simple questions about the relationship between two specific entities rather than complex complete schedules.
- Time-Bounded Path Consistency (PC): GEQCA uses a consistency-checking mechanism to automatically deduce constraints. A
cutoffparameter ensures the system remains responsive, preventing long "thinking" pauses that would frustrate a human user. - PATH Heuristic: This novel strategy selects the next pair of entities to query by traversing the problem graph to maximize the "ripple effect" of each answer, accelerating convergence.
- Background Knowledge ($K$): The system can incorporate pre-existing information, such as task durations, to prune the search space before the first question is even asked.
Experimental Evaluation and Results
GEQCA was evaluated against the previous state-of-the-art method, LQCN, using both synthetic temporal instances and real-world Resource Constrained Project Scheduling Problems (RCPSP).
The results highlight GEQCA's efficiency. On sparse problems (typical of real-world scheduling), GEQCA reaches high filtering levels with significantly fewer calls to the user. For instance, on the Ins_25_8 benchmark, GEQCA achieves over 80% filtering in approximately 35 queries, whereas LQCN requires over 200 queries to reach half that filtering level. On larger problems with 100 intervals, GEQCA saved users from answering over 22,500 unnecessary queries—a 35% reduction in effort.
Conclusion and Future Work
GEQCA represents a significant step forward in making qualitative constraint acquisition feasible for real-world applications. By combining formal qualitative reasoning with efficient heuristics and background knowledge, it bridges the gap between complex modeling and human intuition. Future work will focus on improving performance in dense problem instances and extending the framework to hybrid networks that combine both spatial and temporal constraints in a single learning session.
Summary updated