Towards a Dynamic Algorithm for the Simple Temporal Problem

Towards a Dynamic Algorithm for the Simple Temporal Problem

Ten Thije, J.O.A.

De Weerdt, M.M. (mentor)
Planken, L.R. (mentor)

Electrical Engineering, Mathematics and Computer Science

Software Technology

2011-08-23

Efficient management and propagation of temporal constraints is important for temporal planning as well as for scheduling. During plan development, many solvers employ a heuristic-driven backtracking approach, over the course of which they maintain a so-called Simple Temporal Network (STN) of events and constraints. Recent research has shown that partial path consistency (PPC) can be used to efficiently propagate temporal information in such networks. This insight was applied in the IPPC algorithm, which enforces PPC in an incremental fashion when new constraints are introduced. We present two new algorithms that efficiently enforce PPC in modified STNs. Vertex-IPPC allows the incremental introduction of an event and all its associated constraints at once. Conversely, Support-DPPC allows the removal or loosening of existing constraints. To the best of our knowledge, this is the first decremental algorithm for enforcing PPC. Our ultimate goal is a fully dynamic algorithm for PPC, supporting on-line deletions as well as additions. This will allow solvers to efficiently explore the solution space, rather than solving entire networks after each update.

Constraint Satisfaction
Simple Temporal Problem
Scheduling

http://resolver.tudelft.nl/uuid:bb91b0cf-9ce5-4470-a326-b61885d34988

Student theses

master thesis

(c) 2011 Ten Thije, J.O.A.