Due to the future development of robotic autonomous systems in human environment, the fault tolerance paradigm will be a central issue in robotics. This article presents a survey of fault tolerance concepts, means and implementations in robotic architectures.

I. INTRODUCTION

Step by step fault tolerance in autonomous systems becomes a key challenge for the next decades. As point out in [START_REF]HYCON2 -NoE leaders[END_REF], systems and control science must be able to propose in the near future efficient control strategies optimizing the system's behavior to accomplish intending functions, while satisfying performance requirements and minimizing negative effects (resources consumption, safety behavior, etc.). But the increasing complexity of autonomous systems evolving in open, complex, unstructured and dynamic environment and interacting with vulgum pecus humans implies that the realization of sophisticated missions in a reliable way seems to currently be a fantasy. Fault tolerance integration will be a major part of the answer to the development of reliable and secure autonomous systems. The software aspect related to control architecture will be an important constituent of the fault tolerance deployment.

This paper is based on some relevant works and analysis concerning robots reliability [START_REF] Carlson | How UGVs physically fail in the field[END_REF], dependable concepts [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF], fault tolerance in engineering [START_REF] Zhang | Bibliographical review on reconfigurable fault-tolerant control systems[END_REF] [START_REF] Isermann | Fault-Diagnosis Systems : An Introduction from Fault Detection to Fault Tolerance[END_REF] [6] [START_REF] Venkatasubramanian | A review of process fault detection and diagnosis: Part II: Qualitative models and search strategies[END_REF] [START_REF] Venkatasubramanian | A review of process fault detection and diagnosis: Part III: Process history based methods[END_REF], fault tolerance in autonomous (robotic) systems [START_REF] Lussier | Tolérance aux fautes dans les systèmes autonomes[END_REF] [10] [START_REF] Lussier | Fault tolerance in autonomous systems: How and how much?[END_REF] [12] [START_REF] Durand | Proposition d'une architecture de contrôle adaptative pour la tolérance aux fautes[END_REF], and fault tolerance issues [START_REF] Steinbauer | On the evaluation and certification of the robustness of autonomous intelligent systems[END_REF] [START_REF] Carlson | Technical report for the safety security rescue research center[END_REF].

The next section presents through a wide analysis of on-the-field missions, the existing practical limitations of mobile robot reliability. Some basic definitions concerning dependability are given section III, with discussion about faults categories and location. Then section IV reminds the fault tolerance principles and section V exposes some of the main techniques used in control engineering. Next, sections VI and VII deal with fault tolerance in robotics. Methods really deployed in robotics are presented and analyzed before glancing at some robotic control architectures. Finally the conclusion highlights some important issues for fault tolerance integration for autonomous robotic systems.

II. FAULT TOLERANT ROBOTS: A

FANTASY! For many years J. Carlson works on fault tolerance in mobile robotics [START_REF] Carlson | How UGVs physically fail in the field[END_REF] [15] [START_REF] Carlson | Analysis of how mobile robots fail in field environments[END_REF] [17] [START_REF] Carlson | Follow-up analysis of mobile robot failures[END_REF]. In [START_REF] Carlson | How UGVs physically fail in the field[END_REF] a detailed analysis of Unmanned Ground Vehicles in the field missions is realized. This study covers 24 different robots (15 models), from 3.6 kg (Micro Tracs from Inuktun © ) to more than 27 tons (Panther army tank)! These robots are developed by 7 manufacturers. The concerned applications are Urban Search and Military Operations in Urban Terrian. The analysis concerns mainly on the field missions like during the World Trade Center disaster or for demining in Bosnia. Depending on the robot type, the communication with a distant operator is ensured using wired or wireless means.

The Urban and Rescue missions analyze shows that Inuktun © robots have a MTBF equal to 6.1 hours and an availability ratio of 90% because that encountered faults remain minors and easy to repair. Irobot © robots have approximately the same MTBF but the availability ratio was only equal to 36% because most of the failures are serious and hard to repair. The army robot mission analysis shows that there are only 1.16 failures per day, but that most of them (95%) are terminal for the mission.

It must be mention that the timing granularity of the mission data collection is not always known. For the World Trade Center missions, where a low granularity is available, 1.4 minor failures are observed per minute! Concerning the physical failures location and impact, Figure 1 shows the synthetic diagram proposed by Carlson in [START_REF] Carlson | How UGVs physically fail in the field[END_REF]. It summarizes the range probability of the physical components observed

Fault Tolerance in Control Architectures for Mobile Robots:

Fantasy or Reality? D. Crestani, K. Godary-Dejean Laboratoire Informatique Robotique Microélectronique de Montpellier Université Montpellier Sud de France -CNRS {godary, crestani}@lirmm.fr during the studied missions and their impact on the mission success.

The failures encountered during the different analyzed missions are of several types. The most common ones are the effectors' failures. For example, pinion gear collecting dirt and debris, tracks work off their wheels.

Sensors failures concern occluded camera, incorrect lighting, lack of depth perception, hard external conditions inducing moisture, dirt or mud on the lenses. Power failures are sometimes encountered due to low batteries or fuel problems (level, fuel filters). The control system failures are often encountered. It is a critical origin inducing unresponsive robot, uncontrolled behavior or system shutdown. The solution is to reboot the system. The communication is also a critical function because the wireless communication remains problematic in the field (availability, bandwidth) like for the World Trade Center and the impact of its structural steel. Another result is that failures have an important impact on the mission success since most of them are terminal. This detailed analysis shows that the overall robot reliability is quite low with 6 to 20 hours of MTBF. Moreover it demonstrates that mobile robots must cope with many faults and are not very autonomously fault tolerant. This section presents some accepted definitions used in the dependability and security communities [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF], and then clarifies the robotic point of view.

III. BASIC CONCEPTS

2) Concepts in robotics

Depending on the fault location Lussier in [START_REF] Lussier | Tolérance aux fautes dans les systèmes autonomes[END_REF] [START_REF] Lussier | Fault tolerance in autonomous systems: How and how much?[END_REF] proposes to distinguish two concepts:

• Robustness: Restrict the fault tolerance of the treatment of adverse situations arising due to the variability of the autonomous system environment (unexpected obstacle, lighting variability, etc.). • Fault tolerance: Concerns only the ability to deliver a correct service according to faults affecting the autonomous system itself (hardware or software fault). Figure 2 explains the way leading from a fault to a failure. During design or operational phases, systems are necessarily affected by internal or external (coming from the environment) faults. So a fault is a malicious entity which, once activated, creates an error. This error is propagated through the system until a failure occurs in the system service. If the system is composed of several synchronized sub-systems, the failure of one subsystem service could become a fault for the following sub-system. In robotics, human and physical faults are usually distinguished (Figure 3). Human faults concern system development and interaction faults, whereas physical faults are decomposed into effector, sensor, power, control system and communication faults. It is important to point out that a fault occurrence can only be observed by the user when a failure is detected. So, from Figure 2 it is easy to understand that many (sub-)systems can be affected during the error propagation without external signal of failure. This observation puts in light that a failure is not necessarily a fault. Thus, it is crucial to be able to detect (detectability) as soon as possible a fault activation and to deploy efficient diagnosis mechanisms to get back to the original fault.

3) Fault Location

In [START_REF] Steinbauer | On the evaluation and certification of the robustness of autonomous intelligent systems[END_REF] an in-depth analysis of autonomous systems faults is proposed. Faults are spread through the environment, the autonomous system and its environment awareness (Figure 4). The following types can be distinguished: A fault tolerant autonomous system would be able to detect and react to all these possible encountered faults.

IV. FAULT TOLERANCE PRINCIPLES Zhang [START_REF] Zhang | Bibliographical review on reconfigurable fault-tolerant control systems[END_REF] defines a Fault Tolerant Control System (FTCS) as a control system, which is able to automatically maintain the system stability and an acceptable performance when component failures occur.

To reach these objectives, FTCS must generally implement 4 main principles:

• Fault Detection: To detect that there is something wrong in the system and that a fault has occurred somewhere. • Fault Isolation: To decide which component is faulty and its location in the system. • Fault Identification: To identify the fault and its severity. • Fault Recovery: To adapt the system controller structure, according to the identified fault, to maintain the system stability and an acceptable performance. In the literature the fault isolation and identification steps are often merged into the single word diagnosis.

These last principles allow the fault tolerance execution. However, it must be notice that to be able to detect a fault, it is necessary to be conscious that this fault can occur. Therefore, fault forecasting is an inescapable and preliminary step, which cannot be avoided before undertaking a fault tolerance process. These general principles have generated an important corpus of scientific researches concerning Fault Detection and Diagnosis (FDD) in control engineering over the last decades. Most of them can potentially be used for robotic purpose. The data-based oriented methods don't need an a priori knowledge about the system behavior. They only require a large amount of historical data to extract a knowledge base which is used by the diagnosis system. Expert systems, neural networks using pattern recognition, or multivariate statistical techniques like principal component analysis can be used for example. The data-based methods can easily handle a large amount of data and are mainly used to control industrial processes. They are rarely employed in robotics where a model-based knowledge of the system can be easily addressed and the amount of data is limited.

B. Recovery

Usually, passive and active fault tolerant approaches can be distinguished for recovery.

Passive approaches don't need to previously have a fault diagnosis. Robust control techniques like the quantitative feedback theory, the CRONE control, the H 1 synthesis or the adaptive control are used to design a controller ensuring that the control-loop remain stable and efficient from a performance point of view. Unfortunately these methods can only deal with few system's faults.

Active techniques need to know which fault affects the system to adapt the controller design while preserving the stability and a graceful performance. Two main reconfiguration strategies can be used. On the first hand some predefined control laws can be selected to correct the impact of identified faults. Then approaches using multiple models and variable gain commands can be applied. On the second hand, to react to the occurrence of a fault, an on-line controller synthesis can be realized. Active recovery approaches allow a better fault coverage than passive methods.

C. Conclusion

