Belief Management for High-Level Robot Programs

1 Introduction

High-level control is a serious challenge in autonomous systems design, especially for complex and dynamic domains. In the cognitive robotics domain, the framework around the logic-based robot programming and plan language IndiGolog [Giacomo et al., 2009] (an on-line variant of the Golog family [Levesque et al., 1997]) provides the means for state-ofthe-art high-level control. However, basic assumptions in IndiGolog are that an action's outcome is correctly modeled, and that all exogenous events beyond the system's control are known. Such assumptions are in conflict with reality, as actions and their models are error-prone and sensing results might be noisy and incomplete. Dismissing such details negatively affects a robot's effectiveness in situations where the control system reasons with belief that contradicts reality.

∗ Part of the presented work was done while A. Ferrein was affiliated with the Robotics and Agent Research Lab at the University of Cape Town, South Africa.

Consider, for instance, some office delivery robot that is to deliver a letter to office C. Assume that the robot believes to have delivered the letter to office C, while in reality it moved to room A instead (and is unaware of that). Besides the failed task, all future courses of actions will be based on this very wrong belief. As a first step, execution monitoring and a strong background model could enable the detection of such inconsistencies, say, when an object would be considered to be in two rooms simultaneously. For such encountered inconsistencies, there might be more than one explanation (failing actions, sensing faults, or exogenous events). Hence, the robot has to reason about such explanations, demanding for belief management over multiple hypotheses.

In this paper, we present an approach of such a belief management system in IndiGolog that follows the history-based diagnosis approach by Iwan [Iwan, 2002]. Both, IndiGolog and history-based diagnosis, are based on the situation calculus [McCarthy, 1963]. Instead of addressing "what is wrong", the type of diagnoses is along the lines of explaining "what happened"[McIlraith, 1999]. Our system allows the agent to detect inconsistencies between the modeled belief and real sensor values, and generates a number of hypotheses to explain the mismatch. While we adopt the most likely hypothesis for immediate operation, we keep a pool of alternatives in case future data prove the favored one to be wrong. We limit the pool size in order to keep the number of explanations manageable. Experimental results from a delivery domain show the capabilities of our approach.

The remainder of this paper is organized as follows. First, we introduce IndiGolog and Iwan's history-based diagnosis approach. In Section 3 we formalize our belief management system and show its integration into IndiGolog. Further, we introduce a pool of possible hypotheses and constitute a minimum pool size to still be able to explain a maximum number of k faults. Experimental results can be found in Section 4. We conclude with a discussion of related work and an outlook to our future research.

2 Background

2.1 The Situation Calculus

The situation calculus [McCarthy, 1963] is a sorted second order logical language with equality that allows one to reason about actions and their effects. Starting in the initial situation S0 (when no actions have occurred yet), action sequences (histories) can be evaluated to define the current situation s. For this purpose, there is a special function symbol do : action × situation → situation that denotes the situation s after performing action α in situation s (s′ = do(α, s)). Properties holding in a situation are represented by so-called fluents, where fluents are functions or relations with a situation term as last argument. Action precondition axioms Dap of the form Poss(α(⃗x), s) ≡ Πα(⃗x) and effect axioms describe the validity of an action in a situation s and the effects regarding s′ . In Reiter's variant of the situation calculus, action effects are axiomatized by so-called successor state axioms Dssa of the form: F(⃗x, do(α, s)) ≡ ϕ+(α, ⃗x, s) ∨ F(⃗x, s) ∧ ¬ϕ-(α, ⃗x, s), with formulas ϕ+/-(α, ⃗x, s) evaluating F to true or false respectively. 1 In combination with foundational axioms Σ, unique name axioms for actions Duna, and some axioms about the initial situation DS0 , Dssa and Dap form the so-called basic action theory D = Σ∪Dssa∪Dap∪Duna∪DS0 . For more details, we refer the reader to [Reiter, 2001].

2.2 History-based Diagnosis

