![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
A new search technique is developed to locate the hidden target (object) in one of the N-disjoint regions that are not identical. The lost object follows a bivariate distribution. Minimizing the search effort with discount reward has been applied instead of reducing the expected search time. Moreover, the minimum number of searchers is determined in order to minimize the total expected cost. Assuming the object's position has a Circular Normal distribution, the Kuhn–Tucker necessary conditions are implemented to get the optimum search plan.
1. Introduction
The detection of explosives in places where they are likely to be present in the shortest possible time will prevent many innocent victims. Minimizing the time and the effort to detect one of the explosive needs to increase the number of searchers and the coordination process among them. The case of the randomly located object with a known distribution on the real line has been discussed by Reyniers [Citation1,Citation2]. She considered two unit speeds searchers aim to find this object in the shortest possible time. In addition, Mohamed et al. [Citation3,Citation4] studied this problem for the hidden object which has a known distribution in an open area.
On the other hand, for a stochastically moving object, El-Hadidy and Abou-Gabal [Citation5] and El-Hadidy and Alzulaibani [Citation6,Citation7] used a linear coordinated search technique to present a finite search plan which minimizes the first collision time expected value between one of the searchers and the stochastically moving object. Moreover, this technique is applied by using the Bayesian approach (see, e.g. [Citation8–11]). Earlier, many interesting methods to track the stochastically moving object have been presented by Dai et al. [Citation12] and Deilami et al. [Citation13]. Besides that, Mohamed et al. [Citation14,Citation15], Mohamed and El-Hadidy [Citation16], Mohamed and El-Hadidy [Citation17], Beltagy and El-Hadidy [Citation18], Abou-Gabal and El-Hadidy [Citation19], Mohamed et al. [Citation20], Kassem and El-Hadidy [Citation21], El-Hadidy and El-Bagoury [Citation22], El-Hadidy [Citation23–31], El-Hadidy and Alzulaibani [Citation6,Citation7], and El-Hadidy et al. [Citation32] provided many different mathematical treatments of this issue in both cases stochastically moving and hidden objects.
This paper aims to coordinate the search technique that allows the M-searchers (where M is an even number), start together and searching for a hidden object from the centre of each region
(a point
) , as shown in Figure (the search path in the region
which has 4-unit speed searchers). The purpose is to find the minimum expected value of the detection time by achieving the optimal search plan after applying the discount effort reward function which has been applied before in [Citation25].
In this work, Section 2 explains the problem and presents the expected reward cost of detection. In Section 3, the optimal search policy that minimizes the expected reward cost of detection is presented after considering the Circular Normal distribution of the object's position. A discussion of the results and future works is presented in the conclusion part.
2. Problem formulation
The mathematical model of this problem is formulated by considering the discounted search effort reward. This model gives the expected value of the discounted effort reward for detection in one of N-disjoint and not identical regions
2.1. The searching process
The search space: The space is divided into N-disjoint and not identical regions . Each region has two roads intersected at the centre of this region. These roads divide the region into four identical parts. The two roads are considered as x and y axes (see Figure ). Here, the report for the object position is given at
.
The object: The object is randomly located in one of these regions with symmetric distribution about .
The means of search: Let M searchers start the searching process for the object from the in each region. Each region has an even number of searchers. The searchers go along the two axes (
and
parts) with equal speeds. The sectors and its tracks are searched with regular speed. The searchers return to
and still searching until the object detected.
2.2. 4-Coordinated search technique in the region ![](//:0)
![](//:0)
Let the position of the object in be defined by the two independent random variables
. The surface of
is a “ Standard Euclidean 2-space E”, with points
. In
, we have four searchers,
each searcher of them is always searching one part from the four parts (see Figure ). We will divide the region into many sectors, as shown in Figure .
2.2.1. The Searching path
To find the object, the searchers follow
and
(the search paths), respectively. The first search path
of
is defined as follows:
Begin at the point
and go along the right part of the y-axis (
part) as far as
Look for the object in
and its track.
When
reaches the point
will return to the origin through
part of the x-axis.
In addition, one can define the second search path of
as in the above steps (
,
and
), where
goes a distance
to search the sector
and its track, etc. Thus,
of
is completely defined by a sequence
. The first search path
of
is defined as follows:
Begin at
and go along the left part of the y-axis (
part) as far as
Search the sector
and its track.
When
reaches the point
will return to the origin through
part of the x-axis.
And, ( the second search path) of
is defined as in the above steps from (a) to (c), where
goes a distance
to search
and its track, etc. Thus,
of
is completely defined by the sequence
.
Also, by considering the searchers' movement on the sectors and tracks done in anticlockwise, then the search paths of ,
are
and
respectively, where
,
search the parts III and IV.
Each searcher goes along the x-axis with speed v = 1 and searches the circles, the tracks with regular speed . The time that the searcher takes it through going on the x-axis will add to the time of the searching process (sectors and its tracks searching time).
Let the surface of be a “ Standard Euclidean 2-space E” and the object position has the probability density function
. Also, let
k = 1, 2, 3, 4, be the time that the searchers
take it in
and
in the four parts to
where any track i has a width
. They go on the y-axis and x-axis from the origin before searching the sectors. In addition, they return after finishing the searching process with equal speeds v = 1 to
. Then, the time of going through the y-axis is equal to the distances which done. They are searching
(sectors and tracks) with
Then, the searching time is equal to
, where
is the time league and
is called angular velocity. The searching time
depends on
which depends on the radius
and the time of detection
We choose the discounted effort function as an exponential function , that will reduce the possible rewards at the revolution number i (see [Citation25]). The adjust parameter
gives permission to make the decision indirectly, and this helps the searcher to take appropriate actions in the future.
Theorem 2.1
The expected reward cost of detection for the lost object is given by
Proof.
The object may be in one of the four parts in . Thus, more appropriate formulas for the expected time are available. This leads to the following:
If the object is located at any point on the track of then
.
If the object is located at any point on the track of then
.
If the object is located at any point on the track of then
, etc.
If the object is located at any point on the track of , then
.
If the object is located at any point on the track of , then
.
If the object is located at any point on the track of , then
, etc.
If the object is located at any point on the track of then
.
If the object is located at any point on the track of then
.
If the object is located at any point on the track of then
, and etc.
If the object is located at any point on the track of then
.
If the object is located at any point on the track of then
.
If the object is located at any point on the track of then
, etc.
Each sector is divided into equal small sectors , where these sectors make a set of equal cones. As in Figure , these cones have the same vertex
. Thus, each searcher can cover a track with width
which has equal small areas of cones in the track number i. These cones are determined by a set of lines with equations
y, where
. These equations give a range of equal small spaces to equalize the searching process. Applying the polar coordinates with
and
,
,
and
,
where
and
to evaluate the expected searching time to detect the object. The searching process is performed in the anticlockwise direction.
Figure 2. The small search area in which is made by small sectors
which made by the searchers inside the circles with radiuses
![Figure 2. The small search area in Rℓ which is made by small sectors luℓ,u=1,2,…,n, which made by the searchers inside the circles with radiuses aiℓ,i=1,2,3,…](/cms/asset/4d68597a-aef0-48b9-b1c7-33400316e9d4/tusc_a_1747217_f0002_oc.jpg)
By using our assumptions where the object has symmetric distribution and applying the discounted effort reward function in each revolution, we have
etc., then
Corollary 2.2
In the case of two searchers, one of them searches the sectors in the right part of the y-axis and the other searches the sectors in the left part. In addition, the object has symmetric distribution and . Then, the expected value of the time for the searchers to return to the origin after the object detection is
(2)
(2) It is the same result which has been obtained before in [Citation3] when
; we found that the expected reward cost of detection for the two searchers to return to
after the object has been detected as in (Equation2
(2)
(2) ) will become
(3)
(3) which is less than the expected value of the time in (Equation2
(2)
(2) ). Also, we can notice that the expected value of the time in the case of
searchers, where
is even number, is smaller than the expected value of
searchers; this leads to the following:
Theorem 2.3
For any even number of searchers in one of the non-identical N-regions, where
the total expected reward cost of detection is given by
Proof.
By the same method that prove Theorem 2.1 we can prove this theorem.
Corollary 2.4
If the width is fixed i.e.
then
and if
then in (Equation4
(4)
(4) ) we have
The above result shows that this technique is more suitable to detect an important object (like a bomb or a person in a wilderness area) by using searchers.
3. Optimal search plan
Since the main contribution of this technique is to minimize the expected cost of detection, then we need to get the optimal search plan which give
where
depend on the optimal paths
and
. Rather than finding the optimal sequence
(optimal values of the turning points
for a given initial object distribution), which gives the optimal paths
and
we need to maximize the discounted effort reward
or minimize
to get
for each revolution
. The probability of the object in each region will be affected by the number of searchers. But, the increasing searchers' number will increase the searching cost. Thus, we also need to obtain the optimal number of searchers in each region
this will reduce the total cost.
Really, we face a difficult optimization problem because our problem has an infinite number of variables; that is, which depends on the object distribution F. In addition, we have
are considering an infinite number of variables where
also depend on
,
and speed
is “regular speed” on any circle. Therefore, if we take
constant, we can obtain the optimal values of “ angular velocity” in any circle from
,
. Let us assume, from now on, that the object distribution be known with expected value
.
It is clear that, if
(the class of all possible search plans) for which there is only one element and if
is an optimal search path on the x-axis, then all the optimal search paths will be
and
which belongs to
. Consequently, besides the condition
we can assume that for the necessary condition on the known object's distribution, there exists a search path
and
from class Q such that
.
Theorem 3.1
If and
in each region
then there exists a search path from class Q with finite expected reward cost, which can also lead to
[Citation33].
After proving that objective function (Equation4(4)
(4) ) is convex, we will use the Kuhn–Tucker conditions to obtain these optimal values which minimizes
. Hence, we will obtain the following non-linear programming problem (NLP(1)):
This is equivalent to the following:
From the Kuhn–Tucker conditions, we obtain
Since , we have
(5)
(5)
(6)
(6)
(7)
(7)
(8)
(8)
(9)
(9)
(10)
(10)
(11)
(11)
Many cases have been found to solve Equations (Equation5(5)
(5) )–(Equation11
(11)
(11) ) as follows:
(
)
;
(
)
;
(
)
and
;
(♣)
and
; and
(
)
and
.
Definition 3.1
In the revolution number and region
the optimal values
where
and
(the optimal small integer value of
), are said to be optimal solutions of the above NLP, if there exist
and
for all
.
Since
and
then the optimal solution will be given after using the case (♠). Thus, we have the following system of equations:
(12)
(12)
(13)
(13)
(14)
(14)
If we know the distribution of the object's position, then we can get the optimal value of and
that give the minimum value of
by solving the above system. The following recursion gives a necessary condition for a strategy to be optimal with respect to Circular Normal distribution.
3.1. The case of the initial position given by a Circular Normal distribution
In all search strategies, we consider that the debris diffusion of an aeroplane crash over the oceans and seas have a Circular Normal distribution, why? By considering the disaster of Air France Flight 447, Stone et al. [Citation34] answered this question. They proved that all impact points of debris are found within a 20 nautical mile radius circle from the crashed point. After they analysed the data about these impact points of debris, they found that the distribution of these points is a Circular Normal distribution with centre at the last known position. Thus, we let X, Y are two independent random variables that represent the last position of the object (black box), and they have a Circular Normal distribution with joint probability density function which considered in [Citation27]:
(15)
(15)
By applying the polar coordinates in (Equation15(15)
(15) ) and since
is always convex, then substituting in (Equation12
(12)
(12) )–(Equation14
(14)
(14) ), where
and
, we have
(16)
(16)
(17)
(17)
(18)
(18) It is noticed from (Equation16
(16)
(16) ) to (Equation18
(18)
(18) ) that
is a function of
and
is a function of
Let the set of the critical search paths is not empty, then we can address ourselves to solve (Equation16
(16)
(16) )–(Equation18
(18)
(18) ) to obtain the optimal values
and
4. Conclusion and future work
We discussed the coordinated search technique to find a hidden object in the plane. The position of the object is given by two independent random variables X, Y. The expected value of the reward cost is given in Theorem 2.1. Theorem 2.3 presented the total expected reward cost of detection for any even number of searchers in one of the non-identical N-regions. By assuming the Circular Normal distribution of the object position, we obtain the optimal values of and
that give the optimal search plan after solving a difficult optimization problem.
In the future, this proposed model will be generalized to find multiple hidden objects by using a group of searchers.
Disclosure statement
No potential conflict of interest was reported by the author(s).
References
- Reyniers DJ. Coordinated two searchers for an object hidden on an interval. J Oper Res Soc. 1995;46(11):1386–1392.
- Reyniers DJ. Coordinated search for an object on the line. Eur J Oper Res. 1996;95(3):663–670.
- Mohamed A, Abou-Gabal H, El-Hadidy M. Coordinated search for a randomly located target on the plane. Eur J Pure Appl Math. 2009;2(1):97–111.
- Mohamed A, Fergany H, El-Hadidy M. On the coordinated search problem on the plane. J Sch Bus Admin, Istanbul Univ. 2012;41(1):80–102.
- El-Hadidy M, Abou-Gabal H. Coordinated search for a random walk target motion. Fluct Noise Lett. 2018;17(1):1850002 (11 pp.).
- El-Hadidy M, Alzulaibani A. Cooperative search model for finding a Brownian target on the real line. J Taibah Univ Sci. 2019;13(1):177–183.
- El-Hadidy M, Alzulaibani A. Existence of a finite multiplicative search plan with random distances and velocities to find a d-dimensional Brownian target. J Taibah Univ Sci. 2019;13(1):1035–1043.
- Kassem M, El-Hadidy M. Optimal multiplicative Bayesian search for a lost target. Appl Math Comput. 2014;247:795–802.
- Bourgault F, Durrant-Whyte HF. Process model, constraints, and the coordinated search strategy. In: IEEE International Conference on Robotics and Automation, New Orleans, LA; 2004. p. 5256–5261.
- Bourgault F, Furukawa T, Durrant-Whyte HF. Optimal search for a lost target in a Bayesian world. In: Yaut S, Asama H, Prassler E, et al., editors. Field and service robotics. Vol. 24, Lake Yamanaka: STAR; 2006. p. 209–222.
- Furukawa T, Bourgault F, Lavis B, et al. Recursive Bayesian search-and-tracking using coordinated UAVs for lost targets. Proceedings 2006 IEEE International Conference on Robotics and Automation, ICRA 2006; Orlando, FL; 2006.
- Dai D, Zeng B, Xiong W, et al. Tracking of moving target based on background updating and lifting wavelet neural network. Int J Appl Math Stat. 2013;51(24):312–320.
- Deilami M, Rostamy-malkhalifeh M, Jabbari M. The modified two-phase approach to find non-negative target for inefficient units in the DEA with negative data. Int J Appl Math Stat. 2016;55(3):41–50.
- Mohamed A, Kassem M, El-Hadidy M. Multiplicative linear search for a Brownian target motion. Appl Math Model. 2011;35(9):4127–4139.
- Mohamed A, Kassem M, El-Hadidy M. M-States search problem for a lost target with multiple sensors. Int J Math Oper Res. 2017;10(1):104–135.
- Mohamed A, El-Hadidy M. Existence of a periodic search strategy for a parabolic spiral target motion in the plane. Afrika Mat J. 2013;24(2):145–160.
- Mohamed A, El-Hadidy MA. Optimal multiplicative generalized linear search plan for a discrete random walker. J Optim. 2013;2013: 13 pp. Article ID 706176. doi:10.1155/2013/706176
- Beltagy M, El-Hadidy M. Parabolic spiral search plan for a randomly located target in the plane. ISRN Math Anal. 2013;2013: 8 pp. Article ID 151598. doi:10.1155/2013/151598
- Abou-Gabal HM, El-Hadidy MA. Optimal searching for a randomly located target in a bounded known region. Int J Comput Sci Math. 2015;6(4):392–403.
- Mohamed AA, Abou Gabal HM, El-Hadidy MA. Random search in a bounded area. Int J Math Oper Res. 2017;10(2):137–149.
- Kassem M, El-Hadidy M. On minimum expected search time for a multiplicative random search problem. Int J Oper Res. 2017;29(2):219–247.
- El-Hadidy M, El-Bagoury AH. Optimal search strategy for a three-dimensional randomly located target. Int J Oper Res. 2017;29(1):115–126.
- El-Hadidy M. Searching for a d-dimensional Brownian target with multiple sensors. Int J Math Oper Res. 2016;9(3):279–301.
- El-Hadidy M. Fuzzy optimal search plan for N-dimensional randomly moving target. Int J Comput Methods. 2016;13(6):1650038 (38 pp.).
- El-Hadidy M. On maximum discounted effort reward search problem. Asia-Pac J Oper Res. 2016;33(3):1650019 (30 pp.).
- El-Hadidy M. On the existence of a finite linear search plan with random distances and velocities for a one-dimensional Brownian target. Int J Oper Res. 2020;37(2):245–258.
- El-Hadidy MA. Optimal spiral search plan for a randomly located target in the plane. Int J Oper Res. 2015;22(4):454–465.
- El-Hadidy MA. Optimal searching for a helix target motion. Sci China Math. 2015;58(4):749–762.
- El-Hadidy MA. Study on the three players linear rendezvous search problem. Int J Oper Res. 2018;33(3):297–314.
- El-Hadidy MA. Existence of finite parbolic spiral search plan for a Brownian target. Int J Oper Res. 2018;31(3):368–383.
- El-Hadidy M. Existence of cooperative search technique to find a Brownian target. J Egypt Math Soc. 2020;28(1):1–12.
- El-Hadidy M, Teamah A, El-Bagoury AH. 3-dimensional coordinated search technique for a randomly located target. Int J Comput Sci Math. 2018;9(3):258–272.
- Franck W. An optimal search problem. SIAM Rev. 1965;7(4):503–512.
- Stone LD, Keller C, Kratzke TL, et al. Search analysis for the location of the AF447 underwater wreckage. METRON; 2011. (Report to BEA, January 20).