For the development of fault tolerant robotics, the works dedicated to control engineering are not able to address all issues that must be considered: • It is difficult to ensure that all the proposed approaches always satisfy the real time treatment of a fault occurrence. This point is central for mobile robotic in a dynamic environment. • The tolerant control-loops integrating FDD and recovery issues are efficient to deal with sensors or actuators faults. But they are not able to consider faults related to high-level knowledge.

• Despite the efficiency of the control engineering recovery mechanisms, the proposed answers are not flexible enough to manage the situations which must be handled during complex missions. So, the software aspect is the main dimension to be considered to develop real fault tolerant mobile robots. This is the place where the fault tolerant principles must be integrated and managed. The control architecture provides more flexibility, expendability and adaptability capabilities than a pure oriented computer engineering approach.

VI. FAULT TOLERANCE IN CONTROL

ARCHITECTURES: A FANTASY Efficient autonomous robotics needs to merge planning capabilities with reactive behaviors. Hybrid control architectures decomposed in planning (deliberative), executive and behavioral (reactive) layers are often used. Component oriented development permits to address fault prevention issues.

A. Fault Tolerance principles in control architectures

1) Fault Detection and Diagnosis principles

In [START_REF] Lussier | Tolérance aux fautes dans les systèmes autonomes[END_REF] [10] [START_REF] Lussier | Fault tolerance in autonomous systems: How and how much?[END_REF], four basic mechanisms are identified to implement FDD in autonomous robots architectures.

• Timing checks are frequently introduced for timing fault detection. They supervise robot's functionalities liveness using timers and watchdog principles. • Reasonableness checks are commonly used in robotics to verify the correctness of system's variables according to algorithms constraints or manufacturer specifications • Safety bags checks are also frequently implemented in robotic architectures to monitor the system outputs and blocking erroneous values to avoid unsafe behavior. • Monitoring for Diagnosis is the most attractive axis for fault detection leading to many publications (see a survey in [START_REF] Duan | Fault diagnosis and fault tolerant control for wheeled mobile robots under unknown environments: A survey[END_REF]). This domain is strongly connected to the control engineering techniques previously presented section V. Mainly dedicated to hardware fault detection, software redundancy using modelbased approaches is often used to detect sensors or effectors failure.

2) Recovery principles [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF] presents a large analyze of the recovery mechanisms proposed in computer science which could be classified in error and fault handling. Some of them are used in robotics. Focusing on robotic control architectures, [START_REF] Lussier | Fault tolerance in autonomous systems: How and how much?[END_REF] and [START_REF] Durand | Proposition d'une architecture de contrôle adaptative pour la tolérance aux fautes[END_REF] identify the following recovery means:

For the executive level:

• Specific treatment: When a known situation is encountered, the hardware context or the concerned algorithm is changed to treat the identified fault. • Action retry: The failed action is restarted expecting that its execution context will get better.

• Action retry using functional redundancy:

The failed action is restarted using a functional alternative (if it exists). • Modality switching: The failed action is restarted using the most efficient and operational functioning mode. It is an extension of the previous principle, as it needs to have a degree of redundancy. The redundancy can be software or hardware.

For the planning level:

• Re-planning: It consists of developing a new plan from the current situation facing adverse situation, to the expected final situation. This method is time consuming and the robot must be placed into a safe state during re-planning. • Plan repair: This is a faster solution than replanning, where the initial plan is locally modified to overcome the encountered adverse situation.

For the mission level:

• Autonomy adaptation: When recovery fails at executive and planning levels, a human assistance can be envisaged to pursue the mission. In this last case, an interesting solution is the adaptation of the autonomy level of the robot [START_REF] Durand | Proposition d'une architecture de contrôle adaptative pour la tolérance aux fautes[END_REF].

B. Control architectures and fault tolerance

From [START_REF] Shakhimardanov | Research and development of fault tolerance and robustness in robotics: A survey[END_REF] [13], this part analyses the fault tolerance aspect in some classical robotic control architectures and frameworks. The main results are summarized in Table1.

CLARATY [START_REF] Nesnas | CLARAty: Challenges and Steps Toward Reusable Robotic Software[END_REF] has been developed by the NASA to propose an efficient robotic software for space mission. It is organized in two layers: the Decision layer, which integrates the planning and executive functionalities; and a Functional layer for interfacing with hardware platform. For fault tolerance purpose, each component may integrate a state machine to monitor the state evolution, and uses internal or external estimators for state variables estimation. These means allow implementing diagnostic and recovery mechanisms.

If the conflict cannot be handled locally, it is considered by higher-level modules up to the planner level. The CLEaR (Closed-Loop Execution and Recovery) system is a hybrid controller coordinating goal-driven and event-driven approach. CLEaR integrates CASPER (Continous Activity Scheduling, Planning, Execution and Replanning) and TDL (Task Description Language) systems. TDL can implement exception handling like action retry. CASPER implements plan repair recovery.

CoolBOT [START_REF] Domingez-Brito | CoolBOT: A Component-Oriented Programming Framework for Robotics[END_REF] is a component-oriented system dedicated to robotic purposes. Each component implements a states machine and communicates by forwarding information via event and data ports. Exception handling permits to switch into a set of error states. Hierarchical component variables adaptation, backward error recovery and functional redundancy can be used to manage error handling.

COTAMA FFT (COTAMA For Fault Tolerance) [START_REF] Durand | Proposition d'une architecture de contrôle adaptative pour la tolérance aux fautes[END_REF] is a component-oriented architecture dealing with fault tolerance. Observation modules are used to monitor the identified faults occurrence. A dedicated diagnosis module, using residues analysis, identifies the fault and updates a database of the modules' state. According to the detected fault severity and the available resources, the recovery is engaged using the modality switching principle and autonomy adaptation.

The LAAS architecture [START_REF] Alami | An architecture for autonomy[END_REF] is dedicated for autonomous robots. It is a 3 layers architecture. The decisional level is dedicated to plans generation and execution. At the execution control level, the R2C component checks the validity of the requests of the decisional layer [START_REF] Py | Real-time execution control for autonomous systems[END_REF]. Finally, the functional level proposes modules generated with the GenoM tool, and offers services to hardware and software resources. The BIP software framework [START_REF] Bensalem | Toward a more dependable software architecture for autonomous robots[END_REF] allows the design of a controller enforcing low-level safety properties (ordering or synchronization violations, data freshness). R2C checks that modules correctly interact. It can verify some safety rules and may stop unacceptable actions. IxTeT planner component [START_REF] Lemai-Chenevier | IxTeT-eXeC: Plani fication, reparation de plan et contrôle d'exécution avec la gestion du temps et des ressources[END_REF] implements re-planning and planrepair facilities. Moreover, FTplan [START_REF] Lussier | Tolérance aux fautes dans les systèmes autonomes[END_REF] manages some planning faults and proposes re-planning alternatives.

MIRO [START_REF] Utz | Miro -Middleware for mobile robot applications[END_REF] is an object-oriented middleware dedicated for mobile robot applications. It is structured into 3 architectural layers, interwoven with two layers of the CORBA middleware. The device layer provides interface for robots sensors and actuators. The service layer provides active service abstractions for sensors and actuators. The framework layer specifies the robotic functionalities. In this architecture there are some handling capabilities and a list of exceptions indicating hardware, service or load problems. Miro also defines action patterns organized in behavior hierarchies and guards. They notify external event occurrences which can potentially induce a dynamic reconfiguration.

ORCA [START_REF] Makarenko | ORCA: Components for Robotics[END_REF] is a component-oriented open-source framework for robotics. Components implement algorithms and hardware interfaces. They communicate using push, pull or query patterns via TCP/IP or UDP protocols. Simple checks can be done at low-level, like correct action realization, If an action fails, a cleanup is simply realized. At application level some dynamic reconfiguration capabilities using redundant components are also possible.

ORCCAD (Open Robotic Controller CAD) [START_REF] Simon | ORCCAD, a framework for safe robot control design and implementation[END_REF] is a dedicated framework for the development of robotic applications. The two basics concepts allow the definition of a robotic action. The Robotic Task (RT) which models basic robotic actions and where control aspects are dominants. Robotic Procedure (RP) merges Robotic Tasks to construct more complex actions. RT and RP can be composed hierarchically in structure of increasing complexity. In RT the user can explicitly detailed the exceptions he wants to deal with and the corresponding recovery procedures: Parameters adaptation of a control law, new RT application, safe mode engaged. In [START_REF] Simon | Hardware-in-the-loop test-bed of an Unmanned Aerial Vehicle using Orccad[END_REF] dedicated diagnosis modules are used to detect sensors and motor faults. Moreover, synchronous programming allows to verify crucial properties like safety (any fatal exception handled), liveness (RP reaches its goal in a nominal situation), conflict detection, behavior verification.

IDEA

(Intelligent Distributed Execution Architecture) [START_REF] Muscettola | IDEA: Planning at the core of autonomous reactive agents[END_REF] is an agent based architecture. All agents possess the same structure and behavior (reactive planner, plan data-base, domain model, plan runner). Agent communicates using the communication services of the underlying middleware. More recently a Remote Agent functionality including mode recovery has been introduced. IDEA introduces timelines for the variables monitored. An inconsistency is reported to the Plan Data base which can engaged recovery action within the specified time boundaries. Nonnominal conditions handling can be introduced in the agent's central model. The flexibility of planning capacities (Minimal/long horizon and deliberative planning) can improve the system's responsiveness to external adverse events using local re-planning Recovery using pre-compiled alternative solutions (scripts) is possible.

PROCOSA [START_REF] Barbier | PROCOSA: A software package for autonomous system supervision[END_REF] is an asynchronous Petri net-based software package dedicated for autonomous systems control and monitoring. Petri nets allow the description of the execution logic of the autonomous systems behaviors including nominal and disruptive phases. A Petri net player executes the associated procedures and manages the communications. The Petri net model permits to verify some structural and behavioral properties. PROCOSA takes care of unique faults occurrence and engages adapted recovery means including operator help. However the treatment remains limited and not systematic.

