Multi-Unmanned Aerial Vehicle (UAV) Cooperative Fault Detection Employing Differential Global Positioning (DGPS), Inertial and Vision Sensors

Sensors 2009, 9, 7566-7579; doi:10.3390/s90907566 sensors ISSN 1424-8220 www.mdpi.com/journal/sensors Article Multi-Unmanned Aerial Vehicle (UAV) Cooperative Fault Detection Employing Differential Global Positioning (DGPS), Inertial and Vision Sensors Guillermo Heredia 1,*, Fernando Caballero 1, Iván Maza 1, Luis Merino 2 , Antidio Viguria 3 and Aníbal Ollero 1,3 1 Robotics, Vision and Control Group, University of Seville, Camino de los Descubrimientos s/n, 41092, Seville, Spain; webpage: http://grvc.us.es 2 Pablo de Olavide University, Crta. Utrera km. 1, 41013 Seville, Spain 3 Centro Avanzado de Tecnologías Aeroespaciales (CATEC), Aeropolis, 41309 Seville, Spain; E-Mail: [email protected] (A.O.) * Author to whom correspondence should be addressed; E-Mail: [email protected]; Tel.: +34-954-486-035; Fax: +34-954-487-340. Received: 26 August 2009; in revised form: 14 September 2009 / Accepted: 21 September 2009 / Published: 24 September 2009 Abstract: This paper presents a method to increase the reliability of Unmanned Aerial Vehicle (UAV) sensor Fault Detection and Identification (FDI) in a multi-UAV context. Differential Global Positioning System (DGPS) and inertial sensors are used for sensor FDI in each UAV. The method uses additional position estimations that augment individual UAV FDI system. These additional estimations are obtained using images from the same planar scene taken from two different UAVs. Since accuracy and noise level of the estimation depends on several factors, dynamic replanning of the multi-UAV team can be used to obtain a better estimation in case of faults caused by slow growing errors of absolute position estimation that cannot be detected by using local FDI in the UAVs. Experimental results with data from two real UAVs are also presented. Keywords: UAVs; fault detection and identification; multi-UAV; vision sensors; GPS OPEN ACCESS Sensors 2009, 9 7567 1. Introduction Unmanned aerial vehicles (UAVs) and aerial robotics have attracted significant interest for a wide range of applications [1]. In many of them, the active cooperation of several UAVs may have important advantages [2]. Reliability is a key issue in aerial vehicles, where Fault Detection and Identification (FDI) techniques play an important role in the efforts to increase the reliability of the system. Most FDI applications to UAVs that appear in the literature use model-based methods, which try to diagnose faults using the redundancy of some mathematical description of the system dynamics. FDI has been applied to unmanned aircraft, either fixed wing UAVs [3] or helicopter UAVs [4-6]. Differential GPS (DGPS) receivers are able to achieve accuracies of a few centimeters using carrier-phase measurements, which make them a good choice for UAV positioning main sensors. Since they usually are the only absolute position sensors employed in UAVs, the reliability of their measurements is critical for UAV missions. If DGPS readings are erroneous or differential mode is lost, position estimation may accumulate large drift errors. The literature concerning GPS fault detection is extensive; there exist several techniques developed to detect faulty measurements in the receiver, known as Receiver Autonomous Integrity Monitoring (RAIM) [7,8]. However, RAIM techniques need additional satellites in view to operate, and they are difficult to find in commercial GPS receivers. RAIM techniques are usually implemented in aeronautical-grade GPS receivers, which in general can not be used in small and medium UAVs due to their size, weight and cost limitations. This paper will concentrate in FDI for DGPS when RAIM techniques cannot be used. Ideally, FDI uses all available information to detect malfunctions in UAV subsystems. But there exist positioning errors that cannot be detected using the navigation sensors onboard the UAV. In multi-UAV missions, it is possible to take advantage of the capabilities that the team of UAVs offers to augment each of the individual FDI systems. In this way, sensors from other UAVs can be used to obtain additional data which can be applied to the UAV FDI system to detect faults in its own sensors. If the UAVs are equipped with visual cameras, different UAVs may identify, using their cameras, common objects in the scene. For instance, the use of a robust feature extraction technique capable of identifying natural landmarks of the scene [2], and the correspondences between the same landmarks obtained by two UAVs provide the relative pose displacement between both UAVs. Thus, for example, if the DGPS of UAV-A is faulty, this fault can be detected by using the DGPS of UAV-B and the relative position estimation computed from the images. The proposed idea is to estimate the position of UAV-A using the known position of UAV-B and the estimation of the relative position of UAV-A and UAV-B using the method described above. Unfortunately, these vision-based position estimations have different accuracy and noise levels depending on several factors. Therefore, a variable threshold strategy, for the fault detection process, has been adopted in this paper. Furthermore, in multi-UAV missions, the probability of having the same scene in the field of view of two or more UAVs when executing a plan is not very high. Thus, in this paper we propose the application of replanning techniques with the automatic generation of new tasks for the multi-UAV team in such a way that the above required condition for fault detection is satisfied for two UAVs. Particularly, the application of a market-based approach for the multi-robot task allocation (MRTA) problem is proposed. Sensors 2009, 9 7568 The paper is organized as follows. Section 2 presents the techniques for fault detection and identification in helicopter UAVs. Section 3 describes multi-UAV vision-based relative position estimation. Section 4 presents the method implemented to dynamically replan the mission in order to improve the accuracy of the estimation. Section 5 presents the experimental data and the obtained results. Finally, the conclusions and future trends mentioned in Section 6 complete the paper. 2. Sensor FDI in Small Autonomous Helicopters Several small autonomous helicopter prototypes have been developed in recent years at different research centers throughout the world [1]. Autonomous helicopter flight requires precise position and attitude information for control and stabilization. Small autonomous helicopters carry a pack of sensors that in a typical case includes an inertial measurement unit (IMU) with three gyros, three accelerometers and a 3-axis magnetometer for attitude determination, a centimeter-precision kinematic DGPS and an ultrasonic or barometric altitude sensor for take-off and landing. A fault in one of the sensors, if undetected, may induce position and attitude estimation errors. Reconfiguration in these cases usually consists in isolating the faulty sensor and using the other sensors to get the best estimation of position and attitude. 2.1. Inertial, magnetometer and altitude sensor faults Usual UAV sensor faults are additive (sensor output has a drift term added), multiplicative (sensor output is scaled by a multiplicative term) or “stuck” output (sensor output remains fixed at a constant value). The presence of these faults can be detected in most cases by means of the so-called residuals, i.e., quantities that are over-sensitive to the malfunctions. Observer-based and parameter estimation are the most frequently applied methods for residual generation in FDI [9]. Most published work in recent years on FDI systems for autonomous vehicles also use observer-based methods. Neural networks have also been used to detect sensor and actuator faults in aircrafts [10] and UAVs [4,11]. The FDI system implemented in individual helicopters is described in detail in [5]. The structure of the sensor FDI system is based on a bank of output estimators as shown in Figure 1. The number of these estimators is equal to the number of system outputs. A residual is generated for each sensor, comparing the estimator output with the sensor output. Each residual is not affected by the other sensors, and therefore fault identification is straightforward: each residual is only sensitive to a single helicopter sensor. The FDI system with the above structure has been implemented using ARX input-output estimators. A number of ARX Multi-Input Single-Output (MISO) models have been identified from input-output data. These models are of the type: )()()()( * 11 ,, * 1, *tktujtyty ij r j n kkjii n jjii εβα +−+−= ∑∑∑=== (1) The number of identified MISO ARX models is equal to the number m of the output variables. The model order n and the parameters α i,j and  β i,j,k with i = 1, … , m, of the model have to be determined by the identification approach. The term ε i(t) takes into account the modeling error, which is due to Sensors 2009, 9 7569 process noises, parameter variations, etc. The ARX models are chosen with the structure that achieve the smallest Akaike's Information Theoretic Criterion (AIC) [12], according to a simple search algorithm, in which the first half of data is used for estimation and the second for cross validation. Figure 1. Bank of estimators for output residual generation. Independent residuals are constructed for each different sensor failure. Residuals are designed so that they respond to an individual failure and not to the others. In general, residuals rk are functions of the squared difference between real (ci) and estimated ( i c ˆ) sensor outputs: ∑ = −= n i iiik ccmr 1 2 ) ˆ ( (2) where mi are weighting coefficients that are determined for each failure based on experience and experimentation. Ideally, if no fault is present, the residual would be zero. In practice, the residual will take non-zero values due to estimation errors, sensor noise, etc. Usually, the residual for a specific sensor will be bounded, and therefore a “threshold level” can be defined so that the residual is always below it in absence of failures. The system has been tested with different sensors and failure types. The implemented sensor FDI system is able to detect many of these errors. 2.2. Differential GPS sensor failures Consider now the Differential GPS absolute position sensor. This sensor implements complex processing algorithms to generate absolute position estimations from the received satellite signals and the differential corrections. There are several typical GPS error sources such as atmospheric delays, ephemeris errors, satellite and receiver clock errors or multipath signal reception. Many of these errors can be avoided in differential operation. There are also “system errors”, errors in the space and control segment (satellite hardware failures, control segment software or transmission errors, etc). Although these errors are rare, they can lead to UAV ESTIMATOR 1 u FAULT DIAGNOSIS ESTIMATOR 2 ESTIMATOR m r1 r2 rm . . . y1 y2 ym y . . . Sensors 2009, 9 7570 large position errors. These errors have received much attention since the selective availability turning off in 2000, due to the increasing use of GPS in critical civilian applications such as airport approach or coast navigation. These errors can be partially avoided in differential operation. From a practical point of view, a commercial GPS receiver operating in differential mode may have different error sources, which can be classified in three groups. The first group includes errors that can be detected by the GPS receiver. Among these are satellite signal reception problems, due to intermittent signal blocking when the vehicle is moving because of buildings, foliage and hilly terrain. Another source is differential correction errors. Timely differential corrections are very important for DGPS, but in some cases the correction messages may arrive “corrupted” due to problems on the communication link. Most DGPS receivers can provide an estimation of the level of accuracy of the calculated position, although this accuracy estimation can be erroneous in some cases. The second group includes errors that cannot be detected by the receiver, but can be detected using vehicle dynamics and model-based fault detection techniques. When in operation, position estimations from DGPS receivers may present a priori unknown-source errors. For example, typical results obtained in 24-hour static tests show that estimated position error was less than 2 cm most of the time, but also include several groups of 2 to 5 contiguous points with a 20-60 cm error, which appear from time to time with no predictable frequency, which seems to be caused by RTK integer ambiguity [13], and a few isolated points with large position errors. The number of satellites in view, CRC redundancy code, and indicators of differential carrier-phase estimation were all correct. A possible explanation can be receiver algorithm errors. In [14] another error source is suggested: GPS receivers have thousands of lines of code, many of which are from legacy code that is not fully tested. This can lead to unpredictable errors. Some of the described errors can be detected using model-based fault detection and identification techniques, as described in Section 2.2. Using this information, the faulty GPS estimations can be discarded. Figure 2. Outlier GPS-z sensor failure detection. Upper plot: residual signal. Lower plot: fault detection signal. 0 5 10 15 20 0 1 t=18 time GPS-z residual 25 r1 D Sensors 2009, 9 7571 Figure 2 shows the detection of a one-meter outlier-type fault in the GPS-z sensor of the helicopter. In the upper plot of Figure 2 the residual signal of the GPS-z sensor (r1) generated by the ARX estimator is shown. The fault has been declared at t = 18 sec. Shortly after the fault, the residual goes above the threshold value (dashed line). The lower plot shows the fault detection signal (D, which equals 1 when a fault is detected, and is zero otherwise). But there are some cases in which the individual helicopter FDI system cannot detect the failure. For example, slow growing errors in absolute positioning estimations (due to loss or corruption of differential corrections unnoticed by the receiver) are difficult to detect using incremental sensors as gyros or accelerometers, since DGPS is the only absolute positioning sensor that is used in UAVs. Figure 3 shows an example of this case: at t = 2 s, a slow growing error is present in the GPS-z sensor, but the FDI system is not able to detect it using the other onboard sensors. Figure 3. Slow-growing drift GPS-z sensor failure detection. Upper plot: residual signal r1. Lower plot: fault detection signal. 3. Multi-UAV Vision-Based Relative Position Estimation A method for the estimation of the ego-motion of a single UAV by means of monocular vision has been presented in [15]. This method assumes that the imaged scene is approximately flat or, in full 3D environments, that the UAV flies at relative high altitude compared to the deviations from the flat model. Its robustness would be reduced if the UAVs are flying at low altitudes in urban areas or hilly terrains, so the planning system should take this issue into account. The estimated position may present drifts along the sequence of images. This effect is mainly derived from the accumulative errors in the homography computation used to estimate the planar motion. Mosaicking can help to reduce the registration errors and, hence, to increase the accuracy of the position estimation. This method can be extended to estimate the relative position among several UAVs. Thus, if two UAVs are registering approximately the same scene and it is possible to match a set of features between their images, the relative displacement between the UAVs can be obtained by computing the plane-induced homography matrix that relates their cameras. 0510 15 20 0 1 time GPS-z residual 25 r1 D Sensors 2009, 9 7572 The technique described in [15] obtains the relative displacement between two views of the same planar scene. The relations presented also hold if the views are taken by different calibrated cameras. In this case, the homography that relates both views, 1 and 2, of the same planar scene (see Figure 4) is given by: ( ) 1 2221 12 − ⋅−⋅⋅= AntIRAH T w (3) where A1 and A2 are the intrinsic calibration matrices of both cameras, t2 is the relative translation of the second camera point of view in the first camera coordinate frame, n is an unitary vector normal to the plane in the first camera coordinate frame (in the outward camera direction), w = 1/z, z being the distance from the first camera to the plane and R2 is the rotation matrix that transforms a vector in the first camera coordinate frame into a vector expressed in the second camera coordinate frame. Thus, the relative displacement between two UAVs is obtained by computing the plane-induced homography matrix between their cameras (H12). Figure 4. Scheme of the geometry of multiple views of the same plane z. The computation of matches between images taken from very different points of view may be a hard limitation of this approach. Robust and repeatable features, with some degree of invariance, should be used, as affine invariant neighborhoods or maximally stable extreme regions. In our implementation, the algorithm proposed in [2] for blob matching and robust homography estimation is used. The idea is to use this algorithm to compute the homography that relates two images of the same scene taken by different UAVs. Thus, it is assumed that at a certain time instant (the time of image 0) the same scene is viewed by two UAVs, for instance UAV 1, which is taken as the reference UAV, and UAV 2. The robust matching procedure is applied with the aim to match image 0 of the reference UAV with its most recent captured image of UAV 2. If a number of good blob matches are obtained, the relative displacement between UAV 1 and UAV2 at that time is computed by means of the motion estimation algorithm. Otherwise, the images are discarded. In general, the probability of having the same scene in the field of view of two or more UAVs is not very high. In Figure 5 H12 is the homography matrix that relates two images gathered by UAVs 1 and 2 for image 0 computed by blob matching. H j0i, the homography matrix between image i and image 0 for UAV j is computed by composing the homography matrices between consecutive images. For instance, H 202 = H 201 H 212. Combining the homographies H20i with H12 determines the homography matrices of UAV 2 at different time instants along its trajectory with respect to the view of UAV 1 at image 0. Sensors 2009, 9 7573 Figure 5. Scheme of relations between homographies. If the position of the reference UAV in a global frame is known, it will be easy to estimate the position of all the UAVs in the global frame. For instance, the location of UAV 2 at time of image 2 with respect the reference UAV at time of image 0 is given by H12H201H212. More details are given in [2]. Assume that a UAV team is executing a mission, for example a surveillance mission. One of the purposes of this work is to outline the replanning necessary to achieve that one UAV estimates the relative position of other UAV applying the method described above. As stated before, it is necessary that both UAVs take images of approximately the same scene. Given some invariant characteristic of the features used to establish matches between the two images [16], it is possible to face significant rotations, translations and scale shifts. However, in order to reduce the complexity of the matching stage, it is recommended to locate the two UAVs at approximately the same altitude (to reduce the scale shift effect) performing an angle of no more that 45 degrees (see Figure 6.b). Figure 6. An example illustrating the re-planning process: (a) UAVs following the initial plan. (b) Dynamic replanning: UAV B plan changes to include wp6. UAV B a) b) wp2 wp1 UAV A wp5 UAV B wp2 wp1 wp3 UAV A UAV C wp4 wp5 wp6 wp3 UAV C wp4 Sensors 2009, 9 7574 In addition, the uncertainty of the computed homography can be used as a measure of the accuracy of the relative position estimation. Particularly, the standard deviation of two parameters related with the uncertainty in the computed translation in pixel space will be used (UDev, VDev), when the homography is scaled such as h33 = 1. This standard deviation has been computed with the data obtained in many experiments with the real vehicles. From these results it can be stated that, in general, the computation of the relative position is very good if these deviations are lower than 1, good between 1 and 4, acceptable if they are between 4 and 7 and usually useless for values higher that 8. Notice that the correlation with the GPS has been intentionally discarded. 4. Planning for Multi-UAV FDI As it has been mentioned in Section 1, since the accuracy and the noise level of the estimation depend on several factors, dynamic replanning of the multi-UAV mission is applied to improve the estimation. This replanning is based on the automatic generation of new tasks for the multi-UAV team, which are dynamically allocated during the execution of the mission. In this section, plans are only considered at a “high level”, i.e. each plan consists in a partially ordered set of high level tasks such as “visit a waypoint with a given heading”. Then, if a plan is composed by a list of “visit waypoint” tasks, the executive level of the UAV should compute straight paths between consecutive waypoints as the reference for its controller. Once a waypoint has been reached, the UAV stays in hovering until certain conditions are satisfied. Then, the UAV proceeds with the next waypoint in the list. In general, the accuracy of the estimation is improved when the images of both UAVs are taken from points with similar altitude and camera orientation angles that differ less than 45º. Then, a suitable re-planning strategy is that the faulty UAV generates a task consisting in visiting a waypoint with a given camera orientation following this criteria and the safety constraints. Furthermore, a sufficient amount of texture in the images improves homography-based localization, and this can be used as an additional criterion to select the new waypoint. This new task is generated considering safety issues, which are critical in multi-UAV missions. The best solution would be the implementation of sense-and-avoid techniques, but sometimes this is not possible due to payload limitations in small UAVs. In our approach, the conflicts between paths of different UAVs are solved at a waypoint level considering a safety radius around each UAV and a maximum separation with respect to the reference path. If a potential conflict is detected in a plan, it is solved with the suppression and addition of waypoints. The initial trajectory planning takes into account a fixed inter-UAV safety distance, but when replanning is required, a different safety radius should be applied due to the uncertainties in the position of the faulty UAV. In our particular case, as the UAVs are helicopters, their hovering capabilities allow to simplify the conflict resolution problem when sharing the airspace. Once a fault has been detected, the UAV enters in a vision based hovering mode until another UAV provides additional information for the position estimation. In this mode, the UAV has a bigger (but bounded) safety radius for collision avoidance purposes. Then, the location of the waypoint satisfies the new safety radius constraints. Once an UAV has reached that place, it also stays hovering until the faulty UAV has landed.