We follow the approach of [Iwan, 2002], denoting histories with σ, ¯ δ or ¯α, situation terms with σ or s. Sometimes, we use both terms synonymously, but it will be evident from the context. Iwan distinguishes between action variations and exogenous action insertions as explanations for inconsistencies between an observation φ (a sensor value) and an action history ¯ δ (a situation term). All possible variations and insertions are completely modeled in terms of predicates Var and Ins , where Var (α, A(⃗x), σ) ≡ ΘA(α, ⃗x, σ) and Ins (α, σ) ≡ Θ(α, σ) state under which conditions ΘA and Θ respectively, action A is a variation of action α and some action α is a valid insertion into the action history. We use the notion of executable action histories Exec(do([α1, . . . , αn], S0)) .= ∧j∈{1,...,n} Poss(αj , do([α1, . . . , αj-1], S0))2 and the notion of extended variations, which is inductively defined as:

1. EVar(ϵ, ϵ) .= ⊤,
2. EVar(ϵ, ¯α.α) .= ⊥,
3. EVar(¯ δ.δ, ϵ) .= Ins(δ, do(¯ δ, S0)) ∧ EVar (¯ δ, ϵ),

1 For space reasons, we only show relational fluents here. Further note that, as usual, all free variables in formulas are meant to be implicitly universally quantified. We abbreviate the list of variables x1, . . . , xn with ⃗x.

2ΘA(a,A(⃗x), s) and Θ(a, s) are similar to formulas Πa(⃗x) in the right-hand side of action precondition axioms. do([α1, . . . , αn], σ) is an abbreviation for the term do(αn, do(αn-1, · · · do(α1, σ) · · · )).

¯

meaning that δ.δ is an extended variation of ¯α.α (or ϵ as in case 3) if δ is a valid variation (or insertion, resp.) of α in situation do(¯ δ, S0) and ¯ δ is an extended variation of ¯α. The notion ¯ δ.δ refers to the history of actions in ¯ δ plus the single action δ. The equivalent notation as a situation term is do([¯ δ, δ], s). We denote the empty history with ϵ. In the introductory robot example, going to office A is a variation of going to office C, while adding an exogenous event stating that the robot was robbed of the letter represents an insertion. A ground action sequence ¯ δ is an explanatory history-based diagnosis for an observation φ and a history ¯ η iff D |= ExplDiag(¯ δ, φ, ¯ η) with ExplDiag(¯ δ, φ, ¯ η) .= EVar (¯ δ, ¯ η) ∧ Exec(¯ δ) ∧ φ[¯ δ]. Note that we assume a finite limit to the number of insertions and variations, which is reasonable as during one execution step usually only a limited number of faults occur. Given a complete model considering all possible faults, all possible inconsistencies can be explained. For ranking diagnoses, we define a preference value, as is discussed in Section 3.1.

2.3 IndiGolog

IndiGolog [Giacomo et al., 2009] is an online variant of Golog [Levesque et al., 1997] accounting for offline projections and sensing. It is a robot programming language where the semantic of its constructs is defined in the situation calculus. To this end, a one-step transition semantic with predicates Trans and Final is defined. A program configuration is a tuple 〈γ, s〉, where γ is a program and s a situation. The special predicate Trans(γ, s, γ ′ , s′ ) transforms program γ in the situation s into the program γ ′ resulting in the situation s′ . To denote final (terminating) configurations, a predicate Final(γ, s) exists. For example, to transform a primitive action, the following Trans and Final predicates are required:

1. Trans(nil, s, γ ′ , s′ ) ≡ ⊥;
2. Trans(α, s, γ ′ , s′ ) ≡ Poss(α, s) ∧ γ ′ = nil∧ s′ = do(α, s)
3. Final(nil, s) ≡ ⊤
4. Final(α, s) ≡ ⊥.

The transition for a primitive action is: 〈α, s〉 → 〈nil, do(α, s)〉. The latter is a final configuration as the predicate Final (nil, do(α, s)) holds. Loops, conditionals, and recursive procedures are defined in a similar way (see [Giacomo et al., 2009] for a complete overview).

To account for sensing results, a number of sensing axioms SF(α(⃗x), s) ≡ F(⃗x, do(α(⃗x), s)) which relate sensing actions with fluents are introduced. For each non-sensing action αi, one adds an axiom SF(αi, s) ≡ ⊤.

