Benjamin Lussier

Matthieu Gallien

Jérémie Guiochet

Félix Ingrand

Marc-Olivier Killijian

David Powell

Planning with Diversified Models for Fault-Tolerant Robots

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Planning shows promising success as a central decisional mechanism in experimental studies on complex autonomous systems. However, the dependability of planners remains a stumbling block to real life utilization. Indeed, how can we justifiably trust such mechanisms, whose behavior is difficult to predict and validate?

Autonomous systems strive to accomplish goals in open environments. The space of possible execution contexts is thus, in essence, infinite, and cannot be exhaustively tested during validation. Testing and other validation techniques are nevertheless necessary in order to obtain planners that are as bug-free as possible. Even then, as noted by [START_REF] Fox | Exploration of the Robustness of Plans[END_REF], "it is inevitable that the abstractions in the [planning] domain model will fail to match precisely the reality of the world". Under such conditions, not only is it impossible for a planner to produce plans that are 100% robust, it is also impossible to decide during planner validation whether its domain model still contains residual development faults, or whether the abstractions it contains are too imprecise. One way to tackle this difficulty is to carry out multiple iterations of domain model validation and tuning until the planner produces plans that are "robust enough" for the considered application. Such an approach relies of course on the existence of a method for measuring plan robustness with sufficient confidence. Moreover, there may be a point of diminishing returns in that additional iterations of planner validation and model tuning offer no additional gains in plan robustness. In this paper, we defend the thesis that planner validation techniques can be usefully complemented by a fault-tolerance approach aimed at making planners resilient to residual development faults. The approach uses redundant diversified planning models, i.e., models based on different abstractions.

First, we introduce basic concepts of dependability and dependability issues relative to planning. Second, we present fault tolerance techniques that may be applied to planning mechanisms and the implementation of a fault tolerant planner for an autonomous system architecture. Third, we introduce the validation framework that we developed to assess performance and robustness of our fault tolerance approach. Finally, we present our experimental results.

Dependability and Fault Tolerance

Dependability is a major concern in computing systems controlling critical structures such as railroads, planes and nuclear plants. We introduce here basic dependability concepts extracted from [START_REF] Avižienis | Basic Concepts and Taxonomy of Dependable and Secure Computing[END_REF]). We then discuss validation and other dependability issues relative to planning.

Dependability Basic Concepts

The dependability of a computing system is its ability to deliver service that can justifiably be trusted. Correct service is delivered when the service implements the system function, that is what the system is intended to do. Three concepts further describe this notion: the attributes of dependability, the threats to dependability, and the means by which dependability can be attained (Figure 1).

Dependability encompasses numerous attributes. Depending on the application intended for the system, different emphasis may be put on each attribute. We focus particularly on reliability (the continuous deliverance of correct service for a period of time) and safety (the absence of catastrophic consequences on the users and the environment) of a system.

The threats to a system's dependability consist of failures, errors and faults. A system failure is an event that occurs when the delivered service deviates from correct service. An error is that part of the system state that can cause a subsequent failure. An error is detected if The means to make a system dependable are regrouped in four concepts: (a) fault prevention, that is how to prevent the occurrence or introduction of faults, (b) fault removal , that is how to reduce the number or severity of faults, (c) fault tolerance, that is how to deliver correct service in the presence of faults, and (d) fault forecasting, that is how to estimate the present number, the future incidence, and the likely consequences of faults. Fault prevention and fault removal can together be considered as fault avoidance, that is the attempt to develop a system without faults. Fault tolerance and fault forecasting embody the concept of fault acceptance, in that they attempt to estimate and reduce the consequences of the remaining faults, knowing that fault avoidance is almost inevitably imperfect. The development of a dependable computing system calls for the combined utilization of these four techniques.

Planning Validation and other Dependability Issues

Currently, planning dependability relies almost exclusively on fault avoidance, with only few attempts to consider fault acceptance as a complementary approach.

Planner development tools such as Planware [START_REF] Becker | Model Validation in Planware[END_REF] provide a level of fault prevention up front in that they assist domain analysis and knowledge acquisition by use of a high-level graphical formalism. However, it is the notorious problem of planner validation (i.e., fault removal) that has received the most attention to date, especially in autonomous systems.

Indeed, the classic problems faced by testing and verification are exacerbated. First, execution contexts in autonomous systems are neither controllable nor completely known; even worse, consequences of the system actions are often uncertain. Second, planning mechanisms have to be validated in the complete architecture, since they aim to enhance functionalities of the lower levels through high-level abstractions and actions. Integrated tests are thus necessary very early in the development cycle. Third, the oracle problem1 is particularly difficult since (a) equally correct plans may be completely different, (b) non-deterministic action outcomes and temporal uncertainties can cause otherwise correct plans to sometimes fail when executed, and (c) unforeseen adverse environmental situations may completely prevent any plan from achieving all its goals (for example, cliffs, or some other feature of the local terrain, may make a position goal unreachable).

The planning engine itself is not much different from any other software, so traditional software verification techniques may be applied. For example, [START_REF] Brat | Verification of Autonomous Systems for Space Applications[END_REF]) report successful use of static analysis of the PLASMA planner engine using the PolySpace C++ Verifier. There has also been work on model-checking planner executives (systems that execute plans) that successfully identified serious concurrency problems in the Deep-Space One spacecraft [START_REF] Havelund | Formal Analysis of a Space Craft Controller using SPIN[END_REF].

But the trickiest part of planner software is most certainly the domain model itself, since it is this that changes from one application to another and that in fine dictates what plans are produced. Typically, a planning domain model and the associated domain-specific search heuristics are constructed and refined incrementally, by testing them against a graded set of challenges [START_REF] Goldberg | Verification of Autonomous Systems for Space Applications[END_REF]. However, a small change to either can have surprisingly dramatic changes in the planner's behavior, both in terms of accuracy and performance. One way to validate a planning model is to define an oracle as a set of constraints that characterizes a correct plan: plans satisfying the constraints are deemed correct. Such a technique was used for thorough testing of the RAX planner during the NASA Deep Space One project [START_REF] Bernard | Remote Agent Experiment DS1 Technology Validation Report[END_REF], and is supported by the VAL validation tool [START_REF] Howey | VAL: Automatic Plan Validation, Continuous Effects and Mixed Initiative Planning using PDDL[END_REF]). However, extensive collaboration of application and planner experts is often necessary to generate the correct set of constraints. Moreover, when the plans produced by the planner are checked against the same constraints as those that are included in the model, this approach only really provides confidence about the planning engine and not the domain-specific model.

Automatic static analysis may also be used to ascertain properties on planning models, allowing detection of inconsistencies and missing constraints, whereas manual static analysis requires domain experts to closely scrutinize models proposed by planning developers. The development tool Planware [START_REF] Becker | Model Validation in Planware[END_REF] offers facilities for both types of analysis. Some work [START_REF] Khatib | Mapping Temporal Planning Constraints into Timed Automata[END_REF][START_REF] Penix | Using Model Checking to Validate AI Planner Domain Models[END_REF] has attempted to validate domain-specific models by means of model-checking approaches. However, [START_REF] Goldberg | Verification of Autonomous Systems for Space Applications[END_REF] reports scalability issues when the models become large, and suggests instead run-time verification of plan execution traces against high-level properties expressed in temporal logic. However, no details are given about how such high-level properties are defined.

To the best of our knowledge, not much work has been done on fault acceptance in planners. Whereas planner models commonly consider faults affecting domain objects (e.g., hardware faults affecting sensors or actuators), residual development faults affecting the planner itself are seldom considered.

One exception is [START_REF] Chen | On the Reliability of AI Planning Software in Real-Time Applications[END_REF], which proposes a measure for planner software reliability and compares theoretical results to experimental ones, showing a necessary compromise between temporal failures (related to calculability of decisional mechanisms) and value failures (related to correctness of decisional mechanisms). Later work [START_REF] Chen | Effects of Parallel Planning on System Reliability of Real-Time Expert Systems[END_REF]) addresses this compromise through a fault-tolerance approach based on concurrent use of planners with diversified heuristics: a first heuristic, quick but dirty, is used when a slower but more focused heuristic fails to deliver a plan in time. To our knowledge, no other fault tolerance mechanisms have been proposed in this domain. It is our opinion, however, that such mechanisms are an essential complement to verification and testing for planners embedded within critical autonomous systems.

Fault Tolerant Planning

Complementary to testing, diverse redundancy is the only known approach to improve trust in the behavior of a critical system regarding residual development faults (e.g., diversification is used in software components of the Airbus A320, and in hardware components of the Boeing B777). We propose here fault tolerant techniques based on diversity, adapted to planners and focusing on development faults in the planner knowledge. We first introduce the general principles of the proposed mechanisms, and then present an implementation in an existing autonomous system architecture.

