The Trembling-Hand Problem for LTLf Planning
Pian Yu Shufang Zhu Giuseppe De Giacomo Marta Kwiatkowska Moshe Vardi


Interpretable Machine Learning Models for Predicting the Next Targets of Activist Funds
    [
    April 29, 2024
=======================================================================================








Consider an agent acting to achieve its temporal goal, but with a “trembling hand". 
In this case, the agent may mistakenly instruct, with a certain (typically small) probability, actions that are not intended due to faults or imprecision in its action selection mechanism, thereby leading to possible goal failure. We study the trembling-hand problem in the context of reasoning about actions and planning for temporally extended goals expressed in Linear Temporal Logic on finite traces (), where we want to synthesize a strategy (aka plan) that maximizes the probability of satisfying the goal in spite of the trembling hand. We consider both deterministic and nondeterministic (adversarial) domains. We propose solution techniques for both cases by relying respectively on Markov Decision Processes and on Markov Decision Processes with Set-valued Transitions with objectives, where the set-valued probabilistic transitions capture both the nondeterminism from the environment and the possible action instruction errors from the agent. We formally show the correctness of our solution techniques and demonstrate their effectiveness experimentally through a proof-of-concept implementation.










§ INTRODUCTION


In this paper, we study the trembling-hand (TH) problem in the context of reasoning about actions and planning for temporally extended goals expressed in Linear Temporal Logic on finite traces <cit.>.[All results presented here apply to other linear temporal logics on finite traces, such as  <cit.> and Pure Past LTL <cit.>, as long as the set of traces that satisfy a formula can be characterized by a regular language, i.e., by a deterministic finite state automaton.]
In a chess game, a player may have a trembling hand due to, e.g., nervousness, anxiety, or stress, which results in mistaken moves that were not intended. Likewise, an agent acting in an environment could mistakenly instruct a different action, e.g., due to faults, leading to possible goal failure.

The TH problem originates from Game Theory in Economics, see e.g. <cit.>, referring to the situation where players erroneously select unintended moves with a small quantifiable probability.



This problem highlights the importance of introducing some form of resilience to these errors <cit.> in the player strategies and has given rise to the well-known notion of Trembling Hand Perfect Equilibrium in Economics <cit.>. 

Here, we study this problem in the context of reasoning about actions <cit.> and planning <cit.>.

Specifically, we consider an agent acting in a domain. At each state of the domain, when the agent instructs an action, with a certain probability, it can mistakenly instruct a different action. Notice that this uncertainty is on the agent decision-making capabilities, not on how the environment executes the instructed actions. To stress this point, we consider two settings: deterministic domains, where the environment has no choices in responding to agent actions, as in classical planning <cit.>; and nondeterministic domains, where the environment can adversarially respond to agent actions, as in Fully Observable Nondeterministic Domains (FOND), when considering strong plans <cit.>. In both settings, we want to synthesize a strategy (aka plan) that guarantees to maximize the probability of fulfilling a temporally extended goal expressed in , in spite of the adversarial response of the environment in the case of nondeterministic domains.

We devise solution techniques to solve the problem in the two settings by relying respectively on Markov Decision Processes (MDPs) <cit.> in the case of deterministic domains and on Markov Decision Processes with Set-valued Transitions (MDPSTs) <cit.> in the case of nondeterministic domains.
MDPs specify concrete probability values for each transition. MDPs with imprecise probabilities (MDPIPs) <cit.> and Uncertain MDPs (UMDPs) <cit.> have been proposed for scenarios where the probability values are uncertain. MDPSTs constitute a restricted subclass of MDPIPs, which combine probabilistically quantifiable uncertainty with unquantifiable uncertainty (nondeterminism) in a unified framework. 
They are attractive because they admit a simplified Bellman equation compared to MDPIPs, UMDPs <cit.>, and thus stochastic games.



In both settings, we consider objectives instead of standard reachability. Note that MDPs with objectives have been studied in <cit.>. Instead, MDPSTs with objectives are studied for the first time in this paper. We lift the definition of satisfying objectives from MDPs to MDPSTs by defining the notion of robust strategy, and then an efficient value iteration algorithm is proposed for synthesizing an optimal robust strategy. We evaluate the effectiveness of the proposed solution techniques on a human-robot co-assembly problem, where the robot operates with a trembling hand, and demonstrate promising scalability. 



 §.§ Related Work
 
Interestingly, the trembling-hand problem has never been specifically studied in reasoning about actions and planning, though some related work exists. For example, the classical work on reasoning with noisy sensors and effectors in Situation Calculus <cit.> is indeed related. There, sensors and effectors are considered to be noisy, so they introduce a stochastic element to be taken into account in reasoning. In particular, uncertainty on the effectors may be considered similarly to our trembling hand.  There is, however, an important distinction between the two: in our case, the uncertainty is on which action is actually instructed by the agent; instead, in their case, the uncertainty is on how the action (perfectly instructed) is actually executed by the environment. In other words, in our case, the uncertainty is on the agent, while in theirs, the uncertainty is on the environment, which has been more extensively studied since it corresponds to uncertainty in modeling the reaction of the world to agent moves.  In fact, there is a growing interest in forms of synthesis/planning that are resilient to errors in modeling the environment. For example, in <cit.>, one could compute a maximally permissive strategy for the agent, allowing it to switch from one strategy to another while in execution, in case exceptional environment changes occur such that the predetermined strategy fails. In <cit.>, multiple models of the environment are considered to handle exceptions during planning, aiming to mitigate the intrinsic risk in a single environment model. In <cit.>, a k-resilient strategy allows the agent to fail k times maximally at a repeatedly occurring state. 

Nevertheless, in all these works, the focus is on errors/exceptions wrt expected environment behaviors. The trembling hand, on the other hand, is about errors in the agent behavior, and, as such, has not been much studied yet. Only two papers <cit.> touched on this aspect, accounting for possible errors in robot decisions. Nevertheless, the environment considered is either deterministic or has probabilistic uncertainty. In contrast, our environment admits adversarial behaviors.

















§ PRELIMINARIES


We study the trembling hand (TH) problem in the context of planning for temporally extended goals expressed in . We now briefly introduce the logic ,  deterministic and nondeterministic planning domains, and the notion of strategy (aka plan) in a domain achieving an goal.

LTL_f. 
Linear Temporal Logic on finite traces () is a specification language expressing temporal properties on finite, nonempty traces. In particular, shares syntax with , which is instead interpreted over infinite traces <cit.>. Given a set of atomic propositions Prop, formulas are generated as follows: 
φ ::= a |φ∧φ|φ|φ|φφ,
where a ∈ Prop is an atom,  (Next) and   (Until) are temporal operators. 
We make use of standard Boolean abbreviations, e.g., ∨ (or) and → (implies),  and . In addition, we define the following abbreviations: Weak Next φ≡φ, Eventually φ≡φ and Always φ≡φ, where  is for Release.

A trace = _0_1… is a sequence of propositional interpretations (sets), where for every i ≥ 0, _i ∈ 2^Prop is the i-th interpretation of . Intuitively, _i is interpreted as the set of propositions that are true at instant i. We denote the last instant (i.e., index) in a trace  by ().  

By ^k = _0 ⋯_k we denote the prefix of  up to the k-th iteration, and ^k = ϵ denotes an empty trace if k < 0. 

We denote  satisfies φ by φ. The detailed semantics of can be found in <cit.>.
It is also shown there that, for every formula φ, one can construct a Deterministic Finite Automaton (DFA) Aut_φ = (2^Prop, , q_0, δ, acc), where 2^Prop is a finite alphabet,  is a finite set of states, q_0 ∈ is the initial state, δ : × 2^Prop→ is the transition function, and acc is the set of accepting states, such that for every trace π we have πφ iff π is accepted by Aut_φ.









Deterministic Domain. A deterministic domain is a tuple = (, s_0, A, F_d, Ł), where  is a finite set of states, s_0 ∈ is an initial state, A is a finite set of actions, F_d: × A ↦ is the deterministic transition function, 
where s' = F_d(s,a) is the successor state after performing an applicable action a at s. We use A(s)⊆ A to denote the set of applicable actions at s. Ł: → 2^Prop is the labeling function, where Prop is a finite set of propositions. Note that, compared to typical formulations of domains in planning <cit.>, 

we are assuming that more than one state can have the same evaluation of the propositions (fluents).




Nondeterministic Domain. 
A nondeterministic domain is a tuple = (, s_0, A, F_n, Ł), where , s_0, A, and Ł are defined as in deterministic domains, and F_n: × A ↦ 2^ is now a nondeterministic transition function such that F_n(s,a) denotes the non-empty set of possible successor states that follow an applicable action a ∈ A(s) in s.
It is worth noting that domains that are typically compactly represented, e.g., in Planning Domain Description Language (PDDL) <cit.>, can 
be encoded using a number of bits that is logarithmic in the number of states. 

Planning. A path of  (resp. ) is a finite or infinite sequence of alternating states and actions ρ = s_0 a_0 s_1 a_1⋯, ending with a state if finite, where s_0 is the initial state, and F_d(s_i, a_i) = s_i+1 (resp. s_i+1∈ F_n(s_i, a_i)) for all i with 0 ≤ i < |ρ|, and |ρ| ∈N∪{∞}. We denote by ρ^k = s_0 a_0 s_1 a_1 ⋯ s_k the finite prefix of ρ up to the k-th alternation.
The sequence (ρ, ) = Ł(s_0)Ł(s_1)⋯ (resp. (ρ, ) = Ł(s_0)Ł(s_1)⋯) over Prop is called the trace induced by ρ over  (resp. ). FPaths denotes the set of all finite paths.
An agent strategy (or plan) is a function σ_p:  FPaths→ A mapping a finite path on  (resp. ) to agent actions that are applicable at the last state of the finite path.

For nondeterministic domains, we assume that the nondeterminism is resolved by the environment, which acts according to an (unknown) strategy as an (adversarial) antagonist of the agent. Environment strategies are functions of the form  γ_p:  FPaths× A →, which need to comply with the domain, in the sense that given a finite path ρ∈ FPaths and an action a ∈ A((ρ)) it must be the case that γ_p(ρ)∈ F_n((ρ),a).  Note that, in the case of deterministic domains, this constraint forces the environment to have only one strategy. Given an agent strategy σ_p and an environment strategy γ_p, there is a unique path ρ(σ_p, γ_p) = s_0 a_0 s_1 a_1⋯ generated by σ_p and γ_p, where s_0 is the initial state and for every i ≥ 0 it holds that a_i = σ_p(ρ^i) and s_i+1 = γ_p(ρ^i, a_i). Sometimes, for simplicity, we write ρ instead of ρ(σ_p, γ_p), when it is clear in the context.


An agent strategy σ_p enforces an φ in a domain  (resp. ) if for every environment strategy γ_p, the infinite path ρ(σ_p, γ_p) contains a finite prefix ρ^i such that the finite trace π(ρ^i, )φ (resp. π(ρ^i, )φ). planning concerns computing such an agent strategy σ_p, if one exists. 










































































§ TH IN DETERMINISTIC DOMAINS


We begin investigating the trembling-hand problem for planning by focusing on the case of deterministic domains, where the environment has only one strategy, i.e., following the transitions of the domain. Hence, the only uncertainty is the stochastic one, arising from the “trembling hand". In the next section, we consider the case of nondeterministic domains, where the environment employs adversarial strategies.




 §.§ Problem formulation

The “trembling hand" refers to the agent intending to instruct a certain action but, by mistake, instructing a different action with a (small) quantified probability. This probability only depends on the domain state where the action is instructed (and then performed).

Notice that, here, the environment is fully deterministic, and hence, once the action is instructed, it will be executed (without any error) in a deterministic way.

The problem that we want to address is to maximize the probability of achieving a given objective in a deterministic domain in spite of the (state dependent) action-instruction errors due to the “trembling hand”.



We formalize the action-instruction errors as follows. 

Let = (, s_0, A, F_d, Ł) be a deterministic domain, s ∈ a domain state, and a∈ A(s) an applicable action at s.
We denote by err(s, a)∈ Dist(A(s)) the probability distribution of instructing an action a' instead of a in state s. For instance, suppose the set of applicable actions at s is such that A(s) = {a, a', a”} and err(s, a) = [0.9, 0.04, 0.06]. This means that,  when the agent intends to instruct action a at state s, then with probability 0.04 and 0.06, it may instruct actions a' and a”, respectively. Let = {err(s, a): (s, a) ∈× A} be the set of the (state-dependent) action-instruction errors caused by the “trembling hand”. 
The set of actions that could be instructed when the agent intends to instruct action a at state s is the support set of err(s, a), denoted by supp(s, a) ⊆ A(s). In this example, supp(s,a) = {a, a', a”}.





Recall that, without a trembling hand, executing an agent strategy σ_p in a deterministic domain  results in a unique path. Yet, in the presence of a “trembling hand", i.e., action-instruction errors , we get perturbed paths, where the actually instructed action may differ from the intended one with a probability following .










    Let  be a deterministic domain, σ_p an agent strategy, and  a set of action-instruction errors. A perturbed path in  wrt  is a sequence of triples ρ(σ_p,) = (s_0, a_0, a'_0)(s_1, a_1, a'_1)⋯,  
    where for every i ≥ 0, a_i= σ_p(ρ^i) (the intended action), a'_i ∈ supp(s_i, a_i) (the actually instructed action), and s_i+1 = F_d(s_i, a'_i). The set of all perturbed paths in  wrt σ_p and  is denoted by Φ^σ_p,.