RA (Remote Agent) architecture [START_REF] Muscettola | Remote Agent: to boldly go where no AI system has gone before[END_REF] has been developed for autonomous spacecraft missions at NASA. RA is based is based on a 3 layered abstract machine: a planner/scheduler which plans actions and schedules resources; an executive layer which executes the defined plan; and a mode identification (MI) and mode reconfiguration (MR) layer used for diagnosis and fault recovery. MI is dedicated for observation and MR for recovery. MR is responsible for exiting from a failure mode using component repairing or reconfiguration. Replanning with degraded capabilities can also be envisaged. So RA was design for fault tolerance.

The NASA 3T [START_REF] Schreckenghost | Three tier architecture for controlling space life support systems[END_REF] is a 3 layered architecture. The decisional layer controls the long term capabilities. A mediating layer achieves transitions toward the reactive skills layer. Depending on the experimental applications different fault tolerant capacities have been developed. Remote Agent principle has also been integrated in some 3T architecture experiments. Concerning task scheduling faults a generalized scheduler/reschedule is able to reschedule a task (start, stop, resources, time constraints) if a disruptive event occurs. For the skill layer it is possible to detect that an expected state has not be reached. The skills layer is also able to manage a loss of communication using watchdogs and keep some sub-systems in safe mode. The mediating layer is able to handle nonnominal situations and uses reconfiguring skills or re-setting to manage their detection. Moreover the 3T architecture achieves safety behavior for different autonomy modes (teleoperated, semiautonomous and autonomous).

C. Fault tolerance in control architectures: Current limitations

First of all it must be noticed that all the presented control architectures propose some means to implement fault tolerance. However many limitations can be identified:

• None of the proposed architectures but COTAMA FFT seem to integrate explicitly a preliminary fault forecasting step into the design process. Without a systematic off line approach of fault identification the fault tolerance will be drastically limited. There is a lake of global integration of fault tolerance principles which are generally spread into the software. There is a need of detection, diagnosis and recovery reification in the control architecture design. A framework for fault tolerance integration would be useful.

VII. FAULT TOLERANCE FOR MOBILE

ROBOTS: FROM FANTASY TO REALITY Most of the time, the fault tolerance paradigm is not the central issue that is considered in the research works. Thus, to develop fault tolerant robotics, a set of open issues using Fault Detection Isolation and Recovery principles (FDIR) can be identified. [START_REF] Steinbauer | On the evaluation and certification of the robustness of autonomous intelligent systems[END_REF] [15]: The development of fault tolerant robotics is clearly domain (environment), safety and cost dependant. The set of possible encountered faults is quite different for airplanes, robotic manipulators or autonomous mobile robots. The safety consideration is different when FDIR concerns a domestic or a companion robot. The associated development costs are not comparable. Actually due to a lack of self-confidence in architectural FDIR principles, critical systems [START_REF] Olive | FDI(R) for satellite at Thalès Alenia space: How to deal with high availability and robustness in space domain?[END_REF] (space, avionic) often implement a large hardware redundancy to deal with the fault tolerance issue. Fault tolerant control architectures would be a nice and flexible answer for FDIR. The design of such architecture needs to be able to propose and develop efficient and reliable methodologies, concepts and software. [START_REF] Steinbauer | On the evaluation and certification of the robustness of autonomous intelligent systems[END_REF]: The development of fault tolerant robotics needs to consider the fault tolerance issue from the beginning of the system design. A fault tolerance control architecture cannot be the unique answer. Software, but also hardware and control aspects must be considered together to implement the most efficient solutions for reliability. So specific approaches for FDIR integration and design would be proposed.

Application domains for FDIR

Design for FDIR

Fault tolerant control architecture design [START_REF] Durand | Proposition d'une architecture de contrôle adaptative pour la tolérance aux fautes[END_REF]:

The previous analysis demonstrates that, generally, there is an important lack of fault tolerance consideration into control architecture.

Fault forecasting is an essential and initial step which must be realized to develop fault tolerant architectures. It is central to identify the most significant faults the robotic systems could encounter within its application domain.

Fault detection and particularly monitoring for diagnosis must consider more than actuators and sensors faults to deal with situation awareness. Moreover, noisy sensors problem (false or missed detection) must be overcome to enhance sensors' data reliability.

Fault diagnosis advanced techniques must be really implemented in control architectures. Moreover, these methods have to be more relevant to prepare an efficient recovery. They must be able to distinguish faults, errors and failures detection and to deal with single and multiple faults occurrences.

Fault recovery must be spread over the mission, executive and planning architectural layers using for example adaptive autonomy, modality or replanning capacities. Furthermore, the development of adaptive behaviors could also consider the mission performance aspects (trajectory accuracy, speed, safety, etc.).

For us, the design of a fault tolerant control architecture needs to reify the fault detection, diagnosis and recovery principles. Moreover, as we present in [START_REF] Durand | Proposition d'une architecture de contrôle adaptative pour la tolérance aux fautes[END_REF] and develop further, it is also crucial to propose a fault tolerant methodology integrating the forecasting step, and guiding the developer during the control architecture design. [START_REF] Steinbauer | On the evaluation and certification of the robustness of autonomous intelligent systems[END_REF]: A key point to achieve fault tolerance is to be able to define, like for integrated circuits "a certified" fault coverage. So domain, objective, and comparable public metrics must be defined. As well, realistic and reproductive scenarios must be elaborate considering pure simulation, hardware-in-the-loop, laboratory or in-the-field environments.

FDIR metrics and benchmarks

VIII. CONCLUSION

This article proposes a general survey of the fault tolerance issue in mobile robotics, focusing on control architectures. It puts in light that this objective needs to develop design methodologies for FDIR, merging hardware, control engineering and software knowledge. Due to its flexibility and its adaptability, the design of fault tolerant control architectures would be a central answer for fault tolerance needs. However, nowadays, the fault tolerance principles are neglected in the control architecture design. So an important effort for fault tolerance integration must be realized. Moreover, to be industrially accepted, fault tolerant metrics must be proposed and evaluate for specific application domains and contexts of mobile robots.

Fig. 1

 1 Fig. 1 Component failure probability (from [2])

  This part of the article reminds the basic concepts related to dependability, and discusses about fault and failure definition, taxonomy and location.A. Basic definitions of dependable concepts (from[START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF])

B.

  Failure and fault: Definition, taxonomy and location 1) Definitions • Failure (service failure): Event that occurs when the delivered service deviates from the correct service. • Error: Part of the system's state that may lead to a failure. • Fault: Cause of an error.

Fig. 2 .

 2 Fig. 2. From fault to failure (from [3])

2 )

 2 Taxonomy Many quite similar faults taxonomies have been proposed in the literature [2] [3] [13] [17].

Fig. 3

 3 Fig. 3 Murphy faults taxonomy (from [17])

  Concerning the environment:• Exogenous event fault: The environment might change in an unpredictable way. For example the change can be caused by another agent, indirectly by the autonomous system itself or an inadequate model of the environment. Concerning the autonomous system: • Hardware fault: Effectors, sensors, embedded control hardware faults. • Software fault: Design and implementation flaws, run-time faults. • Knowledge fault: The embedded knowledge about the world (initial or updated) is inappropriate with the mission, leading to inadequate decisions. Concerning the environment awareness: • Execution fault: The real outcome of an action is not the expected one. • Sensing fault: Sensors observations are erroneous due to sensors shortcomings or perception algorithms limitations.

Fig. 4

 4 Fig.4Autonomous system faults (adapted from[START_REF] Carlson | Follow-up analysis of mobile robot failures[END_REF])

V

  . FAULT TOLERANCE IN CONTROL ENGINEERING: EFFICIENT BUT UNSUFFICIENT Fault Detection and Diagnosis require an interdisciplinary expertise. Many interesting and complete bibliographical overviews have been proposed [4] [5] [6] [7] [8]. A. Fault detection and diagnosis Generally two main classes of FDD methods are identified: model-based and data-based methods. The quantitative model-based methods, widely used in robotics, are mainly based on analytical software redundancy. Many approaches performing signal processing techniques have been proposed for fault detection: state estimation observers or Kalman filters based approaches, parameter estimation oriented techniques or parity spaced oriented methods.

•

  In most of the architectures, fault detection and identification are roughly spread into the code.

	Few research works have addressed the fault
	tolerance as a central issue in control architecture.
	There is no structured reasoning guiding their
	implementation.
	• Except for RA and COTAMA FFT the
	diagnosis mechanisms are not explained in the
	literature. This opacity denotes that the
	diagnosis phase remains basic. It seems that
	two important shortcomings are implicitly
	realized. First, there is no distinction made
	between faults and failures detection. Secondly,
	only unique fault occurrence is considered.
	These limitations hardly limit the relevance of
	the recovery phase.
	• Generally, few types of recovery methods are
	proposed in a given architecture. No
	architecture proposes recovery solutions at
	executive, planning and mission levels.
	Recovery mechanisms are rarely formalized
	like in COTAMA FFT, RA, PROCOSA or
	ORCCAD. Furthermore, the most common
	recovery solution is to put the robot in a safe
	state, without proposing most efficient recovery
	solutions.
	• Finally, few architecture complete fault
	tolerance using fault removal techniques
	(LAAS, ORCCAD).


Erol Özgür

Nicolas Bouton

Nicolas Andreff

Philippe Martinet

Dynamic Control of the Quattro Robot by the Leg Edges

This paper discusses variable selection for the efficient dynamic control of the Quattro parallel robot through an inverse dynamic model expressed by means of leg orientations. A selection is made within a group of variables where each can imply the state of the robot. Besides, in this work, steering a parallel robot dynamically using its self-projection onto the image plane (where the edges of the lower-legs are exploited in control) is proposed and validated for the first time. In the light of the realistic control simulation, the formative points of better control of the Quattro robot are figured out.

I. INTRODUCTION

In an industrial automated plant, robots are the key machines for the typical applications such as pick-and-place, high-speed machining, etc., and nowadays the parallel robots meet the demands of production bands well since they are faster and potentially have better stiffness and accuracy than the serial robots [START_REF] Merlet | Still a long way to go on the road for parallel mechanisms[END_REF].

