An Efficient Incremental Simple Temporal Network Data Structure for Temporal Planning
This work addresses the need for incremental computation reuse in temporal planning, offering a domain-specific improvement for planning systems.
The paper tackles the problem of efficiently managing simple temporal networks (STNs) in temporal planning by proposing an incremental data structure called \deltastn, which is shown to be superior in time and memory efficiency compared to state-of-the-art approaches on temporal planning sequences.
One popular technique to solve temporal planning problems consists in decoupling the causal decisions, demanding them to heuristic search, from temporal decisions, demanding them to a simple temporal network (STN) solver. In this architecture, one needs to check the consistency of a series of STNs that are related one another, therefore having methods to incrementally re-use previous computations and that avoid expensive memory duplication is of paramount importance. In this paper, we describe in detail how STNs are used in temporal planning, we identify a clear interface to support this use-case and we present an efficient data-structure implementing this interface that is both time- and memory-efficient. We show that our data structure, called \deltastn, is superior to other state-of-the-art approaches on temporal planning sequences of problems.