To give an example, consider that our robot wants to sense whether a door is open: SF(senseDoor(d), s) ≡ Open(d, s) where senseDoor is a primitive action and Open is a fluent. All sensing axioms are collected in the set {Senses}. In IndiGolog, one further needs a set C that contains axioms for reifying programs as terms. See [Giacomo et al., 2009] for a detailed discussion. Throughout the rest of the paper, we hence use an extended basic action theory D∗ = D ∪ C ∪ {Sensed}.

Having all preliminaries in place, we will show the integration of history-based diagnosis into IndiGolog in the next section.

3 Belief Management in IndiGolog

Our belief management is based on a pool of diagnoses explaining an agent's sensory inputs. In our system, an agent's belief is the set of all fluents' truth values in the current situation, as derived by D∗ . For encountered inconsistencies, the agent computes a number of possible hypotheses that explain them. In order to control the space of possible hypotheses, the agent keeps the most preferred hypothesis to explain the just occurred inconsistency. This is very much in the spirit of IndiGolog, where the agent also commits to the next action by directly executing it. In this section, we formally define history-based diagnosis and show the integration into the IndiGolog interpreter.

3.1 History-based Diagnosis with Invariants

Let us start with the notion of consistency. In this context, for one, we need to check whether the current situation is consistent with additional domain related environment invariants. Invariants are represented by the predicate Invaria(s) .= ∧i ιi(s), a conjunction of invariants sentences ι(s) over fluents formulas. An example for an invariant is ιn(s) ≡ [carry something ⊃ ∃o.has object(o)] stating that if the pressure sensor detects some weight, then the robot is carrying some object. Such invariants are required to detect inconsistencies within not directly accessible fluents. For another, we need to detect inconsistencies between modeled belief and the real world w.r.t. our sensors. We have to compare the modeled belief which is represented by the sense fluent axioms SF with values that come directly from our sensors. To this end, we introduce a helper predicate RealSense(α, s). It is true if the sensor for fluent F connected via the sensing action α returns the value ⊤ (similarly as a sense fluent axiom); and false otherwise. If SF(α, s) ̸≡ RealSense(alpha, s), then the real sensor value contradicts the predicted one, and we have an inconsistency. Due to limited space, we do not introduce RealSense formally, and refer the reader to e.g. [Ferrein, 2008] on how real sensor values can be integrated into IndiGolog.

Definition 1. A history σ is consistent iff D∗ |= Cons(σ) with Cons(·) inductively defined as:

1. Cons(ϵ) .= Invaria(S0)

Before we introduce our diagnosis approach, we need to define a difference measure on action histories.

Definition 2. Let cv : situation × situation → IR+, cv(¯ δ, ¯α) = v with v ≥ 0 evaluate the difference between a diagnosis ¯ δ and a history ¯α. cv is called the change value and is inductively defined as:

¯

1. cv(¯ δ, δ) = 0
2. cv(¯ δ.δ, ¯α) = cv(¯ δ, ¯α) + val (Ins(δ, δ))

¯

1. cv(¯ δ.δ, ¯α.α) = cv(¯ δ, ¯α) + val (Var (δ, α, ¯ δ))

Ins and Var are as in Section 2.2. We assume standard axiomatization of integers together with their standard operations.

The cost function val assigns a positive value that reflects the impact of repair to each single action insertion and variation. The lump sum of total costs for all variations and insertions yields the final difference value between a diagnosis and a history, and therefore defines the diagnosis' change value. Thus the higher the value, the less plausible a diagnosis is. The assumption that diagnoses representing a lower cardinality of faults are more plausible is commonly used in ranking diagnoses [de Kleer and Williams, 1987].

A history-based diagnosis is an executable extended variation that is consistent with the current sensing history.

¯