However, they are structurally very complex to be controlled precisely so as to exploit their full potential. There have been many studies in this area in the last two decades (see [START_REF] Merlet | Parallel Robots[END_REF] for a literature review) which have offered conceptually generic solutions to the problem. The solution of this difficult problem was simply looked for in the following conventional scenario, where it has usually been treated in separate modules, namely sensing, modeling and control, respectively.

In sensing, since the robots are directly equipped with motor encoders that measure the articular positions, many researchers tried to develop models by hovering around this shallow information. As a result, the models were very long, time consuming (difficult to warrant the real-time constraints) and hard to understand. Therefore, inevitably, this urges one to offer simplifications [START_REF] Vivas | Predictive functional control of a parallel robot[END_REF] and to turn a blind eye to some of the modeling errors in the mechanism, thus giving simplified and fast [START_REF] Nabat | On the Design of a Fast Parallel Robot Based on Its Dynamic Model[END_REF] but less accurate new models for control. Consequently, this pushes the community to look for sophisticated control algorithms in order to compensate for the loss of accuracy.

It can easily be noticed from the above scenario that each module has poorly evolved having the negative effects of the others on the way to the precise control of a parallel robot. So, what would be a better approach which directly considers the objective? If one looks over the whole problem from a wide perspective, the answer can be seen in the firstname.lastname@lasmea.univ-bpclermont.fr selection of an "efficient variable set" [START_REF] Paul | Motion Variables Leading to Efficient Equations of Motion[END_REF]. This variable set should let the modules be right in step with one another, namely, make them converge to a unified single system that governs the parallel robot right on target. In this paper, the control module has been explored further in detail so as to incorporate it smoothly into and complete the desired unified system, where the integration of sensing and modeling parts have already been discussed in our previous works [6],

[7], [8]. The expected contributions of this work are: (i) to propose a dynamic control through the leg contour pixels (edgels) of a parallel robot for potentially better performance, (ii) to avoid using an artificial pattern in dynamic tracking, while the parallel robot turns itself into a pattern, (iii) to increase the robustness of dynamic control since the imagespace is resistant to errors, and (iv) to give intuitions that might shed light on a complete image-based (2D) dynamic modeling and control of parallel robots. The remainder of this paper is organized as follows: Section II gives background information on the geometry and the notation of the Quattro robot (Fig. 1) and briefly talks about the leg orientations based inverse dynamic model. In Section III, we discuss both the choice of the sensor-signal and the control-law used to steer the robot efficiently. In Section IV, we give place to comparative results and their annotations. Finally, Section V concludes the paper with some remarks and highlights the future research directions.

II. BACKGROUND

A. The Quattro

The Quattro is composed of four identical kinematic legs, that carry the articulated moving platform. Each of the 4 kinematic legs is actuated from the base by a revolute motor, located at P i , and has two consecutive bodies (an upperleg and a lower-leg) linked with each other at A i . (see Fig. 1). The lower-legs are connected to the articulated moving platform at B i . Notation:

• i = 1, 2, 3, 4 denotes the kinematic legs and j = { l, r} denotes the left and right edges of the slim and cylindrical shaped lower-leg rods

{[A i1 B i1 ] , [A i2 B i2 ]}.
• Vectors are denoted with boldface characters and, in addition, unit vectors are underlined.

• V e = [ ẋ, ẏ, ż ] T and ω z are, in turn, the translational velocity and the angular velocity around the fixed axis z e of the end-effector E. Thus, the Cartesian pose velocity of the end-effector frame can be represented by:

χ = ẋ ẏ ż ω z T B. Dynamics
In previous works [6], [7], an algebraic expression for the inverse dynamic of the Quattro robot was derived through the following procedure:

• Khalil [9], intuition of splitting the parallel robot into subsystems: kinematic legs and a moving platform.

• Kane [10] and Newton-Euler, to calculate the generalized forces on the decomposed parts of the parallel robot. • d'Alembert / principle of virtual work, to combine all the works and write the final equations of motion. yielding the inverse dynamic model (IDM) by means of the lower-leg orientations x ai as below:

Γ = IDM( ẍai , ẋai , x ai ) = A(x ai ) ẍai + h( x ai , ẋai ) (1)
where Γ ∈ ℜ 4×1 is the motor torque vector. The reason for writing the inverse dynamic model as a function of such variables is not only its simple closed-form expression but is also related to sensor-based control issues.

III. SENSOR-BASED DYNAMIC CONTROL

A. Background

The standard method for dynamic control is the so-called computed-torque control (CTC) [11] which linearizes and decouples the control. Its well-known form, adapted to serial mechanisms, is derived from the Lagrange formulation of the dynamic model:

Γ = A(q) q + h(q, q) IDM(q, q, q) (2)
Under the assumption that  and ĥ are correct estimates of A(q) and h(q, q), one can build a control torque of the form:

Γ = Â u q + ĥ (3)
where u q is an auxiliary control vector, equivalent to an acceleration in the joint-space. Indeed, inserting such a control in the direct dynamic model yields a closed-loop equation of the form:

q = A(q) -1 Â ≈I u q + A(q) -1 ( ĥ -h(q, q) ≈ 0 ) (4)
which is a second-order linear-system and can therefore be controlled by any linear controller, the latter being often chosen as a proportional-derivative plus feedforward (PD+FF) controller in the joint-space. Now, for parallel kinematic manipulators, this control is hardly used because it is computationally heavy (partly because one has to solve for the forward kinematic problem at each iteration). It is therefore often discarded to the profit of simplified controllers (the worst being a PID controller in the joint-space) which can be shown [START_REF] Paccot | A review on dynamic control of parallel kinematic machines: theory and experiments[END_REF] to have poor properties as far as linearization and decoupling are concerned.

The essential drawback of this joint-space computedtorque control is its reliance on a dynamic model expressed in joint-space. An alternative to this is to set up a Cartesian-space computed-torque control according to many recommendations for expressing the dynamic model in the Cartesian-space [START_REF] Dasgupta | A general strategy based on the Newton-Euler approach for the dynamic formulation of parallel manipulators[END_REF], [START_REF] Callegari | Dynamics modelling and control of the 3-rcc translational platform[END_REF]:

Γ = A(χ) u χ + h(χ, χ) (5)
where u χ is now equivalent to a Cartesian acceleration and (χ, χ) are the Cartesian pose and velocity of the end-effector to be estimated. This is often considered as a second-order linear-model and controlled with a PD+FF [11], [START_REF] Paccot | A review on dynamic control of parallel kinematic machines: theory and experiments[END_REF], [START_REF] Callegari | Dynamics modelling and control of the 3-rcc translational platform[END_REF], although there exits a formal non-linear control based on the Lie group structure of SE( 3) [START_REF] Bullo | Proportinal Derivative (PD) Control on the Euclidean Group[END_REF]. This control is a state feedback in the case where the inverse kinematic problem has a single solution. However, despite the fact that the dynamic model is lighter, the estimation of χ and χ is not easy and, consequently, one would like to set up a sensor-based computedtorque control:

Γ = A(s) u s + h(s, ṡ) (6)
where u s is now equivalent to the second-order timederivative of the sensor signal s. This control encompasses the former two since a joint-space computed-torque control can be seen as a sensor-based control where the sensor signal is given by the joint encoders and a Cartesian-space control as a sensor-based control where the sensor-signal is the end-effector pose. In fact, the theoretical condition for the validity of a sensor-based control is that there exists a diffeomorphism (i.e. a differentiable bijective mapping) between the sensor-space and the state-space of the system [START_REF] Samson | Robot Control: the Task Function Approach[END_REF]. That is where it hurts in parallel kinematics, especially when one considers only the actuator positions for sensing: the mapping is neither bijective (several solutions to the forward kinematic problem) nor differentiable (singularities of any type). Then, which sensor-signal shall be used?

B. Choosing a sensor signal

The choice of the sensor is influenced by the state of the technology, but more relevantly, since the latter is ever improving, by the control algorithm and, in turn, the control algorithm depends on the model it is built upon. In correlation with the proposed methodology, this comes down to examining the variables in models and to determining how to get them efficiently. There are three kinds of variables involved in the models:

• Variables related to the actuators: { x pi , ẋpi } • Variables related to the end-effector: { x e , ẋe } • Redundant variables: { x ai , ẋai } Which kind, if any, will best conform to an efficient control? Of course, if one can sense all of these variables, the problem is completely solved, except for itching calibration and data coherence issues. For the same reason, a combination of two of the three kinds is temporarily left out of the discussion here (although there might lie the practical optimum).

The variables related to the actuators definitely have to be discarded, since they face up the forward kinematic problem, which is not only a non-linear but also a square problem. The variables related to the end-effector are not necessarily the answer due to either their technological cost (laser) or algorithmic cost (pose estimation in computer vision). The latter case is nevertheless better than the forward kinematic problem since the non-linear problem of pose estimation is not square but over-constrained, which makes it numerically more robust, and since it relies on optics rather than on mechanical parts.

Focusing on the use of redundant variables only and having inspirations of metrological redundancy [START_REF] Baron | The on-line direct kinematics of parallel manipulators under joint-sensor redundancy[END_REF], we have found out that they provide us with a linear formulation of the whole problem. Indeed, once all the variables are known, the proposed models make only use of linear algebra. The variables related to the actuators and the end-effector can linearly be expressed from the known variables related to the lower-legs and the known constant parameters [6].

Consequently, as soon as one can sense the redundant variables, one can derive a control using only linear algebra. And so, the only remaining question is how to measure those redundant variables. Our answer is, unsurprisingly, to observe by vision the associated mechanical elements in the kinematic legs, preferably as revolute cylinders, as we did it in kinematics [8].

C. Sensor-based computed-torque control law

Since we discuss the control law in different variable spaces than the linearized-dynamics in [START_REF] Merlet | Still a long way to go on the road for parallel mechanisms[END_REF] where ẍai = u, it will be appropriate to define a pseudo-system s = ω. Then, the error function, f e , which is expressed in terms of current s and desired s * sensor signals, can simply be denoted as follows:

e = f e ( s * , s ) = s *s

and assuming a second-order diffeomorphism between x ai and s is:

