ABSTRACT
This work considers the problem of performing resilient sensor fusion using past sensor measurements. In particular, we consider a system with n sensors measuring the same physical variable where some sensors might be attacked or faulty. We consider a setup in which each sensor provides the controller with a set of possible values for the true value. Here, more precise sensors provide smaller sets. Since a lot of modern sensors provide multidimensional measurements (e.g., position in three dimensions), the sets considered in this work are multidimensional polyhedra.
Given the assumption that some sensors can be attacked or faulty, the paper provides a sensor fusion algorithm that obtains a fusion polyhedron which is guaranteed to contain the true value and is minimal in size. A bound on the volume of the fusion polyhedron is also proved based on the number of faulty or attacked sensors.
In addition, we incorporate system dynamics in order to utilize past measurements and further reduce the size of the fusion polyhedron. We describe several ways of mapping previous measurements to current time and compare them, under different assumptions, using the volume of the fusion polyhedron. Finally, we illustrate the implementation of the best of these methods and show its effectiveness using a case study with sensor values from a real robot.
PROBLEM FORMULATION AND PRELIMINARIES
This section describes the two problems considered in this paper. We start by formulating the multidimensional sensor fusion problem in a single time step (i.e., without taking history into account). Given this algorithm, we outline the problem of using system dynamics and past measurements to improve the system’s sensor fusion.
- Fusion Algorithm
- Fusing Past and Current Measurements
- Notation
SENSOR FUSION ALGORITHM
Figure 1: An illustration of the proposed sensor fusion algorithm.
The algorithm is illustrated in Figure 1. The system consists of three sensors, hence three polyhedra are obtained, and is assumed to have at most one corrupted sensor. There- fore, all regions contained in at least two polyhedra are found, and their convex hull is the fusion polyhedron (shaded).
Figure 2: An example showing that the bound specified in Theorem 1 is tight.
Theorem 1 suggests that if f < n=v then the volume of the fusion polyhedron is bounded by the volume of some polyhedron. We note that this condition may not always hold as the number of vertices of the fusion polyhedron may be the sum of the number of vertices of the polyhedra. However, the condition is tight in the sense that if it does not hold, then the volume of the fusion polyhedron may be larger than the volume of any of the individual polyhedra. This is illustrated in Figure 2.
FUSING PAST AND CURRENT MEASUREMENTS
Figure 4: Examples showing that, in general, polyhedra obtained using map_R_an_intersect and pairwise_intersect are not subsets of each other if A is not full rank.
We note, however, that without additional assumptions about the rank of A, map_R_and_intersect and pairwise_intersect are not subsets of each other. Counter-examples are presented in Figure 4. In Figure 4a, RN(t);f is a single point that is projected onto the x axis. Hence map_R_and_intersect is a subset of pairwise_intersect, which produces an interval of points. Conversely, Figure 4b shows an example where pairwise_intersect is a point, and map_R_and_intersect is an interval containing that point.
APPLICATIONS
The implementation is shown in Algorithm 2. In essence, at each point in time n polyhedra (the pairwise intersections) are stored. Thus, past meas represents the pairwise intersection” of all previous measurements of each sensor. In addition to being more efficient in terms of the size of the fusion polyhedron, the algorithm also needs very little memory – the required memory is linear in the number of sensors irrespective of how long the system runs.
Figure 6: Sizes of velocity (ONLY) fusion intervals for each of the three simulated scenarios; Dashed line – volume of the fusion polyhedra when measurement history is not considered, Solid line – volume of the fusion polyhedra obtained using pairwise_intersect.
Figure 7: Sizes of fusion polyhedra of velocity and position for each of the three scenarios simulated; Dashed line – volume of the fusion polyhedra when measurement history is not considered, Solid line – volume of the fusion polyhedra obtained using pairwise_intersect.
To illustrate consistence with earlier one-dimensional works, for each of the three scenarios we first computed the size of the fusion interval in one dimension. Figure 6 presents the results. Figure 7 presents the results when two-dimensional polyhedra are considered. Note that in this case there are only two sensors estimating the robot’s position – when one is corrupted, the size of the fusion polyhedron can grow dramatically.
CONCLUSION
This paper considered the problem of resilient multidimensional sensor fusion using measurement history. We focused on the setup where each sensor provides a multidimensional polyhedron as a measurement of the plant’s state. We presented a fusion algorithm for this case and gave bounds on the volume of the fusion polyhedron based on the number of corrupted sensors.
In addition, we investigated several methods of using history to improve sensor fusion and identified the best ones depending on what conditions the system in consideration satisfies. Finally, we presented a case study to illustrate the improvement in sensor fusion that can be obtained when history-based fusion is employed.
There are two main avenues that we plan to explore in the future. Firstly, one could consider extending this approach to nonlinear systems; in this scenario polyhedra may no longer be mapped into polyhedra. Thus, one can utilize a set membership technique in order to compute the set of possible true values. Secondly, one could take into consideration sensor trust, i.e., how often a sensor has been faulty over time, and incorporate this information in the mapping algorithm.
Source: University of Pennsylvania
Authors: Radoslav Ivanov | Miroslav Pajic | Insup Lee