Principles

The general principle of the mechanisms that we propose is similar to that of recovery blocks [START_REF] Randell | System Structure for Software Fault Tolerance[END_REF] and distributed recovery blocks [START_REF] Kim | Distributed Execution of Recovery Blocks: An Approach for Uniform Treatment of Hardware and Software Faults in Real-Time Applications[END_REF]. Diversified variants of the planner are executed either sequentially or concurrently. A recovery choice is made according to errors detected in the plans produced. We focus here on planner knowledge : diversity between the variants is encouraged by forcing the use of different abstractions, variable domains and parameters in the models, and different heuristics of the variants. Using completely diversified planners is also possible, but has not yet been tested. [START_REF] Srivastava | Domain Independent Approaches for Finding Diverse Plans[END_REF]) also propose an approach to find diversified plans from the same model and search engine. This technique could be used, in conjunction with our mechanisms, to tolerate faults in planning heuristics.

Detection Implementing error detection for decisional mechanisms in general, and planners in particular, is difficult. Indeed, there are often many different valid plans, which can be quite dissimilar. Therefore, error detection by comparison of redundantly-produced plans is not a viable option. Thus, we must implement error detection by independent means. Here, we propose four complementary error detection mechanisms: a watchdog timer, a plan analyzer, a plan failure detector and an on-line goal checker.

A watchdog timer is used to detect when the search process is too long or when a critical failure such as a deadlock occurs. Timing errors can be due to faults in the planner model, in its search engine, or ineffectiveness of the search heuristics.

A plan analyzer can be applied on the output of the planner. It is an acceptance test (i.e., an on-line oracle) that verifies that the produced plan satisfies a number of constraints and properties. This set of constraints and properties can be obtained from the system specification and from domain expertise but it must be diverse from the planner model. This mechanism is able to detect errors due to faults in the planner model or heuristics, and in the search engine.

A plan failure detector is a classical mechanism used in robotics for execution control. Failure of an action that is part of the plan may be due to an unresolvable adverse environmental situation, or may indicate errors in the plan due to faults in the knowledge or in the search engine. Usually, when such an action failure is raised, the search engine tries to repair the plan. When this is not possible, it raises a plan failure. We use these plan failure reports for detection purposes.

An on-line goal checker verifies whether goals are reached while the plan is executed. This implies that the checker maintains an internal representation of the system state and of the goals that have been reached. Goals can only be declared as failed when every action of the plan has been carried out.

Recovery We propose two recovery mechanisms, based on redundant planners using diverse knowledge.

With the first mechanism, the planners are executed sequentially, one after another. The principle is given in Figure 2. Basically, each time an error is detected, we switch to another planner until all goals have been reached or until all planners fail in a row. Once all the planners have been used and there are still some unsatisfied goals, we go back to the initial set of planners. This algorithm illustrates the use of the four detection mechanisms presented in the previous section: watchdog timer (lines 8 and 20), plan analyzer (line 13), plan failure detector (line 15), on-line goal checker (lines 3 and 5).

Reusing planners that have been previously detected as failed makes sense for two different reasons: (a) a perfectly correct plan can fail during execution due to It is worth noting that the choice of the planners, and the order in which they are used, is arbitrary in this particular example (line 6). However, the choice of the planner could take advantage of application-specific knowledge about the most appropriate planner for the current situation or knowledge about recently observed failure rates of the planners.

With the second recovery mechanism the planners are executed concurrently. The main differences with respect to the algorithm given in Figure 2 are: (a) the plan request message is sent to every planning candidate, (b) when a correct plan is found, the other planners are requested to stop planning, and (c) a watchdog timeout means that all the planners have failed. The algorithm can be found in [START_REF] Lussier | Fault Tolerance in Autonomous Systems[END_REF].

Coordination Detection and recovery are handled by a middleware level component called FTplan, standing for Fault-Tolerant PLANner coordinator . To avoid error propagation from a possibly faulty planner, FTplan maintains its own system state representation, based on information obtained from the execution control layer.

Whatever the particular recovery mechanism it implements, sequential or parallel, FTplan has to communicate with several planners, e.g., for sending plan requests or for updating their goals and system state representations before replanning. It also needs to be able to control their life cycle: start a new instance, or stop one when it takes too long to produce a plan.

FTplan is intended to allow tolerance of development faults in planners (and particularly in planning models). FTplan itself is not fault-tolerant, but being much simpler than the planners it coordinates, we can safely rely on classic verification and testing to assume that it is fault-free.

Implementation

Our targeted architecture, the LAAS architecture, is presented in [START_REF] Alami | An Architecture for Autonomy[END_REF]. Some recent modifications are given in [START_REF] Lemai | Interleaving Temporal Planning and Execution in Robotics Domains[END_REF]. It has been successfully applied to several mobile robots, some of which have performed missions in open environments (including exploration and human interaction). It is composed of three main components2 as presented in Figure 3: GenoM modules, OpenPRS, and IxTeT. The functional level is composed of a set of automatically generated GenoM modules, each of them offering a set of services, which perform computation (e.g., trajectory movement calculation) or communication with physical devices (sensors and actuators).

The procedural executive OpenPRS is in charge of decomposing and refining plan actions into lower-level actions executable by functional components, and executing them. During execution, OpenPRS reports any action failures to the planner, in order to re-plan or repair the plan.

IxTeT is a temporal constraint planner that builds plans by combining high level actions. The description of actions in the planner model is critical for the generation of successful plans and thus for the dependability of the robot as a whole.

The fault tolerance principles presented previously have been implemented in a fault tolerant planner component as presented in Figure 4. The FTplan component is in charge of communicating with OpenPRS as the original planner does (cf. Figure 3).

The current version of FTplan implements the sequential redundant planner coordination algorithm pre-Figure 4: Fault tolerant planner sented in Figure 2, with two IxTeT planners. Currently, the plan analysis function is empty (it always returns true) so error detection relies solely on just three of the mechanisms presented earlier: watchdog timer, plan failure detection, and on-line goal checker.

The watchdog timer is launched at each start of planning. As soon as a plan is found before the assumed worst-case time limit (40 seconds in our implementation), the watchdog is stopped. If timeout occurs, FTplan stops the current IxTeT, and sends a plan request to the other IxTeT planner, until a plan is found or both planners have failed. In the latter case, the system is put in a safe state (i.e., all activities are ceased), and an error message is sent to the operator.

In the current implementation, FTplan checks every 10ms if there is a message from OpenPRS or one of the IxTeT planners. In case of an action request from a planner or an action report from OpenPRS, FTplan updates its system representation before transmitting the request. If the request is a plan execution failure (the system has not been able to perform the actions of the plan), then FTplan launches a re-plan using the sequential mechanism. If the request indicates that the actions are finished, then FTplan checks if the goals have been reached. Unfulfilled goals are resubmitted to the planner during the next replanning or at the end of plan execution.

The first model used by FTplan was thoroughly tested and used on a real ATRV (All Terrain Robotic Vehicle) robot. We thus use it as primary model and as target for fault injection. We specifically developed the second model through forced diversification of the first. For example, the robot position is in Cartesian coordinates in the first model and in symbolic cells in the second. Similarly, orientation of the robot cameras is characterized symbolically in the first model and numerically in the second. Other forced diversification resulted in merging some of the model attributes (that are variables that together describe the system state in the planning models) and modifying several constraint expressions. Experiments showed that this second model, although less time-performant than the first model, had similar fault-free results considering goal accomplishment for the considered workload [START_REF] Lussier | Fault Tolerant Planning in Critical Robots[END_REF].

Experiments and Validation

Our validation framework relies on simulation and fault injection. Simulation [START_REF] Joyeux | Simulation in the LAAS Architecture[END_REF]) is used since it is both safer and more practical to exercise the autonomy software on a simulated robot than on a real one. The autonomous system is based on an existing ATRV robot, and employs GenoM software modules interfaced with the simulated hardware. Fault injection is used since it is the only way to test the fault tolerance mechanisms with respect to their specific inputs, i.e., faults in planning knowledge. In the absence of any evidence regarding real faults, there is no other practical choice than to rely on mutations3 , which have been found to efficiently simulate real faults in imperative languages [START_REF] Daran | Software Error Analysis: a Real Case Study Involving Real Faults and Mutations[END_REF].

Workload

Our workload mimics the possible activity of a space rover. The system is required to achieve three subsets of goals: take science photos at specific locations (in any order), communicate with an orbiter during specified visibility windows, and be back at the initial position at the end of the mission.

To partially address the fact that the robot must operate in an open unknown environment, we chose to activate the system's functionalities in some representative situations resulting from combinations of sets of missions and worlds. A mission encompasses the number and location of photos to be taken, and the number and occurrence of visibility windows. A world is a set of static obstacles unknown to the robot (possibly blocking the system from executing one of its goals), which introduces uncertainties and stresses the system navigation mechanism.

