Online Planning in MDPs with Stochastic Durative Actions

1 Introduction

In various applications, the controlled system can perform multiple durative (i.e., non-instantaneous) actions concurrently. Examples include robots with multiple actuators, cooperative multi-agent systems, and smart homes. Often, such systems must respect temporal constraints such as deadlines (the meal should be ready by 5 pm) and time windows (the store is open 10 am to 6 pm), constraining both relative and absolute timing of actions in a successful plan. Classical temporal planning deals with these issues [Long and Fox, 2003; Schoenauer et al., 2006; Vidal and Geffner, 2006; Coles et al., 2010b; Bit-Monnot et al., 2020; Panjkovic and Micheli, 2023], but assumes action effects are deterministic. Yet, in many applications actions can fail in various ways and have potential side effects. Although Markov decision processes (MDPs) capture stochastic actions, they assume that actions are applied sequentially, have instantaneous effects, and typically do not consider temporal constraints. Multi-agent extensions of MDPs allow for (concurrent) joint-actions [Bernstein et al., 2002], but they are instantaneous and synchronized.

The combination of durative actions with stochastic effects forces us to consider interactions between temporal constraints, success probability, and failure modes. Suppose we must select between a short, risky action with a high success probability that leads to a dead-end state if it fails, and a longer, safe action with a low success probability that can be retried if it fails. Without a deadline, an optimal policy would typically reapply the safe action until it succeeds. However, if there is insufficient time to try the safe action enough times, the risky action is better. Finding the optimal policy in this case requires reasoning both over temporal constraints (to understand what the deadline is), and stochastic effects (to understand how likely the risky action is to lead to a dead-end).

Planning with stochastic, durative actions was considered by [Little et al., 2005; Buffet and Aberdeen, 2009; Mausam and Weld, 2008] only in the offline setting, which severely limits scalability and requires an explicit model. Moreover, past algorithms insert actions only in pivot points - points in time in which some action's execution terminates. Hence, they cannot solve problems with required concurrency and complex temporal constraints [Mausam and Weld, 2008].

In this paper, we define CoMDP+, a model that extends MDPs with actions with deterministic durations, concurrency, and temporal constraints. Our main contribution is TP-MCTS (Temporal Planning MCTS), an algorithm that combines Monte Carlo Tree Search (MCTS) [Coulom, 2006; Kocsis and Szepesv´ari, 2006] with classical temporal planning techniques. TP-MCTS is an online algorithm that can schedule actions in arbitrary, non-pivot, time points and, consequently, addresses the issues of scalability and temporal flexibility. It requires only information on action duration and the ability to sample them. To the best of our knowledge, it is the first planning algorithm with these properties.

TP-MCTS makes the following algorithmic contributions: (1) We develop a novel heuristic, called PTRPG (probabilistic temporal relaxed planning graph), which estimates the probability of plan success from a given node, taking temporal information such as deadlines into account. We use it to replace rollouts, which provide poor information about node values in the presence of temporal constraints. (2) We develop a novel backpropagation method for MCTS, which manages information about time intervals instead of scalar values. (3) Combining the above, we develop a novel algorithm for deciding not only which action to execute but also when to dispatch it.

Overall, this paper presents: (A) The first online algorithm for stochastic planning with concurrent durative actions. (B) The first (online or offline) algorithm able to insert actions in non-pivot points, and hence solve problems unsolvable by prior methods. (C) Better scalability than previous planners. (D) A comprehensive empirical evaluation on a problem set larger than prior work, including existing and novel domains, demonstrating improved scalability and scope.

Code, domains, additional results and discussion can be found at https://github.com/taliBerman5/TP MCTS.

2 Background

Factored Markov Decision Process

We focus on goal-oriented, factored MDPs (fMDPs) [Boutilier et al., 2000] specified using a variant of PPDDL [Younes and Littman, 2004]. fMDPs assume that states are assignments to variables. Goal-oriented MDPs assume a set of terminal goal states. We model them as a four-tuple: 〈P, A, G, s0〉. P is a set of propositional variables that induce a state space S consisting of all truth assignments to P. 1 s0 is the initial state. G ⊆ P are the goal literals.

