Belief Management for Autonomous Robots Using History-Based Diagnosis - Developing Concepts in Applied Intelligence - page 115

we added another step 1a (executed after step 1 of the main cycle) responsible for the
control of our belief maintenance system.
The main stages of our new step 1a are

1. update all s i ∈ S : s i = s f
2. check consistency of s f
3. perform diagnosis if necessary
4. decide on a new s f if necessary and proceed with stage 2 of the main cycle

The first stage is necessary as steps one and five of the standard cycle deal only with s f
and we have to adopt related changes for the alternative hypotheses in S as well.
In Stage 2 we verify s f 's consistency with reality. For this purpose background
knowledge (common sense, domain knowledge) is used to derive new facts and con-
flicts from perception results while executing a plan π . Although results from percep-
tion can be handled by SSAs the same way as exogenous or endogenous actions, they
do not change the environment. Thus every fluent update resulting from a sensing ac-
tion has to be checked whether it masks an inconsistency. This can be done by assuring
that a fluent is not restricted in such a fashion that would contradict the set of values
proceeding the sensing action.
Stage 3 triggers a diagnosis process in the case that s f is found to be inconsistent.
In this case, we derive diagnoses satisfying the definition in Section 3.1. As already
pointed out, a history is made up of endogenous, exogenous and sensing actions. En-
dogenous and sensing actions are performed actively, so it is a good guess for it or some
variation to be part of the correct hypothesis, whereas exogenous actions can occur any-
time and thus have to be considered with specific conditions.
We adapted history-based diagnosis according to Iwan [3] with these ideas in mind
and created a predicate Va r i a that is used to generate a valid

variation Va r of some action OrigAct with a preference value PV if condition Cond is
met by situation s . The preference value is one of

( OrigAct , Va r , Cond , PV )

, where the higher the value
the less likely this variation occurs. We use a value of 2 for incomplete initial situations
(which we discuss later) and a value of 1 otherwise. The preference value of a derived
sequence is defined as the sum of the individual PVs.
Derived action sequences have to be feasible, that is, it has to be possible to follow
them step-by-step from a given initial state. As this implies that the initial assignment
for all relevant fluents has to be known, our system has to be able to deal with incom-
plete initial belief. We cope with this issue by calculating also possibly executable hy-
potheses under the assumption of an incomplete S 0 and assign them higher preference
values. As in general the number of derivable situations is very large, we apply pruning
and abandon (partly) generated situation whenever they reach a predefined threshold.
In stage 4, we decide on a new s f in case the actual one is found to be inconsistent.
The preference value derived in stage 3 for each s i ∈ S is used for a ranking, where
in a straight forward approach we choose that hypothesis with the highest rank. Unless
there is no valid candidate for s f , execution is continued with stage 2.
With our basic concept we provide an effective belief management system that is
able to handle multiple hypotheses and several type of faults, and that can be easily
integrated into IndiGolog. First experiments are discussed in the next section.

{ 1 , 2 }