We implemented four missions and four worlds, thus applying sixteen execution contexts to each mutation. Missions are referenced as gradually more difficult M1, M2, M3 and M4: M1 consists in two communications and three photos in close locations, whereas M4 consists in four communications and five far apart photos. Environments are referenced as worlds W1, W2, W3 and W4. W1 is an empty world, with no obstacles to hinder plan execution. W2 and W3 contains small cylindrical obstacles, whereas W4 includes large rectangular obstacles that may pose great difficulties to the navigation module, and are susceptible to endlessly block the robot path, irrespectively of any replanning or model switching.

In addition, several equivalent experiments are needed to address the non-determinacy of the experiments. This is due to asynchrony in the various subsystems of the robot and in the underlying operating systems: task scheduling differences between similar experiments may degrade into task failures and possibly unsatisfied goals, even in the absence of faults. We thus execute each basic experiment three times, leading to a total of 48 experiments per mutation. More repetition would of course be needed for statistical inference on the basic experiments but this would have led to a to-tal number of experiments higher than that which could have been carried out with the resources available (each basic experiment lasts about 20 minutes).

Faultload

To assess performance and efficacy of the proposed fault tolerance mechanisms, we inject faults in a planning model by random mutation of the model source code (i.e., in Model1 of Figure 4).

Five types of possible mutations were identified from the model syntax [START_REF] Crouzet | The SESAME Experience: from Assembly Languages to Declarative Models[END_REF]): (a) substitution of numerical values, (b) substitution of variables, (c) substitution of attribute4 values, (d) substitution of language operators and (e) removal of constraint relations. All in all, more than 1000 mutants were generated from the first model.

For better representativeness of injected faults, we consider only mutants that are able to find a plan in at least one mission (we consider that models that systematically fail would easily be detected during the development phase). As a simple optimization, given our limited resources, we also chose to carry out a simple manual analysis aimed at eliminating mutants that evidently could not respect the above criterion.

Recorded Data and Measurements

Numerous log files are generated by a single experiment: simulated data from Gazebo (including robot position and hardware module activity), output messages from GenoM modules and OpenPRS, requests and reports sent and received by each planner, as well as outputs of the planning process.

Problems arise however in trying to condense this amount of data into significant relevant measures. Contrary to more classic mutation experiments, the result of an experiment cannot be easily dichotomized as either failed or successful. As previously mentioned, an autonomous system is confronted with partially unknown environments and situations, and some of its goals may be difficult or even impossible to achieve in some contexts. Thus, assessment of the results of a mission must be graded into more than just two levels. Moreover, detection of equivalent mutants is complexified by the non-deterministic context of autonomous systems.

To answer these issues to some extent, we chose to categorize the quality of the result of an experiment with: (a) the subset of goals that have been successfully achieved, and (b) performance results such as the mission execution time and the distance covered by the robot to achieve its goals. Due to space constraints, we focus in the rest of this paper on measurements relative to the mission goals.

Results

We present in this part several experimental results using the evaluation framework previously introduced.

Experiments

Experiments were executed on i386 systems with a 3.2 GHz CPU and Linux OS. Fault-free experiments were first realized to assess the overhead of the proposed fault tolerance mechanisms. They were conclusive in showing that the proposed mechanisms did not severely degrade the system performance in the chosen activities [START_REF] Lussier | Fault Tolerant Planning in Critical Robots[END_REF]. These experiments also showed that results in world W4 must be treated with caution, as this world contains large obstacles that may cause navigation failures and block the robot path forever. As our work focuses on planning model faults rather than limitations of functional modules, we consider that success in this world relies more on serendipity in the choice of plan rather than correctness of the planner model. It is however interesting to study the system reaction to unforeseen and unforgiving situations that possibly arise in an open and uncontrolled environment.

To test the efficacy of the fault tolerance mechanisms and the FTplan component, we injected 38 faults in our first model, realizing more than 3500 experiments equivalent to 1200 hours of testing. We discarded 10 mutants that were unable to find a plan for any of the four missions. We believe that five of the remaining mutants are equivalent to the fault-free model. However, the non-deterministic nature of autonomous systems makes it delicate to define objective equivalence criteria. We thus include the results obtained with these five mutants, leading to a pessimistic estimation of the improvement offered by FTplan.

The 28 considered mutations consist of: three substitutions of attribute values, six substitutions of variables, nine substitutions of numerical values, four substitutions of operators, and six removals of constraints. The mutants were executed on two different robots: Robot1 uses our first model (with one injected fault), and Robot1/2 contains an FTplan component that uses successively our first model (with the same injected fault) and our fault-free second model.

Behavior in the Presence of Faults

We develop here the results of two mutations as examples of our experiments. In each case (Figure 5 and Figure 6), our results present four different measures of (lack of) robustness: (a-c) three failure proportions to reach the different types of goals in a mission (resp. photos, communications, and returns to initial position), (d) failure proportion of the whole mission (a mission is considered failed if one or more mission goals are not achieved), and a behavior clarification metric (e) the mean number of replanning operations observed during an experiment (in the case of Robot1/2, this number is equivalent to the number of model switches during the mission). Note that, in the absence of injected faults, both Robot1 and Robot1/2 are perfectly robust in worlds W1, W2 and W3, with zero failure proportions for all objectives and all missions.

Results for the first mutation, identified by the reference 1-39, are presented in Figure 5. This mutation causes an overly-constrained robot position during a camera shot. It thus results in the planner's inability to find plans for missions where photographs have to be taken in positions that do not respect the overlyrestrictive constraint (this is the case for missions M2 and M4). This example illustrates the significance of the system activity chosen for the evaluation: numerous different missions are necessary because faults can remain dormant in some missions. Since testing the practically infinite execution context is well nigh impossible, this example underlines the difficulty of testing and thus the interest of fault tolerance mechanisms to cover residual faults in the deployed planning models.

Figure 6 presents the results for mutation 1-589. The fault injected in this mutation affects only a movement recovery action of the planning model. Thus, contrary to the previous example, correct plans are established for all missions. However, as soon as a movement action fails, the planner is unable to find a plan allowing recovery of the movement, which causes failure of the system. This is particularly obvious in the case of missions M1 and M3, where short distances between photograph locations lead to a short temporal margin for the action movement. As the exact motion (taking into account obstacles) is not considered in the planning model, "goto" actions are susceptible to take longer than estimated, and can thus be be interrupted by the execution controller and considered failed, necessitating a recovery action. In missions M2 and M4, movements cover greater distances, resulting in larger temporal margins and thus fewer movement action failures. Robot1/2 tolerates this fault to some extent: completely in mission M2 and partially in mission M4. The high failure rate of mission M3 for Robot1/2 can be explained by a domino effect due to communication goals being given priority over photography goals. the fault is activated due to a failed movement action, FTplan switches to Model2 and requests a plan. However, a communication goal is now so near that the planner is unable to find a plan to achieve it, so it abandons goals of lesser priority, but to no avail. This example underlines two important issues: First, testing with numerous diversified missions and environments is once again pointed out, as the fault is not activated in several activities. Second, testing must be realized in an integrated system. Indeed, the original plans produced by the planner are correct, as well as the lower levels of the system. However, the planning model contains a serious fault that can cause critical failure of the system in some executions.

Fault Tolerance Efficacy

The general results, including all 28 mutations, are presented in Figure 7. These results give objective evidence that model diversification favorably contributes to fault tolerance of an autonomous system considering the proposed faultload: failure decreases for photo goals of 62% (respectively, 50% including W4), 70% (64%) for communication goals, 80% (58%) for return goals, and 41% (29%) for whole missions. Note, however, that the experiments show that RobotFT in the presence of injected faults is less successful than a single faultfree model (some goals are still missed, even when the constrained world W4 is omitted). This apparent decrease in dependability is explained by the fact that, in our current implementation, incorrect plans are only detected when their execution has at least partially failed, possibly rendering one or more goals unachievable, even after recovery. This underlines the importance of plan analysis procedures to attempt to detect errors in plans before they are executed.

Conclusion

We presented in this paper a component, based on diversification, that tolerates software development faults in planners. This component can use four detection mechanisms (watchdog timer, plan failure detector, online goal checker and plan analyzer), and two recovery policies (sequential planning and concurrent planning).

We also described its implementation in an existing robot architecture, using sequential planning associated with the first three error detection mechanisms.

To evaluate the performance overhead and the efficacy of our component, we introduced a validation framework using simulation of the robot hardware and fault injection by mutation of the planner declarative model. Previous experiments showed that the proposed component does not severely degrade the system performance in the chosen activities. In this article, we discussed example behaviors of the simulated robot in the presence of injected faults. In particular, several experiments demonstrated the necessity of integrated testing, and numerous missions and environments to validate models supposed to take decisions in open environments. We also presented overall results that show that the proposed component usefully improves the system behavior in the presence of model faults.