Given a deterministic domain , an formula φ, and a set of action-instruction errors , the probability of σ_p enforcing φ in  wrt 
is defined as Pr_^σ_p, (φ) :=  Pr_({ρ∈Φ^σ_p, |π(ρ^k, ) φ for some  k ≥ 0}).











The problem is a tuple ^d = (, φ, ), where  is a deterministic domain, φ is an formula, and  is a set of action-instruction errors. Solving ^d consists in synthesizing an agent strategy σ_p^* that maximizes the probability of enforcing φ in  wrt , i.e., an optimal strategy for ^d, that is:
σ_p^* = max_σ_p Pr_^σ_p, (φ).





In the following, an example is given to demonstrate a perturbed transition in a deterministic domain .


    Consider a robot assembly problem, where the robot aims to assemble an arch using N blocks. In Figure <ref>, the goal configurations for N (2 ≤ N ≤ 6) blocks are depicted (which are used later in Section 5). Let OBJ = {Obj_i | i∈{1, ⋯, N}} be the set of blocks and LOC = {L_j | j∈{0, ⋯, M}} be the set of locations, where L_0 represents the storage. Initially, all the blocks are stored in the storage.

    During assembly, the robot can perform move actions to relocate blocks. The  set of robot actions is A = {(Obj_i, L_j): Obj_i∈ OBJ, L_j∈ LOC}∪{}, where (Obj_i, L_j) means move block i to location j. Due to the “trembling hand" (which may be caused by drifting), the robot’s action is subject to uncertainty. For instance, if the robot intends to move block i to location j, there exists a probability that it may mistakenly move a different block i' ≠ i or inaccurately place it in location j' ≠ j. In addition, the probability of errors varies for different actions. For instance, if the robot chooses Do-nothing, one can safely assume that the probability of error is 0. However, if the robot chooses to move, we assume a positive probability of error, leading to perturbed transitions resulting in perturbed paths.

    Figure <ref> shows a perturbed transition example in this case. The dashed arrow shows the intended action and the solid arrows represent the set of actions that may be actually instructed with their respective probabilities.

 





 §.§ MDPs with objectives