ẋai = L s ṡ ⇒ ẍai = Ls ṡ + L s s (8)
where L s is the differential kinematic model between the sensor signal and a lower-leg unit orientation vector. One can write the control u using (8) and pseudo-control ω as below: where f u is a function of a differential kinematic model L s and its derivative (computed numerically), of the derivative of the sensor signal s and the pseudo-control ω, respectively. Afterwards, one only needs to measure / compute the { s, ṡ, L s , Ls }. One should prove as well that linearizeddynamics ( ẍai = u) is equivalent to pseudo-system (s = ω) in order to bring the error down to zero. Subsequently, one can rewrite the linearized-dynamics using the right sides of the last two expressions in ( 8) and (9) as follows:

u = f u ( L s , Ls , ṡ, ω ) = Ls ṡ + L s ω (9)
Ls ṡ + L s s = Ls ṡ + L s ω (10)
and this will boil down to the state of pseudo-system (s = ω), on condition that the good approximations of the models exist and (sω) does not lie in the null-space of L s . Finally, the pseudo-control ω can be set up as below:

ω = K P e + K D ė + s * ( 11
)
where K P and K D are the proportional and derivative positive controller gains, respectively. This yields a second-order convergence in s. In the following three subsections, we will be deriving the control laws with different sensor-signals for comparative purposes of dynamic control.

1) Image-space computed-torque control (IS-CTC):

On the image plane, the left and right fitted line equations in pixel-units p n ji ∈ ℜ 3×1 of the edgels of a projected lowerleg rod (see Fig. 2) of the Quattro parallel robot are exploited as sensor signals in control (see Fig. 3). The error vector for each leg, e i ∈ ℜ 6×1 , is written over them as follows:

e i = e li e ri = p n * li - p n li p n * ri - p n ri ( 12
)
where { p n * li , p n * ri } are the left and right desired projectionlines of a lower-leg rod. One interesting advantageous side of the representation of a projection-line is that c n ji , meanwhile, corresponds to the unit vector orthogonal to the interpretation plane which is defined by the 3D line L ji lying along the surface of the cylindrical rod and the center of projection (see Fig. 2) [8]. The transformations between the expressions of the projection-line in pixel coordinates p n and in camera frame coordinates c n are given as below:

c n = K T p n K T p n , p n = K -T c n K -T c n ( 13
)
where K is the intrinsic camera matrix. The geometry of a cylindrical lower-leg rod allows one to calculate its direction as well (see Fig. 2) through its projection-lines as follows:

c ai = c n li × c n ri c n li × c n ri ( 14
)
Hence, one can derive the differential relation between the orientation vector of a lower-leg rod and its projectionlines in pixel coordinates by differentiating ( 14) and the first expression in [START_REF] Dasgupta | A general strategy based on the Newton-Euler approach for the dynamic formulation of parallel manipulators[END_REF]. Afterwards, the following expression comes up:

c ẋai = L n i p ṅli p ṅri (15)
where L n i ∈ ℜ 3×6 is the interaction matrix between the velocities of a lower-leg rod 3D direction and its projectionlines:

L n i = [ f i ] v [ c n ri ] T × [ k li ] v K T [ c n li ] × [ k ri ] v K T ( 16
)
and where f i and k ji are:

f i = c n li × c n ri , k ji = K T p n ji ( 17
)
The [•] × represents the skew-symmetric matrix associated to the vector cross-product and [•] v ∈ ℜ 3×3 denotes the differential tensor matrix for a given vector which will be scaled down to a unit vector by its norm:

d dt v v = [ v ] v v = 1 v I 3 - v v T v 2 v (18)
Then, the corresponding control u i is derived from (9) as follows:

u i = Ln i p ṅli p ṅri + L n i ω i ( 19
)
where

ω i = p nli T p nri T T
is obtained with ( 12) and (11). In Figs. 3, 4 and5, the function f x ai calculates the directions of the lower-legs and their first-order derivatives via ( 14) and ( 15) in order to be used in the IDM.

2) Leg orientations space computed-torque control (LS-CTC): Since the 3D directions of lower-legs stand in almost at the heart of the IDM, the sensor-signal is chosen as { x ai | 4 i=1 } for control (see Fig. 4) and the error is directly regulated over them in order to have an efficient performance:

e i = c x * ai -c x ai ( 20
)
where c x * ai is the desired i th lower-leg orientation and the e i ∈ ℜ 3×1 is the error vector for the i th lower-leg. Afterwards, the auxiliary control law, u i ∈ ℜ 3×1 , can simply be calculated through ( 20) and (11) (ω i = u i ). One can directly use it as the final control signal since the inverse dynamic model is represented in the lower-legs orientations space.

3) Cartesian-space computed-torque control (CS-CTC):

In Cartesian space, the end-effector pose χ of the Quattro, which is calculated through the linear function f χ as in [6] by using the projection-lines of the lower-legs rather than through a non-linear pose estimation from a set of points on a grid, is used as a sensor-signal in control (see Fig. 5). Then, the error is defined as difference in poses as follows:

e = c χ * -c χ (21)
where c χ * ∈ ℜ 4×1 is the desired end-effector pose. Then, the control signal u i can be found from (9) as below:

u i = Lχ i c χ + L χ i ω ( 22
)
where ω = c χ is computed from ( 21) and (11), and L χ i ∈ ℜ 3×4 is the inverse differential kinematic model between the end-effector pose and a lower-leg 3D direction vector [START_REF] Dallej | Visual Servoing of Par4 using Leg Observation[END_REF].

IV. RESULTS

The vision-based control simulations are conducted on the ADAMS/Simulink platform. The simulation frequency is 500 Hz. A 0.2 m diameter circle motion with 2 m/s maximum velocity and 4G maximum acceleration is planned out such that it spans XY, XZ and YZ planes. The simulations are executed in three different control-spaces and results are compared. Table I gathers the accuracy obtained under various types of noises for each control law, where the accuracy of the control laws is assessed in terms of mean (bold) and standard deviation (italic) values of the tracking errors that are evaluated in the Cartesian space. Firstly, 100µm of uncertainty is injected on the 3D coordinates of the extremity points {A i1 , B i1 } of the lower-legs so as to imitate the effects of clearances in passive joints, assembly errors and etc. (This noise has a great impact since it directly changes the orientations of the lower-legs and a good calibration is a must in case of ignorance that kind of mechanical errors.) Afterwards, for the sensory noise, the locations of the edgels of a lower-leg are orthogonally perturbed (with respect to its noiseless projection-line) in between [-2, +2] pixels which will make the new fitted line take a slight deflection off the previous noiseless one. We also performed (see last row in Table I) a computed-torque control with a feedback pose estimated by direct observation of the end-effector (EE-CTC) instead of the lower-legs and the feedback χ is corrupted with a {100 µm, 0.01 • } noise, corresponding to state-ofthe-art accuracy of high-speed vision. Figure 6 shows the reference circle motion in time. The results for the fourth row of the Table I are plotted in Figs. 7 to 10. Figures 7,8, and 9 depict the traces of the performed trajectories and the applied torques. Figure 10 shows the Euclidean and rotational distances to the reference trajectory, respectively. Observing the results in Table I, one can immediately conclude that CS-CTC performs better and IS-CTC performs worse than the others. It is surprising to have that result while our expectations are put on the IS-CTC since the control variable p n is directly defined in the very sensor-space. However, differences on the orders of magnitudes of the errors are not so decisive to promote one over the others. Going into details of the results, one can end up that: IS-CTC and LS-CTC seem robust only to the errors in the sensor space (line fitting smooths out the sensor noise), being sensitive to the mechanical errors. They are slightly better in rotation but slightly worse in translation. It seems that, the closer the control-variable to the operational space of the robot is, the better the results are. Moreover, the superior robustness of the CS-CTC to the both types of noise (mechanical and sensory) can be explained by the fact that the pose is calculated from the projection-lines of the lower-legs. This imposes explicitly the closed-loop kinematic constraint that is helping to smooth out the 3D errors. In the applied torques the CS-CTC performs better as well, while the others are more oscillatory and peaky. Let us finally remark that the EE-CTC is worse than any other proposed controls, which confirms that observing the lower-legs is probably one good way to enhanced accuracy. Note that those results were achieved with a PD+FF controller under the assumption of a perfect decoupling and linearizing of the dynamics. In practice, due to noise, this assumption might not be valid and the actual performance of the system should be improved by making call to advanced control.

V. CONCLUSIONS

In this paper, for a competent control performance of a parallel robot, the variable-spaces have been explored regarding a specific IDM expressed in leg orientations. The prevailing results are brought by the CS-CTC. This outcome suggests that: (i) the chosen variable set should be as close as possible to the sensor space, (ii) the models should be able to be directly / compactly expressed by that variable set and (iii) the control-variable should be in the operational space of the robot and has to be linearly calculated by the chosen variable set. In this work, the only but quite challenging assumption for the moment is that vision can perceive the leg edges and their velocities at high speed and control rates. However, it seems feasible in the close future, since the sensing technology is fast by this point [START_REF] Nakabo | 1ms column parallel vision system and its application of high speed target tracking[END_REF]. Thereafter, the impact of the noisy n on IDM should be analyzed as well, namely as decoupling is concerned. We build also the following perspectives for the future: (i) Shall we be able to do identification / calibration from {n, ṅ} and Γ ? and (ii) As stated earlier, shall the way towards optimum lie in the merging of the measurements in different spaces, such as q and χ (calculated from n) ? Finally, we conclude that this work bricks the last hole up theoretically in the controloriented unified system and, once the real-time tracking of the edges is worked out, will let it be practically put to good use in parallel robots as a favourable option.

-0.22 -0.2 -0.18 -0.16 -0.14 -0.12 -0.1 -0.08 -0.06 -0.04 -0.02

Fig. 1 .

 1 Fig. 1. The Quattro parallel robot with a base-mounted camera.

Fig. 2 .

 2 Fig. 2. An image of lower-legs with their edgels (green), orientation vector (blue) and projection-line vectors (red) from the base-mounted camera of the Quattro robot in Fig. 1.