A is a set of actions, where each action a ∈ A is a pair (Pre, Eff) such that: Pre ⊆ P are a's preconditions, and Eff are a's effects, consisting of a set of triples (C,E, p). C and E are conjunctions of literals representing a context and an effect. p ∈ (0, 1] is its probability. The set of contexts within Eff are mutually exclusive and exhaustive. The sum of probabilities of different effects E for each context C is 1.

Action a =(Pre, Eff) is applicable in state s only if s |=Pre. Let (C,E1, p1), . . . (C,Ek, pk) be all triples in Eff such that s |= C and s |= Pre. If a is applied in s then effect Ei will occur with probability pi, and the resulting state s′ will be identical to s on every proposition q ∈ P such that q does not appear (possibly negated) in Ei, and every other proposition will be assigned its value in Ei. It is also possible to associate a cost with each action. States satisfying G are terminal and considered goal states.

Monte-Carlo Tree Search

MCTS [Coulom, 2006; Kocsis and Szepesv´ari, 2006] is a class of online, anytime, sampling-based search algorithms for sequential decision problems. In the time allocated for decisions, the algorithm performs multiple path-sampling iterations. Then, it selects the next action to perform, executes it, and the process is repeated.

In each iteration, MCTS traverses the current tree from the root down the tree until it reaches a node with an unexpanded child or a terminal state (selection). It adds a new child node to this leaf node (expansion). It estimates the added node's value by executing some default policy (rollout/simulation). Finally, it back-propagates the value up the tree, updating the value of all nodes on the path to the root (back-propagation).

Temporal Planning Concepts

A simple temporal network (STN) [Dechter et al., 1991] models temporal constraints between events and supports efficient inference algorithms. It is a pair S = (T , C) where T is a set of temporal variables (events); and C is a finite set of binary constraints on T , each of the form: Y -X ≤ δ, where X, Y ∈ T and δ ∈ R.

1 We often abuse notation, using P to refer to all literals.

A solution to an STN S is called a schedule. It is a function σ : T →R+, assigning a time-point to each event in T such that all constraints in C are satisfied. If such a schedule exists the STN is called consistent.

Temporal planning (TP) problems that can be solved only if actions are applied concurrently are called problems with required concurrency [Cushing et al., 2007]. For example, a shorter makespan (i.e., plan execution length) may be essential for meeting a deadline. Another classic example is match-cellar. A fuse must be replaced to fix the lights. Fuse repair requires light, too, obtainable by lighting a match. This example requires actions with both start and end effects (light on when the match is lit and off when it ends) and requires the match to be lit before starting to fix the fuse, but not too long before, to cover the entire fix-fuse action duration.

CoMDP

CoMDP [Mausam and Weld, 2008] extends fMDP by associating a deterministic duration with each action and allowing concurrent execution of non-interacting actions. Action preconditions must hold at their starting point, with effects obtained at their endpoint. Actions a and a′ interact if: (1) their preconditions are inconsistent; (2) their effects are contradictory; (3) the preconditions of a contradict a possible effect of a′ ; or (4) an effect of a modifies a proposition influencing the transition probabilities of a′ . We extend this model with start effects, overall conditions, end conditions, and deadlines.

3 RelatedWork

(Classical) temporal planning (TP) solves planning problems with concurrent actions that have deterministic action durations or durations confined to some interval [Fox and Long, 2003]. Recent work solves contingent domains with deterministic actions and non-deterministic sensing using search [Carreno et al., 2022]. TP-MCTS does not deal with partial observability, but it models stochastic action effects and uses a different search technique in which temporal information is maintained in the search tree.

Unlike classical methods, Markov decision processes (MDPs) [Puterman, 2005] model stochastic actions. SemiMDPs (SMDPs) extend them to model stochastic actions with stochastic durations. However, action execution in SMDPs is sequential, while we seek to model concurrent execution and handle deadlines and other temporal constraints.

Constrained MDPs (CMDPs) [Altman, 1999] and SMDPs [Beutler and Ross, 1986] extend MDPs/SMDPs seeking to maximize expected cumulative reward while satisfying constraints, typically in expectation only. The constraints are defined on g : S × A × S → R where S are system states, and A are actions, and g(s, a, s′ ) is the cost of a transition from s ∈ S to s′ ∈ S using a ∈ A. Durative actions could be defined by setting transition costs to equal action durations and constraining their sum to capture deadlines. This model, too, captures sequential execution only. Furthermore, temporal constraints have specific features, and TP-MCTS exploits this by using STNs and altering the backpropagation step, while allowing concurrent execution.

