Qualitative timeline-based planning models domains as sets of independent, but interacting, components whose behaviors over time, the timelines, are governed by sets of qualitative temporal constraints (ordering relations), called synchronization rules. Its plan-existence problem has been shown to be PSPACE-complete; in particular, PSPACE-membership has been proved via reduction to the nonemptiness problem for nondeterministic finite automata. However, nondeterministic automata cannot be directly used to synthesize planning strategies as a costly determinization step is needed. In this paper, we identify a fragment of qualitative timeline-based planning whose plan-existence problem can be directly mapped into the nonemptiness problem of deterministic finite automata, which can then synthesize strategies. In addition, we identify a maximal subset of Allen's relations that fits into such a deterministic fragment.
Figures & tables
Figure 1. A (partial) plan satisfying the rule from Equation ( 1 ), which is eager, and the one from Equation ( 2 ), which is not. The token starting at time 1 triggers both rules. In both cases, the satisfaction of the rule is witnessed by the second token of value v1 in the relevant timeline (not the first one). However, a DFA that behaves eagerly can be instructed to identify the witnessing token for the eager rule, but not for the non-eager one. Note that the token for x1 starting at time 3 has value v2=v1 ; thus, it does not match token name a1 , and cannot be used to fulfill the rule from Equation ( 1 ).
Figure 2. Graphical representation of sets Wn , with n∈N . Wn includes words λ=σ0σ1…σh , for all even positive natural numbers h , encoding plans over SVn and such that: the timeline associated with variable x0 features h/2v0 -valued tokens and a final v0 -valued token; timelines associated with variables other than x0 feature an initial vj -valued token, followed by h/2 tokens labeled with either vj or vj , for j∈[n]>0 .
Figure 3. The picture shows two DAGs on the left-hand side. The one on the top is associated with (the existential statement of) the rule a0[x0=v0]→∃a1[x1=v1].(\tokstart(a0)≤\tokstart(a1)∧\tokstart(a1)≤\tokstart(a0)∧\tokend(a0)≤\tokend(a1)) . It forces token a0 to either be a prefix of or coincide with token a1 . The one on the bottom is associated with the existential statement obtained replacing \tokend(a0)≤\tokend(a1) with \tokend(a0)<\tokend(a1) , that forces a0 to be a (strict) prefix of a1 . The labeling function is the same for both DAGs, and it is shown on the right-hand side.
Figure 4. The automaton AP for the non-strict rule whose DAG is depicted in Figure 3 (non-strict), with four non-sink states.
Figure 5. The automaton AP for the strict rule whose DAG is depicted in Figure 3 (strict), with six non-sink states.
Figure 6. Emergency Department BPMN Process Diagram
Figure 7. SESE Block Decomposition Tree for Emergency Department Process
Figure 8. Timeline execution for the non-critical path in the Emergency Department BPMN process with two iterations of the monitoring loop. The diagram shows the execution flow when the XOR decision selects the low branch (non-critical patient). The monitoring loop ( b9 ) executes twice with consecutive monitoring task iterations: first iteration from time 4-7 (length 3), second iteration from time 7-9 (length 2). The loop block covers exactly the concatenation of the two monitoring executions with no gaps, with the patient becoming stable after the second monitoring cycle, allowing progression to discharge planning.
Figure 9. Timeline execution for the critical path in the Emergency Department BPMN process, including all state variables and flow control timelines. The diagram shows both the main block activations and their corresponding flow control variables that enforce sequential execution semantics. Flow variables with subscript “flow” implement the before/after phases for FLOW blocks, while the decision variable for the XOR block tracks branch selection. Tasks T2 (Emergency Tests) and T3 (Emergency Imaging) execute in parallel between time points 2 and 6, synchronized by the parallel block constraint, both completing simultaneously before proceeding to emergency treatment (T4).
We present an approach to unsolvability certification of temporal planning. Our approach is based on encoding the planning problem into a network of timed automata, and then using an efficient model checker on the network followed by a certificate checker to certify the output of the model checker. Our approach prioritises trustworthiness of the certification: we formally verify our implementation of the encoding to timed automata using the theorem prover Isabelle/HOL and we use an existing certificate checker (also formally verified in Isabelle/HOL) to certify the model checking result.
Background: We address the problem of planning when the set of feasible states or actions changes over time. For example, in the problem of path planning among moving obstacles (sometimes known as SIPP), the feasibility of being at a particular location can change as the obstacles move. Or, the action of boarding a particular train is feasible only while it is stopped at the station. This dynamism means that the optimal plan and its duration can change depending on when execution begins. In practice, execution start time is often unknown until planning has completed or another agent gives the go-ahead. However, most prior planning work either ignores dynamism or assumes a known start time. This makes it straightforward to assess state and action feasibility but is impractical for some applications. Objectives: In this paper, we relax the assumption of a known start time. We define the setting of {\em any-start-time planning} and provide algorithms for it. Methods: We present a data structure called a compound arrival time function (cATF) that compactly encodes the optimal plan as a function of start time. We provide general-purpose planning algorithms, based on heuristic graph search, that assemble cATFs by propagating functions along edges instead of scalar costs. Results: We prove that the size of a cATF is at most linear in the problem size. An experimental evaluation of an implementation for the specific problem of SIPP shows that, on difficult problems, agents that rely on replanning often fail, while any-start-time algorithms using cATFs can quickly look up the optimal plan once the execution start time is known. Conclusions: By enabling efficient representations and reasoning for time-dependent plans, this work provides a foundation for planning in dynamic worlds.
Since the introduction of the PDDL+ modeling language, it was known that temporal planning with durative actions (as in PDDL 2.1) could be compiled into PDDL+. However, no practical compilation was presented in the literature ever since. We present a practical compilation from temporal planning with durative actions into PDDL+, fully capturing the semantics and only assuming the non-self-overlapping of actions. Our compilation is polynomial, retains the plan length up to a constant factor and is experimentally shown to be of practical relevance for hard temporal numeric problems.
Andrea Micheli, Enrico Scala, Alessandro Valentini
Fondazione Bruno Kessler, Trento, Italy · University of Brescia, Italy