Definition 3. Let δ and σ be histories. Let Diag(¯ δ, σ, v) .= EVar (¯ δ, σ) ∧ Exec(¯ δ) ∧ Cons(¯ δ) ∧ v = cv(¯ δ, σ), denoting that ¯ δ is an extended variation of σ that is executable and consistent. ¯ δ is a proper history-based diagnosis (or diagnosis for short) based on σ iff D∗ |= Diag(¯ δ, σ, v).

To illustrate this, we come back to our introductory robot example. Assume the robot performed the following consistent action history σ = [pickup(letter), goto(room1), drop(letter)]. It now performs a sensing action sense(letter ) with

which is inconsistent. Possible explanations are: (1) the robot failed to pick it up: ¯ δ = [pickupFail , goto(room1), dropNothing]); (2) the sensing result was wrong: RealSense(sense(letter), σ2) ≡ SF(sense(letter), σ2); or (3) somebody snatched the letter: ¯ δ′ = [pickup(letter), snatch(letter), goto(room1), dropNothing].

We can estimate an upper bound for the size of the diagnosis space w.r.t the number of variations and insertions that happened between two consecutive actions.

Theorem 1. Let l be the length of the history σ, n be the number of different possible exogenous events, k be the maximum number of insertions between two actions of σ, and m be the maximum number of variations of an action. Then, the number H of potential diagnosis candidates is H = ((m + 1) · ∑ki=0 ni )l .

Proof (Sketch). For every action there are m variations plus the action itself. Every action can be followed by 0 to k insertions. The number of insertions is exponential in i. The whole term is exponential in the history length l.

To accommodate a possible state-space explosion, in our implementation we keep a fixed-sized pool Pool of diagnoses together with their respective change values. As we assume a finite number of insertions and variations, we can define the pool of diagnoses as a formula over all possible diagnoses in case the current history is not consistent with our observations of what happened in the real world. Otherwise, the pool consists of the history itself.

Definition 4. Let σ be a history. Then Pool is defined as

The implementation of our belief management system evaluates the pool of hypotheses in a lazy fashion. It focuses therefore on (one of) the simplest explanation(s) for an inconsistency first, that is a hypothesis with the smallest preference value.

Definition 5. Let σ be a history. The preferred diagnosis prefDiag is defined as:

¯

For a specific number c of faults we can determine a necessary minimum pool size (i.e. the length of the formula) ensuring the completeness of our approach. We can show that w.r.t. a fixed maximum number of changes c to a given history, the required pool size is much smaller than the number H established in Theorem 1.

Theorem 2. Let σ be a history and p be number of diagnoses of Pool(σ). Let c be the maximum number of all insertions i and variations v to a history σ and let k, l, m and n be as in Theorem 1. Further, let τ = ∑cc′=1 ∑c′ i=0,v=c′-i ( lv)mv (i+l-1 i )ni . If c ≤ k, l then τ is the exact amount of possible hypotheses. τ is an upper bound for c > k, l. With p ≥ τ we can guarantee that our approach is complete.

Proof (Sketch). We investigate variations v and insertions i separately, where the product of the corresponding options determines the total amount of diagnoses. For each of the ( lv) possibly faulty action combinations we have mv instances. Regarding insertions, after adding i elements to σ we get |σ′ | = i + |σ| = i + l. As the first element is fixed, similarly as with the variations we have for each of the (i+l-1 i ) combinations ni instances. Consequently, we have to sum over all different distributions of variations and insertions and finally sum over all c′ ≤ c. If the pool size is greater or equal to this maximum number of hypotheses, then obviously all hypotheses can be considered to be in the pool.

Algorithm 1: Extended mainloop of the Prolog Implementation of IndiGolog.

1. Exogenous events indigo(E,H) :- exog_occurs(Act), exog_action(Act),!,indigo(E,[Act|H]). 2. Transition of the program indigo(E,H):- readPool(PrefD,H), transBM(E,H,E1,H1,PrefD), storePool(PrefD,H1), indixeq(H,H1,H2),!,indigo(E1,H2). 3. Final condition check indigo(E,H) :- final(E,H), length(H,N), write(N), write(' actions.'), nl.

3.2 Integrating the Diagnosis Step into IndiGolog