Solving ^d = (, φ, ) requires a modeling technique that is able to capture the action-instruction errors  in a deterministic domain. To this end, we first review Markov Decision Processes (MDPs), which are used in our solution technique.

MDPs allow action choice in each state, and each state action transition is a probability distribution on successor states, which provides a natural way of capturing the probability of the agent mistakenly taking a different action in a deterministic domain. 
Following <cit.>, 
an MDP is a tuple = (, s_0, A, ,  Ł), where  is a finite set of states, s_0∈ is the initial state, A is a finite set of actions, : × A ×→ [0, 1] is the probabilistic transition function, and Ł: → 2^Prop is the proposition labelling function. Analogously to planning domains, for each s∈, the set of actions applicable at state s is denoted by A(s).  

Denote by ξ=s_0 a_0 s_1 a_1⋯ a path and by FPaths the set of all finite paths of .


In this work, we focus on deterministic agent strategies for MDPs, instead of randomized. A strategy σ_m of  is a function σ_m:  FPaths→ A such that, for each ξ∈ FPaths, σ_m(ξ)∈ A((ξ)), where (ξ) is the last state of ξ. We denote by Ξ^σ_m the set of all probably infinite paths of  generated by σ_m.

Given an MDP = (, s_0, A, ,  Ł) and a set of goal states G ⊆, the probability of an agent strategy σ_m enforcing G in  is defined as Pr_^σ_m(G) :=  Pr_({ξ∈Ξ^σ_m|(ξ^k) ∈ G  for some  k ≥ 0}).



Computing an optimal strategy σ^*_m that maximizes the probability of enforcing G is the reachability problem over .  Analogously, an agent strategy can also enforce a temporal objective on an MDP. Given an MDP  and an formula φ, the probability of an agent strategy σ_m enforcing φ in  is defined as Pr_^σ_m(φ) :=  Pr_({ξ∈Ξ^σ_m|π(ξ^k, ) φ for some  k ≥ 0}).