Fig. 3 .

 3 Fig. 3. Image-space computed-torque control (IS-CTC).

Fig. 4 .

 4 Fig. 4. Leg orientations space computed-torque control (LS-CTC).

Fig. 5 .

 5 Fig. 5. Cartesian-space computed-torque control (CS-CTC).

Fig. 6 .

 6 Fig. 6. CS reference trajectory expressed in the camera frame.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Reference (red) and performed (black) superimposed trajectories in ZY and ZX planes (top), motor torques (bottom) for the IS-CTC.

Fig. 9 .Fig. 10 .

 910 Fig. 9. Reference (red) and performed (black) superimposed trajectories in ZY and ZX planes (top), and motor torques (bottom) for the CS-CTC.

  This work is supported by the ANR-VIRAGO project. The authors are with LASMEA-CNRS, Clermont Universit és, 24 Avenue des Landais 63177 Aubi ère Cedex, Clermont-

	Ferrand,	France.	N.	Andreff	is	also	with	FEMTO-ST
	Institute,	Universit é	de	Franche-Comt é,	Besanc ¸on,	France.

TABLE I TRACKING

 I ERRORS EVALUATED IN CS (µm, deg). • 356 0.23 • 359 0.23 • 239 0.19 • 190 0.16 • 182 0.16 • 100 µm 674 0.32 • 652 0.37 • 553 0.36 • 447 0.26 • 385 0.26 • 269 0.25 • ±2 pixels 553 0.22 • 522 0.22 • 529 0.34 • 428 0.18 • 371 0.16 • 236 0.23 •

				IS	( n )		LS	( x ai )	CS		( χ )
	no noise 408 0.23 100 µm 881 0.28 • 899 0.29 • 560 0.36 • ±2 pixels 647 0.23 • 703 0.24 • 264 0.25 •
	100 µm 0.01 •						862 0.56 • 400 0.38 •
	-1.5
	-2	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1


Agostino Martinelli

Visual-Inertial Structure from Motion Observability

Keywords: Sensor Fusion, Observability, Inertial Sensors, Vision, Structure from Motion Fusion Sensoriel, Observabilité, Capteurs inertiels, Vision, Structure from Motion

This paper investigates the visual inertial structure from motion problem with special focus on its observability properties. The considered system is a sensor assembling consisting of a monocular camera and inertial sensors (i.e., three orthogonal accelerometers and three orthogonal gyroscopes). The considered state contains the vehicle speed and attitude, the biases on the inertial measurements, the position of the features observed by the camera, the parameters characterizing the extrinsic camera-inertial sensors calibration and the magnitude of the gravity. In the case of a single feature, this state consists of 24 components. The observability analysis is carried out by using the method of continuous symmetries, which has recently been introduced. Due to the system complexity, a direct derivation of the system continuous symmetries would require an excessive computational cost. For this reason, new theoretical results are derived in order to significantly reduce the load of symbolic computation. The paper contribution is therefore twofold. From one side it provides new theoretical results, which allow significantly reducing the symbolic computational load necessary to investigate the observability properties of any estimation problem by making the use of the concept of continuous symmetry. From the other side, it provides a new result in the framework of the observability of the visualinertial structure from motion. Specifically, it is proven that, the information contained in the data provided by a monocular camera which observes a single point-feature and by an Inertial Measurement Unit (IMU), allows estimating the absolute scale, the speed in the local frame, the absolute roll and pitch angles, the biases which affect the accelerometer's and the gyroscope's measurements, the magnitude of the gravitational acceleration and the extrinsic camera-IMU calibration.

Introduction

The structure from motion problem (SfM) consists in determining the threedimensional structure of the scene by using the measurements provided by one or more sensors over time (e.g. vision sensors, ego-motion sensors, range sensors). In the case of visual measurements only, the SfM problem has been solved up to a scale [START_REF] Chiuso | Structure from Motion Causally Integrated Over Time[END_REF][START_REF] Davison | MonoSLAM: Real-Time Single Camera SLAM[END_REF][START_REF] Hartley | In Defense of the Eight-Point Algorithm[END_REF][START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF][START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF] and a closed form solution has also been derived [START_REF] Hartley | In Defense of the Eight-Point Algorithm[END_REF][START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF][START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF], allowing the determination of the three-dimensional structure of the scene, without the need for any prior knowledge.

The case of inertial and visual measurements, i.e., the visual-inertial structure from motion problem (from now on the Vi-SfM problem), has particular interest and has been investigated by many disciplines, both in the framework of computer science [START_REF] Bryson | Observability Analysis and Active Control for Airbone SLAM[END_REF][START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF][START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF][START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF][START_REF] Strelow | Motion estimation from image and inertial measurements[END_REF] and in the framework of neuroscience (e.g., [START_REF] Berthoz | Perception of Linear Horizontal Self-Motion Induced by Peripheral Vision (Linearvection) Basic Characteristics and Visual-Vestibular Interactions[END_REF][START_REF] Dokka | Estimating distance during self-motion: a role for visual-vestibular interactions[END_REF][START_REF] Fetsch | Visual-vestibular cue integration for heading perception: Applications of optimal cue integration theory[END_REF]). Vision and inertial sensing have received great attention by the mobile robotics community since they require no external infrastructure and this is a key advantage for robots operating in unknown environments where GPS signals are shadowed.

In [START_REF] Hesch | Towards consistent vision-aided inertial navigation[END_REF][START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF][START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF][START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] and [START_REF] Weiss | Vision Based Navigation for Micro Helicopters[END_REF] the observability properties of the Vi-SfM have been investigated. In [START_REF] Hesch | Towards consistent vision-aided inertial navigation[END_REF] the authors investigated the estimator inconsistency in the Vi-SfM problem. They found that standard EKF-based estimators lead to spurious information gain along unobservable directions. They also suggested a modification on the basic estimator in order to enforce the unobservable directions and thus to reduce inconsistency. In [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF][START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF] and [START_REF] Weiss | Vision Based Navigation for Micro Helicopters[END_REF] the observability properties have been derived by accounting an unknown transformation between the camera and the IMU1 frames and an unknown magnitude of the gravity. Additionally, in [START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF] and [START_REF] Weiss | Vision Based Navigation for Micro Helicopters[END_REF] also the case of biased inertial measurements has been considered. We remark that in [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF][START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF] and [START_REF] Weiss | Vision Based Navigation for Micro Helicopters[END_REF] the observability properties have been derived starting from basic results in computer vision. Specifically, in [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF] and [START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF], starting from the results derived in [START_REF] Chiuso | Structure from Motion Causally Integrated Over Time[END_REF], a global frame has been fixed by constraining three directions determined by three points on the image plane. In [START_REF] Weiss | Vision Based Navigation for Micro Helicopters[END_REF], the camera is considered as a localization sensor up to a scale. This is based on the assumption that the camera is observing a number of features (at least five [START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF]) which guarantees that its motion can be reconstructed up to a scale. This significantly simplifies the observability analysis since, the expression of the observation provided by the camera consists of three components of the state which defines the system. In [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] the observability properties have been derived without using the previous mentioned results from computer vision and this allowed us to deal with the case when a single point feature is observed by the camera. The analysis was based on the concept of continuous symmetry introduced in [START_REF] Martinelli | State Estimation Based on the Concept of Continuous Symmetry and Observability Analysis: the Case of Calibration[END_REF]. Since under these conditions the camera observation has an expression much more complex, the analysis in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] was limited to the case when the camera extrinsic calibration in the IMU frame is a priori known.

In this paper we extend the observability analysis carried out in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] in order to cope with the case of unknown camera extrinsic calibration. In order to achieve this objective, the theory introduced in [START_REF] Martinelli | State Estimation Based on the Concept of Continuous Symmetry and Observability Analysis: the Case of Calibration[END_REF] has been extended by adding some new techniques which allow us to significantly reduce the load of symbolic computation required to perform the analysis and the derivation of the system symmetries. Specifically, we introduce the quasi-projection operation which allows us to reduce the space dimensionality when deriving the observability properties of any estimation problem. The considered system together with its basic equations are provided in section 2. In section 3 the observability properties of this system are derived by firstly introducing the quasi-projection operation (3.1) and then by applying this operation to our system (3.2). Finally, conclusions are provided in section 4.

The Considered System

We consider a system (from now on we call it the vehicle) consisting of a monocular camera and an Inertial Measurement Unit (IMU). The IMU consists of three orthogonal accelerometers and three orthogonal gyroscopes. We introduce a global frame in order to characterize the motion of the vehicle moving in a 3D environment. Its z-axis points vertically upwards. We will adopt lower-case letters to denote vectors in this frame (e.g., the gravity is g = [0, 0, -g] T , where g is the magnitude of the gravitational acceleration). We define the vehicle local frame as the IMU frame. We will adopt upper-case letters to denote vectors in the vehicle frame. The camera frame differs from the local frame. We characterize the transformation between these two frames through R c and q c , where

R c ≡ [X c , Y c , Z c ]
T is the position of the camera optical center in the local frame and q c ≡ q c t + q c x i + q c y j + q c z k is the unit quaternion which characterizes the orientation of the camera frame in the local frame. We assume that both R c and q c are independent of time and are unknown.

The IM U provides the vehicle angular speed and acceleration. We will denote the measured quantities by Ω and A, respectively. These quantities differ from the true values, Ω true and A true . Regarding the angular speed, the one measured by the gyroscopes includes a bias and a zero-mean error, i.e.: Ω = Ω true + Ω bias + n Ω . Regarding the acceleration, the one measured by the accelerometers includes the inertial acceleration (A inertial ), the gravitational acceleration (G), a bias and a zero-mean error. In other words: A = A inertial + A bias -G + n A . Note that the gravity comes with a minus since, when the vehicle does not accelerate (i.e. A inertial is zero), the accelerometers perceive an acceleration which is the same of an object accelerated upward in absence of gravity.

Our system is characterized by the state [r, v, q] T where r = [r x , r y , r z ] T is the 3D vehicle position in the global frame, v is its time derivative, i.e. the vehicle speed in the global frame (v ≡ dr dt ) and q ≡ q t + q x i + q y j + q z k is the unit quaternion which characterizes the vehicle orientation in the global frame.