Several directions are open for future work. First, implementation of the plan analyzer detection mechanisms would allow better goal success levels to be achieved in the presence of faults, since it should increase error detection coverage and provide lower latency. The state of the art in planning already proposes several examples for off-line plan validation, but application for on-line validation is an open issue. Implementation of the concurrent planning policy and comparison with the sequential planning policy are also of interest. Moreover, note that the proposed mechanisms focus principally on the reliability of the system: its efficacy in goal accomplishment. Other fault tolerance mechanisms are also needed to guarantee safety of the system and its direct environment.

Figure 1 :

 1 Figure 1: Dependability tree (Avižienis et al. 2005) its presence is indicated by an error message or error signal. A fault is the adjudged or hypothesized cause of an error. Here, we focus particularly on development faults: faults that are unintentionally caused by man during the development of the system.The means to make a system dependable are regrouped in four concepts: (a) fault prevention, that is how to prevent the occurrence or introduction of faults, (b) fault removal , that is how to reduce the number or severity of faults, (c) fault tolerance, that is how to deliver correct service in the presence of faults, and (d) fault forecasting, that is how to estimate the present number, the future incidence, and the likely consequences of faults. Fault prevention and fault removal can together be considered as fault avoidance, that is the attempt to develop a system without faults. Fault tolerance and fault forecasting embody the concept of fault acceptance, in that they attempt to estimate and reduce the consequences of the remaining faults, knowing that fault avoidance is almost inevitably imperfect. The development of a dependable computing system calls for the combined utilization of these four techniques.

Figure 2 :

 2 Figure 2: Sequential Planning Policyan adverse environmental situation, and (b) some planners, even faulty, can still be efficient for some settings since the situation that activated the fault may have disappeared.It is worth noting that the choice of the planners, and the order in which they are used, is arbitrary in this particular example (line 6). However, the choice of the planner could take advantage of application-specific knowledge about the most appropriate planner for the current situation or knowledge about recently observed failure rates of the planners.With the second recovery mechanism the planners are executed concurrently. The main differences with respect to the algorithm given in Figure2are: (a) the plan request message is sent to every planning candidate, (b) when a correct plan is found, the other planners are requested to stop planning, and (c) a watchdog timeout means that all the planners have failed. The algorithm can be found in[START_REF] Lussier | Fault Tolerance in Autonomous Systems[END_REF].

  Figure 3: The LAAS architecture

Figure 5 :

 5 Figure 5: Results for mutation 1-39

Figure 6 :

 6 Figure 6: Results for mutation 1-589

Figure 7 :

 7 Figure 7: Impact of planner redundancy (with injected faults)

How to conclude on correctness of a program's outputs to selected test inputs?

An additional control component, R2C, is introduced in[START_REF] Py | Dependable Execution Control for Autonomous Robots[END_REF]. We have not considered it in this study since its current implementation is not compatible with our experimentation environment.

A mutation is a syntactic modification of an existing program.

Remember that, in the IxTeT formalism, attributes are the different variables that together describe the system state.


Benjamin Lussier

Matthieu Gallien

Jérémie Guiochet

Félix Ingrand

Marc-Olivier Killijian

David Powell

Fault Tolerant Planning for Critical Robots

Autonomous robots offer alluring perspectives in numerous application domains: space rovers, satellites, medical assistants, tour guides, etc. However, a severe lack of trust in their dependability greatly reduces their possible usage. In particular, autonomous systems make extensive use of decisional mechanisms that are able to take complex and adaptative decisions, but are very hard to validate. This paper proposes a fault tolerance approach for decisional planning components, which are almost mandatory in complex autonomous systems. The proposed mechanisms focus on development faults in planning models and heuristics, through the use of diversification. The paper presents an implementation of these mechanisms on an existing autonomous robot architecture, and evaluates their impact on performance and reliability through the use of fault injection.

Introduction

Autonomous systems cover a large range of functionalities and complexities, from robotic pets to space rovers, including elderly care assistants, museum tour guides, and autonomous vehicles. As successes arise in autonomous navigation, exemplified by Mars rovers and the clearing of the DARPA Grand Challenge [START_REF] Monterlo | Winning the DARPA Grand Challenge with an AI Robot[END_REF], complex autonomous systems that are able to choose and execute high-level actions without human supervision are not yet ready for real life applications. Indeed, one of the major drawbacks in the utilization of such systems is the difficulty to predict and validate their behavior. To increase the confidence that we may have in such systems so that they may be used in more critical applications, we consider in this paper the tolerance of residual development faults in planning models.

First, we introduce autonomous systems and specific aspects such as decisional mechanisms, robustness and planning. Second, we propose error detection and recovery mechanisms that are appropriate for planning to tolerate de-velopment faults in their application-dependent knowledge. Finally, we validate the proposed mechanisms through an experimental framework based on fault injection.

Dependability in Autonomous Systems

This section presents several aspects of autonomous systems relevant to their dependability. We present a definition of autonomy and give key aspects of architectures for autonomous robots.

Autonomy

A dictionary definition of "autonomy" is "the ability to act independently". However, in the field of robotics, this definition is insufficient since it does not enable a distinction between classic automatic systems, that simply apply preprogrammed reactions in response to the system's inputs (e.g., as in feedback control), and truly autonomous systems that seek to carry out goal-oriented tasks whose implementation details are not defined in advance, either by necessity (the input space is unbounded) or as a design strategy (to simplify the code). We adopt here the definition of autonomy given in [START_REF] Huang | Autonomy Levels for Unmanned Systems (ALFUS) Framework[END_REF]: "An unmanned system's own ability of sensing, perceiving, analyzing, communicating, planning, decision-making, and acting, to achieve its goals as assigned by its human operator(s) through designed humanrobot interaction (HRI). Autonomy is characterized into levels by factors including mission complexity, environmental difficulty, and level of HRI to accomplish the missions."

The level of autonomy of an autonomous system is often discussed in terms of its "robustness". Indeed, autonomous robots are intended to cope with uncertainty and non-nominal situations. A good or "robust" robot is understood to be one that can survive and fulfill its mission despite partial knowledge about its environment as well as unforeseen contingencies such as obstacles, rough terrain and failures. In this paper, we choose to distinguish between robustness and fault tolerance as follows:

Robustness is the ability of an autonomous system to cope with adverse environmental situations (lighting conditions, unexpected obstacles, etc.) while providing an acceptable service.

Fault Tolerance is the ability of an autonomous system to provide an acceptable service despite system faults (hardware failures, software bugs, etc.).

Autonomous System Architectures

Four architectural styles for designing autonomous robot systems are usually distinguished:

1. The sense-plan-act style is based on a closed loop of three components devoted respectively to sensing the environment (including the state of the robot itself), finding a plan to change the state of the environment to reach a goal state, and acting on the environment according to the plan. 2. The subsumption style allows several "behavior" components to simultaneously sense and act on the environment, with actions that can be prioritized or crossinhibited between different components. 3. The hierarchical style defines several abstraction levels with different real-time constraints, resulting in a layered architecture. 4. The multi-agent style considers a set of autonomous systems or agents immersed in the same environment and interacting to achieve their individual or shared objectives.

Whereas the sense-plan-act style has largely been abandoned (at least as the basis for a monolithic architecture) due to its poor real-time performance, the subsumption style is still commonly used in entertainment robots, such as Sony's Aibo™. The multi-agent style is now receiving considerable attention both as the basis for designing a taskable robot [START_REF] Muscettola | IDEA: Planning at the Core of Autonomous Reactive Agents[END_REF] and in the context of agent swarms with emerging "intelligence" [START_REF] Pearce | Using virtual pheromones and cameras for dispersing a team of multiple miniature robots[END_REF]. However, most practical robots currently adopt the hierarchical style, usually resulting in an architecture with three layers [START_REF] Gat | On Three-Layer Architectures[END_REF]: a decisional layer, an executive layer and a functional layer.

• The decisional layer is responsible for elaborating plans to reach operator-defined mission goals. The execution time of the decisional layer is often unbounded, due to the complexity of the involved solution space search processes, for which heuristics need to be used to render them tractable. • The executive layer is charged selects and sequences elementary actions that implement the high-level tasks included with the current plan. It reacts in real-time to errors raised by the functional layer, but reports unforeseen contingencies to the upper, decisional layer. • The functional layer interfaces with the hardware sensory and action devices. It may contain several reactive feedback control modules that operate asynchronously according to requests from the executive layer or in response to hardware interrupts.

