Detecting and locating faults in the control software of autonomous mobile robots

1 Introduction

Control software of autonomous mobile robots is characterized by its fairly high complexity which is in con�ict with stability. Complexity is caused by the software components implementing the basic functionality like planning, sensor fusion, actuator interfaces, and their interactions. Because of the high complexity but also the instability of hardware components and connections, and the underlying operating system, complete stability is very unlikely. But if we want to build a robot that is truly autonomous it has to deal with failures during its runtime without degrading the desired behavior or even worse failing to ful�ll its mission. Hence, a diagnosis system on top of the control system which does monitoring the current behavior, locating the cause of a detected failure, and taking the appropriate actions is a necessity.

To achieve this we introduce a model-based solution. This includes a model of software components and their relationships that are speci�ed in the software architecture of the robot's control system. This model is then used to derive root causes of a detected failure. The failure detection is based on observations. For this we use the concept of observers. If the monitored value exceeds its pre-speci�ed boundaries, the observer raises a con�ict which causes the diagnosis engine to compute the root causes. Once the root cause has been identi�ed, the diagnosis system takes appropriate actions in order to retain the system's correct behavior. The fault detection, localization, and correction procedures are all based on declarative models of the control software.

2 Modeling software architectures

Software architectures comprise software components and their connections. Components represent a collection of classes which implement a certain behavior. The connections between components represent dependency relations like client-server relationships and data �ow. During the execution of a program the components might spawn processes and interact using method calls, or other means of communication, like events. Figure 1 depicts parts of the software architecture of our mobile robot.

The formalization of the structural properties of the software architecture considers the software components, their cause a detected misbehavior, we have to introduce a notation of observations. The easiest way of doing this is to use the same ok predicate for the purpose. If we detect a misbehavior at OM (ObjectMeasurement), we could represent this by the literal ¬ok(OM). We introduce a distinguished predicate correct for observations to distinguish observations and computed values . correct(x) for a connection x is true whenever the observed connection shows the correct behavior. Otherwise correct(x) is false. The appropriate model for OT and OM is: correct(OM) → ok(OM), ¬correct(OM) → ¬ok(OM), correct(OM) → ¬AB(OT )

∗This research has been funded in part by the Austrian Science Fund (FWF) under grant P17963-N04.

3 Monitoring, Diagnosis and Repair

Coupling the running program with its software architecture model requires an abstraction step. The running program changes its state via changing variable values which is caused by inputs from the environment. But SAM only represents the software components and their communication means. Therefore, we require to map changes to communication patterns. For this purpose we introduce observers. An observer monitors a certain part of the program's behavior during the execution. If an observer detects a behavior that contradicts its speci�cation, it computes the appropriate observations in terms of setting the observation predicates ¬correct(x) for the connection x, and invokes the diagnosis engine. In the current implementation we used the following observers: Periodic event production checks whether an event e is produced at least every n ms, Conditional event production checks whether an event e1 is produced n ms after the occurrence of an event e2, Spawn processes checks whether a component spawns a number n of processes and Periodic method calls checks whether a component calls a method m at least every n ms.

The observers are used to monitor the state of the system. For this purpose the observers check their rules on a regular basis. In cases of failure the diagnosis procedure is invoked.

The diagnosis task is based on the model-based diagnosis (MBD) paradigm [Reiter, 1987]. In particular we use Reiter's hitting set algorithm [Reiter, 1987]. In order to minimize diagnosis time we only search for minimal cardinality diagnoses which can be easily obtained when using Reiter's algorithm. We only construct the hitting set graph until a level where the �rst diagnosis is computed. In most practical cases single fault diagnoses can be found.

After diagnosis those components that are responsible for a detected failure have to be killed and restarted. We have to take care of the fact that restarting one component might require restarting another component. This can be done by using the information about strong dependencies between components. The components that have a strong dependency relationship with each other have to be restarted. Hence, the steps for repair would be: (1) compute the diagnoses. (2) compute a set of components that have to be restarted. In this step we compute all components that strongly depend on components of a diagnosis. (3) Maximize the chance of repair by using a larger set of components to be restarted.

The proposed diagnosis system has been tested on our mobile robot system. For the evaluation of the diagnosis we introduced arti�cial faults into the robot control system and analyzed if the diagnosis system detected and located the fault and recovered the control system.

Figure 2 shows the results for an introduced deadlock in the motion service (MO). After introducing the deadlock in MO the Event Observer for the event MotionDelta perceives that no more events are produced. The diagnosis kernel derived that MO is malfunctioning. Instantly the repair process starts. The repair action comprises a stop of the Behavior Engine (BE), a stop of MO, and a restart of MO and BE. The restart of BE is necessary because BE is strongly coupled with MO. After repair the diagnosis kernel derives the diagnosis that all components work properly now. The relatively long time for the recovery could be explained by the fact that a repair of services could take a while because of the required starting, stopping and re-con�guration of hardware components.

4 Related research and conclusion

Williams and colleagues [Williams et al., 1998] used modelbased reasoning to detect and recover failures of the hardware of a space probe. Verma and colleagues [Verma et al., 2004] used particle �lter to estimate the state of the robot and its environment. These estimations together with a model of the robot were used to detect faults. Previous research has dealt either with hardware diagnosis or diagnosis of software as part of the software engineering cycle. However, diagnosis of software and repair at runtime has never been an issue. The paper described a model-based diagnosis for detecting, locating and repairing faulty software at runtime. For this purpose a modeling technique for representing software architectures which include components, control and data �ow, and dependencies has been introduced. Moreover, the concept of observers, have been described in the paper. Finally, the paper presented a repair algorithm and �rst empirical results of our implementation. These results show that software failures, e.g., deadlocks, can be detected and corrected at runtime.