Few works tackle concurrent probabilistic durative domains, and all in the offline setting. Prottle [Little et al., 2005]

develops an AND/OR tree by either adding an action or an event concurrently with the current action or event, or moving forward in time to the next event or action. Its action description allows effects at (fixed) intermediate time points and outcomes with different durations. Our implementation does not support these extensions and considers only effects at the start and end of the action (as in classical TP) and identical, deterministic durations for different outcomes. Yet, our algorithm easily extends to handle these features. Importantly, Prottle restricts the decision epochs to pivot points, which implies incompleteness in the general case [Mausam and Weld, 2008]. FPG [Buffet and Aberdeen, 2009] uses factored policy gradients and also restricts action insertion to pivot points. Foss and Onder (2005) use STNs to capture temporal constraints, like us, but their uncertainty is not probabilistic and only over time. Beaudry, Kabanza, and Michaud (2010) construct a Bayesian Network, which is more general than an STN, but uncertainty is over durations, not effects. Furthermore, their adaptation of the RPG heuristic is geared to this property, whereas our adaptation is for uncertain effects.

The planner of [Mausam and Weld, 2008], denoted MW, addresses the setting closest to ours. MW reduces a CoMDP to an MDP whose actions are sets of non-interacting CoMDP actions, with a potential exponential blowup, greatly increasing the branching factor. The state is extended with variables denoting the remaining execution time of currently executing actions. An action can be applied only when an action in a currently executed action set terminates. They solve this MDP using real-time dynamic programming (RTDP) [Barto et al., 1995]. TP-MCTS employs a compilation that only doubles the action set size, allows for flexible action scheduling not restricted to pivots and supports a more expressive CoMDP+ model.

4 The Model

A Goal-oriented CoMDP+ is a tuple 〈P, A, G, s0, D〉 where P, G, s0 are as defined in an fMDP. D ∈ R+ is a deadline. 2 A is a set of durative actions: a = (P, E, d) where:

• P = (PS, PO, PE) defines the conditions of a, consisting of three sets of propositions determining the applicability of action a, referred to as start condition, overall condition, and end condition.
• E = (ES,EE), where ES and EE are a's start effects and end effects, respectively. ES and EE are defined as in fMDPs, via sets of triples (c, e, p), with similar constraints on the sets of contexts c and their probabilities. We assume no effect in ES contradicts PO.
• d is the action duration.

If a is applied at time t, two instantaneous changes of the system's state occur: immediately after time t, the state changes according to ES. Immediately after t + d (when a ends), the state changes according to EE. In both cases, the state changes as in the definition of effects in fMDPs.

2 CoMDP+ supports timed initial literals (TILs), too. TIL (l, t) denotes that literal l will become true at time t. TILs can capture deadlines and time windows. They can be compiled into a CoMDP+ action executed at time 0 [Cresswell and Coddington, 2003].

The semantics of actions applied concurrently must be well defined, either by explicitly specifying the outcome of any two potentially conflicting actions, or by restricting such applications. The former can be quite laborious, and even more so when action timing can impact the effect. As in classical TP, we opt for the latter. We require certain actions to be mutually exclusive (mutex) [Smith and Weld, 1999], and assume that otherwise, an action's effects are not impacted by other actions. To simplify the description, our mutex definition is global and ignores contexts. Weaker, state-dependent mutex are easy to define, as well as treating contradictory effects as implying plan failure, but are not supported by our code.

Mutex: 3 Actions a = (P,E, d) and a′ = (P ′ ,E′ , d′ ) are mutex if ES and P ′O are inconsistent or E′S and PO are inconsistent or ES ∪EE and E′S ∪E′E are inconsistent. That is, a has a start effect that contradicts an overall condition of a′ or vice-versa. Or, a and a′ have contradictory potential effects at some state s.

Soft Mutex: a′ = (P ′ ,E′ , d′ ) is soft mutex with a = (P, E, d) if E′E is inconsistent with PO. That is, an end effect of a′ violates the overall condition of a.

