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

3.1 Situation Calculus, IndiGolog and History-Based Diagnosis

IndiGolog (Incremental Deterministic Golog) [13] is a logic-based programming and
planning language used for agents and robots. It lets the user choose whether com-
putational resources should favor planning or imperative programs, and is based on
Reiter's variant of the situation calculus [14]. With the situation calculus, all activities
and changes in the world are encoded as actions. A situation is therefore completely
determined by some initial situation and an action sequence (that is also called history).
This entails that the terms situation and history are interchangeable. Properties are de-
scribed by situation-dependent predicates and functions, named fluents. The user speci-
fies dependencies between a fluent and an action by successor state axioms (SSAs). The
so-called basic action theory (BAT) [14] models the environment and the robot's capa-
bilities. IndiGolog programs are interpreted by a transition semantics in a step-by-step
fashion. The semantics of program statements are defined by Trans and Final predi-
cates. Final .

Program interpretation in IndiGolog is based on a five step main cycle [13]:

( σ, s )

1. All exogenous events reported in the last cycle are integrated into the history.
2. The currently considered history fragment is moved forward if necessary. Taking
only a fragment into consideration keeps the history at a processable length.
3. The program σ is checked if it may terminate in the current situation s using Final .
4. The program σ evolves a single step using the predicate Trans , a primitive action is
executed if applicable and the history changes accordingly.
5. Sensing results obtained in the current cycle are integrated into the history.

This cycle is repeated until either the program terminates legally or there is no further
executable legal transition.
In [3], Iwan describes a diagnosis approach, named history-based diagnosis (HBD),
for robots in dynamic environments. HBD generates action sequences (histories) that
are consistent with some observation Φ that contradcits the original history. Based on
the situation calculus, alternative histories are generated by two operations: (1) variation
of individual actions in the original sequence (action and sensing faults), and (2) inser-
tion of exogenous actions. In order to isolate the most attractive history out of a possibly
large set of hypotheses, probabilities and the amount of variation from the original one
are used to rank the alternatives.

3.2 A Belief Management System for Dynamic Environments

We designed and implemented our belief management system around history-based
diagnosis and IndiGolog. For our purpose, we had to adapt the standard features and the
interpretation cycle of IndiGolog by adding diagnostic reasoning and related decision
procedures as well as features to handle multiple hypotheses.
Our concept for handling multiple hypotheses mainly bases on an adapted IndiGolog
temporal projector that is able to maintain a pool of hypotheses S (of configurable size)
as well as a reference to the current favorite hypothesis s f ∈ S . While the current steps
in the IndiGolog cycle were only adapted for the changes to the temporal projector,