In the following, we want to derive the analytical expression of the dynamics and the camera observations. For the sake of simplicity, we consider the case of noiseless measurements. The case with noise can be easily obtained with the substitution A → A + n A and Ω → Ω + n Ω . The dynamics of the previous state can be easily provided by expressing all the 3D vectors as imaginary quaternions. In practice, given a 3D vector w = [w x , w y , w z ] T we associate INRIA with it the imaginary quaternion w q ≡ 0 + w x i + w y j + w z k. The dynamics of the state [r q , v q , q] T are:

       ṙq = v q vq = qA inertial q q * = qA q q * -qA bias q q * + g q q = 1 2 qΩ q - 1 2 qΩ bias q (1)
being q * the conjugate of q, q * = q t -iq x -jq y -kq z . By considering the case of unknown biases, unknown magnitude of the gravity and unknown transformation between the IMU and the camera frames, the state which defines our system becomes the following 24-dimensional vector:

X ≡ r, v, q, A bias , Ω bias , R c , q c , g T (2)
whose dynamics are given in (1) with the following trivial additional equations:

Ȧbias = Ωbias = Ṙc = [0 0 0] T ġ = qc = 0 (3)
Note that this is the state which defines our system when a single point feature is observed by the camera. In this case the origin of the global frame can be chosen as coincident with the observed feature. In the case of multiple features, the state dimension becomes 24 + 3(N f -1) (N f being the number of observed features) and the coordinates of the further N f -1 features are included in the state (see [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] for more details). On the other hand, the state defined in (2) is not a suitable choice to characterize our system. Indeed, the expression of the camera observations in terms of it involves the product of five quaternions: (q c ) * q * r q qq c . This makes impossible to efficiently derive the observability properties. In order to have a simple expression of the camera observations it is much more convenient to adopt a new state. Let us refer to the case of a single feature. The new state is:

X n ≡ c F , V , q, A bias , Ω bias , R c , q c , g T (4)
where

c F ≡ [ c F x , c F y , c F z ]
T is the position of the feature in the camera frame and V is the vehicle speed in the local frame (i.e., in the IMU frame). By using the equations in (1) we obtain the following dynamics for the new state:

          c Ḟ = M ( c Ω) c F -R q c [V + (Ω -Ω bias ) ∧ R c ] V = M (Ω -Ω bias )V + A -A bias + G q = 1 2 qΩ q - 1 2 qΩ bias q Ȧbias = Ωbias = Ṙc = [0 0 0] T ġ = qc = 0 (5)
where:

• M (Ω) ≡   0 Ω z -Ω y -Ω z 0 Ω x Ω y -Ω x 0   ; RR n°8272
• c Ω is the angular speed in the camera frame, i.e., c Ω q = (q c ) * (Ω q -Ω bias q )q c ;

• R q c is the rotation matrix associated with the quaternion q c (i.e., for a 3D vector w = [w x , w y , w z ] T , (R q c w) q = (q c ) * w q q c );

• the symbol "∧" denotes the vectorial product.

Figure 1 displayes the three reference frames together with some of the previous vectors. As the majority of real control systems, the dynamics given in [START_REF] Davison | MonoSLAM: Real-Time Single Camera SLAM[END_REF] are affine in the controls, i.e. they can be written as follows:

Ṡ = f (S, u) = f 0 (S) + nc i=1 f i (S)u i (6) with S = X n , n c = 6 and u = [u 1 , u 2 , ..., u nc ] T = [A x , A y , A z , Ω x , Ω y , Ω z ] T .
The expression of the vector fields f i , i = 0, 1, ..., n c , which is necessary for the computation of the Lie derivatives, can be obtained by a direct computation2 . The expression of the camera observations in terms of the new state is trivial. Indeed, the camera provides the direction of the observed feature in its own frame. Hence, it provides the vector c F up to a scale, or, equivalently, the two following ratios:

h cam (X n ) ≡ [h u , h v ] T = c F x c F z , c F y c F z T (7)
We have also to consider the two constraints q * q = 1 and (q c ) * q c = 1. These can be dealt as further observations:

h const (X n ) ≡ [h q , h q c ] T = [q * q, (q c ) * q c ] T (8)
Finally, the case of multiple features can be characterized by including in the state the position of each feature in the camera frame, i.e., c

F → c F i , i = 1, 2, • • • , N f .
The resulting state has dimension 24 + 3(N f -1).

Observability Properties

In [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] we investigated the observability properties of the Vi-SfM problem in several contexts which include the case of a single and multiple features, the case of known and unknown magnitude of the gravity, the case of biased and unbiased inertial measurements. In all the considered cases, the extrinsic camera-IMU transformation was assumed known. In the case of a single feature, the state adopted to characterize the case of biased inertial measurements and unknown magnitude of the gravity was r, v, q, A bias , Ω bias , g T , whose dimension is 17. The results of the observability analysis carried out in [START_REF] Martinelli | Vision and IMU Data Fusion: Closed-Form Solutions for Attitude, Speed, Absolute Scale and Bias Determination[END_REF] can be summarized as follows:

Theorem 1 (Known extrinsic calibration) Let us consider the Vi-SfM problem with biased inertial measurements, unknown magnitude of the gravity and known camera-IMU transformation. All the independent observable modes are: the positions in the local frame of all the observed features, the 3 components of the speed of the vehicle in the local frame, the two biases affecting the accelerometer and gyroscope measurements, the roll and the pitch angle and the magnitude of the gravity.

The derivation of this result required to analytically compute the Lie derivatives up to the third order. In general, the complexity of the computation of the Lie derivatives and the determination of their dependence or independence dramatically depends on the state dimension. Let us consider now the case when the extrinsic camera-IMU transformation is unknown. In order to solve the structure from motion we also need to estimate the parameters which characterize this transformation. In other words, the state which defines our system, is the one given in [START_REF] Berthoz | Perception of Linear Horizontal Self-Motion Induced by Peripheral Vision (Linearvection) Basic Characteristics and Visual-Vestibular Interactions[END_REF] or in (4), for the case of a single feature. In this case, even by using the state in (4), we found prohibitive to analytically deal with second-order Lie derivatives. Specifically, by using the symbolic computation tool of Matlab running on a 2.7GHz dual-core Intel Core i7 processor with 4MB shared L3 cache, the time demanded to compute the rank of the matrix whose lines are the gradients of all the Lie derivatives up to the second order, is equal to 101734s and the analytical determination of its null space required 127683s. One of the goal of this paper is to show how the theory developed in [START_REF] Martinelli | State Estimation Based on the Concept of Continuous Symmetry and Observability Analysis: the Case of Calibration[END_REF] can be used to deal with such complex cases, namely, how the observability properties can be derived by avoiding the computation of high-order Lie derivatives and how the space dimensionality where the rank must be computed can be reduced.

Quasi-Projection Operation and Matrix

In this section we introduce new theoretical results which allow significantly reducing the load of symbolic computation requested in order to derive the observability properties of a given system starting from the analysis of its continuous symmetries. Throughout this section, we denote by n the dimension of the state. We start by reminding the reader the definition of continuous symmetry and the basic result derived in [START_REF] Martinelli | State Estimation Based on the Concept of Continuous Symmetry and Observability Analysis: the Case of Calibration[END_REF], which characterizes the observable modes.

Definition 1 (Continuous Symmetry) The vector field w s (S) is a continuous symmetry in S for the system defined in [START_REF] Dokka | Estimating distance during self-motion: a role for visual-vestibular interactions[END_REF] if and only if it is a non null vector belonging to the null space of the matrix whose lines are the gradients of all the Lie derivatives computed in S.

Property 1 g(S) is an observable mode if and only if its gradient is orthogonal to all the symmetries.

According to this result, the derivation of all the observable modes requires, first of all, to derive all the symmetries. The following remark provides an upper bound on the number of Lie derivatives which must be computed in order to detect the system symmetries:

Remark 1 In order to detect the symmetries of the system in ( 6), only the first (n -1)-order Lie derivatives must be computed.

The reader is addressed to [START_REF] Anguelova | Non linear Observability and Identifiability: General Theory and a Case Study of a Kinetic Model[END_REF] to verify the validity of this remark. On the other hand, this remark is not useful to deal with our case since it is prohibitive even to deal with the second-order Lie derivatives.

Let us denote with φ 1 , ..., φ n (1 ≤ n < n) a set of independent column vectors of dimension n which are orthogonal to the gradients of n -n independent Lie derivatives. We have the following result: Property 2 A sufficient condition for g(S) to be an observable mode is that its gradient is orthogonal to all the vectors φ 1 , ..., φ n .

Proof: According to definition 1, if n -n is the number of all the independent Lie derivatives, φ 1 , ..., φ n are all the symmetries of the system. In this case, as stated in property 1, the previous condition is also necessary. When n -n is smaller than the number of all the independent Lie derivatives, we only know that the vector space generated by the symmetries is a subspace of the space generated by φ 1 , ..., φ n . Hence, if the gradient of g(S) is orthogonal to this latter vector space it is also orthogonal to any of its subspace. From property 1 we conclude that g(S) is an observable mode This result is useful since it can be used by computing any number of independent Lie derivatives and not necessarily all of them. Additionally, this simple result allows us to reduce the system dimensionality in the special case when a component of the state verifies the sufficient condition stated in the previous property. In this case, since we know that this component is observable, in order to detect the other observable modes we can consider the reduced system, which is obtained by removing this component from the state.

INRIA