Action a = (P,E, d) is applicable at time t if PS is satisfied at time t, PO is satisfied in the interval (t, t + d), PE is satisfied at t + d, and no action a′ mutex with a is executed within the interval [t, t+d]. Notice that for PO to be satisfied in the interval (t, t + d), any action a′ that is soft-mutex with a and which overlaps a, must end after a ends. Hence, actions whose preconditions are satisfied can be applied at any time point, including concurrently, as long as they do not conflict with or compromise the end and overall conditions of an executing action.

Finally, we assume that any effect in ES that supplies some q ∈ PO is deterministic. We note that one can extend CoMDP+ with a reward function, but we focus on goaloriented problems with the objective of maximizing goal achievement probability subject to the temporal constraints.

5 TP-MCTS

TP-MCTS works in two stages: Offline: transform the CoMDP+ domain into an fMDP with instantaneous actions plus temporal constraints. Online: select an action and its timing by developing a search tree whose root corresponds to the current state. Apply the action at the chosen time. Repeat.

TP-MCTS operates under the following assumptions: (1) The goal is achieved if all propositions g ∈ G are satisfied, even if this occurs during action execution. (However, with a simple change, we can require that all actions have terminated, as well.) (2) An executing action cannot be stopped. (3) The algorithm does not take into account the passage of time during the search, i.e., time is considered stopped during the search phase. (4) As in classical TP, actions cannot be started simultaneously and must be ϵ-separated. 4

In practice, online decision time acts as a minimal ϵ value, which (in line with (3)), we assume is negligible w.r.t. action durations. True simultaneity can be achieved by defining explicit action combinations, sometimes called collaborative actions [Shekhar and Brafman, 2020].

3 When clear from context, we abuse notation and use Ex to denote the set of possible effects {e|(c, e, p) ∈ Ex}.

4 Otherwise, an action could use the simultaneous effect of a concurrent action as a precondition, which is undesirable semantically.

5.1 Offline Preprocessing

We split every durative action a into two instantaneous actions astart and aend (called snap actions [Coles et al., 2010a; Benton et al., 2012; Jim´enez et al., 2015]) and a constraint that aend is scheduled d time units after astart. astart takes care of the start conditions and effects, and aend takes care of the end conditions and effects. This can be extended to additional deterministic events that occur in specific time points during the execution of a, by splitting a into more instantaneous actions. We can represent the concurrent execution of actions a, a′ by performing astart, a′start , followed by a′end , aend, for example.

To ensure that the overall conditions are satisfied, we add one new fluent, InExecution(a) for each action a, that is true while a is executing. Its negation is a precondition of the start (respectively, end) of any action that is mutex (resp. softmutex) with a. To ensure that aend occurs d time units after astart, we use an STN to keep track of such constraints.

Formally, given a CoMDP+ 〈P,A, G, s0,D〉, generate the fMDP 〈P ′ ,A′ , G, s0〉 (plus some auxiliary data), where P ′ = P ∪ {InExecution(a)|a ∈ A}; A′ = {astart = (Pastart , Eastart )|a ∈ A}∪{aend = (Paend , Eaend )|a ∈ A}. Assuming a = (P,E, d), P = (PS, PO, PE) and E = (ES , EE ):

• Pastart = PS ∪ (PO \ ES) ∪ ¬InExecution(a)
• Eastart = {(c, e∧InExecution(a), p) | (c, e, p) ∈ ES}
• Paend = PE ∪ InExecution(a)
• Eaend = {(c, e∧¬InExecution(a), p)|(c, e, p) ∈ EE}

Additional preconditions and effects ensure that mutex and soft-mutex actions are not applied incorrectly:

• If a is mutex with a′ , add ¬InExecution(a) to the precondition of a′start .
• If a is soft-mutex with a′ , add ¬InExecution(a) to the precondition of a′end .

We assume that two copies of the same ground action cannot overlap. 5 If the original effects are stochastic, then so are those of astart and/or aend, with the added effect on the InExecution proposition. Because of the latter, the state at each point reflects the set of currently executing actions. These conditions ensure that both strict and soft mutex conditions of CoMDP+ are respected in the generated fMDP.

Beyond the fMDP, we also maintain the correspondence between every astart, aend pair corresponding to an original action a, a's duration, and the deadline D, so that the algorithm can add the relevant constraints to the STN.

5.2 Online Solution

