Combining Probabilities, Failures and Safety in Robot Control

1 Introduction

Uncertainty, both about the domain in which a robot has to operate and about the effective sequence of actions it is executing, is one of the most crucial problem that cognitive robotics has to face in robot control. In this paper we present a formal framework for dealing with uncertainty both in the initial database and during the execution of a course of actions: actions can fail. The failure of an action can lead to exogenous events, e.g. if the agent fails to pick up a block then the exogenous event that the block falls to the floor can take place. The complete framework is designed for autonomous manipulators endowed with perception. Perception, in fact, can be used to diagnose what really happened during a failed execution (a similar approach is taken in [9]). Here, leaving perception aside, we shall concentrate on the different aspects concerning uncertainty:

1. Incomplete initial information. The most prominent logical approaches to probability are [14; 4] and [11; 1; 21; 13; 7; 17]. We introduce in the Situation Calculus [15; 20] a formal theory, which turns out to be equivalent to the possible world approach, under certain restrictions (e.g. [13]). Instead of possible worlds, we propose a suitable axiomatization inducing possible state descriptions [4] therefore relying on a classical semantics. Probability of sentences is entailed by the axiomatization. We do not provide nested probabilities.

2. Incomplete information for a course of actions, and exogenous events. A logical approach to failures has been presented in [2]. In general, the problem of failures during the execution of plans is thoroughly treated in the planning community (see e.g. [16; 12]. To cope with the non deterministic effect of actions during the execution of a plan, say, we extend the classical language and axiomatization of the Situation Calculus with stochastic actions and events so that different possible runs, for a given sequence of actions, can be obtained. However we preserve the core ontology of the Situation Calculus in which actions are deterministic and the whole dynamic of change is idealized. In fact, each run of stochastic actions is obtained as an expansion of a fixed sequence of deterministic actions. An expansion is formed by considering both probability of success and failure for each action, and exogenous events. We make a closed world hypothesis about exogenous events: the exogenous events are all and only those fixed in the theory. Probability of events is empirical, it accounts for the relative frequency of properties of events like the usual failures of an agent, due to its normal behavior or the circumstances under which it operates.

The probability of a sentence depends only on the amount of information available in the initial database, i.e. with state descriptions. Probability of actions, on the other hand, depends on properties of events, like a robot behavior. With the notion of expected probability we combine the two former notions (the logical and frequency ones) into a new probability that can account for the probability of a sentence after the execution of a course of actions, in the hypothesis that this sequence can fail in several different ways and exogenous actions can occur. This idea captures in some sense the dynamic execution under incomplete information ([8]). An example is the probability that the screwdriver is on the floor, given that the action the robot has to execute is to pick it up, and its goal is holding it in its hand. Expected probability, combining the two previous probabilities, gives a measure of safety of a sequence of actions chosen to achieve a goal. Therefore it can be used to determine whether a course of actions is more safe than another one. The notion of safety can be suitably extended to treat decision theory in the Situation Calculus (see e.g. [19; 3]).

2 Preliminaries

We consider the Situation Calculus (SC) ([15; 20]) as the core of our logic and language, and we suitably extend it to include new sorts, new symbols for its alphabet and new axioms. We refer the interested reader to [18] for a full presentation of the core logic and language and [9] for more details related to the extensions concerning probability on events. The core consists of the three sorts: action, situation and object = worldEntities ∪ genericObjects. Here the sort genericObject is a catch-all that can include any possible additional sorts needed in an application, like the reals or sets. We have extended the core with three new sorts: outcome, stochasticAction, event. The sort event consists of two sub-sorts, event = condEvent ∪ seqEvent. Observe that the sorted domain D could be infinite or uncountable even if some of its subsets is finite. For example we are interested in imposing a finite domain for world entities, while we would require probabilities to range over the reals. We shall use the following alphabet, with subscripts and superscripts, to denote terms: a, for variables of sort action; s, for variables of sort situation; sta, for variables of sort stochastic action; e, for variables of sort event; w for variables of the sub-sort seqEvent and u for variables of the sub-sort condEvent; p, for variables of sort object denoting probabilities and x, y, z..., for variables of sort object (these might be further distinguished, e.g for terms of sort worldEntity). The family of terms over SC and the set of formulae LSC over SC are inductively defined as usual. In particular a basic sentence is one formed only by fluents, e.g. ∃x∀y(P(x, S0)→Q(x, y, S0)), in which fluents take as argument only elements of sort worldEntities (we). A sentence uniform in σ is one in which no variable, free or quantified, of sort situation is mentioned. E.g. ∃sP(t, s) is not uniform and ∃x(P(t, do(transmit(x), S0))), is uniform in σ = do(transmit(x), S0).

Omitted quantifiers are always universal quantifiers.

3 The Basic Theory of Actions

The notions related to a basic theory of action with its set of foundational axioms and domain description axioms, are presented in detail in [20] and in [18]. These axioms represent an agent's prior knowledge about its domain of application, and its behavior, and are denoted by the following:

Here, DS0 is the initial database, describing what properties hold initially about the objects in the domain. Dssa ∪ Dap specify, respectively, the successor state axioms and the action precondition axioms. Σ is the set of foundational axioms for situations, and Duna ensures the uniqueness of each action. We present in the following a simple example to illustrate the basic ontology.

3.1 The basic ontology: a dispatching domain

An agent has to dispatch a string of bits from a source to a receiver and the information it has concerns some of the bits and the constrains that the string has to satisfy. The transmission can fail and thus an exogenous action that distorts the signal can take place. (A robotic oriented example is given in [9]).

Fluents Source(x, n, s): At the source there is a bit x ∈ {0, 1} in position n in situation s. E.g. Source(1, 1, S0) ∧ Source(0, 2, S0) specifies that the string 10 is at the source in the initial situation S0.

Receiver(x, n, s): At the receiver there is a bit x ∈ {0, 1} in position n in situation s.

Control and Exogenous Actions transmit(n). This is a control action with the following effect: the n-th bit at the source is transmitted.

distort(n). This is an exogenous action with the following effect: the complement of the n-th bit at the source is transmitted.

The initial database DS0 There are properties of the domain that the initial database has to represent. We list some of them, where x is complement of x:

1. ¬Receiver(x, n, S0) 2. Source(x, n, S0) → ¬Source(x, n, S0) 3. ∃n.(∀n′ .n′ ≤ n→∃ySource(y, n′ , S0))∧ (∀x∀n′′ .n′′ > n→¬Source(x, n, S0))

The first axiom says that no string of bits is at the Receiver in S0. The second says that at the source there is always one fixed bit in position n, the last specifies that the length of the string at the source is a priori fixed. Here for example we can fix ∀x¬Source(x, 4, S0). The following constrains to the strings in Source are also in DS0 .

C1. If a bit b is in position n > 2, b is either in position n-1 or in position n - 2:

Source(x, n - 1, S0) ∨ Source(x, n - 2, S0) C2. If a bit b is in position n = 2, b is in position n = 1:

For example: 011 is a legal string. 001 and 111 are not. Finally some axioms will state that bits, which we denote by b are limited to 1 and 0, and positions, which we denote by n, constitute a finite set of natural number. Both the sets are ordered and pairwise disjoint.

Successor State Axioms The successor state axiom for Receiver is:

Receiver(x, n, do(a, s)) ≡ (a = transmit(n) ∧ Source(x, n, S0))∨ (a = distort(n) ∧ Source(x, n, S0))

4 Incomplete initial information

If the initial database DS0 is incomplete (see [20; 10]), we can assign a probability to those statements ψ, s.t. DS0 ̸|= ψ. So, for example, if a goal G is given, we might be interested in finding a sequence σ of actions, such that Prob(G(σ)) ≥ 0.7 is entailed by the theory. A classical, and certainly the most intuitive approach, is based on a possible world semantics, in which all worlds are assigned the same probabilities (see [2; 13] and the probability of a sentence ψ is obtained by summing up the probabilities of the worlds in which ψ is true. We take an analogous method but we avoid introducing possible worlds. In some sense our approach can be viewed as a way to treat worlds in the object language, under certain restrictions. The basic idea develops Carnap's [4] idea of defining state descriptions. In fact, we construct a set of sentences such that each sentence captures exactly one class of structures of the language. Here a class of structures is obtained by filtration: if two structures are isomorphic, w.r.t. the domain of sort we, then they belong to the same class. If the domain of sort we is finite, then we shall get a finite number of classes. As each state description identifies exactly a unique class of structures, we use these sentences to count those classes of structures which are models of DS0 . Having the number of classes of models of DS0 we can finally assign probability to sentences, analogously as is done in the possible world approach. The advantage of our approach relies only on the fact that we filter the isomorphic models and we identify them directly in the language by the state description that we add to the initial database. Observe that our approach is, however, possible just in case the domain of sort we has a fixed finite cardinality.

We shall now give few details about the formalization. Let DS0 be the initial database, which we assume is a finite set of basic sentences, uniform in S0. The set of basic sentences uniform in S0 is denoted, for short, by Lwe .

Given DS0 we shall consider a set of State Description axioms (SD). SD is defined by the following set:

(1)

Here n is the cardinality of the domain of sort we, and q ∈ I is an index which will be specified below (3). Φi(S0), that appears in (1) is constructed as follows.

Definition 1 Let X be a set of variables. A function fX is a variable renaming isomorphism iff fX maps X onto X and is one-to-one. Let A and B be two sets of m-tuple of variables from X.

fX induces an equivalence relation between sets of m-tuples. An equivalence class of m-tuples is:

Example 1 Let X = (x1, x2, x3), A = {〈x1, x1〉, 〈x2, x1〉} and B = {〈x3, x3〉, 〈x2, x3〉}. fX(x1) = x3 and fX(x2) = x2 is a variable renaming isomorphism, and A =fX B.

Let φ be a basic atom uniform in S0, of the form F(⃗x, y) or t(⃗x, y) = t′ , with ⃗x possibly empty, y = S0 if it appears, and t, t′ terms of sort we. Let m ∈ { a | φa ∈ Lwe , a the arity of φ}. Let X = {x1, . . . , xn}:

Cm = {〈x1, . . . , xm〉j | 1 ≤ j ≤ nm, xi ∈ X} {Am}i∈I a family of sets of m-tuples, s.t. for each [Bm], Bm ⊂ Cm, only one representative is in{Am}i∈I

The above definitions are used to form all the possible m-tuples out of n variables and ensure to gather only one representative for each equivalence class, under the renaming isomorphism. Let us order all the atoms φs, as defined above. Let φk be the k-th element in such ordering Ord, with |Ord| = α. Φi(S0) is defined as follows:

Observe that, given n > 0 the number of variables, and m > 0 the arity of the tuples, and φk ∈ Ord,

Here ♯fX is the number of renaming isomorphisms and I = {1, . . . , λφk }.

To show that each Φi(S0) and, consequently each P ⋆ i , is uniquely defined, many lemmata have to be used. Moreover an equivalence relation, actually an isomorphism on structures, based only on the domain of sort we, and mirroring the renaming isomorphism, has to be defined. We skip all these details and leave only the main theorem.

Theorem 1 Let Mbe a structure of LSC with domain of sort we with cardinality n. There exists a unique P ⋆ i such that M |= P ⋆ i .

The above theorem tells us that each P ⋆ is a possible state description and, by the uniqueness, there is a one-to-one correspondence between the P ⋆ s and the classes of structures of LSC, with domain of sort we of fixed cardinality n.

Theorem 2 Let φ be a basic sentence, uniform in S0, such that SD∪{φ} is consistent. There is an ordering on the P ⋆ s,

To count probabilities we need to extend LSC with a number p1, . . . , pq of parameters.

Lemma 1 Let p1, . . . , pq be new parameters of the language, and let us add the following to DS0 :

Then there is an ordering on the P ⋆ s such that DS0 ∪ SD entails both:

Observe that the role of (4) is to assign to each model M of DS0 , which is also a model of a unique P ⋆ i a value 1 for the associated pi. On the other if Mi is not a model of DS0 the pi associated with its unique state description P ⋆ i , will have everywhere value 0. We can, now, count the models of DS0 as follows, where ♯M is a new parameter:

We are, now, ready to introduce the probability of sentences based on the equivalence classes of models of DS0 ∪ SD. This can be done at the object level just by operating on the P ⋆ 's. First we define:

Definition 2 Let DS0 be equivalent, for some ordering on the P ⋆ s, to ∨1≤i≤j P ⋆ i ∧ ∧i̸=k j<k≤n ¬P ⋆ k , let r ∈ R:

It follows, by Lemma 1 and Definition 5, that ∑ i P rob(P ⋆ i ) = 1.

The following definition will give us the probability of a sentence with respect to the state descriptions.

Definition 3 For any basic formula φ, uniform in S0:

Theorem 3 The following properties are satisfied for each basic sentence φ, either uniform in S0, or equivalent to a sentence uniform in S0, in all models of DS0 ∪ SD:

1. 0 ≤ Prob(φ)
2. Prob(⊤) = 1
3. Prob(φ) = Prob(φ ∧ψ) +Prob(φ ∧¬ψ)
4. If DS0 ∪SD |= φ ≡ ψ then Prob(φ) = Prob(ψ)

It follows that, if ψ is uniform in S0 then:

Observe that differently from Bacchus and Halpern we do not allow any nesting of probabilities. In other words we do not admit sentences of the form: Prob(Prob(φ) ≥ 0.3). However, given the above limitations, and the strict constraint that the domain of sort world entities has a fixed, finite, cardinality, the above theorem shows that our logic is equivalent to Halpern's logic, when to Halpern's axiomatization the finiteness axiom FIN is added.

Example 2 (Continued) Let Dwe = {{0, 1}, {1, 2, 3}}. We assume that no information about the three bits in the source's string in S0 is given, but the string is three bits and it satisfies C1 and C2. The possible strings are:

Each string corresponds to a state description. E.g. 100 is captured by P ∗ 1 with the following Φ1:

Here χ1 states the ordering defined respectively on bits and positions. P ∗ 2 , P ∗ 3 and P ∗ 4 can be defined analogously. DS0 ≡ P ∗ 1 ∨P ∗ 2 ∨P ∗ 3 ∨P ∗ 4 ∧ ∧4<j<q ¬P ∗ j where the Pj are all the other state descriptions admitted by the 5-structures of Lwe. Hence ♯M = 4 and P rob(P ∗ i ) = 14 . We want to evaluate the probability of the following sentence:

Stating that each bit b is followed by b, which is not entailed by DS0 . As Ψs(S0) ≡ P ∗ 2 ∨ P ∗ 3 ∧ ∧j̸∈{2↪3} ¬P ∗ j then P rob(Ψs(S0)) = 12 .

5 Amodel for failures

The nice behavior of the Situation Calculus as a logic of change, is that once we have suitably defined truth and probabilities in the initial database, everything about uniform sentences in σ > S0 (i.e. about the future of the initial database) can be easily computed in DS0 , using regression. Regression [18] is a proof method that, given a sentence uniform in a situation σ reduces such a sentence to an equivalent sentence in which the only situation mentioned is S0. Regression amounts to the following equivalence, given a sentence ψ(σ):

Here R(ψ(σ)) is a sentence uniform in S0. Now, by the properties of probability shown in Theorem 3, regression allows us to compute the probability for any sentence uniform in σ.

Observe however that we do not have a method to compute the probability of any sentence, what so ever. For example we would not be able to compute the probability of a sentence of the form ∃s∀s′∃s′′∃x y(P (x, s) ∧ Q(x, y, s′ )→R(y, x, s′′ )). And since the definition of Prob is based on state descriptions, which are closed sentences, we cannot either express sentences of the form: ∀xProb(φ(x)).

Independently of probabilities, we have so far given an idealized representation of the world in which the effects of actions are exactly those intended, i.e. actions, even exogenous actions, are deterministic. However, due to various circumstances (e.g. noise in the channel), an agent might fail in its intended execution of an action and probabilities on sentences cannot capture this fact. To address this problem, we have extended the specification of an action theory with stochastic actions and events, therefore we introduce a complementary notion of probability as a relative frequency of events. We introduce in the sequel the functions, constants and relations of the extended LSC that we use to model stochastic actions and probability of events, a more detailed description is in [9].

A stochastic action is a pair 〈v(a), a〉 with v(a) taking values in the outcome space outcome = {0, 1}, where 0 means that a failed and 1 that it succeeded. Given a sequence of deterministic actions, this sequence expands to a tree of events due to all the possible outcomes of each action. See Figure 1.

To model the tree and the probability distribution we introduce the following notion of event.

Event. ◦ : stochasticAction × seqEvent ↦→ seqEvent. | : stochasticAction × seqEvent ↦→ condEvent, and the special constant E0. E.g. 〈1, distort(bit2)〉 ◦ 〈0, transmit(bit1)〉 ◦ E0 is a sequence of stochastic actions, i.e. is a term of sort seqEvent, hence a term of sort event. An event e is either a sequence event w of sort seqEvent or a conditional event u of sort condEvent, according to the following definition:

sequence event :

1. E0 : the empty event.
2. (〈v(a), a〉 ◦ w) : the event obtained as a result of executing a with value v(a) ∈ {0, 1}, after the sequence event w. conditional event :
3. (〈v(a), a〉 | w) : the event obtained as a a result of executing a with value v(a) ∈ {0, 1}, given the sequence event w

Probability of events. P: stochasticAction × event ↦→ object. E.g. P(〈0, distort(n)〉|E0) = 0.9. Probability on events, is a functional event fluent P which takes as arguments events and returns their probability: P maps events into [0, 1].

Finally the following functions and predicates are used for the theory of events.

Measure. µP : objectn × seqEvent ↦→ object. E.g. µSource(bit, pos,E0) = 0.7. For each fluent P there is a belief measure µP .

Axioms for probability P We shall not treat here axioms for events, we refer the reader to [9]. These axioms mirror the foundational axioms for situations, and for all events of sort sequence the analogous theorems as for situations [18] are derivable. The properties of P are:

1. P(e) ≥ 0, for any event e.
2. P(E0) = 1.
3. P(sta ◦ e) = P(sta | e) × P(e)
4. P(〈0, a〉| e) = 1 - P(〈1, a〉 | e).

We define the following function:

Let ν ∈ {0, 1}. The following sets can be defined, with ExAct a predicate that sorts out the exogenous actions:

Given the above axioms and the above functions, the following properties hold:

5.1 Treating preconditions for stochastic actions

When a stochastic action sta is taken into account we need to know what holds at a given event in order to decide if sta is executable. In fact, we shall use the conditional probabilities to state that, if the preconditions are not satisfied, then the probability of success of the action will be 0. We need, therefore, suitable action preconditions axioms and successor state axioms concerning the dynamic of stochastic actions. Consider the dispatching domain and the control and exogenous actions given in paragraph 3.1: transmit and distort. The corresponding stochastic actions are 〈x, transmit(n)〉 and 〈x, distort(n)〉, where x is a random variable on the values 1 or 0. Preconditions are defined as follows:

The conditional probabilities for non exogenous action are:

The preconditions for the success of an exogenous action like distort depends on the result of a previous action. Therefore the probability of an exogenous actions is conditioned on the random effect of stochastic actions.

Observe that, by the axioms for P, we get a conditional probability for failure, for each of the above stochastic actions:

Successor state axioms for fluent measures. Since in the core language of SC fluents can take as argument only sequences of deterministic actions, by a principle of preservation, we prefer to extend the language with event fluents, namely µ-fluents, which we call measures of fluents. For each fluent F(⃗t, s) we add a functional event fluent µF (⃗t, e), with the same arity as F and such that all arguments which are not of sort situation are the same as F and the argument of sort situation is replaced by an argument of sort event. The value of a µ-fluent is given as follows:

The successor state axioms for fluent measures capture the dynamic of the domain, in terms of measures, under the circumstances that stochastic actions occurred. These successor state axioms are strictly tied to the successor state axioms for fluents and they have to preserve the following property:

Property 1 For any µ-fluent µF (⃗t, e):

According to the above property a simple method can transform a successor state axiom for a fluent into a successor state axiom for the corresponding µ-fluent. In particular, as a successor state axiom has the form F(⃗x, do(a, s)) ≡ Ψ, then we get Prob(F(⃗x, do(a, s))) = Prob(Ψ). By suitable manipulations we get the required successor state axioms.

5.2 Expected Probability and Safety

We want to combine the logical probability on sentences and the event probability defined on stochastic actions to get a third probability (see Theorem 4) that accounts for both incomplete information and possible failures of actions during execution. We are interested to know, given that G(σ) is what an agent should achieve, what is the probability that G will hold at σ. We also want to know the probability that a sentence G′ will hold at σ, given the evidence that G was to be achieved at σ. To capture these ideas we introduce the notion of Expected Probability. Let Eset(σ′ , σ) = {ei : ei ∈ leaves(σ), trans(ei) = σ′}. Let T(σ) = {σ′ | trans(ei) = σ′ , ei ∈ leaves(σ)}.

Definition 4 (Expected probability in S0) Let φ and ψ be sentences uniform in σ. The expected probability, in S0, of φ, given evidence ψ is:

The above defined expected probability allows us to compare two sequences of actions and decide which one is safer:

Definition 5 (Safety) Let φ(σ1) and φ(σ2) be two sentence uniform, respectively, in σ1 and σ2. Let ⪯safe be a ordering relation:

Example 3 (Continued) Let Ψr(σ) be the sentence (Receiver(x, n, σ) ∧ Receiver(⃗x, n + 1, σ)) where σ = do(transmit(2), do(transmit(1), S0)). We consider the stochastic tree expansion of σ. Considering the set {σ′ : σ′ = trans(e), e ∈ leaves(σ)}, we get the following possible executions of σ, see Figure 1.

σ1 = do(transmit(2), do(transmit(1), S0)) σ2 = do(transmit(1), S0), σ3 = do(transmit(2), S0) σ4 = do(transmit(2), do(distort(1), S0)), σ5 = S0 σ6 = do(distort(2), do(transmit(1), S0)) σ7 = do(distort(1), S0), σ8 = do(distort(2), S0)

σ9 = do(distort(2), do(distort(1), S0))

By regression, Prob(R[Ψr(σi)]) = 1/2, for i ∈ {1, 4, 6, 9} and Prob(R[Ψr(σi)]) = 1 for i = {2, 3, 5, 7, 8}. Considering the probability of events, from (7) and (8) we get:

P(〈0, distort(x)〉|E0) = 0.7 P(〈0, transmit(x)〉|E0) = 0.3 P(〈1, distort(x)〉|E0) = 0.3 P(〈1, transmit(x)〉|E0) = 0.7 P(e1) = 0.49 P(e2) = 0.147 P(e3) = 0.147 P(e4) = 0.063 P(e5) = 0.0441 P(e6) = 0.063 P(e7) = 0.0189 P(e8) = 0.0189 P(e9) = 0.0081

By Definition 4 we get EP (Ψr(σ)) = 0.68795.

6 Discussion

The notion of probability that we are concerned with, comes from the tradition of the logical interpretations of probability ([21]). The basic idea is that when assertions are not entailed it is always possible to conclude something about these assertions, a logical proximity as a degree of deducibility, treated as a probability on statements. The idea of attributing probabilities to logical statements was earlier introduced by Keynes's and illustrated in [14]. Carnap, in [4] addresses a distinction between degree of confirmation and relative frequency. In [13] Halpern proposes both a logic for statistical measure statements and probability statements. The former provides a probabilistic measure of events defined on a generic object: "the probability that a bird flies is 0.5". The latter is about probabilities of logical assertions: "the probability that Tweety flies is..". Following the tradition of probability logic, we have considered the Carnaps'notion of degree of confirmation to declare a probability Prob on sentences and the relative frequency idea to declare probability P on actions. Bacchus and Halpern in [1; 13] presents two systems for both the statistical and confirmative approaches. A unified theory is presented in [7]. In particular, in [13; 1] axioms and rules of inference are presented and the logic is proved sound and complete (under given restrictions), w.r.t. a semantics based on possible worlds. Differently from Halpern's and Bacchus one, our theory is based on a classical Tarskian semantics. By suitably axiomatizing the initial database we get a semantical definition of probabilities analogous to the possible worlds approach. We introduce axioms for state description, typical extension formulas used in finite model theory [5; 6]. Finally we have introduced a third probability, the expected probability, which can be used to compute the probability of a sentence given both incomplete knowledge and failures during the execution of a course of actions.