Sometimes the executive layer is merged into either the decisional layer or the functional layer. Hierarchical architectures for autonomy include the RAX architecture developed by NASA as part of its Deep Space One project [START_REF] Muscettola | Remote Agent: To Boldly Go Where No AI System Has Gone Before[END_REF], Honeywell's CIRCA [START_REF] Musliner | World Modeling for the Dynamic Construction of Real-Time Control Plans[END_REF], JPL's CLARATy [START_REF] Volpe | CLARAty: Coupled Layer Architecture for Robotic Autonomy[END_REF] and the LAAS architecture [START_REF] Alami | An Architecture for Autonomy[END_REF] developed at LAAS-CNRS (the latter architecture will be described in more detail in 3.2.1). From a dependability viewpoint, tolerance of hardware faults is considered in some of these architectures [START_REF] Lussier | Fault Tolerance in Autonomous Systems: How and How Much[END_REF]. For example, the RAX architecture includes a model-based mode identification and reconfiguration (MIR) component specifically aimed at diagnosing and recovering from faults affecting hardware resources [START_REF] Muscettola | Remote Agent: To Boldly Go Where No AI System Has Gone Before[END_REF]. Indeed, autonomous system architectures provide an elegant framework for application-specific tolerance of hardware faults since, ideally, they can include the state of hardware resources within the "world state" taken into account when elaborating high-level plans. For development faults, apart from on-line checking mechanisms aimed at guaranteeing safety [START_REF] Py | Real-Time Execution Control for Autonomous Systems[END_REF], the focus has been largely been on fault avoidance approaches (rigorous design, and thorough verification and testing). For example, intensive testing was carried out on the RAX architecture [START_REF] Bernard | Remote Agent Experiment DS1 Technology Validation Report[END_REF]: six test beds were implemented throughout the development process, incorporating 600 tests. The authors of [START_REF] Bernard | Remote Agent Experiment DS1 Technology Validation Report[END_REF] underline the relevance of intensive testing, but acknowledge particular difficulties regarding autonomous systems, notably the problem of defining suitable test oracles. Given the inherent difficulty of testing autonomous systems, we believe that a tolerance approach with respect to residual development faults should be of considerable interest. Yet, to the best of our knowledge, such an approach has not been previously envisaged.

Deliberation and Decision

From our perspective, deliberation and decision are the key features of autonomy. Many different decisional capabilities have been studied and deployed on robots or other autonomous systems. Here, we discuss what distinguishes such decisional capabilities from other programmed functionalities.

Most decisional mechanisms boil down to some sort of search in a very large state space. In general, this search leads to a decision (a plan to reach a goal, a diagnosis, an action, etc). This search can be done either off-line or online, that is in advance to produce a precompiled data structure or on the fly while the system is running. It may reason about past states (as in diagnostic) or about future states (as in planning). It may have a limited horizon or, conversely, a very deep scope. But a key aspect is that the search needs to be efficiently guided to avoid a combinatorial explosion. As a result, a decisional mechanism can be complete (it is guaranteed to find a solution if one exists) or not (it can "miss it"), correct (solutions are always valid) or not (they are approximate), tractable (solutions are found in a polynomial time and space) or not.

Another important feature of decisional mechanisms is that they are organized in a way that makes a clear separation between the knowledge and the inference mechanism. The aim is to make the inference mechanism (e.g., a search engine) as generic and as independent as possible from the application. Conversely, the knowledge is domain-specific and typically specifies what states are reachable through the search process and what is the "best" next state from any given state. However, knowledge and inference mechanisms are often tightly linked in practice (e.g., heuristics that guide a search engine).

The implementation of decisional mechanisms relies on various formalisms (logic, neural networks, Markov models, constraints, simple temporal networks, etc.) and computational models (constraint-based programming, logic programming, heuristic search, dynamic programming, etc.).

The most common decisional functionalities deployed on autonomous systems are the following: planning, execution control, diagnosis, situation recognition and learning. In this paper, we focus particularly on planning, which is the activity of producing a plan to reach a goal from a given state, using given action models (e.g., the activity plan for the day of an exploration rover).

Planning

Planning is necessary in complex autonomous systems as a means to select and organize the robot's future actions to achieve specified high-level goals. We introduce here some generalities on planning in autonomous systems, before presenting dependability issues.

General Principle.

Planning can be implemented in several ways but, in practice, two approaches are preferred: search in a state space and constraint planning.

Search in a state space manipulates a graph of actions and states. It explores different action sequences from an initial state to choose the most suitable one to achieve given goals.

Constraint planning uses CSP 1 solving to determine a possible evolution of the system state that satisfies a set of constraints, some of which specify the system objectives. CSP solving is commonly an iterative algorithm assigning successively possible values to each variable and verifying that all constraints remain satisfied. particularly difficult since (a) equally correct plans may be completely different and (b) an unforeseen adverse environmental situation may completely prevent some goals from being achieved, thus ineluctably degrading the system performance, however well it behaves 3 . One way to address the latter issue is to define an oracle as a set of constraints that necessarily and sufficiently characterizes a correct plan: plans satisfying the constraints are deemed correct. Such a technique was used for thorough testing of the RAX planner during the NASA Deep Space One project [START_REF] Bernard | Remote Agent Experiment DS1 Technology Validation Report[END_REF], or in the VAL validation tool [START_REF] Howey | VAL: Automatic Plan Validation, Continuous Effects and Mixed Initiative Planning using PDDL[END_REF]. Extensive collaboration of application and planner experts is necessary to generate the correct set of constraints. A Failure Recovery Analysis tool is proposed in [START_REF] Howe | Improving the Reliability of Artificial Intelligence Planning Systems by Analyzing their Failure Recovery[END_REF] to ease model corrections during development.

Automatic static analysis may also be used to ascertain properties on planning models, whereas manual static analysis requires domain experts to closely scrutinize models proposed by planning developers. For example, the development tool Planware [START_REF] Becker | Model Validation in Planware[END_REF] offers facilities for both types of analysis.

Some work has also been done on evaluating planning dependability. A measure for planner reliability is proposed in [START_REF] Chen | On the Reliability of AI Planning Software in Real-Time Applications[END_REF], which compares theoretical results to experimental ones, showing a necessary compromise between temporal failures (related to calculability of decisional mechanisms) and value failures (related to correctness of decisional mechanisms). Later work [START_REF] Chen | On the Reliability of AI Planning Software in Real-Time Applications[END_REF] proposes concurrent use of planners with diversified heuristics to answer this compromise: a first heuristic, quick but dirty, is used when a slower but more correct heuristic fails to deliver a plan in time. To our knowledge, no other fault tolerance mechanisms have been proposed in this domain. We strongly believe, however, that such mechanisms are essential to provide more dependability in autonomous systems.

Fault Tolerant Planning

We investigate here how to tolerate design and implementation faults in planner models and heuristics. These mechanisms are particularly well adapted to hierarchical autonomous systems with a centralized planner at the decisional layer.

Principles

The general principle of the mechanisms we propose is to execute concurrently or sequentially several variants of the planner. The diversity lies in the different models and heuristics used by the variants.

3.1.1. Detection. Implementing error detection for decisional mechanisms in general, and planners in particular, is difficult [START_REF] Lussier | Fault Tolerance in Autonomous Systems: How and How Much[END_REF]. There are often many different valid plans, which can be quite dissimilar. Therefore, error detection by comparison of redundantly-produced plans is not a viable option. Thus, we must implement error detection by independent means. Here, we propose four complementary error detection mechanisms: watchdog timer, a plan analyzer, a plan failure detector and an on-line goal checking.

A watchdog timer is used to detect when the search process is too slow or when a critical failure such as a deadlock occurs. Timing errors can be due to faults in the planner model, in its search engine, or ineffectiveness of the search heuristics.

A plan analyzer can be applied on the output of the planner. A plan analyzer is an acceptance test (i.e., an on-line oracle) that verifies that the produced plan satisfies a number of constraints and properties. This set of constraints and properties can be obtained from the system specification and from domain expertise but it must be diverse from the planner model. This mechanism is able to detect errors due to faults in the planner model or heuristics, and in the planner itself.

An action failure detector is a classical mechanism used in robotics for execution control. Failure of an action which is part of the plan may be due to an unresolvable adverse environmental situation, or may indicate errors in the plan due to faults in the knowledge or in the decisional mechanism. Usually, when such an action failure is raised, the decisional mechanisms tries to repair the plan. When this is not possible, it raises a plan failure. We use these plan failure reports for detection purposes.

On-line goal checking verifies, when a plan has been executed, that every goal has been reached. These checks must be performed on-line but can be validated only when every action of the plan has been accomplished. This implies that the checker maintains an internal representation of the system state and of the goals that have been reached.

Recovery. We propose two recovery mechanisms, both using different planners based on diverse knowledge.