The second new result allows us to determine the dependence or independence of a given set of Lie derivatives by computing the rank of matrices whose dimension is smaller than the dimension of the original state. Let us suppose that we detected n -n independent Lie derivatives (L 1 , ..., L n-n ) and, as before, let us denote with φ 1 , ..., φ n (1 ≤ n < n) a set of independent column vectors orthogonal to their gradients. Let us suppose that we compute m additional Lie derivatives (P 1 , ..., P m ). We need to determine if they are independent from the previous ones and also if they are independent one each other. In other words, we want to know the number of independent Lie derivatives in the set L 1 , ..., L n-n , P 1 , ..., P m . The easiest way to determine this is to compute their gradients and then the rank of the matrix which contains these gradients. The dimension of this matrix is (n -n + m) × n. We know that this rank is larger or equal to n -n since we assumed that L 1 , ..., L n-n are independent. Let us denote this rank by n-n +p. We remark that determining p is very easy if the vectors φ 1 , ..., φ n are orthonormal. In this special case, it is immediate to project the gradients of the Lie derivatives (P 1 , ..., P m ) onto the vectors φ 1 , ..., φ n . This allows us to reduce the space dimensionality: instead of working in the original n-dimensional space we can work in a n -dimensional space. In other words, p is the rank of the m × n matrix, whose lines are the projections of the gradients of the Lie derivatives (P 1 , ..., P m ) onto the vectors φ 1 , ..., φ n . On the other hand, even in the case when the vectors φ 1 , ..., φ n are not orthonormal, p can be computed by computing a rank of a m × n matrix. We have the following result: Property 3 p is the rank of the m × n matrix, whose i, j entry is the scalar product ∇ S P i • φ j .

Proof: In this proof we will use the following two results from linear algebra about the matrix rank [START_REF] Mirsky | An Introduction to Linear Algebra[END_REF]:

1. rank(AB) = rank(A) when rank(B) = k,
where k is the number of lines of B;

2. If A is a matrix over the real numbers, rank(AA

T ) = rank(A T A) = rank(A) = rank(A T ).
Let us introduce the following notation:

• D is the (n -n ) × n matrix whose lines are the gradients of the functions L 1 , ..., L n-n , i.e.:

D ≡   ∇ S L 1 • • • ∇ S L n-n  
• E is the m × n matrix whose lines are the gradients of the functions P 1 , ..., P m , i.e.:

E ≡   ∇ S P 1 • • • ∇ S P m   RR n°8272
• M is the (n-n +m)×n matrix whose lines are all the previous gradients, i.e.: M ≡ D E

• F is the n × n matrix whose columns are the vectors φ 1 , ..., φ n ;

• N is the following n × n: N ≡ D T F

We have: n-n +p = rank(M). Since rank(N ) = n, by using the first property mentioned at the beginning of this proof, we also have rank(M) = rank(MN ).

We have:

MN = DD T 0 (n-n )×n ED T EF (9)
where 0 (n-n )×n is the zero (n-n )×n matrix. Because of the second property mentioned at the beginning, rank(DD T ) = rank(D), which is n -n , because of the independence of L 1 , ..., L n-n . In order to compute the rank of the matrix in ( 9), we detect the largest number of independent columns. Let us consider any linear combination of its columns which includes all the first n-n columns.

A necessary condition to be the null vector is that the first n -n coefficients are equal to zero. Hence, a necessary and sufficient condition such that this linear combination vanishes if and only if all the coefficients are equal to zero, is that the columns selected among the last m columns of the matrix MN are independent among them. This proves that rank(MN ) = n -n + rank(EF). But the i, j entry of EF is precisely the scalar product ∇ S P i • φ j This result is very important since allows us to verify the independence of a set of Lie derivatives by computing the rank of matrices with low dimension. Specifically, the gradients of the Lie derivatives are n-dimensional vectors. Once we have detected n -n independent Lie derivatives and a basis for its null space (i.e., φ 1 , ..., φ n ), in order to detect further independent Lie derivatives, we can work with n -dimensional vectors. Indeed, for a given Lie derivative P, instead of working with the n-dimensional vector ∇ S P, we can work with the n -dimensional vector, which is defined as the vector whose j th entry is ∇ S P • φ j (j = 1, • • • , n ). This operation would be a projection if the basis φ 1 , ..., φ n were orthonormal. For this reason we will call this operation a quasi-projection. This result is very powerful since it can be applied more consecutive times. Specifically, let us suppose that, by quasi-projecting the gradients of additional Lie derivatives in the n -dimensional space we detect additional n -n independent Lie derivatives (1 ≤ n < n ). Let us denote with φ 1 , ..., φ n a basis of the null space of the matrix made by these gradients quasi-projected in the n -dimensional space. Now, in order to work in the new n -dimensional space, we must quasi-project the gradient of a given Lie derivative, first on the n -dimensional space and then on the n -dimensional space. By computing the matrix whose i, k entry is j φ j i φ k j we can simply multiply the gradient of the Lie derivative by this matrix. We we will call this matrix the quasi-projection matrix. Therefore, each time we apply the result in property 3, we need to compute the new quasi-projection matrix.

INRIA

Vi-SfM Observability

We illustrate the power of the previous two properties by referring to our case, where the original state has dimension n = 24. We remind the reader that the time demanded to compute the rank of the matrix whose lines are the gradients of all the Lie derivatives up to the second order, is equal to 101734s. We start by considering the matrix whose lines are the gradients of the following Lie derivatives:

L 0 h u , L 0 h v , L 0 h q , L 0 h p , L 1 f 5 h u , L 1 f 6 h u , L 1 f 6 h v .
The computation of its rank and its null space demands 0.37s and 0.24s, respectively. In particular, the rank is 7 proving that these functions are independent. In a second step we quasi-project the gradient of the following Lie derivatives: L 1 f 0 h u and L 1 f 4 h u . We build with them a 2 × 17 matrix. The computation of its rank and null space requires 0.027s and 3.11s, respectively. The rank is 2. The computation of the quasi-projection matrix requires 6.48s. In a third step we quasi-project the gradient of the following Lie derivatives: L 1 f 4 h v and L 1 f 5 h v . We build with them a 2 × 15 matrix. The computation of its rank and null space requires 64s and 81s, respectively. The rank is 2. The computation of the quasi-projection matrix requires 0.34s. Finally, we quasi-project the gradient of the Lie derivative L 1 f 0 h v . We build with it a 1 × 13 matrix. The computation of its rank and null space requires 0.041s and 0.089s, respectively. The computation of the quasi-projection matrix requires 0.44s. We can proceed further in order to detect all the independent Lie derivatives. However, it is more convenient to use property 2. Specifically, we can check if some of the components of the state are observable (property 2 is a sufficient condition). We compute the gradient of the components of the original state and we quasi-project them on the final 12-dimensional space. Regarding the four components of the quaternion q c we obtain the null vector, meaning that these components are four observable modes. Hence, we remove these coponents from the original state and we start again the observability analysis of a new system whose state has now dimension equal to 20. As previously mentioned, the complexity of the computation dramatically depends on the dimension of the state. Specifically, with the new state, it is possible to work with third-order Lie derivatives. In particular, we found the following 19 independent Lie derivatives:

L 0 h u , L 0 h v , L 0 h q , L 1 f 0 h u , L 1 f 5 h u , L 1 f 6 h u , L 1 f 0 h v , L 1 f 6 h v , L 2 f 0 f 0 h u , L 2 f 0 f 1 h u , L 2 f 0 f 4 h u , L 2 f 0 f 5 h u , L 2 f 0 f 6 h u , L 2 f 0 f 0 h v , L 2 f 0 f 4 h v , L 3 f 4 f 0 f 0 h u , L 3 f 0 f 0 f 4 h u , L 3 f 0 f 0 f 5 h u , L 3 f 0 f 0 f 6 h v .
The computation of the null space of the matrix whose lines are their gradients requires 0.46s and provides the vector:

w Rotz s = [0 1×6 , -q z , -q y , q x , q t , 0 1×10 ] T
where 0 i×j denotes the i×j zero matrix. This vector expresses the system invariance under rotations around the vertical axis. Indeed, an infinitesimal rotation of magnitude about the vertical axis leaves the vectors c F , V , A bias , Ω bias and R c unchanged and the quaternion q changes as follows [?]:

    q t q x q y q z     →     q t q x q y q z     + 2    
-q z -q y q x q t    

i.e., the reduced 20-dimensional state X r ≡ c F , V , q, A bias , Ω bias , R c , g T changes as follows: X r → X r + 2 w Rotz s . Hence, w Rotz s is a continuous symmetry for our system and the only non-observable mode is the yaw angle. In other words, we extended the result in theorem 1 to the case of unknown camera-IMU calibration. We have the following new result: Theorem 2 (Unknown extrinsic calibration) Let us consider the Vi-SfM problem with biased inertial measurements, unknown magnitude of the gravity and unknown camera-IMU transformation. All the independent observable modes are: the positions in the local frame of all the observed features, the three components of the speed of the vehicle in the local frame, the two biases affecting the accelerometer and gyroscope measurements, the roll and the pitch angle, the magnitude of the gravity and the transformation between the camera and IMU frames.

Note that this result holds even in the case when the camera observes a single point-feature.

Conclusion

In this paper we extended the results of the state of the art about the Vi-SfM observability. Specifically, it has been proven that, even in the case of a single point feature, monocular vision and inertial sensors provide the necessary information to determine the scale, the vehicle speed, the absolute roll and pitch, the inertial biases, the magnitude of the gravity and the camera extrinsic calibration in the IMU frame. To achieve this result, we introduced the operation of quasi projection and new results which allow us to perform an observability analysis with a reduced load of symbolic computation. It is remarkable to note that, by using these new results, it is possible to check the independence of the Lie derivatives up to the third order in less than 200 seconds while, on the same processor and for the same problem, the computational time required to check the independence of the Lie derivatives up to the second order is larger than 10 5 seconds.

INRIA

Figure 1 :

 1 Figure 1: Global frame, local (IMU) frame and camera frame with the feature position ( c F ) in the camera frame and the vehicle speed (V ) and the camera position (R c ) in the local frame.

In this paper IMU is the Inertial Measurement Unit, which consists of three orthogonal accelerometers and three orthogonal gyroscopes.RR n°8272

The reader is addressed to[START_REF] Martinelli | State Estimation Based on the Concept of Continuous Symmetry and Observability Analysis: the Case of Calibration[END_REF] for the definition and details about the computation of the Lie derivatives.INRIA

RR n°8272