Safety Science 65 (2014) 125–137
Contents lists available at ScienceDirect
Safety Science journal homepage: www.elsevier.com/locate/ssci
An evidential approach to physical protection system design Peida Xu a, Yong Deng b,c,⇑, Xiaoyan Su a, Xin Chen a, Sankaran Mahadevan c a
School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China School of Computer and Information Science, Southwest University, Chongqing 400715, China c Department of Civil and Environmental Engineering, Vanderbilt University, Nashville, TN 37235, USA b
a r t i c l e
i n f o
Article history: Received 15 May 2013 Received in revised form 23 October 2013 Accepted 13 January 2014 Available online 13 February 2014 Keywords: Information fusion Dempster–Shafer evidence theory Risk analysis Physical protection system Optimization design
a b s t r a c t A physical protection system (PPS) integrates people, procedures, and equipment for the protection of assets or facilities against theft, sabotage, or other malevolent intruder attacks. The physical protection components (detection, delay, and response) within a facility interact with each other and their locations significantly affects the effectiveness of PPS. This paper proposes a method based on an evidential approach to evaluate the risk level of PPS and optimally locate the physical protection components to balance cost and performance. Each individual component of the system is modeled in a simulated plane. Then, the risk level distribution of each component is determined based on its actual environment. The comprehensive risk level distribution is obtained by combining information from multiple sources within the framework of Dempster–Shafer evidence theory. Finally, optimization algorithms are used to find the optimal locations. A hypothetical example is discussed which demonstrates the usefulness of the developed methodology. Ó 2014 Elsevier Ltd. All rights reserved.
1. Introduction A physical protection system (PPS) integrates people, procedures, and equipment for the protection of assets or facilities against theft, sabotage, or other malevolent intruder attacks. The design of an effective PPS requires a systematic approach in which the designer weighs the objectives of the PPS against available resources, and then evaluates the proposed design to determine how well it meets the objectives. Without this kind of careful assessment, the PPS might waste valuable resources on unnecessary protection or, worse yet, fail to provide adequate protection at critical points of the facility. A PPS can be seen as a typical man-in-the-loop system. The system includes not only the physical equipment to detect, delay and respond, but also guards to monitor and protect the system, where human factors analysis plays an important role. Many studies have been reported on PPS-related research (Kobza and Jacobson, 1997; Garcia, 2001; Jaeger, 2003; Garcia, 2005; Moore et al., 2007; Scaparra and Church, 2008; Jang et al., 2009; Hester and Mahadevan, 2010; Hester et al., 2010; Xu et al., 2010; Berle et al., 2011). Garcia provided detailed discussion on models and methods to guide the design, evaluation and vulnerability assessment of PPS (Garcia, 2001, 2005). The main functions of PPS are detection, delay and response. For an effective system ⇑ Corresponding author at: School of Computer and Information Science, Southwest University, Chongqing 400715, China. Tel./fax: +86 023 68254555. E-mail address:
[email protected] (Y. Deng). http://dx.doi.org/10.1016/j.ssci.2014.01.003 0925-7535/Ó 2014 Elsevier Ltd. All rights reserved.
there must be awareness of an intruder (detection) and slowing of progress of the intruder to the target (delay), thus allowing a response force to interrupt or stop the adversary in time (response). Therefore, the effectiveness of a PPS can be calculated in terms of its degree of success in achieving detection, delay and response. Several vulnerability assessment methods for security systems have been proposed (Moore et al., 2007; Scaparra and Church, 2008; Jaeger, 2003; Berle et al., 2011; Xu et al., 2010). One of the commonly used methods to evaluate the effectiveness of a PPS is pathway analysis of potential outside attack (Garcia, 2001, 2005), focusing on delay time. For example, one can use a simulation code to find the highest risk pathway of the PPS, then some improvements such as adding a new delay unit in the pathway can increase the effectiveness of the system. However, as pointed out in Jang et al. (2009), Garcia’s work (Garcia, 2001, 2005) does not use a two-dimensional map for pathway analysis and thus has limitations in representing the structure of a PPS. Besides the problem above, other issues also need attention. There are many sources of uncertainty in a PPS. Probability theory has been applied for uncertainty modeling and vulnerability assessment. In some situations, however, the uncertainty is not randomness but fuzziness. Fuzzy set theory and Dempster–Shafer evidence theory have been shown to be effective in dealing with both aleatory and epistemic uncertainty in many applications of decision making and risk analysis. The PPS consists of many different kinds of sensors which provide subjective or objective data. A data fusion method is desired to combine various types of data.
126
P. Xu et al. / Safety Science 65 (2014) 125–137
Then how to efficiently represent and propagate the available information in the evaluation procedure? Probability theory, fuzzy set theory, rough set theory and evidence theory, have been proposed to deal with uncertainty. For example, Bajpai et al. (2010) use fuzzy numbers to analyze security risk. However, among these tools, evidence theory is able to model not only probabilistic data but also fuzzy data. In addition, the Dempster’s rule in evidence theory provides an effective method to combine evidence from different sources (Deng et al., 2011a,b,c; Deng and Chan, 2011; Basir and Yuan, 2007). Therefore, evidence theory is seen to be a reasonable tool to handle uncertainty in PPS evaluation. A 3-D visual threat distribution map of a PPS can be constructed using a mathematical model based on evidence theory (Xu et al., 2010). This model integrates multiple sensor information and facility layout information within the framework of the Dempster–Shafer evidence theory. By this method, a simplified PPS model, as shown in Fig. 1, can be evaluated as a 3-D visual threat distribution map, as shown in Fig. 2. Following Garcia’s work (Garcia, 2001, 2005), we can calculate the delay time corresponding to the path lengths and the additional delay that the delay equipments bring about. One can easily find two paths with the same delay time but significantly different threat distribution along each path. Based on this model, this paper aims to solve the following two problems: 1. Can the PPS designer optimally locate the sensors based on this visual mathematical model? In other words, are there some optimal solutions of the corresponding optimization problem? 2. How to solve the corresponding optimization problem? This paper proposes solutions to the above problems and shows an approach to finding a global optimal solution in an efficient manner. The designer can also consider different objectives and their weights in the overall objective function using the proposed method. In summary, this paper proposes a method to optimally design the PPS under the framework of evidence theory. The proposed method is helpful not only in mathematical modeling and visualization but also provides potential guidance to engineering practice with respect to PPS. The organization of the rest of this paper is as follows. Section 2 gives a brief introduction to some necessary related concepts. The proposed method is presented in Section 3. Section 4 investigates the effectiveness of the proposed method for optimization of PPS using a hypothetical facility example. The paper is concluded in Section 5. 2. Preliminaries In this section, some related concepts are briefly introduced, including evidence theory, the evidence distance, and the modified
averaging approach to combine evidence. These concepts are used to handle uncertainty and obtain the risk level in the PPS evaluation. 2.1. Dempster–Shafer evidence theory The mathematical theory of evidence, as introduced by Dempster (1967) and extended later by Shafer (1976), is concerned with the question of belief in a proposition and systems of propositions. ‘Belief’ in a proposition conceptually does not necessarily mean the ‘chance’ of the proposition being true. Evidence can be considered in a similar way when forming propositions, and as such, the Dempster–Shafer theory (D–S theory) is concerned with evidence, weights of evidence and belief in evidence (Shafer, 1976). Thus, this theory can be viewed as a generalization of the classic probability theory. Due to its ability to handle uncertainty or imprecision embedded in the evidence, the D–S theory has been increasingly applied in many fields (Andersen and Hooker, 1996; Murphy, 2000; Liu and Shenoy, 2004; Deng et al., 2004; Hilhorst et al., 2008; Xu et al., xxxx). Formally, the evidence theory consists of the following basic concepts: (1) Frame of discernment: Evidence theory starts with the definition of a set of hypotheses h called the frame of discernment, defined as:
h ¼ fH1 ; H2 ; . . . ; HN g
ð1Þ
The set h is composed of N exhaustive and exclusive hypotheses. Denote PðhÞ, the power set composed of 2N propositions of h as:
PðhÞ ¼ f;; fH1 g; fH2 g; . . . ; fHN g; fH1 [ H2 g; fH1 [ H3 g . . . hg ð2Þ where ; denotes the empty set. The N subsets containing only one element each are called singletons. (2) Mass functions, focal elements, and kernel elements: When the frame of discernment is determined, the mass function m is defined as a mapping of the power set PðhÞ to a number between 0 and 1, i.e.,
m : PðhÞ ! ½0; 1
ð3Þ
and which satisfies the following conditions:
X
mðAÞ ¼ 1;
ð4Þ
mð;Þ ¼ 0
ð5Þ
A2PðhÞ
The mass function m is also called the basic probability assignment (BPA) function. mðAÞ expresses the proportion of all relevant and available evidence that supports the claim that a particular element of h belongs to the set A but to no particular subset of A. Any subset A of h such that mðAÞ > 0 is called a focal element; C ¼ [mðAÞ–0 A is called a kernel element of mass function m in h. (3) Rule of evidence combination: Suppose m1 and m2 are two mass functions formed based on the information obtained from two different information sources in the same frame of discernment h; the Dempster’s rule of combination (also called orthogonal sum), denoted by m ¼ m1 m2 , combines two BPAs m1 and m2 to yield a new BPA:
P
B\C¼A m1 ðBÞm2 ðCÞ
mðAÞ ¼ k¼
X
1k m1 ðBÞm2 ðCÞ
B\C¼;
Fig. 1. System model.
ð6Þ ð7Þ
127
P. Xu et al. / Safety Science 65 (2014) 125–137 1 0.9
1 0.8
Threat
0.8
guard
0.6
0.7
0.4
0.6
0.2
0.5
0 100
0.4 0.3
80 60
0.2
100
40
camera y
80
0.1
60
20
40 0
20 0
0
x
Fig. 2. 3-D visual threat distribution map of the PPS.
where k represents a basic probability mass associated with conflicts among the sources of evidence. It is determined by summing the products of mass functions of all sets where the intersection is null. The larger the value of k is, the more conflicting the sources, and the less informative their combination. 2.2. Evidence distance In Jousselme et al. (2001), Jousselme et al. proposed an evidence distance function. Definition 2.1. Let m1 and m2 be two BPAs on the same frame of discernment H, containing N mutually exclusive and exhaustive hypotheses. The distance between m1 and m2 is:
rffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ! T ! ! 1 ! dBPA ðm1 ; m2 Þ ¼ ðm1 m2 Þ Dðm1 m2 Þ 2
ð8Þ
where m1 and m2 are the BPAs and D is a 2N 2N matrix whose elejA \ Bj . A; B 2 PðHÞ. ments are DðA; BÞ ¼ jA [ Bj Evidence distance function plays an important role in conflict management in multi-source data fusion (Deng et al., 2004; Guo et al., 2006). For detailed steps to compute the evidence distance, refer to the appendix in Beynon (2006). 2.3. Pignistic probability transformation In Section 3, Pignistic Probability Transformation (PPT) is used to transform BPA to probability. The pignistic probability is defined as below (Smets and Kennes, 1994):
X jA \ Bj mðBÞ Ppig ðAÞ ¼ jBj ð1 mð;ÞÞ B#h
ð9Þ
and since mð;Þ ¼ 0, this equation can be simplified as:
Ppig ðAÞ ¼
X jA \ Bj mðBÞ B#h
jBj
2.4. Modified averaging approach to combine evidence Dempster’s rule of combination has several interesting mathematical properties such as commutativity and associativity but becomes invalid when combining highly conflicting evidence, as discussed by Zadeh (1986). For example, if H ¼ fa; b; cg, and m1 ðAÞ ¼ 0:99; m1 ðBÞ ¼ 0:01, m2 ðBÞ ¼ 0:01; m2 ðCÞ ¼ 0:99, according to Dempster’s combination rule, the result is mðAÞ ¼ 0, mðBÞ ¼ 1; mðCÞ ¼ 0, which is paradoxical. Many methods are proposed to solve this problem (Smets and Kennes, 1994; Lefevre et al., 2002). Murphy proposed an averaging method, which can handle the conflicting evidence combination efficiently (Murphy, 2000). Deng et al. proposed a modified averaging approach based on Murphy’s method and obtained a more reasonable result (Deng et al., 2004). This method is described as below: Denote dðmi ; mj Þ as the distance between two bodies of evidence ðRi ; mi Þ and ðRj ; mj Þ. The similarity measure Simij between two bodies of evidence can be defined as:
Simij ðmi ; mj Þ ¼ 1 dðmi ; mj Þ
Suppose the number of bodies of evidence is k. After all the degrees of similarity between the bodies of evidence are obtained, we can construct a similarity measure matrix (SMM), which gives us insight into the agreement between the bodies of evidence.
0
1 B . B .. B B SMM ¼ B B Si1 B . B . @ .
S12 .. .
Si2 .. .
Sk1
Si2
Snj
where jX j is the number of singleton elements in set X. After the combination, a decision can be made according to the pignistic probability. Refer to Smets’ work (Smets and Kennes, 1994) for more details about PPT.
Sij
Sij
The support degree of ði ¼ 1; 2; . . . ; kÞ is defined as:
Supðmi Þ ¼ ð10Þ
ð11Þ
k X
Simðmi ; mj Þ
.. .
S1k
1
1
C C C C S1n C C C .. C A . the
body
of
evidence
ðRi ; mi Þ
ð12Þ
j¼1;j–i
The credibility degree Crdi of the body of evidence ðRi ; mi Þ ði ¼ 1; 2; . . . ; kÞ is defined as:
Supðmi Þ Crdi ¼ Pk i¼1 Supðmi Þ
ð13Þ
128
P. Xu et al. / Safety Science 65 (2014) 125–137
Pn
It is obvious that i¼1 Crdi ¼ 1, thus, the credibility degree is actually a weight, which shows the relative importance of the evidence collected. After defining the credibility degree, the modified average (or the weight average) of the evidence MAE is given as:
MAEðmÞ ¼
n X ðCrdi mi Þ
ð14Þ
i¼1
If there are n pieces of evidence, one can use the classical Dempster’s rule to combine the weighted average evidence ðn 1Þ times, which is the same as Murphy’s approach (Murphy, 2000). Solving Zadeh’s example by the modified averaging approach, a more reasonable result, mðAÞ ¼ 0:4999; mðBÞ ¼ 0:0002; mðCÞ ¼ 0:4999, is obtained. For more detailed information, refer to Deng et al. (2004). 3. Proposed method The proposed method is detailed in this section. First, the evidential risk evaluation model is constructed. Then, the optimization problem is formulated and optimization algorithms are used
to find the optimal solution. The flowchart of the proposed method is shown in Fig. 3. 3.1. Evidential risk evaluation model 3.1.1. System constitutive model There are significantly different steps in physical protection system design. First, the designer should determine the components that can be used and the protection area. Second, all the components need to be located in a simulated 2-D plane, thus a simplified system model is built. Third, the calculating method of threat distribution for each component needs to be specified. In this paper, we assume that the PPS consists of the following three types of components: (1) Detection equipment, which has the ability to detect the intruder and raise alarm. Examples are interior sensors and exterior sensors, which are widely used in the PPS. (2) Delay equipment, which can slow down the adversary progress (such as fences, walls and doors which can slow the intruder). The delay equipment has a limited range of action. (3) Response force, which consists of the actions taken by the response force to prevent adversary success. Examples are guards, police dogs and so on. Their distances to the target are very important, and can be used to calculate the maximum safety range for each target. Most of the intruding acts are not random; they are intentional by a thinking malevolent adversary. Much of the uncertainty in estimating the risk of an intruding act is epistemic (state of knowledge) instead of aleatory (stochastic). There are several types of intruding acts, such as theft, and sabotage. In this paper, we consider the worst case, sabotage, which is to reach the target and damage it. For example, consider a simplified system as shown in Fig. 1. This model contains different types of equipment and will be used as a hypothetical example in this paper to show the proposed method. Given a square plane, we consider the following four components. Component 1 is a camera, component 2 a guard, component 3 a door, and component 4 a wall. In the middle of the plane, the protection target is given. There may be multiple targets and multiple intruders. One target and one intruder are considered in this paper for simplicity. 3.1.2. Component threat distribution The camera is detection equipment. Its reported threat for each point in the plane will become larger as the distance of the point to it increases.
T1 ¼
d1 d1 max
ð15Þ
In Eq. (15), d1 represents the distance to the camera for each plane point in the camera’s range of action, d1max represents the maximum value of d1 . As d1 becomes larger, the probability to detect the intruder becomes smaller, thus T 1 becomes higher. The threat distribution for the camera is shown in Fig. 4. The blue area is out of the camera’s action range, thus the corresponding points’ threats are regarded as unknown and will not be included in the subsequent transformation and combination. The guard is response force. The reported threat can be obtained in a similar manner as the camera.
T2 ¼
Fig. 3. Flowchart of the proposed method.
d2 d2 max
ð16Þ
In Eq. (16), d2 represents the distance to the guard from each plane point in the model plane, d2max represents the maximum value of d2 . As d2 becomes larger, the probability to prevent adverse behavior becomes smaller, thus T 2 becomes higher. The threat distribution
129
P. Xu et al. / Safety Science 65 (2014) 125–137 1
0.9
1 0.8
Threat
0.8 0.6
0.7
0.4 0.2
0.6
0 100
0.5
0.4
80 60
0.3
40
y
100
camera
0.2
80 60
20 40 0
0.1
20
x
0
0
Fig. 4. Threat distribution for the camera (location: (0, 0)).
1
0.9
0.8
1
guard
0.8
Threat
0.7
0.6 0.6
0.4 0.2
0.5
0 100
0.4
80
0.3
60 100
y
0.2
80
40 60 20
0.1
40 20 0
x
0
0
Fig. 5. Threat distribution for the guard (location: (15, 80)).
for the guard is shown in Fig. 5. The guard’s position is obviously important, so the guard should not be too far from the target. The minimum safe distance is denoted as Dmin . When the intruder’s distance to the target is smaller than Dmin , even though the guard receives the alarm, the intrusion cannot be defeated, which means the protection system has failed. Dmin is conditional on the guard’s distance to the target, the door’s and wall’s effectiveness. The threat for Dmin decreases as the intruder’s distance to the target increases. In this paper, we assume the door has detection function and delay function. Its reported threat depends on the probability of the intruder being detected by the door, P d , and the delay caused by the door’s resistance, Dd . We consider it in the calculation of Dmin . In order to measure its delay function, denote:
D3 ¼ Pd Dd
ð17Þ
Locations outside the door will have additional delay distance to the target. On the other hand, the door has no effect on locations inside the inner wall. The inner wall is also delay equipment. Its reported threat depends on its physical strength. We also consider this delay in the calculation of Dmin . Denote D4 as the expected delay distance of the wall. Given some parameters related to Dmin , as shown in Table 2, the threat distribution for Dmin can be obtained, as shown in Fig. 6. In this step, the number of components and their threat distribution strategies can be determined by the system designer according to the actual situation. The strategies shown above are simple and they are only used to illustrate the proposed method.
130
P. Xu et al. / Safety Science 65 (2014) 125–137 1
0.9
0.8
1
Threat
0.8 0.7
0.6 0.4
0.6
0.2 0.5
0 100
0.4
80 0.3
60 100
y
40
80
0.2
60 20
40 20 0
0.1
x
0
0
Fig. 6. Threat distribution for Dmin .
3.1.3. Transform threat to BPA In order to represent and propagate the uncertainty under the framework of evidence theory, the threat distributions obtained above need to be transformed into basic probability assignments (BPA). First, the designer needs to determine the frame of discernment (FOD) according to the specified system requirement. In this paper, we assume the FOD as flow; moderate; high; v eryhighg. The threat value of each location for each component ranges from 0 to 1. The following method is used to achieve the transformation. Set four threshold values of threat for the interval [0, 1], i.e., 0.125, 0.375, 0.625 and 0.875. They divide the threat range into five parts. The BPA can be determined according to Table 1: The remaining situations can be obtained in the similar manner. The transformation process is shown in Fig. 7. For example, when the threat is 0.2, we have: mðflowgÞ ¼ 0:7; mðflow; moderategÞ ¼ 0:3. Since T ¼ 0:2, we not only assign 0.7 to the proposition flowg, but also assign 0.3 to the proposition flow; moderateg. 3.1.4. Combination and visualization So far, we have obtained the BPA of each location for each component. In order to get a comprehensive system risk BPA, the BPAs for each location from different components need to be combined. Since there is always high conflict between the BPAs from different components, combination should not be implemented using the Dempster’s combination rule. Instead, we adopt the modified averaging approach (Deng et al., 2004) as mentioned in Section 2.
Table 1 Transformation rules. If
then
T 2 ½0; 0:125Þ T 2 ð0:875; 1 T 2 ½0:125; 0:25Þ
mðflowgÞ ¼ 1 mðfv ery highgÞ ¼ 1 mðflowgÞ ¼ ð0:375 TÞ=0:25 mðflow; moderategÞ ¼ 1 mðflowgÞ mðflowgÞ ¼ mðfmoderategÞ ¼ 0:5 mðfmoderategÞ ¼ ðT 0:125Þ=0:25 mðflow; moderategÞ ¼ 1 mðfmoderategÞ ...
T ¼ 0:25 T 2 ð0:25; 0:375 ...
The system risk BPA can be obtained using the above steps. Considering decision-making and visualization, the system risk BPA should be transformed into a single valued threat from 0 to 1. Therefore, the system risk BPA is transformed to a probability value using PPT, as shown in Eq. (10). Then, based on the probability distribution, the system threat can be calculated as in.
T ¼ 0:33 Ppig ðfmoderategÞ þ 0:66 Ppig ðfhighgÞ þ Ppig ðfv ery highgÞ
ð18Þ
In Eq. (18), the weights can be set based on the actual environment. Finally, a comprehensive system threat distribution is obtained in the model plane. For example, for the simplified PPS model shown in Fig. 1, the overall threat distribution map is obtained from Eq. (18) and shown in Fig. 8. 3.2. Comparison with the probability risk evaluation model For each point in the plane, its threat with respect to each component can be regarded as the probability to prevent adverse behavior when the intruder is in that point. We can calculate the average threat (probability) to get a threat distribution map of the PPS as shown in Fig. 9. Comparing Figs. 8 and 9, we found that the evidential risk evaluation model has the following advantages: 1. The result of evidential model has a higher differentiation degree than that of the probability model since the exploitation of the combination rule. For example, the threats in the areas that near the camera and the guard in the evidential model are very low since the existence of these two protection components. In the critical area as shown in Fig. 8, the threat is high since two components (the camera and the guard) show high threat levels in this area. In the result of the probability model, the differences of threats in these three areas are not that significant. Therefore the evidential model is more reasonable and intuitive. 2. The evidential model is more effective in dealing with both aleatory and epistemic uncertainty. The basic probability assignment (BPA) can represent different kinds of knowledge. For example, the expert can express their opinion eas-
131
P. Xu et al. / Safety Science 65 (2014) 125–137
1 0.9
{low}
0.8 high
moderate
low
{low, moderate}
very high
mass functions
0.7 {moderate}
0.6 {moderate, high}
0.5 0.4
{high}
0.3
{high, very high}
0.2 {very high}
0.1 0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
threat Fig. 7. Transform threat to BPA.
1 0.9
1
Threat
0.8
0.8
guard
0.6
0.7
0.4 0.6
0.2 0 100
0.5 0.4 0.3
50 100
camera y
0.2
80 60
0.1
40 0
20 0
x
critical area
0
Fig. 8. Threat distribution map of the PPS using the proposed method.
ily by using the BPA. The PPS consists of many different kinds of sensors which provide subjective or objective data. These data can be represented as BPA as well. Thus the evidential model provides a solution to handle different kinds of uncertain information, and can help to make a decision after information fusion. The evidential model requires more computational effort than the probability model due to the combination process. This problem can be mitigated by using the advanced computation technology or the modification of combination rule. 3.3. Design optimization The purpose of this subsection is to develop a mathematical model for design optimization of PPS. In order to undertake this optimization, a multi-objective optimization problem is introduced and some optimization algorithms are used to solve this problem. 3.3.1. Problem formulation The optimization problem can be formulated as follows:
minimize T obj ¼
p X wk T k ðxÞ
ð19Þ
k¼1
subject to 0 6 xð2i 1Þ 6 L1 i ¼ 1; 2; 3; . . . ; n 0 6 xð2iÞ 6 L2 i ¼ 1; 2; 3; . . . ; n xðjÞ is integer j ¼ 1; 2; 3; . . . ; 2n
where T obj is the overall objective function, x is the vector of input coordinates (design variables) of all the components (camera or guard), T k ðxÞ is the kth objective related to the system threat distribution surface, p is the number of objectives, wk is the weight of the kth objective, L1 L2 is the plane’s size, and n is the components’ number. The designer should determine the different objectives related to the system threat map, and then set their weights according to the practical case. The weights show the relative importance of different and will affect the final optimization results. For example, the objectives can be the maximum threat of the PPS or the mean threat of the PPS, etc.
132
P. Xu et al. / Safety Science 65 (2014) 125–137
1 0.9
1
Threat
0.8
0.8
guard
0.7
0.6 0.4
0.6
0.2 0.5
0 100
0.4 0.3 0.2
50 100 80
camera
0.1
60 40
y
20
0
0
critical area
0
x
Fig. 9. Threat distribution map of the PPS using the probability risk evaluation method.
3.3.2. Solution methodology Eq. (19) gives a nonlinear integer programming problem and is NP-hard in general. Research efforts during the past two decades have led to the development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables (Hemmecke et al., 2010). There are several algorithms that may address the problem in the proposed method, the Branch-and-Bound (B&B) algorithm (Land and Doig, 1960), the Extended Cutting Plane (ECP) algorithm (Westerlund and Pettersson, 1995), the branch-and-cut algorithm (Mitchell, 2002), the genetic algorithm (Holland, 1975; Deep et al., 2009; Deb, 2000), and the DIRECT (DIviding RECTangles) algorithm (Jones et al., 1993; Finkel, 2003). In order to use the DIRECT algorithm, we round the elements of x to the nearest integers when the DIRECT algorithm evaluates the objective function. When we solve the problem by using the algorithms mentioned above individually, the global optimization
Table 2 Component parameters. Component
Facility area
Wall
Door
Dmin
Pd
Dd
D3
D4
Parameter
100 100
40 40
(45, 70)
50
0.6
50
30
40
Table 3 System evaluation results in Experiment 1. Best location
Worst location
0.5089 0.6347 0.3831 (50, 72) (39, 72)
0.7559 0.9947 0.5171 (100, 0) (71, 50)
1
camera
0.9
guard
1
0.8
0.8
Threat
T obj T1 T2 Camera Guard
0.7
0.6 0.6
0.4 0.2
0.5
0 100
0.4
80
0.3
60
y
100 80
40
60 40
20 20 0
x
0
Fig. 10. System threat surface in the best location scenario.
0.2 0.1 0
133
P. Xu et al. / Safety Science 65 (2014) 125–137
1
guard
0.9
camera
1
0.8
Threat
0.8 0.7
0.6 0.4
0.6
0.2 0.5
0 100
0.4
80 0.3
60 100
y
40
0.2
80 60 20
0.1
40 20 0
x
0
0
Fig. 11. System threat surface in the worst location scenario.
solution is not always obtained. In some cases, the algorithm converges to the local minimum value or cannot converge. In other cases, although the algorithm found the global minimum solution, the computational expense is too high. Inspired by the concept of surrogate model, we combine the DIRECT algorithm with the genetic algorithm, to solve the problem accurately and efficiently. The DIRECT algorithm samples points in the domain, and uses the information it has obtained to decide where to search next. The DIRECT algorithm will globally converge to the minimal value of the objective function. Unfortunately, this global convergence may come at the expense of a large and exhaustive search over the domain. A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population ’’evolves’’ toward an optimal solution. The design variables in the nonlinear integer programming problem can be easily encoded in the genetic algorithm. Thus the problem can be solved using the genetic algorithm in a heuristic manner. However, the random initial population significantly affects the result and computational expense of the genetic algorithm. When the current minimum value in the DIRECT algorithm does not change for several iterations, we take the current minimum solution as the initial point of the genetic algorithm. In other words, the DIRECT algorithm is used to find an initial suboptimal solution, and then the genetic algorithm efficiently searches the domain near the optimal solution to find a better solution. Since the genetic algorithm is a heuristic search algorithm, the output solution is not always the global optimal solution. However, with the initial solution generated by the DIRECT algorithm, the genetic algorithm can find the solution with an objective function value that is close to the global minimum objective value in a few generations (iterations). The optimized objective value of the genetic algorithm also has a small. The variance can be controlled based on the number of runs of the genetic algorithm.
Table 4 System evaluation results in Experiment 2.
a
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Best location
Worst location
T obj
T1
T2
T obj
T1
T2
0.3172 0.3580 0.3902 0.4464 0.4563 0.5089 0.5205 0.5444 0.5681 0.5919 0.6155
0.9932 0.6497 0.6476 0.7270 0.6469 0.6347 0.6157 0.6157 0.6157 0.6157 0.6155
0.3172 0.3256 0.3258 0.3261 0.3292 0.3831 0.3776 0.3779 0.3779 0.3779 0.3781
0.5181 0.5648 0.6134 0.6612 0.7091 0.7559 0.8050 0.8529 0.8992 0.9488 1.0000
0.9947 0.9947 0.9947 0.9967 0.9967 0.9947 0.9967 0.9967 0.9947 0.9967 1.0000
0.5181 0.5171 0.5181 0.5174 0.5174 0.5171 0.5174 0.5174 0.5171 0.5174 0.4208
Table 5 Component coordinates in Experiment 2.
a 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Best location
Worst location
Camera
Guard
Camera
Guard
(43, 60) (41, 4) (42, 2) (61, 9) (58, 2) (50, 72) (32, 71) (33, 71) (33, 71) (33, 71) (33, 71)
(29, 71) (38, 73) (38, 73) (33, 72) (38, 73) (39, 72) (39, 72) (39, 72) (39, 72) (39, 72) (39, 71)
(100, 0) (100, 0) (100, 0) (100, 2) (100, 2) (100, 0) (100, 2) (100, 2) (100, 0) (100, 2) (50, 50)
(100, 47) (71, 50) (100, 47) (100, 47) (100, 47) (71, 50) (100, 47) (100, 47) (71, 50) (100, 47) (83, 50)
4. Experiments In this section, a hypothetical example is discussed and three experiments are carried out to demonstrate the proposed method. 4.1. Example problem We use the simplified model in Fig. 1 as a hypothetical example. The components’ parameters are set as in Table 2. The size of the
134
P. Xu et al. / Safety Science 65 (2014) 125–137
1
Best location Worst location
0.9 0.8 0.7
Tobj
0.6 0.5 0.4 0.3 0.2 0.1 0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
α Fig. 12. T obj vs. a.
1 0.9 0.8 0.7
T1
0.6 0.5
Best location Worst location
0.4 0.3 0.2 0.1 0
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0.7
0.8
0.9
1
α Fig. 13. T 1 vs. a.
1 0.9
Best location Worst location
0.8 0.7
T2
0.6 0.5 0.4 0.3 0.2 0.1 0
0
0.1
0.2
0.3
0.4
0.5
0.6
α Fig. 14. T 2 vs. a.
facility is 100 100 units. The inside wall’s size is 40 40 units. Dmin is the minimum safety distance. P d indicates the probability of the intruder being detected by the door. Dd is the door’s delay distance (physical strength), and D3 is the expected delay distance
of the door. D4 is the wall’s physical delay distance. We consider D3 and D4 within the Dmin ’s threat distribution. When the camera is located at (0, 0) and the guard is located at (15, 80), the system threat distribution is shown in Fig. 2.
135
P. Xu et al. / Safety Science 65 (2014) 125–137
We construct the optimization problem as below:
4.3. Experiment 2
minimize T obj ¼ aT 1 þ ð1 aÞT 2
In this experiment, we want to show how a affects the system evaluation results. The designer can change the weights of different objectives in the overall objective function to meet the specific requirement. a is set from 0 to 1 in steps of 0.1 (eleven scenarios). The system only contains one camera and one guard. a can reflect the relative importance of different objectives through the system evaluation results. In each of the eleven scenarios, we solved the optimization problem as in Eq. (20) and found the solution for the best locations of the components. Then we solved the problem that maximizes T obj and found the solution for the worst locations of the components. The results are shown in Tables 4, 5 and Figs. 12–14. In Figs. 12–14, the blue bar indicates the range of threat. From the results, we observe that the range of T obj increases as a becomes larger. T 1 decreases and T 2 increases as a becomes larger, since the importance of T 1 and T 2 varies with regard to Eq. (20).
where T 1 ¼ maxfTðxÞg T 2 ¼ meanfTðxÞg
ð20Þ
subject to 0 6 xð2i 1Þ 6 L1 i ¼ 1; 2; 3; . . . ; n 0 6 xð2iÞ 6 L2 i ¼ 1; 2; 3; . . . ; n xðjÞ is integer j ¼ 1; 2; 3; . . . ; 2n where T obj is the objective function, x contains the input coordinates of all the components (camera or guard), TðxÞ is the system threat distribution surface, T 1 is the maximum threat, T 2 is the mean threat, a is the weight of T 1 , ð1 aÞ is the weight of T 2 , L1 L2 is the plane’s size, and n is the components’ number. We use the DIRECT algorithm (Jones et al., 1993; Finkel, 2003) to find the initial suboptimal point. When the current minimum value in the DIRECT algorithm does not change for three iterations, we take the current minimum solution as the initial point for the genetic algorithm. We implement the genetic algorithm with MATLAB, using the method in Deep et al. (2009) and Deb (2000). 4.2. Experiment 1
4.4. Experiment 3
In this experiment, we want to show the improvement of the system effectiveness after using the proposed method. a is set as 0.5 and the system only contains one camera and one guard. The locations of the camera and the guard will affect the system threat distribution. We solved the optimization problem as in Eq. (20) and found the optimal or best locations of the components. Then we solved the problem that maximizes T obj and found the worst locations of the components. The results are shown in Table 3. The corresponding system threat surfaces are shown in Figs. 10 and 11. From the above results, we observe that the locations of system components obviously affect the system protection performance. Therefore, it is necessary to intelligently locate the system components to meet the protection requirements.
In this experiment, we want to show how the available resources affect the system optimization results. The designer can improve the system effectiveness by optimally locating the protection resources or by adding more protection resources. a is set as 0.5. We consider four scenarios with different amounts of resources. In each of the four scenarios, we found the solutions for the best and worst locations of the components. The results are shown in Table 6 and Figs. 15–17. From the results, we observe that in the cases of best location, T obj decreases as the amount of resources becomes larger. The ranges of threat in different scenarios are wide, which manifests optimally locating of components can improve the system protection ability.
Table 6 System evaluation results in Experiment 3. Scenario
Resources
NO.
#Camera
#Guard
T obj
Best location T1
T2
T obj
Worst location T1
T2
1 2 3 4
1 1 2 2
1 2 1 2
0.5089 0.4975 0.4855 0.4794
0.6347 0.6694 0.6274 0.6595
0.3831 0.3255 0.3435 0.2992
0.7559 0.7995 0.7819 0.8035
0.9947 0.9995 0.9951 1.0000
0.5171 0.5994 0.5687 0.6070
0.85 Best location Worst location
0.8 0.75
Tobj
0.7 0.65 0.6 0.55 0.5 0.45 0
1
2
3
scenario Fig. 15. T obj in four scenarios.
4
5
136
P. Xu et al. / Safety Science 65 (2014) 125–137
1 0.95 0.9
T1
0.85 0.8 0.75 0.7 0.65 Best location Worst location
0.6 0.55 0
1
2
3
4
5
4
5
scenario Fig. 16. T 1 in four scenarios.
0.65 Best location Worst location
0.6 0.55
T2
0.5 0.45 0.4 0.35 0.3 0.25 0
1
2
3
scenario Fig. 17. T 2 in four scenarios.
4.5. Discussion
Acknowledgments
From the above experiments, we observe that the proposed method can help the designers in locating the system resources optimally and provides them with a flexible tool to consider different objectives with different importance. Given a fixed resources (fixed cost), one can optimally locate the system components via the proposed method. On the order hand, the designers can add extra protection resources and optimally locate the system components to meet their requirements with the proposed method.
The work is partially supported by Chongqing Natural Science Foundation (for Distinguished Young Scholars), Grant No. CSCT, 2010BA2003, National Natural Science Foundation of China, Grant Nos. 60933006 and 61174022, National High Technology Research and Development Program of China (863 Program) (No. 2012AA041101), R&D Program of China (2012BAH07B01), Doctor Funding of Southwest University Grant No. SWU110021, China State Key Laboratory of Virtual Reality Technology and Systems.
5. Conclusion The focus of this paper is to develop a mathematical framework for design optimization of physical protection system (PPS). The developed methodology utilizes an evidential approach to evaluate the risk level of PPS and optimally locates the physical protection components to balance cost and performance. The proposed method makes it possible to solve the design optimization problems based on evidence theory in an efficient manner, and assist critical facility operators in improving the design of physical protection systems. In future work, the method presented in this paper should be extended to include the space information of the facility structure, and to achieve a 3-D risk evaluation and optimization design model.
References Andersen, K.A., Hooker, J.N., 1996. A linear programming framework for logics of uncertainty. Decis. Support Syst. 16 (1), 39–53. Bajpai, S., Sachdeva, A., Gupta, J., 2010. Security risk assessment: applying the concepts of fuzzy logic. J. Hazard. Mater. 173 (1), 258–264. Basir, O., Yuan, X., 2007. Engine fault diagnosis based on multi-sensor information fusion using Dempster–Shafer evidence theory. Inform. Fusion 8 (4), 379–386. Berle, Ø., Asbjørnslett, B.E., Rice, J.B., 2011. Formal vulnerability assessment of a maritime transportation system. Reliab. Eng. Syst. Safety 96 (6), 696–705. Beynon, M.J., 2006. The role of the DS/AHP in identifying inter-group alliances and majority rule within group decision making. Group Decis. Negot. 15 (1), 21–42. Deb, K., 2000. An efficient constraint handling method for genetic algorithms. Comput. Methods Appl. Mech. Eng. 186 (2), 311–338. Deep, K., Singh, K.P., Kansal, M., Mohan, C., 2009. A real coded genetic algorithm for solving integer and mixed integer optimization problems. Appl. Math. Comput. 212 (2), 505–518.
P. Xu et al. / Safety Science 65 (2014) 125–137 Dempster, A., 1967. Upper and lower probabilities induced by a multivalued mapping. Ann. Math. Stat. 38 (2), 325–339. Deng, Y., Chan, F., 2011. A new fuzzy dempster MCDM method and its application in supplier selection. Expert Syst. Appl. 38 (8), 9854–9861. Deng, Y., Shi, W.K., Zhu, Z.F., Liu, Q., 2004. Combining belief functions based on distance of evidence. Decis. Support Syst. 38 (3), 489–493. Deng, Y., Chan, F.T.S., Wu, Y., Wang, D., 2011a. A new linguistic MCDM method based on multiple-criterion data fusion. Expert Syst. Appl. 38 (6), 6985–6993. Deng, Y., Jiang, W., Sadiq, R., 2011b. Modeling contaminant intrusion in water distribution networks: a new similarity-based DST method. Expert Syst. Appl. 38 (1), 571–578. Deng, Y., Sadiq, R., Jiang, W., Tesfamariam, S., 2011c. Risk analysis in a linguistic environment: a fuzzy evidential reasoning-based approach. Expert Syst. Appl. 38 (12), 15438–15446. Finkel, D.E., (2003). DIRECT Optimization Algorithm User Guide. Tech. Rep., Center for Research in Scientific Computation, North Carolina State University. Garcia, M.L., 2001. The Design and Evaluation of Physical Protection Systems. Butterworth-Heinemann, Boston. Garcia, M.L., 2005. Vulnerability Assessment of Physical Protection Systems. Butterworth-Heinemann, Boston. Guo, H.W., Shi, W.K., Deng, Y., 2006. Evaluating sensor reliability in classification problems based on evidence theory. IEEE Trans. Syst. Man Cybern. Part B – Cybern. 36 (5), 970–981. Hemmecke, R., Köppe, M., Lee, J., Weismantel, R., (2010). Nonlinear integer programming. 50 Years of Integer Programming 1958–2008, pp. 561–618. Hester, P.T., Mahadevan, S., 2010. A multicriteria approach to critical facility security system design. Appl. Multicriteria Decis. Making, Data Envelop. Anal. Finance 14, 105–131. Hester, P.T., Adams, K.M.G., Mahadevan, S., 2010. Examining metrics and methods for determining critical facility system effectiveness. Int. J. Crit. Infrastruct. 6 (3), 211–224. Hilhorst, C., Ribbers, P., van Heck, E., Smits, M., 2008. Using Dempster–Shafer theory and real options theory to assess competing strategies for implementing it infrastructures: a case study. Decis. Support Syst. 46 (1), 344–355. Holland, J.H., 1975. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence/by John H. Holland. MIT Press, Cambridge. Jaeger, C.D., 2003. Chemical facility vulnerability assessment project. J. Hazard. Mater. 104 (1), 207–213.
137
Jang, S., Kwak, S., Yoo, H., Kim, J., Yoon, W., 2009. Development of a vulnerability assessment code for a physical protection system: systematic analysis of physical protection (SAPE). Nucl. Eng. Technol. 41 (5), 747–752. Jones, D.R., Perttunen, C.D., Stuckman, B.E., 1993. Lipschitzian optimization without the Lipschitz constant. J. Optimiz. Theor. Appl. 79 (1), 157–181. Jousselme, A.L., Grenier, D., Bosse, E., 2001. A new distance between two bodies of evidence. Inform. Fusion 2 (2), 91–101. Kobza, J.E., Jacobson, S.H., 1997. Probability models for access security system architectures. J. Oper. Res. Soc. 48 (3), 255–263. Land, A.H., Doig, A.G., 1960. An automatic method of solving discrete programming problems. Econom.: J. Econom. Soc. 28 (3), 497–520. Lefevre, E., Colot, O., Vannoorenberghe, P., 2002. Belief function combination and conflict management. Inform. Fusion 3 (2), 149–162. Liu, L.P., Shenoy, P.P., 2004. Representing asymmetric decision problems using coarse valuations. Decis. Support Syst. 37 (1), 119–135. Mitchell, J.E., 2002. Branch-and-cut algorithms for combinatorial optimization problems. Handbook Appl. Optimiz., 65–77. Moore, D.A., Fuller, B., Hazzan, M., Jones, J.W., 2007. Development of a security vulnerability assessment process for the RAMCAP chemical sector. J. Hazard. Mater. 142 (3), 689–694. Murphy, C.K., 2000. Combining belief functions when evidence conflicts. Decis. Support Syst. 9 (1), 1–9. Scaparra, M.P., Church, R.L., 2008. A bilevel mixed-integer program for critical infrastructure protection planning. Comput. Oper. Res. 35 (6), 1905–1923. Shafer, G., 1976. A Mathematical Theory of Evidence. Princeton University Press, New Jersey. Smets, P., Kennes, R., 1994. The transferable belief model. Artif. Intell. 66 (2), 191– 234. Westerlund, T., Pettersson, F., 1995. An extended cutting plane method for solving convex MINLP problems. Comput. Chem. Eng. 19, 131–136. Xu, P.D., Su, X.Y., Wu, J.Y., Sun, X.H., Zhang, Y.J., Deng, Y., 2010. Risk analysis of physical protection system based on evidence theory. J. Inform. Comput. Sci. 7 (13), 2871–2878. Xu, P.D., Deng, Y., Su, X.Y., Mahadevan, S., A new method to determine basic probability assignment from training data, Knowl.-Based Syst. http://dx.doi.org/ 10.1016/j.knosys.2013.03.005. Zadeh, L.A., 1986. A simple view of the Dempster–Shafer theory of evidence and its implication for the rule of combination. AI Mag. 7 (2), 85.