With the first mechanism, the planners are executed sequentially, one after another. The principle is given in Figure 1. Basically, each time an error is detected, we switch to another planner until all goals have been reached or until all planners fail in a row. Once all the planners have been used and there are still some unsatisfied goals, we go back to the initial set of planners. This algorithm illustrates the use of the four detection mechanisms presented in Section 3.1.1: watchdog timer (lines 8 and 21), plan analyzer (line 13), plan failure detector (line 15), on-line goal checking (line 3).

Reusing planners that have been previously detected as failed makes sense for two different reasons:

1. A perfectly correct plan can fail during execution due to an adverse environmental situation. 2. Some planners, even faulty, can still be efficient for some settings since the situation that activated the fault may have disappeared.

It is worth noting that the choice of the planners, and the order in which they are used, is arbitrary in this particular example (line 6). However, the choice of the planner could take advantage of application-specific knowledge about the most appropriate planner for the current situation or knowledge about recently observed failure rates of the planners.

With the second recovery mechanism, the planners are executed concurrently. The main differences with respect to the algorithm given in Figure 1 are:

1. The plan request message is sent to every planning candidate. 2. When a correct plan is found, the other planners are requested to stop planning. 3. A watchdog timeout means that all the planners have failed.

In this case, the choice of planner order is implicit: the first planner obtaining a plan is chosen. However, this could lead to the repeated selection of the same faulty but rapid planner. Some additional mechanism is thus required to circumvent this problem. For example, the planner selected during the previous round can be withdrawn from the set of candidates for the current round.

3.1.3. Coordination. From a dependability point of view, the fault-tolerance mechanisms have to be as independent as possible from the decisional layer, i.e., in this case from the planners. This is why we propose to handle both the detection and recovery mechanisms and the services necessary for their implementation in a middle-ware level component called FTplan, standing for Fault-Tolerant Planning.

This component has to integrate the fault tolerance mechanisms into the robot architecture. This implies essentially two features: providing communication and synchronization for the fault tolerance mechanisms, and coordinating the redundant planners.

To avoid error propagation from a possible faulty planner, FTplan should not take any information that comes from or depends on the planner themselves. The watchdog can easily be implemented from the operating system timing primitives. Action failure detection is performed at the execution control layer, so error reports can be obtained and reused at the FTplan level. A plan analyzer performs simple acceptance checks using rules expressed independently from the planners and their knowledge.

However, implementing an on-line goal checker without relying on information obtained through the planner is more tricky. FTplan maintains for this purpose its own system Whatever the particular recovery mechanism it implements, sequential or parallel, FTplan has to manage several planners. It needs to communicate with them, e.g., for sending plan requests or for updating their objectives and system state representations before replanning. It also needs to be able to control their life cycle: start a new instance or even stop one when it takes too long to produce a plan.

Implementation

We present here the implementation of the proposed mechanisms. We introduce the target architecture and then give some implementation details about the FTplan component.

LAAS architecture.

The LAAS architecture is presented in [START_REF] Alami | An Architecture for Autonomy[END_REF], and some recent modifications have been proposed in [START_REF] Lemai | Interleaving Temporal Planning and Execution in Robotics Domains[END_REF]. It has been successfully applied to several mobile robots, some of which have performed missions in real situations (human interaction or exploration). It is composed of three main components4 as presented in Figure 2: GenoM modules, OpenPRS, and IxTeT.

The functional level is composed of a set of GenoM modules (which are automatically generated), each of them offering a set of services, which perform computation (e.g., trajectory movement calculation) or communication with physical devices (sensors and actuators). After delivering the service, a report is sent to the requester to report success or failure of the action, along with other action-specific information. Data exchange between modules is performed through the use of "posters", each of which is a shared memory space attached to a module, and readable by the others.

The procedural executive, OpenPRS, is in charge of decomposing and refining plan actions into lower-level actions executable by functional components, and executing them. This component links the decisional component (Ix-TeT) and the functional level. During execution, OpenPRS reports any action failures to the planner, in order to re-plan or repair the plan. As several IxTeT actions can be performed concurrently, it has also to schedule sequences of refined actions. This higher level includes the deliberative capability of producing task plans. IxTeT, is a temporal constraint planner as presented in Section 2.3.1. To build a plan, the planner combines high level actions. Each action is described in a model file used by the planner as a set of constraints on attributes (e.g., robot position), resources (e.g., energy consumption), numeric or temporal data (e.g., action duration). Then, a valid plan is calculated combining a set of actions in such a way that they are conflict-free and they fulfill the goals. The description of actions in the planner model is critical for the generation of successful plans and thus for the dependability of the robot as a whole.

Fault Tolerant Planner Implementation.

The fault tolerance principles presented in Section 3.1 have been implemented in a fault tolerant planner component as presented in Figure 3. This component replaces the original component "Planner" presented in Figure 2. The FTplan component is in charge of communicating with OpenPRS as the original planner does. To be consistent with the current implementation, FTplan uses the same technologies as OpenPRS and IxTeT for communication (i.e., a client library of a MessagePasser component).

The current version of FTplan implements the sequential redundant planner coordination algorithm presented earlier (Section 3.1, Figure 1) with two IxTeT planners. A se- The watchdog timer is launched at each start of planning. As soon as a plan is found before the time limit (40 seconds in our implementation), the watchdog is stopped. If timeout occurs, FTplan stops the current IxTeT, and sends a plan request to the other IxTeT planner, until a plan is found or all planners have failed.

On-line goal checking is performed after each action successfully executed by OpenPRS and that can result in a goal being reached (for instance a camera shot). This checking is carried out by analyzing the system state at the end of an action, and checking that no inconsistent actions have been executed simultaneously.

In the actual implementation, FTplan checks every 10ms if there is a message from OpenPRS or one of the IxTeT planners. In case of an action request from a planner or an action report from OpenPRS, FTplan updates its system representation before transmitting the request. If the request is a plan execution failure (the system has not been able to perform the actions of the plan), then FTplan launches a re-plan using the sequential mechanism. If the request indicates that the actions are finished, then FTplan checks if the goals have been reached.

Mechanism Validation

We present here the validation process we have followed to assess the performance and efficacy of the proposed fault tolerant mechanisms. We discuss first a validation framework that extensively uses simulation and fault injection, then present experimental results.

Framework for Validation

Our validation framework relies on fault injection and simulation. Fault injection is needed to confront the system with representative faults in planning knowledge. There are no extensive studies of faults in autonomous system knowledge, but previous work on imperative languages [START_REF] Daran | Modélisation des comportements érronés du logiciel et application à la validation des tests par injection de fautes[END_REF] has demonstrated that mutations 5 may efficiently simulate real software faults. The autonomous software is exercised on a simulated robot rather than a real one. This is motivated by two main reasons:

• A large number of experiments is required to perform a significant evaluation; experiments on real systems usually need more time to be executed, and are more difficult to automate. • The behavior of the robot may be hazardous during an experiment; as we inject faults into it, we cannot predict its behavior, which may cause damage to itself or its direct surroundings.

We now introduce successively the targeted software architecture, the workload, the faultload, and the readouts and measurements we obtain from system activity. The robot simulator 6 is used to simulate the physical world and the actions of the autonomous system; it takes as input a file describing the environment of the simulation (mainly a list of static or dynamic obstacles containing their position, and the physical description of the robot) and executes the movement of the robot and dynamic obstacles, and possible interactions between objects.

The Pocosim library [START_REF] Joyeux | Simulation in the LAAS Architecture[END_REF] is a software bridge between the simulated robot (executed on Gazebo) and the software commands generated by the GenoM modules: it transforms commands to the actuators into movements or actions to be executed on the simulated robot, and relays the sensor inputs that Gazebo produces from the simulation. 5 A mutation is a syntactic modification of an existing program. 6 Our autonomous system, based on an existing ATRV robot, employs eight GenoM modules, that can be categorized into three groups:

• SICK and RFLEX are modules compiled with the Pocosim library and interfaced with Gazebo simulated hardware. SICK commands the laser proximity sensor of the robot, while RFLEX controls wheels and odometry. • NDD, ASPECT and POM are software modules that make use of SICK and REFLEX to implement navigation and obstacle avoidance. • CAMERA, PLATINE and ANTENNA are modules controlling components that are not simulated in Gazebo: their code source has been modified to provide a simple behavioral simulation. CAMERA controls the stereo-cameras of the robot, PLATINE controls the pan and tilt unit on which the cameras are fixed, and ANTENNA simulates a communication unit.

The upper layer of the LAAS architecture executes as presented in the previous chapter. Two different models are used with the IxTeT planners. The first model was thoroughly tested and used on a real ATRV robot; we use it as primary model and as target for fault injection. We specifically developed the second model through diversification of the first: for example, the robot position is characterized numerically in the first model and symbolically in the second.