Now, we show the integration of our diagnosis step into IndiGolog. The Prolog implementation of the mainloop of our extended IndiGolog interpreter (cf. [Giacomo et al., 2009] for a complete description of the implementation) is shown in Alg. 1. First it is checked, whether an exogenous event occurred. If so, it is entered up front in the action history. Step 3 of the mainloop checks, if the program reached a final configuration and if so, the interpreter terminates. Step 2 of Alg. 1 performs a single-step transitions of the program. Here, we integrated the diagnosis step. Therefore, we exchanged the original Trans predicate with a predicate TransBM that is introduced below; it extends Step 2 with a consistency check and the pool update (as described in the previous section). Before we can check for consistency, we need to get the pool of diagnoses from Prolog's database (via the predicate readPool); after our consistency check, the pool is stored again (storePool). In our implementation, we incrementally generate the different hypotheses. This means that we do not compute all possible hypotheses after the execution of each action. Only in case of an inconsistency, we extend invalid hypotheses in the pool. This is done for run-time efficiency. The predicate indixeq is also used in the original version of the interpreter and provides the interface to execute actions in the real world. Now, we come to the consistency check step and define TransBM formally:

TransBM takes a program γ in situation s and transforms it to program γ ′ in situation s′ . First, the Trans predicate, which is defined as usual (cf. [Giacomo et al., 2009]) performs a single step transition. prefDiag identifies the new preferred diagnosis ¯ δ, which is used to generate a new program consisting of necessary actions to retrieve a consistent situation.

Assuming a correct model and a sufficient pool size, now we have at least one consistent diagnosis that explains the current world state. However, the situation s′ could still be inconsistent, and future program transitions might not be possible or will lead to more inconsistencies. Therefore, we need to generate a consistent world state. One possibility could be to just go on with the program execution on history ¯ δ. But as this is only a hypothesis, it does not seem advisable to do so. Instead, we decided to introduce a predicate align that takes the preferred diagnosis ¯ δ and generates a program γ ′′′ whose world state agrees with ¯ δ. This is achieved by a special action set val(F(⃗x, ψF )) that sets the value of fluent F to the value ψF explicitly (see [Ferrein, 2008] for details on how to define such an action in IndiGolog). align(¯ δ, γ) generates a sequence of "set" actions, one for each fluent in the domain description. To this end, we need a number of macros of the form ψF1 ( ⃗ x1, s) .= F1( ⃗ x1, s), . . . , ψFn ( ⃗ xn, s) .= Fn( ⃗ xn, s), one for each fluent. align is defined as:

The execution of this sequence of set val actions leads to a world state that agrees with ¯ δ∗ . In the next section we show the results of our belief management.

4 Experimental Results

In order to evaluate our approach, we simulated and analyzed two robot control systems for delivery robots. We compared one system (BM) equipped with our belief management system against a plain one (P) that lacks it. The contestants were to move 3 objects in an office environment consisting of 59 rooms and 12 hallway segments (resembling our department). The robots' set of actions allowed them to pickup an object, move between connected rooms, and drop an object.

For our tests, we defined three action fault types and one exogenous one: The robot might (1) fail to pick up an object Var(pickup(·), pickupNothing, s), (2) pick up the wrong object Var(pickup(o1), pickup(o2), s) ≡ obj(o1) ∧ obj(o2)∧o1 ̸= o2), with obj(o) = o .= letter∨o = box∨. . . defining a finite set of objects; and (3) fail to release an object Var(drop(o), dropNothing, s) ≡ has obj(o, s). These faults resemble issues that frequently occur in reality. As exogenous issue, mean agents snatch objects currently carried by the robots Ins(snatchObject(o), s) ≡ has obj(o, s)).

Our four fault scenarios F1 to F4 define the following fault probabilities: In F1 the probability for picking up the wrong object is 0.2 and 0.4 for it to fail entirely. Additionally, in F2 a 0.3 probability for a failing drop action is defined. In F3 we add a probability of 0.05 that a sensing action fails, extended by mean agents snatching objects with a probability of 0.2 in F4. In order to model real robots more closely, we implemented continuous passive sensing in IndiGolog 3 , and defined three sensing rates S1 to S3: S1 refers to the availability of sensor data after every action. For S2 sensor data is available after every second action and for S3 after every third one. The sensing rates represent the fact that due to resource limitations (e.g. bandwidth, power, or computation time), in reality sensing might not be available at high rates.

