Minimizing the expected time to detect a randomly located lost target using 3-dimensional search technique

Minimizing the expected time to detect a randomly located lost target using 3-dimensional search technique Tom´ as Caraballo1, Abd El-Moneim Anwar Teamah2, and Abd Al-Aziz Hosni El-Bagoury3 1Departamento de Ecuaciones Diferenciales y An´ alisis Num´ erico, Facultad de Matem´ aticas, Universidad de Sevilla c/ Tarfia s/n, 41012-Sevilla, Spain 2,3Department of Mathematics, Faculty of Science, Tanta University, Tanta, Egypt Abstract This paper considers a new model in search theory to find a randomly located target in the 3-dimensional space. An approximation algorithm that facilitates searching procedures for searchers or robots is presented. The expected time to detect the target is also proved. The statistical analysis by calculating the optimal search strategy which minimizes the time to detect the target, assuming trivariate standard normal distribution is provided, and the technique by flowcharts is designed as well. The effectiveness of this strategy is illustrated by introducing an application from real world. Keywords: 3-D Search; search theory; trivariate standard normal distributions, expected time, lost black box, 3-D search algorithm; optimal search.1 1 Introduction The study of search plans for located or moving targets has become an important tool in modern applications. To cite some interesting examples, we can start 1Corresponding author: Tom´ as Caraballo (email: [email protected]). Abd El-Moneim Anwar Teamah (email: [email protected]); Abd Al- Aziz Hosni El-Bagoury (email: [email protected]) 1 with a linear search strategy (see El-Rayes, Mohamed, and Fergani (1993), Mohamed, and Abou Gabal (2000, 2003, 2004)) and some important applications of this search model. For instance, searching for a defective unit in a large linear electric system, or searching for survivors in a desert, or a coordinated search technique studied in case of linear search (see Reyniers (1995,1996), Mohamed et al. (2007)). In the works Mohamed, Abou Gabal, and El-Hadidy (2009), Mohamed, Abou Gabal, and Afifi (2007), Mohamed, Abou Gabal, and El-Hadidy (2012), the authors discussed the coordinated search technique in the plane, when the located target has symmetric and asymmetric distribution. In case of moving targets, the cooperation between two searchers at the origin to find a random moving target on the real line has been analyzed in by El-Hadidy, and Abou Gabal (2018). Recently, El-Hadidy, and El-Bagoury (2017) proposed and studied a modern search model in the three dimensional space, in order to determine a located target in a 3-D known zone by a single searcher. More recently, El-Hadidy, and El-Bagoury (2017) introduced a coordinated search technique to find a 3-D randomly located target by two searchers. For more different kinds of applications and search plans, see Mohamed, Kassem, and El-Hadidy (2011, 2017), Mohamed, and El-Hadidy (2013), Mohamed, Abou Gabal, and El-Hadidy (2017), El-Hadidy (2016). 2 Problem Formulation Aircraft crashes have recently become one of the most difficult problems faced by scientists and research teams. In most cases, the cause of the accident remains unknown until the black box can be obtained and analyzed, and the problem becomes more complicated if the black box is hanged between two rocks in the bottom of seas and oceans. It is well known that the depths of seas and oceans have a special nature and shape (for instance, coral reefs and manifold rocks) which makes modern search devices unable to locate the target. Based on the more and more information introduced from air navigation devices, the difficulties of searching for the lost black box to determine the cause of air crash can be reduced a little. Also the target may be located in one of four zones, where it happens that the probability of detecting the target in the first zone is greater than the probability of detecting it in the second zone, and this is greater than the probability of detecting it the third one, and the latter is bigger than in the fourth zone. Therefore, we divide the search zone into four sub-zones zk, k = 1,2,3and 4where z1< z2< z3< z4, and we denote the probability of detecting the target in zone zkby p(zk);p(z1)> p(z2)> p(z3)> p(z4)These theoretical assumptions refer to the experts and statisticians as a result of the information provided from the air navigation devices, for example the beginning of a plane deviation etc. The primary purpose of the search mission is to facilitate the searching way by using 2 a new search technique, we should also take account of the fact that modern technologies are facing high difficulties to locate the target, so we should decrease the first zone returns (distance units), where me may have high probability of detecting the target. Then, we have to decrease the range of the sensor (radar) in the first zone, to fads away the special nature of seas and oceans. In the second zone, the range of the sensor will be larger than in the first one and smaller than in the third zone, where the probability of detecting the target in the second zone smaller than in the first zone and bigger than the probability of detecting in the third zone, by similarity in the third and fourth zones the situation is similar, as we mentioned the cause of decreasing the range of radar to fade away the high difficulty of oceans nature. 3 The searching framework 3.1 The space of search: We divided the 3-dimensional zone (Ξ) into four sub-zones (zk, k = 1,2,3and 4) as indicated in Fig. (1). 3.2 The target: Randomly located in (Ξ) , its position is given by the values of three independent random variables (X, Y, Z)which have distribution F 3.3 The means of search: By considering that the target will be carried out by the searchers s1, s2, s3and s4. Every searcher starts looking for the target from (0,0,0), using a continuous path with the velocity equals to the time. 4 The searching technique 4.1 The first searcher: The first searcher will conduct his search as following: I. Starts searching from the point (0,0,0). II. Searching in the first cubic C1and its tracks as follow: i. Moving forward r1units towards the point (r1,0,0). 3 ii. Turning 90oclockwise and move forward r1units. iii. Turning 90oclockwise, move r1units forwards, and travel along the same direction, completing the search to another r1units. iv. Repeating the turning 90oclockwise, moving r1units forwards and extend it to another r1. v. Turning 90oclockwise, moving r1units forwards, extend it to another r1units. vi. Turning 90oclockwise, moving r1units forwards towards the point (r1,0,0). III. A second search in the second cube C2and its tracks may carry out if the black box is not detected, the searcher could move to the point (r2,0,0) with r2−r1units, and repeat the searching with r2units, if the target still is not detected, the searcher will retrace the steps as far as r3−r2to check the third cube C3and its tracks, and therefore the fourth until the target be detected as illustrated in Figure 1. The searcher uses a sensor in his searching; the sensor range is smaller than or equal to ri−ri−1,i= 1,2,···. 4.2 The second searcher: The second searcher will search in the second zone as following: I. Starts searching from the point (0,0,0). II. Searching in the first cubic C1and its tracks as follows: i. Moving forwards 2r1units towards the point. ii. Turning 90oclockwise and move 2r1units forwards. iii. Turning 90oclockwise, move 2r1units forwards, and travel along the same direction, completing the search to another 2r1units. iv. Repeating the turning 90oclockwise, moving 2r1units forwards, extend it to another 2r1units. v. Turning 90oclockwise, moving 2r1units forwards, extend it to another 2r1units. vi. Turning 90oclockwise, moving forwards 2r1units towards the point (2r1,0,0). 4 Figure 1: The searching technique 5 III. A second search in the second cube C2and its tracks may carry out if the black box is not detected, the searcher could move to the point (2r2,0,0) with 2r2−2r1units, and repeat the searching with 2r2units, if the target is still not detected, the searcher will retrace the steps as far as 2r3−2r2 to check the third cube C3and its tracks, and so fourth until the target is detected as illustrated in Figure 1. 4.3 The third searcher: The third searcher will search in the third zone as follows: I. Starts searching from the point (0,0,0). II. Searching in the first cubic C1and its tracks as follows: i. Moving forwards 3r1units towards the point (3r1,0,0). ii. Turning 90oclockwise and move forwards 3r1units. iii. Turning 90oclockwise, move forwards 3r1units, and travel along the same direction, completing the search to another 3r1units. iv. Repeating the turning 90oclockwise, moving forwards 3r1units and extend it to 3r1another. v. Turning 90oclockwise, moving forwards 3r1units, extend it to another 3r1units. vi. Turning 90oclockwise, moving forwards 3r1units towards the point (3r1,0,0). III. A second search in the second cube C2and its tracks may carry out if the black box is not detected, the searcher could move to the point (3r2,0,0) with 3r2−3r1units, and repeat the searching with 3r2units, if the target is still not detected, the searcher will retrace the steps as far as 3r3−3r2 to check the third cube C3and its tracks, and so fourth until the target is detected as illustrated in Figure 1. 4.4 The fourth searcher: The fourth searcher will search in the fourth zone as follows: I. Starts searching from the point (0,0,0). II. Searching in the first cubic C1and its tracks as follow: i. Moving forwards 4r1units towards the point. 6 ii. Turning 900clockwise and move forwards 4r1units. iii. Turning 900clockwise, move forwards 4r1units, and travel along the same direction, completing the search to another 4r1units. iv. Repeating the turning 900clockwise, moving forwards 4r1units extended to another 4r1. v. Turning 900clockwise, moving forwards 4r1units, extended to another 4r1units. vi. Turning 900clockwise, moving forwards 4r1units towards the point (4r1,0,0). III. A second search in the second cube C2and its tracks may carry out if the black box is not detected, the searcher could move to the point (4r2,0,0) with 4r2−4r1units, and repeat the searching with 3r2units, if the target is still not detected, the searcher will retrace the steps as far as 4r3−4r2 to check the third cube C3and its tracks, and so fourth until the target be detected as illustrated in Figure 1. 5 Algorithms and flowcharts 5.1 Main algorithm (Figure 2) From the initial point to the first point in the first cube for each zone. •Main algorithm •For (k= 1 to 4) –Initialize the searcherkto his start point. –Move and search for distance kr1. –If (target not found in this distance) then ∗search in cube by ( 1 ,k ). –Else ∗Success –End if •End for •End main 7 5.2 Search in cube algorithm (Figure 3) •Search in cube algorithm •Inputs i,k •Turn 90oclockwise •Move and search for distance kri •Turn 90oclockwise •Move and search for distance 2kri •Turn 90oclockwise •Move and search for distance 2kri •Turn 90oclockwise •Move and search for distance 2kri •Turn 90oclockwise •Move and search for distance kri •Turn 90oclockwise •If (target not found) then –If (i⩽n) ∗Execute Moving and searching (i+1,k) –Else ∗Search fail for this searcher •Else –Success •End if •End of search in cube 8 5.3 Moving and Searching algorithm (Figure 4) •Moving and Searching algorithm –inputs i, k •Move and search from the start point for distance k(ri−ri−1) •If (target not found in this distance) then –Execute search in cube by ( i ,k ) •Else –Success •End if •End of Moving and searching 6 The expected time Theorem 6.1. If the target has symmetric trivariate known distribution, then the expected time of detecting the target in the first zone for the first searcher is given by: n X i=1 h(9ri−ri−1)ZZZ Ci f(x, y, z)dxdydz −ZZZ Ci−1 f(x, y, z)dxdydzi (1) Proof. The search path is Q={Qi:i= 1,2,··· , n}, the target has symmetric trivariate known distribution. Referring to our hypothesis we can see that, if the first searcher travels in the first cubic C1and its track to locate the target, then D(Q1) = r1+ 8r1= 9r1, may the target lies in the space between C1and C2, then D(Q2)=(r2−r1) + 8r2= 9r2−r1. Similarly, if the target lies in the space between C2and C3then D(Q3)=(r3−r2)+8r3= 9r3−r2etc. Consequently, 9 30ZZZ Ci f(x, y, z)dxdydz +ri ∂ ∂riZZZ Ci f(x, y, z)dxdydz 27ri+1 ∂ ∂riZZZ Ci+1 f(x, y, z)dxdydz −27 ZZZ Ci−1 f(x, y, z)dxdydz (7) −3ri−1 ∂ ∂riZZZ Ci f(x, y, z)dxdydz −3ZZZ Ci+1 f(x, y, z)dxdydz = 0 Theorem 7.4. For the fourth searcher, supposing F(x, y, z)is a joint continuous distribution function with joint density function f(x, y, z). Let Q∗∈Qbe an optimal search path, then 40ZZZ Ci f(x, y, z)dxdydz +ri ∂ ∂riZZZ Ci f(x, y, z)dxdydz 36ri+1 ∂ ∂riZZZ Ci+1 f(x, y, z)dxdydz −36 ZZZ Ci−1 f(x, y, z)dxdydz (8) −4ri−1 ∂ ∂riZZZ Ci f(x, y, z)dxdydz −4ZZZ Ci+1 f(x, y, z)dxdydz = 0 We deduce that, if Q0is a subclass of Qfor which only one element, and if r∗is an optimal search path; then the optimal search path will be Q∗∈Q0. The search path Qis optimal search path if r∗={r∗ i−r∗ i−1, i = 1,2,··· , n}, so the condition on considering distribution, will be Q∗={Q∗ i, i =,2,··· , n}from class Qsuch that D(Q∗, F) = inf{D(Q, F) : Q∈Q}. Now a complex optimization problem appears, where we have n−number of variables; that is, r={ri−ri−1, i = 1,2,··· , n}. The following nonlinear optimization problem NLOP reads: NLOP: min ri D(Q, F), Subject to ri−ri−1⩾0,0⩽RRR Ci f(x, y, z)dxdydz ⩽1,∀i= 1,2,··· , n. where, n X i=1 h(9ri−ri−1)ZZZ Ci f(x, y, z)dxdydz −ZZZ Ci−1 f(x, y, z)dxdydzi (9) 16 n X i=1 h(18ri−2ri−1)ZZZ Ci f(x, y, z)dxdydz −ZZZ Ci−1 f(x, y, z)dxdydzi (10) n X i=1 h(27ri−3ri−1)ZZZ Ci f(x, y, z)dxdydz −ZZZ Ci−1 f(x, y, z)dxdydzi (11) n X i=1 h(36ri−4ri−1)ZZZ Ci f(x, y, z)dxdydz −ZZZ Ci−1 f(x, y, z)dxdydzi (12) 8 The case of trivariate standard normal distribution Assume that X, Y, Z are three independent random variables which represent the position of the target and have a trivariate standard normal distribution where µ1= µ2=µ3= 0 and σ2 1=σ2 2=σ2 3= 1. Thus, the joint probability density function of the trivarite standard normal distribution will become: f(x, y, z) = 1 √2π3 e−1 2(x2+y2+z2),where −∞ <x<∞,(13) −∞ < y < ∞,−∞ < z < ∞. Supposing the spherical coordinates x=ρsin φcos θ,y=ρsin φsin θ,z= ρcos φ, we obtain: DY, F= n X i=1 (9ri−ri−1)Zπ 0Z2π 0Zri 0 g(ρ, ϕ, θ)ρ2sin φdρdϕdθ −Zπ 0Z2π 0Zri−1 0 g(ρ, ϕ, θ)ρ2sin φdρdϕdθ = n X i=1 "(9ri−ri−1)(Zπ 0Z2π 0Zri 01 √2π3 e−1 2ρ2ρ2sin φdρdϕdθ 17 −Zπ 0Z2π 0Zri 01 √2π3 e−1 2ρ2ρ2sin φdρdϕdθ)# =1 2√2π n X i=1 [9ri−ri−1]Zri 0 ρ2e−1 2ρ2dρ −Zri−1 0 ρ2e−1 2ρ2dρ Consequently, DY, F=1 2√2π n X i=1 [9ri −ri−1]× ×rπ 2Erf ri √2−rie−1 2r2 i+rπ 2Erf ri−1 √2−ri−1e−1 2r2 i−1(14) where Erf represents the error function, in the usual approach, the distances are changed according to the probability of the target. Therefore, the above NLOP becomes: NLOP1: min ri(1 2√2π n X i=1 [9ri −ri−1]× ×rπ 2Erf ri √2−rie−1 2r2 i+rπ 2Erf ri−1 √2−ri−1e−1 2r2 i−1, Subject to ri−ri−1 rπ 2Erf ri √2−rie−1 2r2 i−1 2√2π,∀i= 1,2, ..., n. Assuming the convexity of D(Q, F), by using Kuhn-Tucker conditions: ∂D(Q, F ) ∂ri + 2 X ε=1 uε ∂Nε(ri) ∂ri = 0 Nε(ri)≤0, uεNε(ri) = 0, uε≥0. necessary conditions of r∗=r∗ i−r∗ i−1, i = 1,2, ..., n, are calculated as follows: 1 2√2π n X i=1 n9hrπ 2erf(ri √2)−rie−1 2r2 i+rπ 2erf(ri−1 √2)−ri−1e−1 2r2 i−1i + (9ri−ri−1)hr2 ie−1 2r2 iio+u1(1) + u2r2 ie−1 2(ri)2= 0,(15) 18 u1(ri−1−ri) = 0,(16) u2rπ 2erf ri √2−rie− r2 i 2−1 2√2π= 0.(17) Now, we have different cases to solve (15), (16) and (17). 1. uε= 0, ε = 1,2; 2. uε>0, ε = 1,2; and 3. u℘>0, ℘ ∈ {1,2}and uε= 0, ε = 1,2, ℘ 6=ε. We found that the optimal values of ri, i = 1,2, ..., n are given only from Case 1. We used iteration method where the initial valuer0= 0, as a result the optimal distances r∗ i, i = 1,2, ..., n after solving the following equation: n X i=1 n9hrπ 2erf(ri √2)−rie−1 2r2 i+rπ 2erf(ri−1 √2)−ri−1e−1 2r2 i−1i + (9ri−ri−1)hr2 ie−1 2r2 iio= 0 (18) By substituting in (14), we will obtain the minimum expected search time for detecting the target. 9 Application Our main purpose of this application is calculating the optimal values r∗ i, i = 1,2, ..., n. Certainly, these values help the searcher to find the lost black box, then determines the cause of air crash in the least possible time where minimizing the cost (time). By solving numerically, also using mathematica and maple, A.H.El-Bagoury et al. [12] illustrated the optimal values, i = 1,2,3and 4. We benefit from previous results and developed the paper published in to a different search technique. The results commensurate with our search problem will be as in the taple (1) Table 1: The optimal values 19 n r∗ i(1st searcher) 2r∗ i(2nd searcher) 3r∗ i(3rd searcher) 4r∗ i(4th searcher) 1 2.15991×10−84.31982×10−86.47973×10−88.63964×10−8 2 0.0000242396 4.84792×10−57.27188×10−59.69584×10−5 3 0.000754752 0.001509504 0.002264256 0.003019008 4 0.168538 0.337076 0.505614 0.674152 The application shows that, the first searcher starts at a point (0,0,0) and should go a distance r∗ 1= 2.15991 ×10−8(length unit), then the searcher should search for the target in the first cubic C1and its tracks until reaches the point (2.15991 × 10−8,0,0), completing searching if the target still not located , going forward with distance 0.0000242396 to explore the cubic C2and its tracks. . . etc.by similarity ,the second, third and fourth searchers. Certainly, the numerical calculations we obtained provide important results; that is; the optimal values we obtain,is increasing, it confirming our technique accuracy. 10 Conclusions and future work. We have designed a new search technique in the 3-D space, we obtained the expected value of the time and calculated the optimal search path where minimizing the expected value of the time to detect the lost black box, the accuracy of the technique is illustrated in a numerical example. In future work, we will investigate interesting search problem, coordinated search strategy for a randomly located target in 3-D by using four searcher. In particular we plan to analyze a medical application to benefit from the results in the current manuscript in the discovery of diseases or tumors. References Blouhi, T.,Caraballo, T.,and Ouahab, A. 2017. Corrigendum to the paper: Existence and stability results for semilinear systems of impulsive stochastic differential equations with fractional Brownian motion. Stochastic Analysis and Applications 34 (2016), no. 5, 792–834. Stochastic Analysis and Applications 35 (5): 941–942. Caraballo, T.,El Fatini, M.,Pettersson, R.,and Taki, R. 2018. A stochastic SIRI epidemic model with relapse and media coverage. Discrete and Continuous Dynamical Systems Series B 23 (8): 3483–3501. 20 El-Hadidy, M. 2016. On Maximum Discounted Effort Reward Search Problem, Asia-Pacific Journal of Operational Research, 33 (3) 1650019 (30 pages). El-Hadidy, M., and Abou Gabal, H.M. 2018. Coordinated Search for a Random Walk Target Motion, Fluctuation and Noise Letters 17 (01): 1850002. El-Hadidy, M., and EL-Bagoury, A.H. 2017. Optimal search strategy for a threedimensional randomly located target, International Journal of Operational Research 29 (1): 115–126. El-Rayes, A.B., Mohamed, A. and Fergani, H. 1993. On the generalized linear search problem, Delta Journal No. 6. Second Part. 1–10. Mohamed, A., and Abou Gabal, H.M. 2000. Generalized optimal search paths for a randomly located target, In: Annual Conference, Cairo ISSR, 35, Math. Statistics 17–19. Mohamed, A., and Abou Gabal, H.M. 2003. Linear search with multiple searchers for a randomly moving target, In: International Conference for Statistices, Computer Science and Its Application, Egypt, 115-124. Mohamed, A., and Abou Gabal, H.M. 2004 Multiplicative linear search problem, Egyptian Statistical Journal 48 (1) : 34–45. Mohamed, A., Abou Gabal, H.M., and Afifi,W. 2007. On the coordinated search problem. International Journal of Applied Mathematics 5: 627–636. Mohamed, A., Abou Gabal, H.M., and El-Hadidy, M. 2009. Coordinated search for a randomly located target on the plane. European Journal on Pure and Applied Mathematics 1 (2) : 97–111. Mohamed, A., Abou Gabal, H. M., and El-Hadidy, M. 2017. Random Search in a bounded area, International Journal of Mathematics in Operational Research, 10 (2): 137-149. Mohamed, A., and El-Hadidy, M. 2013. Existence of a periodic search strategy for a parabolic spiral target motion in the plane, Afrika Matematika Journal, 24 (2): 145-160. 21 Mohamed, A., El-Hadidy, M., and El-Bagoury, A.H. 2017. 3-Dimensional Coordinated search technique for a Randomly Located target, International Journal of Computing Science and Mathematics. Mohamed, A., Fergany, H., and El-Hadidy, M. 2012. On the coordinated search problem on the plane. Journal School of Business Administration, Istanbul University 41: 80–102. Mohamed, A., Kassem, M., and El-Hadidy, M. 2011. Multiplicative linear search for a brownian target motion, Applied Mathematical Modelling 35 : 4127–4139. Mohamed, A., Kassem, M., and El-Hadidy, M. 2017. M-States search problem for a lost target with multiple sensors, Int. Journal of Mathematics in Operational Research, 10 (1) : 104-135. Mohamed, A., Teamah, M., Abou Gabal, H.M., and Afifi, W. 2007. On the Coordinated search problem, International Journal of Applied Mathematics 5: 627– 636. Reyniers, D. J. 1995. Coordinated two searchers for an object hidden on an interval, Journal of the Operational Research Society, 46 : 1386–1392. Reyniers, D. J. 1996. Coordinated search for an object on the line, European Journal of the Operational Research 95 : 663–670. 22