Online, TP-MCTS generates an initial root node containing state s0 and initSTN, an initial STN with startPlan and endPlan events and a constraint endPlan - startPlan ≤

5 Otherwise, planning is undecidable [Gigante et al., 2020]

D. It then repeats the following process until either the goal is achieved or the deadline passes: Search to find the next action for root; Schedule this action; Step: execute it; Update root to contain the current state and an updated STN.

Search

Starting with the current root, TP-MCTS uses the time allocated per decision online to construct a search tree with state and action nodes. State nodes contain a state, while action nodes contain an action and an STN representing the temporal constraints associated with the branch ending with this action. Both nodes maintain n.V , their value, whose form differs between the two TP-MCTS versions (discussed later), and n.N, their visit counter.

Search consists of the four stages of MCTS: Select, Expand, Evaluate, and Backpropagate. We assume the reader is familiar with MCTS. Hence, for space reasons, the pseudocode focuses on the changes made w.r.t. MCTS, mostly ignores action nodes (and therefore, associates the action node's STN with its state node children) and the depth bound, and omits the Select, Expand, Step, and UpdateSTN functions. See our GIT for full pseudo-code.

Select (omitted - follows standard MCTS.) Traverse the tree from the root. Apply the UCB criterion [Auer et al., 2002] to select among actions. Sample the next state based on the action's effect distribution. Terminate once reaching a goal state, a state whose STN is inconsistent (e.g., any solution will miss the deadline), or a new child state, s.

Expand (omitted). Add the new state s to the tree, and for every legal action a in s, add a child action node containing a and the STN obtained by updating the parent's STN with the relevant events and with constraints (c1)-(c4):

• c1 startPlan-a ≤ 0
• c2 a- endPlan ≤ 0
• c3 pa(a) - a < 0; pa(a) is the action at a's parent node.
• c4 If a is a start action and enda its end action then:
• enda - a = d; (and enda is add to the STN)
• For every end action enda′ in the STN that has not been selected yet: a - enda′ < 0

(c3)+(c4.2) ensure that a is scheduled after any action selected earlier, and prior to any End action not yet selected. Evaluate. MCTS' evaluate uses a simulation (rollout) step to assess the node's value. Instead, TP-MCTS uses PTRPG, a novel heuristic estimate of the probability of reaching the goal from this node in time.

Backpropagate. Information from the leaf node is backpropagated up the tree using two methods explained later.

Schedule

In standard MDPs, the only decision is what action to execute next. As in standard MCTS, we select the action with the highest value. However, in temporal domains, the value of an action is contingent on when it is executed. For example, scheduling it after the deadline has no value. Therefore, we must also select its execution time.

Ideally, we would like to choose an action a and an execution time t for which the probability of successfully terminat-

Algorithm 1 TP-MCTS (root-interval version)

1: procedure TP-MCTS(CoMDP+ 〈P,A, T r, G, s0〉) 2: 〈P ′ , A′ , G, s0〉 = TransformTofMDP(〈P, A, T r, G, s0〉) 3: root = (s0, initSTN()) //node's state+STN components 4: repeat 5: a, Va() ← SEARCH(root) 6: t ← SCHEDULE(a, Va()) 7: root ← (Step(a, t),UPDATESTN(a, t, root.STN)) 8: until Terminal(root.state) 9: end procedure 10: procedure SEARCH(Node root) 11: while within computational budget do 12: nleaf ← SELECT(root) 13: EXPAND(nleaf ) 14: V () = EVALUATE(nleaf , nleaf .STN) 15: BACKPROP(root, nleaf , V ()) 16: end while 17: abest ← argmaxroot actions a maxt(a.V (t)/a.N) 18: return abest, abest.V ()

19: end procedure 20: procedure BACKPROP(Node root, Node nleaf , func Vleaf()) 21: for all node n on branch from nleaf 's parent to root do 22: ∀t ∈ [0, deadline], n.V (t) ← n.V (t) + Vleaf (t) 23: n.N ← n.N + 1 24: end for 25: end procedure 26: procedure SCHEDULE(action a, func Va()) 27: Tmax ← argmaxt Va(t) //returns an interval 28: t ← mint Tmax 29: return t 30: end procedure 31: procedure EVALUATE(Node n, STN stn) 32: c ← P T RP G(n, stn, G) 33: I ← stn.legalRoot 34: ∀t ∈ I, V (t) ← c; ∀t ̸∈ I, V (t) ← 0 35: return V () 36: end procedure

ing is maximized. In that case, we would have an asymptotically optimal algorithm for problems with deadlines because (due to the deadline), the tree has bounded depth, and hence, leaf nodes would eventually be goal-achieving or dead-ends, and because, in the limit, the frequency MCTS samples each stochastic effect converges to its true probability.

Unfortunately, the best current algorithm for finding a policy that always succeeds given stochastic actions is polynomial in tree size, hence, exponential in its depth [Hunsberger and Posenato, 2016]. Our setting is much more complex: we must assess the maximal probability of success of each policy sub-tree, maximizing over possible policies, while checking which branches can consistently schedule common actions. This can be done, in principle, using mixed-integer programming, but is not realistic computationally beyond very small trees. Hence, we resort to heuristics in which only some of the information in leaf-node STNs is propagated up the tree. Consequently, our algorithm is not guaranteed to be asymptotically optimal, but its empirical performance will be shown to be superior to previous methods.

We consider two combinations of the Evaluate, BackPropagate, and Schedule steps: earliest and root-interval. Earliest. Like UCT [Kocsis and Szepesv´ari, 2006], it maintains at each node a value V and a visit count N. Both initialized to 0. The estimated success probability of a new leaf node (computed by evaluate) is added to each of its ancestors' V value, and their visit count, N, is incremented by 1. The root action with the highest average value is chosen. It is scheduled at the earliest time the STN associated with this action considers consistent.

Earliest relies only on the selected action node's STN. Hence it ignores constraints on the root action's execution time stemming from future actions in the plan. For example, suppose the root action astart adds q, which aend negates, and q is a precondition of a later action a′start . If astart is scheduled too early, the constraint that a′start precedes aend would not be satisfiable. Root-Interval uses the STNs of leaf nodes to deduce such information and propagate it upwards. Root-Interval. In this version, each node n maintains a counter N and a function V (t) from t ∈ I0 = [0, D] to [0, 1], instead of a single value. n.V (t) is an estimate of the probability the goal will be achieved if the root action leading to n is scheduled to t.

Evaluate initializes the function for leaf nodes using their STN and PTRPG's estimate as follows: Let n be a leaf node. Let p be the probability of plan success returned by PTRPG for n. Let I be the set of time points such that: if the root action leading to n is scheduled at t ∈ I, a legal schedule for all actions on the path to n exists. (Denoted STN.legalRoot in l.33.) For STNs, I is always an interval, efficiently computable from n's STN. For all t ∈ I, set n.V (t) = p. For all t ̸∈ I set n.V (t) = 0. Propagate this information backward to n's ancestors as follows: Increment their visit and (conceptually) update the value function point-wise - i.e., ∀t ∈ I0: add n.V (t) to every ancestor's V (t). When Search terminates, it returns the action maximizing maxt V (t)/N (l.17). Schedule then selects the earliest time point achieving this maximal value (l.28). Because at leaf nodes I is an interval, at non-leaf nodes V can be represented as a set of constant-valued intervals. Each update is very efficient, but the set size at the root is worst-case linear in the number of leaf nodes, i.e., worstcase exponential in depth.

Step and Update

We apply the chosen action a at the selected time t (Step - omitted) and generate a new root node for the next decision (l.7). This node contains the state resulting from a's application in the real world, and an STN with the action that extends the current root node's STN with constraints (c2-c4) above and the constraint a - startP lan = t.

As noted, the constraints ensure a is scheduled after any previously selected action. And since search follows step, the next action is selected only after a is executed. So if at t we schedule a to t + δ, no other action will be executed prior to t+δ. During [t, t+δ], we can further develop the tree. The sub-tree corresponding to a's actual outcome can be re-used for the next decision, as in some MCTS implementations.

PTRPG

We estimate the probability of achieving the goal on time from a leaf node n using a heuristic function we developed that combines ideas from the temporal relaxed planning graph heuristic TRPG [Coles et al., 2008], sampling, and Bayesian techniques. PTRPG is stochastic and is executed once for each leaf node. It maintains a set L of literals initialized to contain all literals in node n's state, and the current time t, initialized to the smallest consistent value for endPlan according to n's STN, and a set C of inapplicability constraints, restricting the application of End actions in the STN, not selected yet, until their earliest possible execution time.

At each iteration, all actions whose preconditions are contained in L that are not inapplicable according to C at time t are "applied". That is, for every effect context whose context conditions are contained in L, one effect e is sampled and added to L. Because L is typically an inconsistent set of literals, multiple effects corresponding to inconsistent contexts might be added. For every action astart applied, we add to C the constraint that astart and aend cannot be applied before t + d, where d is the duration associated with astart. Actions applied can enable other actions' application at the same time, and this continues until no new action can be applied at t. At this point, t is incremented to t + d′ where d′ is the minimal duration of an action astart applied at t. PTRPG terminates if either G ⊆ L or t > D.

Suppose we terminated with literal set L at time tg, such that G ⊆ L. We use tg to derive a heuristic estimate of the success probability p using a Bayesian probabilistic modeling technique [Gelman et al., 2013]: We transform from the time domain to the probability domain by chaining logit from the time range to the unconstrained space, an affine transformation on the unconstrained space, and logistic sigmoid (expit) from the transformed unconstrained space to [0,1]. More specifically: given parameters a, b, c: Let D be the deadline. Define (1)D′ = D + c; (2)z1 = ln( tg D′-tg ); (3)z2 = a ∗ z1 + b; (4)p = 1 1+exp(-z2) . If tg > D we set p = 0. Otherwise, compute p with a = -0.5, b = c = 1.

Although noisy, tg is almost always an underestimate of the time required to reach the goal. Hence, if tg > D, it is highly unlikely to succeed and for this reason, we set p = 0. If tg = D, we consider goal achievement minimally possible (p = 1 1+exp(-(a∗ln(D/c)+b)) ). As tg gets smaller, there is more time to compensate for the relaxed assumptions made by the heuristic, and so p increases. By adjusting the parameters of the affine transformation, we can adjust the relationship between the heuristic's outcome and the probability of meeting the deadline, reflecting the properties of each particular domain. Here, we made no effort to optimize these values or adjust them to different domains. We selected simple constants that seemed to make sense and still got good results. Learning better parameters, possibly per domain, would be an interesting direction for future work.

6 Experiments

We compare the two TP-MCTS variants (earliest and rootinterval) with MW, the closest relevant algorithm [Mausam and Weld, 2008]. MW-RTDP is the original MW variant that uses RTDP, adapted to the online setting. For a fairer comparison, we also tested MW-MCTS, which replaces RTDP with MCTS, which is often better suited for online planning. Like TP-MCTS, MW-MCTS uses PTRPG to estimate node values instead of a rollout. Assumptions 1-4 hold for all versions.

Our comparison covers more domains than previous work. We consider five structured domains that model realworld problems: NASA Rover and Machine Shop, as used by [Mausam and Weld, 2008], Stuck-Car, a new domain with more interesting stochastic effects, and two new domains with required concurrency: Hosting and Probabilistic MatchCellar. We also use three synthetic domains to study basic properties of the algorithms. We conducted experiments with two possible decision-time budgets: 1 and 10 seconds and domain instances of different sizes.

All algorithms were implemented in Python. Experiments were run on an AMD EPYC 7702P 64-Core Processor. Each experiment was repeated 100 times. Our TP-MCTS implementation supports domain representations written in the Unified Planning Framework [Kapellos et al., 2023].

Domains

We describe the main properties of the domains used. Detailed descriptions appear in the supplementary material and their definition appears in our git repository.

Stuck Car(C). C agents must get C cars out of the mud before a deadline is reached. Agents can push a car and/or its gas pedal, possibly simultaneously. Pushing the car has a higher probability of success than pushing the gas. Executing both actions simultaneously has a higher probability of success than performing each action independently, but takes longer, and the agent may become tired. The agents can also search for a rock and place it beneath the car to aid in its release. The rock's quality influences the probability of success, and it may be better to drop a rock of poor quality.

Hosting-v. We must clean our house and prepare food before guests arrive. We can clean and cook at the same time. Cooking may result in a dirty floor that requires cleaning, later. There are two versions. The more complex one has required concurrency. In it, the broom is missing and the agent needs to find it. There is a probability of the broom being found and the light needs to be turned on while searching.

Prob Match Cellar(O). A probabilistic variant of the Match Cellar domain [Coles et al., 2009] with required concurrency, in which fix-fuse actions can fail.

Nasa Rover(R) and Machine Shop(O). Classical domains to which MW added action durations and stochastic effects. Some actions can fail, and different actions (e.g., using different machines) have different durations.

Simple-x. Each of x non-interacting actions with duration 4 achieves a unique goal. Best is to execute all actions simultaneously. As x grows, MW's representation grows exponentially, but solution depth remains 1, while our action space, solution depth, and the number of propositions grows linearly. Conc. Designed to test the ability to provide maximal concurrency needed to meet a deadline. Four actions take 1 sec.; two take 2 sec.; one takes 4 sec.; and one takes 9 sec. Meeting the 9 sec. deadline requires executing four actions concurrently, one from each class, except between times 4 and 5.

Prob Conc+G. A probabilistic variant of Conc. with four actions: A deterministic action with duration 8 and three probabilistic actions with duration 4,2,1, all of which must succeed to achieve the goal. G irrelevant non-interacting actions are added to this action set.

Results

TP-MCTS's offline compilation time is often less than 0.01 seconds, with the largest Machine Shop problem requiring 0.35 seconds, and hence negligible. MW's compilation time reaches 74 for Rovers(2) and 28 minutes for Machine Shop(3), and times out on larger versions of these problems. Tables 1 and 2 show the success rate of each planner on 100 trials for 1 and 10 seconds per decision. Deadlines were set to the length of an optimal plan + time for one action failure, so as to be challenging. Our GIT contains additional results.

The following general trends emerge: (1) MW-MCTS almost always dominates MW-RTDP. RTDP is better only in the smaller Simple domain, where, due to action noninteraction, it can update the value function quickly. (2) TPMCTS dominates in almost all domains. There are two exceptions: In Nasa Rover(1), MW benefits from its shorter solution depth given 1sec. This advantage disappears in the larger Nasa Rover(2). MW-RTDP has a higher success rate in Prob-Conc+8 given 10sec. Given the performance on other Prob-Conc variants, this may be due to the variance in the success estimates. The impact of domain size on the algorithms is clearly visible in the three structured domains. (3) Additional search time almost always leads to increased success rates for all algorithms, but trends (1)-(2) hold in both tables. (4) Hosting-2 and Prob MC(i) are not solvable by MW's method due to the need for required concurrency.

Simple-x highlight the difficulty MW's algorithm has scaling up as the number of non-mutex actions increases due to the exponential growth in the number of legal action combinations. Although the solution depth is smaller, the algorithm does not have sufficient time to explore all actions and has a low chance of detecting the solution. With more time, it slightly scales up. TP-MCTS requires deeper solutions, but MCTS combined with PTRPG can focus exploration on more promising paths. Similar behavior is observed in Nasa Rover(2), Machine Shop(2), and Machine Shop(3).

Comparing earliest and root-interval, earliest performs better given less time when temporal constraints are not complex because it can expand more nodes. Thus, trying to start an action as soon as possible is often a good heuristic. However, with sufficient time, root-interval succeeds more often, and in domains with more complex temporal dependencies, such as Hosting, only it can solve the problem reliably.

Additional experiments (see GIT) show that: (1) When deadlines are relaxed, success rates increase, but makespan is rarely impacted. (2) PTRPG's evaluation formula can have a significant impact on success rates, Nevertheless, but the relative strength of all variants remains similar, with TP-MCTS remaining much stronger than the MW variants.

7 Summary

We presented the first online algorithm for planning in MDPs with durative, concurrent actions. TP-MCTS combines MCTS and temporal planning techniques, including Start/End actions, STNs, with a new backpropagation scheme and the PTRPG heuristic to both select and schedule actions online. TP-MCTS uses a rich yet economical representation, is more scalable than previous methods, and is the first such online/offline algorithm to handle required concurrency.

Acknowledgments

This work was supported in part by the Lynn and William Frankel Center for Computer Science at Ben-Gurion University of the Negev and by the Helmsley Charitable Trust through the Agricultural, Biological and Cognitive Robotics Initiative of Ben-Gurion University of the Negev