3 It is quite common in real robot systems that they automatically provide sensing information after each action execution without actively triggering special sensing actions.

For the results given in Table 1(a), the contestants P and BM had to prove themselves in the context of 50 different missions (plans). For any scenario and sensing rate they had to solve these missions 10 times with varying seeds. In order to exclude any impact of planning issues on the results, both agents used a simple control program generating a trace of typical 40 actions in the absence of faults. The table reports the rate of successfully completed missions. A mission is failed if its execution is aborted or exceeds a timeout of 120 minutes, or if the 3 objects are not at the desired locations.

The results in Table 1(a) show that the agent BM clearly outperforms the plain one with a significance level of 1%. Though the success rate decreases along decreasing sensor and increasing fault rates, in contrast to the plain agent, BM is still able to finish most of its missions. Especially the impact of sensing rates can be minimized using the agent BM instead of the plain one.

In Table 1(b) we report the average runtime for BM for all twelve scenarios 4 . The average runtime of the plain agent is almost constant at 29.4 seconds over all scenarios. Whereas there is just a very small overhead of the BM agent in F1, F2 and F3 the overhead in F4 increases exponentially.

5 Discussion

In this paper we presented a belief management system that allows an agent or robot to detect inconsistencies between its internal representation of the world and reality. In order to be able to cope with such inconsistencies, the system provides explanations about what has happened in terms of the occurrence of wrong outcomes of primitive and sensing action and exogenous events the agent is not aware of. This is in contrast to diagnoses that answer the question of "what is wrong" and was first addressed in the situation calculus by [McIlraith, 1999] (later also by [Sohrabi et al., 2010]). McIlraith addresses explanatory diagnoses which are continuations of a given history of actions. It is shown that finding such diagnoses is analogous to planning. [Grastien et al., 2007] established the connection to satisfiability problems.

The main contributions of this paper are a formalization of the belief management system based on the situation calculus and history-based diagnosis, and the integration of the system into an existing IndiGolog interpreter. Besides a formal proof that the system (under some assumptions) is capable to find the right explanation for an inconsistency, we present experimental results from a simulated delivery robot domain. These show that an agent equipped with the proposed system is able to finish more tasks successfully under the occurrence of faults and exogenous events. We integrated the diagnosis step in a fashion similar to the work of De Giacomo et al. [de Giacomo et al., 1998; de Leoni et al., 2007] about execution monitoring. While they show how to integrate a monitoring step in the IndiGolog interpreter, they do not use a sophisticated diagnosis mechanism. Other related works on execution monitoring in Golog is e.g. [Lesp´erance and Ng, 2000; Ferrein et al., 2004].

4 On an Intel quad-core CPU with 2.40GHz and 4GB of RAM

• (a) Percentage of successfully finished missions plus standard deviations.
• (b) Average runtime in seconds (BM) and standard deviations.

Table 1: Results for scenarios F1 - F4 and sensing rates S1 - S3 for a robot using belief management (BM) and a plain one (P).

A drawback of the approach is its current high complexity, as the number of potential explanations to be considered is double exponential in the number of faults considered and the length of the action history. Even if pruning techniques help to control this number, this potentially limits the applicability to more complex domains. In future work we will investigate whether our proposed system can benefit from more compact representations already used in the planning, diagnosis or model checking domain. Another important issue is that all potential faults and their effects have to be modeled. It is still questionable if and how such models can be generated automatically in an efficient way, and if there is a way to cope with non-modeled faults.

Acknowledgments

This work has been partly funded by the Austrian Science Fund (FWF) under grants P22690 and P22959. A. Ferrein is supported by a grant of the Alexander von Humboldt foundation as a Feodor Lynen fellow. We would like to thank the anonymous reviewers for their helpful comments and M. Thielscher for his help to revise an earlier version of this paper.