Incrementally Solving STNs by Enforcing Partial Path Consistency

Planken, L.; de Weerdt, M.; and Yorke-Smith, N. Incrementally Solving STNs by Enforcing Partial Path Consistency. Proceedings of ICAPS'10, Toronto, Canada, May 2010.

Abstract: Efficient management and propagation of temporal constraints is important for temporal planning as well as for scheduling. During plan development, new events and temporal constraints are added and existing constraints may be tightened; the consistency of the whole temporal network is frequently checked; and results of constraint propagation guide further search. Recent work shows that enforcing partial path consistency provides an efficient means of propagating temporal information for the popular Simple Temporal Network (STN). We show that partial path consistency can be enforced incrementally, thus exploiting the similarities of the constraint network between subsequent edge tightenings. We prove that the worst-case time complexity of our algorithm can be bounded both by the number of edges in the chordal graph (which is better than the previous bound of the number of vertices squared), and by the degree of the chordal graph times the number of vertices incident on updated edges. We show that for many sparse graphs, the latter bound is better than that of the previously best-known approaches. In addition, our algorithm requires space only linear in the number of edges of the chordal graph, whereas earlier work uses space quadratic in the number of vertices. Finally, empirical results show that when incrementally solving sparse STNs, stemming from problems such as Hierarchical Task Network planning, our approach outperforms extant algorithms. The Temporal Constraint Satisfaction Problem with Uncertainty (TCSPU) and its disjunctive generalization, the Disjunctive Temporal Problem with Uncertainty (DTPU), are quantitative models for temporal reasoning that account simultaneously for disjunctive constraints and for events not under the control of the executing agent. Such a problem is Weakly Controllable if in each possible scenario the agent can find a decision for that scenario that satisfies all the constraints; further, a problem is Dynamically Controllable if the agent can build a consistent decision online, as the scenario is incrementally revealed. We first consider Weak Controllability. We present two sound and complete algorithms for checkingWeak Controllability of DTPUs. The first algorithm needs to examine only a limited number of scenarios, but operates only on a restricted class of problems. The second algorithm is fully general, but is more expensive in terms of space. We then consider Dynamic Controllability. We present a complete algorithm for testing this property for TCSPUs. Complexity results are presented for all three algorithms.

PDF (865K) | Bibtex entry

©2010 AAAI

Conference homepage