4.1.2. Workload. Our workload mimics the possible activity of a space rover. The system is required to achieve three subsets of goals: take science photos at specific locations (in any order), communicate with an orbiter during specified visibility windows, and be back at the initial position at the end of the mission.

To partially address the fact that the robot must operate in an open unknown environment and to activate the system's functionalities as broadly as possible, we combine several sets of mission and worlds. A mission encompasses the number and location of photos to be taken, and the number and occurrence of visibility windows. A world is a set of static obstacles unknown to the robot (possibly blocking the system from executing one of its goals), which introduces uncertainties and stresses the system navigation mechanism.

We implemented four missions and four worlds, thus applying sixteen execution contexts to each mutation. Missions are referenced as gradually more difficult M1, M2, M3 and M4: M1 consists in two communications and three photos in close locations, whereas M4 consists in four communications and five far apart photos. Environments are referenced as worlds W1, W2, W3 and W4. W1 is an empty world, where no unspecified obstacles hinder plan execution. W2 and W3 contains small cylindrical obstacles, whereas W4 includes large rectangular obstacles that may pose great difficulties to the navigation module, and are susceptible to endlessly block the robot path.

In addition, several equivalent experiments are needed to address the non-determinacy of the experiments. This is due to asynchrony in the various subsystems of the robot and in the underlying operating systems: task scheduling differences between similar experiments may degrade into task failures and possibly unsatisfied goals, even in the absence of faults. We thus execute each basic experiment three times, leading to a total of 48 experiments per mutation. More repetition would of course be needed for statistical inference on the basic experiments but this would have led to a total number of experiments higher than that which could have been carried out in the time available (each basic experiment lasts about 20 minutes).

Faultload.

To assess performance and efficacy of the proposed fault tolerance mechanisms, we inject faults in a planning model by mutation of the model source code. Five types of possible mutations were identified from the model syntax:

• Substitution of numerical values: each numerical value is exchanged with members of a set of real numbers that encompasses (a) all numerical variables in all the tasks of the model, (b) a set of specific values (such as 0, 1 or -1), and (c) a set of randomly-selected values. • Substitution of variables: since the scope of a variable is limited to the task where it is defined, numerical (resp. temporal) variables are exchanged with all numerical (resp. temporal) variables of the same task.

• Substitution of attribute values7 : values are exchanged with other possible values in the range of the attribute. • Substitution of language operators: in addition to classic numerical operators on temporal and numerical values, the IxTeT formalism employs specific operators, such as "nonPreemptive" (that indicates that a task cannot be interrupted by the executive). • Removal of a constraint relation: a randomly selected constraint on attributes or variables is removed from the model.

Substitution mutations were automatically generated using the SESAME tool [?]. Using an off-line compilation, this tool detects and eliminates binary equivalent or syntactically incorrect mutants. Removal of random constraint relations was carried out through a PERL script and added to the mutations generated by SESAME. All in all, more than 1000 mutations were generated from the first model.

For better representativeness of injected faults, we only choose to consider mutants:

• that are able to find a plan in at least one mission (we consider that models that systematically fail would easily be detected during the development phase), • whose results (with and without FTplan) are different to those of the fault-free original model (if the results are similar, we consider that the fault had no impact in the chosen execution contexts).

To augment the number of relevant mutants in our experiments, mutant selection was carried out in two phases: first a random selection in one of the five considered types of mutation, second a simple manual analysis aimed at eliminating mutants that trivially do not respect the above criteria.

4.1.4. Records and Measurements. Numerous log files are generated by a single experiment: simulated data from Gazebo (including robot position and hardware module activity), output messages from GenoM modules and Open-PRS, requests and reports sent and received by each planner, as well as outputs of the planning process. Problems arise however in trying to condense this amount of data into significant relevant measures. Contrary to more classic mutation experiments, the result of an experiment cannot be easily dichomotized as either failed or successful. As previously mentioned, an autonomous system is confronted with partially unknown environments and situations, and some of its objectives may be difficult or even impossible to achieve in some contexts. Thus, assessment of the results of a mission must be graded into more than just two levels. Moreover, detection of equivalent mutants is complexified by the non-deterministic context of autonomous systems

To answer these issues to some extent, we chose to categorize the quality of the result of an experiment with: (a) the subset of goals that have been successfully achieved, and (b) performance results such as the mission execution time and the distance covered by the robot to achieve its goals. Due to space constraints, we focus in the rest of this paper on measurements relative to the mission goals.

Results

We present in this part several experimental results using the evaluation framework previously introduced. Experiments were executed on i386 systems with 3.2 GHz CPU and the Linux OS. We first study the performance cost of the proposed mechanisms, then present their efficacy in tolerating injected faults. We focus particularly on two systems: a non-diversified LAAS robot using just our first model (referred to as Robot1), and a diversified LAAS robot with FTplan using our first and second model (referred to as RobotFT).

Performance.

To determine the overhead of the proposed fault tolerance mechanisms, we first concentrate on supposed fault-free models, and study the impact of FTplan on the system behavior and temporal performance. Figure 6 shows the observed failure proportions for Robot1, Robot2 8 and RobotFT.

First, the mean numbers of replanning operations ob-8 Same as Robot1, but using the second model instead of the first.

served during one experiment are listed 9 Second, five failure proportions are represented graphically: failure of the mission (that indicates that one or more mission goals was not achieved), failure of the planner (that is a crash or a process hang), and failure to reach the three different types of goals (photos, communications, return to initial position). Note that results in W4 must be treated with caution, as this world contains large obstacles that may completely block the robot path. As such, success in this world relies more on serendipity in the choice of plan rather than correctness of the planner model. It is however interesting to study the system reaction to unforeseen and unforgiving situations that possibly arise in an open and uncontrolled environment. Note that these results show that different models give rise to different failure behaviors: particularly in W4, the three systems fail differently.

W4 set aside, results are globally very good: Robot1 and RobotFT succeed in all their objectives, while Robot2 fails a few objectives in M3, and all its return objectives in M4W1. These failures may be attributed to a larger set of constraints in this model that may be costly in performance, and underestimated distance declarations. The mean activity time of the systems (that is the time until the system stops all activity in a mission) are 404 seconds for Robot1, 376 seconds for Robot2, and 405 seconds for RobotFT. Time performance-wise, the three systems are thus roughly equivalent.

Although the results are globally positive, showing that FTplan's main execution loop does not negatively impact goal achievement or performance, they are still insufficient to assess the overhead of planner switches as very few occurred in these fault-free experiments. To stress this aspect, we used a version of IxTeT without the optimizing functionality of plan repair: any failed action systematically leads to complete replanning, with an additional planner switch in the case of FTplan. This version was tested on two systems: Robot1NR and RobotFTNR 10 . Model 1 was used as both models of FTplan, in order to focus on the cost of the coordination mechanisms rather than on actual recovery. Results are presented in Figure 7.

We effectively see that there are many more replannings (and thus planner switches) than in the previous experiments (a mean per experiment of 8.3 against 0.3 for Robot1NR, and 8.9 against 0.4 for RobtFTNR). M1W2 appears as a singularity for RobotFTNR as after a few minutes of execution, the IxTeT planner finds no solution in its current situation. We believe that this is to an elusive bug in either the model, FTplan, or the IxTeT planner 11

Figure 7. Effect of additional replanning

Apart from this singularity, RobotFTNR only fails more objectives than Robot1NR in the over-stressing W4 execution contexts, as well as the complex M4W3. Setting aside W4 (and the M1W2 singularity), the mean activity time of the systems is this time 4194 seconds for Robot1NR and 4744 seconds for RobotFTNR, indicating an overhead of 13%. Including W4, the time is 6837 seconds for Robot1NR and 8027 seconds for RobotFTNR, indicating an overhead of 17%. We deem these results as quite acceptable considering the negative impact of discarding plan repair.

Efficacy.

To test the efficacy of the proposed mechanisms and the FTplan component, we injected 39 faults in our first model, realizing more than 3500 experiments equivalent to 1200 hours of testing. We discarded 10 mutants that were unable to find a plan for any of the four missions 12 We believe that five of the remaining mutants are equivalent to the fault-free models. However, the nondeterministic nature of autonomous systems makes it delicate to define objective equivalence criteria. We thus include the results obtained with these five mutants, leading to a conservative measure of the efficacy of model diversification.

The 29 considered mutations are categorized in the following manner: three substitutions of attribute values, six substitutions of variables, ten substitutions of numerical values, four substitutions of operators, and six removals of constraints. The mutants were executed on Robot1 and RobotFT. The results are presented in Figure 8.

These results give objective evidence that model diversification favorably contributes to fault tolerance of an autonomous system: improvement of 48% for photo goals, 32% for communication goals, and 27% for returns goals. Note, however, that RobotFT in the presence of injected faults is less successful than a single fault-free model. This apparent decrease in dependability is easily explained by the fact that incorrect plans are only detected when their execution has failed, possibly rendering one or more goals unachievable, despite recovery. This underlines the importance of studying appropriate plan analysis procedures to attempt to detect errors in plans before they are executed.