The problem of MDP with objective is to compute an optimal strategy σ^*_m, which maximizes the probability of enforcing φ in  <cit.>.





 §.§ Solution technique








We now present our solution technique to synthesize an optimal agent strategy σ_p^* for ^d = (, φ, ), which aims to maximize the probability of enforcing φ in  in spite of . The key idea is to reduce ^d to an MDP with an objective. Intuitively, the MDP provides a probabilistic abstraction of instructing mistaken actions in the domain due to the trembling hand. Hence, the MDP has the same states as the domain, retains its original action choices, and incorporates the probability of action-instruction errors in its transitions. 

Probabilistic abstraction. 
We define an MDP ℳ = (, s_0, A, , Ł) from ^d = (, φ, ) as follows. , s_0, A, and Ł are the same as in . In order to construct the probabilistic transition function : ××→ [0, 1], note that (s, a, s') gives the probability of transitioning from state s to s' on action a. Assuming no “trembling hand” errors,  we have that (s, a, s') = 1 if s' = F_d(s, a) and (s, a, s') = 0 otherwise. Due to “trembling-hand” errors, however, unintended actions (e.g., a') may be instructed with some probability (given by err(s, a)(a')), thus resulting in a different successor state s” = F_d(s, a'). Following this observation, we construct 𝒯 as follows:
    
    𝒯(s, a, s') = 
            err(s, a)(a'),    if a' ∈ A(s), s'=F_d(s, a'),
    
            0,    otherwise.


































The TH problem for planning in deterministic domains is now reduced to an MDP with an objective. 



Let ^d = (, φ, ) be a TH problem defined in Def. <ref>, and  the constructed MDP described above. An optimal strategy for  with φ is an optimal strategy for ^d and vice versa, that is: 
  
    σ_p^* =  max_σ_m{ Pr_^σ_m(φ)},

where σ_p^* (optimal strategy for ^d) is given in Def. <ref>.



First, we observe that σ_p = σ_m, by construction. Second, one can derive, according to Def. 1 that 
Φ^σ_p,  = Ξ^σ_m if σ_p = σ_m. 

Finally, given a state s and an intended action a = σ_p(s) in ^d, one has that,  with probability err(s, σ_p(s))(a'), the agent may actually instruct a different action a' and then transit to s' = F_d(s, a'). Denote by Pr_^d(s' | s, σ_p(s)) the probability of transiting to state s' from the state s with action σ_p(s). We obtain that if σ_p(s) = σ_m(s), then Pr_^d(s' | s, σ_p(s)) = err(s, σ_p(s))(a') = (s, σ_m(s), s').



Hence, the conclusion follows.


Thm. <ref> allows us to utilize existing algorithms for MDPs with objectives to solve the TH problem for planning in deterministic domains. The common approach 
is by reduction to the reachability problem of an MDP <cit.>. 
More specifically, given an MDP  with objective φ, we first construct the corresponding DFA Aut_φ of the formula φ, then construct the product MDP ℳ^× of  and Aut_φ. In this case, computing an optimal strategy for  with φ reduces to the reachability problem over ℳ^×, where the goal states G are those in ^× that consist of the accepting states of Aut_φ. The reachability problem of ^× wrt G can be solved via value iteration, strategy iteration, or linear programming <cit.>. Due to the cross product, every finite path ρ∈ FPaths_ such that ρ = s_0a_0s_1a_1 ⋯ s_k+1, where FPaths_ denotes the finite paths on , corresponds to a finite path ρ^× on ^×, where ρ^× = (s_0,q_0)a_0(s_1,q_1)a_1 ⋯(s_k,q_k)a_k(s_k+1,q_k+1). 
Therefore, every strategy σ^*_m for ℳ^× wrt G induces a strategy for ^d = (, φ, ) as follows: σ^*_p(ρ) = σ^*_m(ρ^×) for ρ∈ FPaths_. Together with Thm. <ref>, the following theorem is an immediate result.


Let ^d = (, φ, ) be a TH problem defined in Def. <ref>, ^× = × Aut_φ the constructed product MDP, and G the set of goal states. We have that the computed optimal strategy σ^*_m of ^× with reachability goal G induces an optimal strategy σ^*_p for ^d.












§ TH IN NONDETERMINISTIC DOMAINS


We now turn to the case in which the domain is nondeterministic, i.e., the environment can choose its strategy adversarially. Hence, in planning, we have to overcome two forms of uncertainty: the stochastic uncertainty from the trembling hand and the adversarial uncertainty from the environment. 



 §.§ Problem formulation


Consider the case where the agent acts in a nondeterministic (adversarial) domain. We assume the nondeterminism is unquantifiable, so it is adversarial without a probabilistic behavior. In this setting, we want to synthesize an agent strategy that maximizes the probability of achieving its goal in spite of the adversarial behavior of the environment and the (small) probability of instructing wrong actions at every step. In other words, the agent seeks a maxi-min strategy, that is, a strategy that maximizes the minimal probability across all possible environment strategies. We find this case to be particularly interesting, since it combines the probabilistic aspects of the previous case's action-instruction errors and the environment's adversarial nondeterminism.

We first define perturbed paths of an agent acting in a nondeterministic domain  with action-instruction errors , i.e., the trembling hand, and adversarial environment behaviors.


    Let  be a nondeterministic domain, σ_p an agent strategy, γ_p an environment strategy, and  a set of action-instruction errors. A perturbed path in  wrt  is a sequence of triples ρ(σ_p, γ_p, ) = (s_0, a_0, a'_0)(s_1, a_1, a'_1)⋯. We denote by ρ' the projection of ρ by considering only the states s_i and actually instructed actions a'_i. It holds that, for every i ≥ 0, a_i∈σ_p(ρ'^i) (the intended action), a'_i ∈ supp(s_i, a_i) (the actually instructed action), and s_i+1 = γ_p(ρ'^i, a'_i). The set of all perturbed paths in  wrt σ_p, γ_p, is denoted by Φ^σ_p, γ_p,.





The probability of an agent strategy σ_p enforcing φ considering environment strategy γ_p and the action-instruction error  is denoted by 
Pr_^σ_p, γ_p, (φ).


The problem is a tuple ^n = (, φ, ), where  is a nondeterministic domain, φ is an formula, and  is a set of action-instruction errors. Solving ^n consists in synthesizing an agent strategy σ^*_p that maximizes the probability of enforcing φ in  with  in spite of adversarial strategies of the environment, i.e., an optimal strategy for ^n, that is: 

    σ^*_p = max_σ_pmin_γ_p Pr_^σ_p, γ_p, (φ).





Consider the human-robot co-assembly problem adapted from <cit.>, where the robot aims to assemble an arch along with a human in a shared workspace. During assembly, the robot can perform actions to relocate blocks, and the human may perform moves to intervene. The robot has a “trembling hand" as described in Example <ref>. Compounding this issue, the robot must ensure that the arch is successfully built, considering the human involvement. 



At each step, the robot instructs an action to relocate a block, though with a trembling hand, and then the human can react by moving blocks among locations. Human movements are not controllable, thus introducing nondeterminism into the consequences of instructed robot actions. Figure <ref> shows a perturbed transition example of a robot working in such a nondeterministic domain with a trembling hand. Note that each intended action (dashed arrow) corresponds to a set of actions (solid arrow) that may be actually instructed, together with their respective probabilities. Furthermore, each actually instructed action leads to a set of possible changes due to uncontrollable human intervention.




    




 §.§ MDPSTs with objectives

We now introduce Markov Decision Processes with Set-valued Transitions (MDPSTs), which combine probabilistically quantifiable uncertainty with unquantifiable uncertainty (nondeterminism), hence providing a natural probabilistic abstraction of 
an agent acting with a trembling hand in a nondeterministic domain. Note that MDPSTs are favorable due to their simplified Bellman equation compared to MDPIPs, 
UMDPs, and thus stochastic games. This distinction will be further clarified in Section 4.3.

An MDPST is a tuple _N = (, s_0, A, , _N, Ł), where , s_0, A, and Ł are defined as for MDPs, and

    
  * : × A ⇒ 2^ is the set-valued nondeterministic transition function;
    
  * _N: × A × 2^→ [0, 1] is the transition probability (or mass assignment) function, i.e., given a set Θ∈ℱ(s, a), where Θ⊆, 𝒯_N(s, a, Θ)= Pr(Θ|s, a).

Note that, in MDPSTs, the transition function ℱ(s, a) returns a set of state sets, i.e., (s,a) ⊆ 2^, and the transition probability function 𝒯 expresses the probability of transitioning to such sets via a given action.  















It is worth noting that the problem of MDPSTs with objectives is studied for the first time in this paper.
To define the problem, one needs to lift the definition of enforcing objectives from MDPs to MDPSTs by defining the notion of robustness for strategies to incorporate the unquantifiable uncertainty. In an MDPST, due to the unquantifiable uncertainty, the 
distribution on the set of reachable successor states of a state-action pair (s,a), where a ∈ A(s), is not uniquely determined by (s,a), in contrast to MDPs. We denote by Post(s, a) the set of reachable states of (s,a), despite both quantifiable and unquantifiable uncertainties. Formally, Post(s, a) = {s' |∃Θ∈ℱ(s, a)  s.t. 𝒯_N(s, a, Θ)>0 and s'∈Θ}. A feasible distribution of an MDPST guarantees that, given a state action pair (s,a), where a ∈ A(s), (i) only one state is chosen within Θ for each Θ∈ℱ(s, a); (ii) the sum of probabilities of selecting a state from Post(s,a) equals 1; and (iii)  the probability of selecting a state out of Post(s,a) is 0. 
In the following definition, 
ι^Θ_s' indicates whether s' is in Θ. Hence ι^Θ_s'=1 if s'∈Θ and ι^Θ_s'=0 otherwise. Furthermore, α_s'^Θ indicates whether s' is selected from Θ. Hence α_s'^Θ = 1 if s' is selected from Θ, and α_s'^Θ = 0 otherwise. 
 


    Let ℳ_N=(, s_0, A, ℱ, 𝒯_N, Ł) be an MDPST, (s, a) a state-action pair, where a ∈ A(s). 𝔥_s^a∈ Dist() is a feasible distribution of (s, a), denoted by s 𝔥_s^a, if 
    
    
        
  (i) 
        ∑_s'∈Θα_s'^Θ =1, Θ∈ℱ(s, a);
        
  (ii) 𝔥_x^a(s')=∑_Θ∈ℱ(s, a)ι^Θ_s'α_s'^Θ𝒯_N(s, a, Θ), 
         s'∈ Post(s, a); 
        
  (iii) 𝔥_s^a(s')=0,  s'∈∖ Post(s, a).
      




Following Def. <ref>, it is evident that, in MDPSTs, a feasible distribution is not uniquely determined for a given state-action pair, in contrast to MDPs.


It highly depends on α_s'^Θ (see item (ii)), the unquantifiable uncertainty of whether s' is selected from Θ. We now introduce nature for MDPSTs to characterize this unquantifiable uncertainty, motivated by the definition of nature in robust MDPs <cit.>. One can intuitively perceive nature as the environment in the context of nondeterministic domains, playing a role in resolving nondeterminism. We denote by _̋s^a the set of feasible distributions of state action pair (s,a). Analogously to MDPs, FPaths denotes the set of finite paths of an MDPST.

 
A nature of an MDPST is a function
γ_m:  FPaths× A → Dist() such that, γ(ξ, a)∈ℋ_s^a for ξ∈ FPaths and a∈ A((ξ)). 


Suppose we fix a nature γ_m. The probability of an agent strategy σ_m enforcing φ is denoted by Pr__N^σ_m, γ_m(φ) :=  Pr__N({ξ∈Ξ^σ_m, γ_m|π(ξ^k, _N) φ for some  k ≥ 0}),
where Ξ^σ_m, γ_m is the set of all probable paths generated by the agent strategy σ_m and nature γ_m. 
We now define (optimal) robust strategies for MDPSTs, which quantify all natures.  


    Let ℳ_N be an MDPST, φ an formula, and β∈ [0,1] a threshold. An agent strategy σ_m robustly enforces φ in ℳ_N wrt β, if for every nature γ_m, the probability of the probably generated paths satisfying φ is no less than β, that is, P_ℳ_N^σ_m (φ)≥β, where P_ℳ_N^σ_m (φ):=min_γ_m{ Pr_ℳ_N^σ_m, γ_m(φ)}.
    Such σ_m is referred to as a robust strategy for _N (wrt β).





    An optimal strategy σ^*_m robustly enforces an formula φ in an MDPST _N is σ_m^*=max_σ_m{ Pr_ℳ_N^σ_m (φ)}.
     In this case, σ^*_m is referred to as an optimal robust strategy for _N.









The problem of MDPSTs with objectives is to compute an optimal robust strategy σ^*_m, which maximizes the probability of robustly enforcing φ in _N, i.e., achieving the maximal value of β. Analogously, we can also define an MDPST with simple reachability, i.e., reaching a set of goal states. To avoid repetition, it has been omitted.











 §.§ Solution technique


The key idea to solve the TH problem for planning in nondeterministic domains is to combine the quantifiable action-instruction errors and the unquantifiable adversarial nondeterminism of the domain into an MDPST. This MDPST has the same states as the domain , and incorporates the action-instruction errors and the domain's adversarial nondeterminism into its transitions. In this case, we reduce ^n to an MDPST with an objective.

Probabilistic abstraction. 
We build an MDPST ℳ_N = (, s_0, A, , _N, Ł) from ^n = (, φ, ) as follows. S, s_0, A, and Ł are the same as in . To construct the set-valued nondeterministic transition function  and the mass assignment function _N, we incorporate the action-instruction errors  into the probabilistic transitions, much like in deterministic domains. In nondeterministic domains, however, the successor for each state-action pair is not singular due to the adversarial environment behaviour. Consequently, the successor of each probabilistic transition is a set, with environment deciding which element of the set to transit to.

Based on these observations, we can construct the set-valued nondeterministic transition function  as (s, a) = ∪_a'∈ A(s){F_n(s, a')}, such that (s, a) is a set of subsets in ,



for s∈ and a∈ A(s). The corresponding mass assignment function 𝒯_N is such that 
    
    𝒯_N(s, a, Θ)= 
            err(s, a)(a'),    if a' ∈ A(s), Θ=F_n(s, a'),
    
            0,    otherwise.


We now reduce ^n to an MDPST with an objective. 


    Let ^n = (, φ, ) be a problem defined in Def. <ref>, and _N the constructed MDPST described above. An optimal robust strategy for _N with φ is an optimal strategy for ^n, and vice versa, that is: 
    
    σ^*_p=max_σ_m{ Pr_ℳ_N^σ_m (φ)},

    where σ^*_p is given in Def. <ref>, and Pr_ℳ_N^σ_m (φ) is in Def. <ref>.


First, we observe that σ_p = σ_m, by construction. Second, one can derive, according to Definitions 4, 5, and 6 that 
∪_γ_pΦ^σ_p, γ_p,  = ∪_γ_mΞ^σ_m, γ_m if σ_p = σ_m. 

The rest of the proof can be completed similarly to Theorem 1. 

Finally, we propose an algorithm to solve the problem of MDPSTs with objectives. This algorithm is based on a reduction to an MDPST with simple reachability, i.e., reaching a set of goal states. The algorithm is motivated by existing value iteration algorithms for MDPs with objectives <cit.>. Essential adaptations, however, are needed to handle the set-valued transitions in MDPSTs.

Given an MDPST _N = (, s_0, A, , , Ł) and an formula φ, we first construct the corresponding DFA Aut_φ = (2^Prop, , q_0, δ, acc) of φ. Then, the product MDPST _N^× = (
 ^×, s^×_0, A^×, ℱ^×, 𝒯^×, Ł^×) is constructed accordingly with  ^×=× Q, A^×=A.
The set of goal states is given by acc^× = {(s, q)∈| q∈ acc}. 

For the efficiency of strategy synthesis, we further introduce 
an optimization that computes an optimal robust strategy on a sub-MDPST, which only consists of states that are (forward) reachable from the initial state s^×_0 and (backward) reachable from the set of accepting states acc^×. To do so, we first partition  ^× wrt the initial state s^×_0 and the set of accepting states acc^×. Specifically, 

let S_r⊆^× be the set of states that can be reached from s^×_0. We now partition ^× into ^×=S_n∪ S_d∪ S_p, where S_n=^×∖ S_r consists of states that cannot be reached from s_0, S_d⊆ S_r consists of states reachable from s_0 but that cannot reach any states in acc^×, and S_p=S_r∖ S_d includes those that can be reached from both the initial and accepting states. 

We construct a sub-MDPST 𝒵 = (_p, s_0, A_p, _p, 𝒯_p, Ł_p) from ^×_N with respect to _p as follows. A_p = A^×∪{a_ϵ}, where a_ϵ denotes self-loop action. The set-valued transition function is such that _p(s, a) = ^×(s, a), ∀ s∈ S_p∖acc^× and _p(s, a_ϵ) = s, ∀ s∈acc^×. 
The mass assignment function 𝒯_p is then given by i) 𝒯_p(s, a, Θ)=𝒯^×(s, a, Θ), ∀Θ∈_p(s, a) if s∈ S_p∖acc^×, a∈ A^×, and ii) 𝒯_p(s, a_ϵ, s)=1 if s∈acc^×. 

Define a value function V_𝒵: _p →ℝ_≥ 0 by V_𝒵(s)
    =max_σ_mmin_γ_m{ Pr_𝒵^σ_m, γ_m(acc^×)}, 






which represents the maximal probability of reaching acc^× from s. Then one can get that V_𝒵(s)=1, ∀ s∈acc^×. For s∈ S_p∖acc^×, the Bellman principle of optimality is <cit.>:

    V_𝒵(s)
        =max_a∈ A_p(s)min_ Pr(·| s, a)∈_̋s^a{∑_s'∈_p Pr(s'| s, a)V_𝒵(s')}.


Moreover, it was further shown in <cit.> that a simplified Bellman equation exists for MDPSTs. That is, one can safely pull the min operator inside the summation, which gives a more efficient variant

    V_𝒵(s)
        =max_a∈ A_p(s){∑_Θ∈ℱ_p(s, a)𝒯_p(s, a, Θ)
        min_s'∈Θ{V_𝒵(s')}}.


An optimal robust strategy σ_m^* can be derived from V_𝒵. Analogously to Sec. <ref>, due to cross product, every strategy σ_m for _N^× wrt acc^× induces a strategy for ^n = (, φ, ). Together with Thm. <ref>, we have the following.


Let ^n = (, φ, ) be as defined in Def. <ref>, _N^× = _N × Aut_φ the constructed product MDPST, and acc^× the set of goal states. The computed optimal robust strategy σ^*_m of _N^× with reachability goal acc^× induces an optimal strategy σ^*_p for ^n.



Let F̅ = max_s∈ S_p{max_a∈ A_p(s)|_p(s, a)|} be an upper bound of |_p(s, a)| for all (s, a) ∈ S_p× A_p. Let ϵ be the convergence precision of the value iteration (i.e., Eqn. (<ref>)).
The complexity for achieving an ϵ-suboptimal solution is 𝒪(|S_p|^2|A_p|F̅log1/ϵ).
We highlight that MDPSTs are a subclass of MDPIPs, and they admit more efficient strategy synthesis algorithms than general MDPIPs. This is because for general MDPIPs, each round of value iteration of its corresponding Bellman equation (Eqn. (<ref>)) involves two stages: 1) the inner minimization problem
is solved (e.g., using a bisection algorithm) for each state and each action
and 2) the value function is updated with  dynamic programming. 


























§ IMPLEMENTATION AND EXPERIMENTAL RESULTS




We implemented the solution technique described in Sec. 4, which subsumes the method described in Sect. 3,
in Python, and use LYDIA <cit.> for -to-DFA construction. The implementation details of our algorithms and experiments can be found on GitHub: https://github.com/piany/Tremblinghand_LTLfhttps://github.com/piany/Tremblinghand_LTLf.


In this section, we present a case study to demonstrate the effectiveness of the proposed method. 
Our case study is based on the human-robot co-assembly problem, described in Example <ref>. The “trembling-hand" robot aims to stack blocks to a certain configuration with unpredictable human interventions. Note that we assume the human only has a limited number K of moves (otherwise, the robot has no way to guarantee task completion <cit.>.). In particular, we consider the configurations of having certain objects in certain locations. The goal configurations for N blocks are depicted in Figure <ref>, involving objects ranging from 2 to 6 (i.e., |OBJ|∈{2, 3, ⋯, 6}). 






Implementation.
The key challenge in the implementation is an effective representation of the planning domain with error actions. On one hand, it impacts the efficiency for model construction.
As shown in <cit.>, the state space of the co-assembly problem grows exponentially in the number of objects. Therefore, it is extremely challenging to build a tractable model for a large number of objects. On the other hand, the efficiency of strategy synthesis is also impacted, as discussed in Remark 1.



In <cit.>, three different choices are examined to encode the state space, integer encoding (states are enumerated by breadth-first search), object encoding (use tuples, e.g., (1, 2, 0), mapping each object to its location), and location encoding (using tuples, e.g., (0, 1, 1, 0), mapping each location to the number of objects therein), where location encoding shows the best overall performance. 
We follow this observation and use location encoding for state-space representation. Note, however, that in our case a single tuple is not enough to represent a state. This is due to the one-to-one correspondence between objects and locations in the goal configuration. For example, in the configuration involving 5 objects (where the goal configuration is shown on the upper right of Figure <ref>), if the locations of the green and blue blocks are interchanged, the task is deemed incomplete. 
To resolve this issue, we use a tuple of tuples for state encoding. For instance, a state ((0, 0, 0, 1), (1, 0, 0, 0), (0, 1, 0, 0)) means that Obj_1 is at location 3, Obj_2 is at the storage (the first element in each tuple represents storage), and Obj_3 is at location 1. Therefore, given N objects, the co-assembly domain has at most 2^N(N+1) states. Luckily, many of the states are invalid due to physical constraints, e.g., one block cannot be at two different locations, and each location (except for storage) can have at most one block. Using these physical constraints, we design a recursive algorithm (to avoid enumerating all possible states, hence greatly improving efficiency) to prune the co-assembly state space such that only valid states are maintained. The details of the state pruning algorithm can be found in Appendix. 

Moreover, the K-move limitation of the human should also be considered. We use a counter = {0, 1, ⋯, K} to record the human moves. Together with the (pruned) state-space X of domain = (, s_0, A, F_n, Ł), i.e., X ⊆, we obtain an augmented state-space ' = X ×. 

If the counter value is K, then the set of applicable human actions is restricted to Do-nothing for all s ∈'. Finally, we can construct the probabilistic abstraction of the co-assembly problem in the form of an MDPST over ' following Sec. <ref>.







Figure <ref> depicts a (simplified) execution example of an optimal strategy for an arch-building task with 5 blocks at 5 certain locations (see the right-most arch).
All blocks are in storage (state s0) at the beginning. Then, the robot intends to put the green block at L1, which succeeds without any interference from the human (state s1). Next, the robot intends to finish building the base level by putting the blue block at L2. However, due to the trembling hand, the blue block was put to L3. Furthermore, the human put the red block at L2 to prevent the robot from building the arch (state s2). Note that the red block is supposed to be at L5 (see the right-most arch). In this case, the robot intends to remove the red block, which succeeds (state s3). After a finite number of executions, in spite of the trembling hand and the interventions from the human, the robot builds the arch (state sn). 













Experimental results.
In our experiments, the convergence precision for the value iteration in Eqn. (<ref>) was set to 10^-3. All experiments were carried out on a Macbook Pro (2.6 GHz 6-Core Intel Core i7 and 16 GB of RAM). 

We first show the effectiveness of the state-pruning technique. For the case that K = 3, the number of states and transitions in the constructed MDPST are shown in Figure <ref> for different numbers of objects (2≤ |OBJ|≤ 6). It is worth noting that six is the maximum number of objects that have been considered in the literature <cit.> (due to the exponential blowup in the number of states). It is evident that the state space, post-pruning, exhibits much slower growth compared to exponential expansion.

























    



    

In addition, the computation time for model construction (including state-space pruning and MDPST construction) and strategy synthesis (including DFA construction, product MDPST computation, and robust value iteration of Eqn. (<ref>)) with respect to different number of objects (2≤ |OBJ|≤ 6) are depicted in Figure <ref>. Note that synthesis in nondeterministic domains is 2EXPTIME-complete in the size of the formula and EXPTIME-complete in the size of the domain <cit.>. Moreover, the probabilistic behaviour of the agent (caused by the “trembling hand") further complicates the synthesis problem.
Nevertheless, one can see that, for the case of six objects, the overall problem (including model construction and strategy synthesis) can still be solved quite efficiently using the proposed algorithm.

For the case of 5 objects, we further explore situations where the upper bounds on human interventions range from 3 to 8 (i.e., K∈{3, 4, ⋯, 8}). 
The experimental results are shown in Table 1, where the size of the problem, i.e., the number of states and transitions, and the computation
time for MDPST construction and strategy synthesis with respect to K, are listed. It is clear that, although both the number of states and transitions grow linearly as K increases (as does the model construction time), the synthesis time grows faster. This is because computing an ϵ-suboptimal solution for an MDPST _N = (
 , s_0, A, ℱ, 𝒯_N, Ł), which consists of reachable states only (following the partition optimization described in Section 4.3), is 𝒪(||^2|A|F̅log1/ϵ).




§ CONCLUSIONS


In this paper, we have investigated the trembling hand problem for planning in deterministic and nondeterministic domains. We formulate the problem formally by defining action-instruction errors and perturbed paths influenced by these errors. For the case of deterministic domains, we show that the problem can be reformulated as an MDP with an objective, leveraging existing algorithms for synthesis. In the case of nondeterministic domains, on the other hand, we utilise 
MDPSTs with objectives, for which we propose an efficient robust value iteration algorithm for synthesis. In particular, MDPSTs with objectives have been studied here for the first time. 
We also demonstrate the promising scalability of the proposed algorithm in a case study. For future work, we plan to leverage symbolic techniques for synthesis, aiming to improve efficiency.









§ APPENDIX: STATE PRUNING ALGORITHM
























Given N objects, the co-assembly domain has at most 2^N(N+1) states. To obtain an effective representation of the co-assembly domain, we design a state pruning algorithm (Algorithm 1), which takes into account the physical constraints: (1) each block cannot be at more than one location, and (2) each location (except for storage) can have at most one block. In this way, only a set of valid states that satisfy these constraints are maintained for strategy synthesis. Note that Algorithm 1 employs a recursive approach, strategically avoiding the enumeration of all possible states. This recursive nature enhances efficiency.

Algorithm 1 takes as input the number of objects N and outputs the set of valid states S_valid(N). It starts by computing S_valid(2) for 2 objects (lines 2-9),  followed by the recursive computation of S_valid(≥ 3) through S_valid(N) (lines 10-23). When i =2, we first create all possible states 𝕊 using CreateStates(i, i+1), where each state is a 2× 3 tuple and each element of the tuple is either 0 or 1 (line 3). Then for a state s∈𝕊, if all the rows sum equal to 1 (checked by RowsSumIsOne) and all the columns (except for column 0, which represents storage) sum equal to 1 (checked by ColsSumIsOne), then s is added to S_valid(2) (lines 4-8). 

When i≥ 3, we compute S_valid(i) by expanding each state s_i-1∈ S_valid(i-1) (which is a (i-1) × i tuple) into a set of valid states s_i (which is a i × (i+1) tuple). In line 11, sub-algorithm CreateRow(i) returns a set of 1× (i+1) tuples whose row sum equals to 1 (i.e., r_valid). In lines 13-15, we expand each row r(k) of s_i-1 into a set of two rows, i.e., r_new(k), by adding one element (either 0 or 1) to the end of r(k). Then, in line 17, sub-algorithm Product(·) computes a set of tuples containing all possible combinations of elements from r_new(0), ⋯, r_new(i-2) and r_valid (i.e., S_comb). For each s_expand in S_comb, if all the rows sum equal to 1  and all the columns sum (except for column 0) equal to 1, the state s_expand is added to S_valid(i) (lines 17-21). 






§ ETHICAL STATEMENT


There are no ethical issues.




§ ACKNOWLEDGEMENTS


This work was supported in part by the ERC ADG FUN2MODEL
(No. 834115), in part by the ERC ADG WhiteMech (No. 834228), in part by the EU ICT-48 2020 project TAILOR (No. 952215), in part by NSF grants IIS-1527668, CCF-1704883,
IIS-1830549, CNS-2016656, DoD MURI grant N00014-20-1-2787,
and in part by an award from the Maryland Procurement Office.


named