Conclusion

To our knowledge, the work presented in this paper is the first proposition of fault tolerant mechanisms based on diversified planning models. We proposed a component providing error detection and recovery appropriate for faulttolerant planning, and implemented it in the LAAS architecture. This component can use four detection mechanisms (watchdog timer, plan failure detector, on-line goal checking and plan analyzer), and two recovery policies (sequential planning and concurrent planning). Our current implementation is that of sequential planning associated with the first three error detection mechanisms.

To assess the performance overhead and the efficacy of the proposed mechanisms, we developed a validation framework that exercises the software on a simulated robot platform, and carried out what we believe to be the first ever mutation experiments on declarative models. These experiments were conclusive in showing that the proposed mechanisms do not severely degrade the system performance, yet significantly improve the system behavior in the presence of model faults.

There are many directions for future research. First, implementation of a plan analyzer should allow better goal success levels to be achieved in the presence of faults since it should increase error detection coverage and provide lower latency. Implementation of the concurrent planning policy and comparison with the sequential planning policy are also of interest. Moreover, we would like to evaluate diversification on planning heuristics rather than just mod-els and investigate also the additional detection capabilities of recent additions to the LAAS architecture [START_REF] Py | Real-Time Execution Control for Autonomous Systems[END_REF]. Finally, many more experiments are needed to improve the statistical relevance of the results. As experiments are time and performance costly, the use of a large computer grid would drastically improve the number of experiments that could be executed in reasonable time.

Figure 1 .

 1 Figure 1. Sequential Planning Policy

Figure 3 .

 3 Figure 3. Fault tolerant planner

Figure 4 .

 4 Figure 4. A fault tolerance scenario quence diagram illustrating implemented principles is presented in Figure 4. Currently, the plan analysis function is empty (it always return true) so error detection relies solely on just three of the mechanisms presented in Section 3.1.1: watchdog timer, plan failure detection, and online goal checking.The watchdog timer is launched at each start of planning. As soon as a plan is found before the time limit (40 seconds in our implementation), the watchdog is stopped. If timeout occurs, FTplan stops the current IxTeT, and sends a plan request to the other IxTeT planner, until a plan is found or all planners have failed.On-line goal checking is performed after each action successfully executed by OpenPRS and that can result in a goal being reached (for instance a camera shot). This checking is carried out by analyzing the system state at the end of an action, and checking that no inconsistent actions have been executed simultaneously.In the actual implementation, FTplan checks every 10ms if there is a message from OpenPRS or one of the IxTeT planners. In case of an action request from a planner or an action report from OpenPRS, FTplan updates its system representation before transmitting the request. If the request is a plan execution failure (the system has not been able to perform the actions of the plan), then FTplan launches a re-plan using the sequential mechanism. If the request indicates that the actions are finished, then FTplan checks if the goals have been reached.

4. 1 . 1 .

 11 Software Architecture. Our simulation environment is represented in Figure 5. It incorporates three elements: an open source robot simulator named Gazebo, an interface library named Pocosim, and the components of the LAAS architecture already presented in section 3.2.1.

Figure 5 .

 5 Figure 5. Simulation environment

Figure 6 .

 6 Figure 6. Impact of FTplan on performance

Figure 8 .

 8 photos comms returns

  .

	#replan
	Robot1NR	3	6.3	6.3	14.6	5.6	4.3	2.3	5.6	10	9	10	25	4.6	6.3	8	11
	RobotFTNR	3.6	2	4.6	25.6	4	2	6.3	13.6	10	9.6	8.3	20.6	6.6	4.3	9.3	12.6
	mission	100% 66% 33%
	planning	100% 66% 33%
	returns	100% 66% 33%
		100%
	comms	75% 50% 25%
		100%
	photos	75% 50% 25%
			W1	W2	W3	W4	W1	W2	W3	W4	W1	W2	W3	W4	W1	W2	W3	W4
	Robot1NR		M1			M2			M3			M4

¡

RobotFTNR

How to conclude on correctness of a program's outputs to selected test inputs?

For example, cliffs, or some other feature of the local terrain, may make a position goal unreachable.

An additional robustness component, R2C, is introduced in[START_REF] Py | Real-Time Execution Control for Autonomous Systems[END_REF]. We have not considered it in this study since its current implementation is not compatible with our experimental environment.

In the IxTeT formalism, attributes are the different variables that together describe the system state.

In the case of RobotFT, this number is equivalent to the number of planner switches during the mission.

Robot1 No Repair and RobotFT No Repair

However, the same experiment with a RobotFTNR using the first and second models gives successful executions, suggesting that the bug lies in our modified version of IxTeT.

In this case, FTplan gives the same results as the fault-free model2: nearly perfect success rates in W1, W2 and W3.


Catherine Pellenq

Suzan Gunn

Janessa Graves

Mohamed Vaqas

Mental health of child workers

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

3. The mental health of working children Brick kiln workers have also low self-esteem (80% are never proud of their work, 73% feel they do not have the skills needed to do the job well). They are likely to experience stress (60% feel tired because of long or heavy work, get bored at work doing the same thing, 82% have no free time). They may be suffering more injuries from lack of supervision (72% feel nobody watches over them to make sure they do not get hurt, 68% feel no one teaches them what to do and how to do). Low personal agency: they feel unable to influence what is happening to them (66% feel that they cannot choose what to do or not to do). .420

CONCLUSIONS

As a result of this study, it is obvious that there is a negative impact of early brick kiln work on psychosocial development. There is also some indication, however, that other variables such as sex, country, age, work intensity, schooling, familial and social support may modulate these effects to some extent but further work is required to demonstrate this conclusively. This evidence-based study provides new rationale and impetus for parents, brick kiln operators, and policy makers who seek to remove children from this work. This conclusion is derived from the global analysis of the data (and is confirmed by regression analyses not presented here). There are also indications of interacting effects of other variables.

For example, our data indicate that, compared with other countries, Afghanistan shows considerable difference between working and non-working children on negative emotions. These results show that IPAC is a valid tool for measuring psychosocial well-being of working children. It can be used in other settings and with other occupations.

  control study of the brick manufacturing industry in four countriesInternationally, brick kilns employ tens of thousands of children. Due to extreme poverty facing families who work in this industry, child labor in this sector has been challenging to eliminate. If work has well known effects on physical health of the children, does it affect their mental health as well? One reason that there is little hard evidence of the impact of work on psycho-social development of children is because there has been no methodology for assessing it. This cross-national, field-based study was conducted by the International Labour Organization in four countries -Afghanistan, Bangladesh, Nepal, and Pakistan -to address this issue. OBJECTIVES 1. developing and testing a questionnaire that can be used cross-culturally and by non-professionals to assess the psychosocial health of working children 2. determining the nature and extent of the impact of work on children's psychosocial functioning and development by comparing working children with nonbetween working and non-working children on the three last psychosocial factors (variance analysis)

  As for the country variable, there are indications in our data of interactional effects between psychosocial factors and sex for the working children: eg. girls have lower self-esteem at work (except in Pakistan).

  Negative emotionsDo you get very angry and often lose your temper?.723Do you get into fights or quarrels easily?.531 Do you think back about all the bad things that have happened to you? .443 Maltreatment Have you been severely punished for mistakes made at your work? .788 Do you get scolded, or criticized or made to feel small or stupid? .685 Do you people reject or tease you or call you names? , economic level, migration status, ethnic, social or linguistic group. Catherine.pellenq@ujf-grenoble.fr Woodhead, M. 2004. Psychosocial impacts of child work: A framework for research, monitoring and intervention. -demog Age, sex, schooling, family work Duration, other work, domestic service health Injuries, illness, incidents, fatigue psychosocial Stress, self esteem, supervision at work. Emotional, maltreatment, personal security, personal agency, social integration, anxiety, hope and helplessness 1. Validation of the tool 38 items were kept; the reliability for the tool was quite good (alpha of Cronbach >.80) and varies among countries from .71 to .87. A Principal Component Analysis (Varimax after rotation) identified 6 main factors: 3 concerning all children, 3 concerning only working children.

  NON-WORKING PEERS, CHILD BRICK KILN WORKERS FEEL SIGNIFICANTLY LESS SECURE AND EXPERIENCE MORE NEGATIVE EMOTIONS AND MALTREATMENT

ACKNOWLEDGEMENTS

This study was funded by the International Labour Organization and the collaborators in this study come from: Laboratoire Sciences Education, Grenoble University, France* International Labour Organization, Geneva, Switzerland** Washington State University, Pullman, USA*** Punjab University, Lahore, Pakistan****

Marginal means of negative emotions

Marginal means of self-esteem