Share This Article:

Quasi-Coordinate Search for a Randomly Moving Target

Abstract Full-Text HTML XML Download Download as PDF (Size:295KB) PP. 1814-1825
DOI: 10.4236/jamp.2019.78124    80 Downloads   162 Views  

ABSTRACT

In this paper, we study the quasi-coordinated search technique for a lost target assumed to move randomly on one of two disjoint lines according to a random walk motion, where there are two searchers beginning their search from the origin on the first line and other two searchers begin their search from the origin on the second line. But the motion of the two searchers on the first line is independent from the motion of the other two searchers on the second line. Here we introduce a model of search plan and investigate the expected value of the first meeting time between one of the searchers and the lost target. Also, we prove the existence of a search plan which minimizes the expected value of the first meeting time between one of the searchers and the target.

1. Introduction

The searching for a lost target either located or moved is often a time-critical issue, that is, when the target is very important. The primary objective is to find and search for the lost target as soon as possible. The searching for lost targets has recently applications such as the search for a goldmine underground, the search for Landmines and navy mines, the search for the cancer cells in the human body, the search for missing black box of a plane crash in the depth of the sea of ocean, the search for a damaged unit in a large linear system such as telephone lines, and mining system, and so on [1] [2] [3] . Search problem when the lost target is located or moved on the real line has been considered in [4] - [9] . The coordinated search technique discussed on the real line when the located target has symmetric or unsymmetric distribution as in [10] [11] [12] . Also, the coordinated search for a located target in the plane has been examined in [13] [14] [15] [16] . Recently, [17] and [18] proposed and studied a modern search model in the three-dimensional space to find a 3-D randomly located target by one searcher, two searchers and four searchers.

2. Problem Formulations

One of the most complicate problems when a mother loses her son in a way of multiple ways, here the primary objective is finding the lost son, as soon as possible in a minimum time. The survival rate of the son in this region gradually decreases, so the search team must organize itself quickly to begin the mission of the searching for the lost son immediately. Also, when the target is serious as a car, which filled by explosives, and it moves on one road from disjoint roads, and then the search effort must be unrestricted and we can use more than searcher to detect the target at right time.

The search team which consists of 4 searchers will organize itself on 2 straight lines to find the lost target as soon as possible. We clarify a modern technique by collaboration between each two searchers to find the lost person in minimum time. This problem can be characterized as follows.

2.1. The Searching Framework

The space of search: 2 disjoint lines.

The target: The target moves with a random walk motion on one of 2 disjoint straight lines.

The means of search: Looking for the lost target performed by two searches on each line. The searchers start searching for the target from the origins of the two lines with continuous paths and with equal speeds. In addition, the search spaces (2 straight lines) are separated into many distances.

2.2. The Searching Technique

Assume that we have two searchers S1 and S2 that start together looking for the lost target from O1 on L1. The two searchers coordinate their search about the lost target, where the searcher S1 searches to the right and goes from the O1 to H1, and the searcher S2 searches to the left and goes from O1 to −H1, the two searchers S1 and S2 reach to H1 and −H1 in the same time of G1. Then they come back to O1 again in the same time of G2. If one of the two searchers do not find the lost target, then the two searchers S1 and S2 begin the new cycle search for the lost target, where they go from O1 to H2 and −H2, respectively and they will reach to H2 and −H2 in the same time of G3. Then they come back to O1 again in the same time of G4 and so on. Also, we have two other searchers S3 and S4 start together looking for the lost target from O2 on the second line L2, the searcher S3 searchers to the right and goes from O2 to H ¯ 1 , and the searchers S4 searches to the left and goes to the left and goes from O2 to H ¯ 1 , the two searchers S3 and S4 reach to H ¯ 1 and H ¯ 1 in the same time of G ¯ 1 . Then they come back to O2 again in the same time of G ¯ 2 . If one of the two searchers not find the lost target, then the two searchers S3 and S4 begin the new cycle search for the lost target, where they go from O2 to H ¯ 2 and H ¯ 2 , respectively and they will reach to H ¯ 2 and H ¯ 2 in the same time of G ¯ 3 , then they come back to O2 again in the same time of G ¯ 4 , and so on. The four searchers return to the O1 and O2 after searching successively common distances until the target is found.

2.3. The Movement of the Target and the Searchers

A target is assumed to move randomly on one of two disjoint lines according to a stochastic process { S ( t ) , t I + } , I + = { 0 , 1 , 2 , } . Assume that { Z i } i 0 is a sequence of independent identically distributed random variables such as for any i 1 : p ( Z i = 1 ) = p and p ( Z i = 1 ) = 1 p = q , where p , q > 0 . For t > 0 , t I + ,

S ( t ) = i = 1 t Z i , S ( 0 ) = 0 .

We assume the searchers S1 and S2 begin their search path from O1 on L1 with speeds V1, and the searchers S3 and S4 begin their search path from O2 on L2 with speeds V2, following the search paths which are functions ϕ 1 : R + R and ϕ ¯ 1 : R + R on L1 and ϕ 2 : R + R and ϕ ¯ 2 : R + R on L2, respectively, such that:

| ϕ 1 ( t 1 ) ϕ 1 ( t 2 ) | = | ϕ ¯ 1 ( t 1 ) ϕ ¯ 1 ( t 2 ) | V 1 | t 1 t 2 | , (1)

and

| ϕ 2 ( t 1 ) ϕ 2 ( t 2 ) | = | ϕ ¯ 2 ( t 1 ) ϕ ¯ 2 ( t 2 ) | V 2 | t 1 t 2 | , t 1 , t 2 I + , (2)

where V1 and V2 are constants in R + and ϕ 1 ( 0 ) = ϕ ¯ 1 ( 0 ) = ϕ 2 ( 0 ) = ϕ ¯ 2 ( 0 ) = 0 . Let the set of all search paths of the two searchers S1 and S2, which satisfy condition (1), be respectively by Φ v 1 and Φ ¯ v 1 respectively and the set of all search paths of the searchers S3 and S4 which satisfy condition (2), be represented by Φ v 2 and Φ ¯ v 2 , respectively. we represented to the path of S1 and S2 by ϕ 0 = ( ϕ 1 , ϕ ¯ 1 ) Φ 0 where ϕ ¯ 0 = ( ϕ 2 , ϕ ¯ 2 ) Φ ¯ 0 , where

Φ ¯ 0 = { ( ϕ 2 , ϕ ¯ 2 ) : ϕ 2 Φ v 2 , ϕ ¯ 2 Φ ¯ v 2 } .

The search plan of the four searchers be represented by ϕ ^ = ( ϕ 0 , ϕ ¯ 0 ) Φ ^ , where Φ ^ = { ( ϕ 0 , ϕ ¯ 0 ) : ϕ 0 Φ 0 , ϕ ¯ 0 Φ ¯ 0 } is the set of all search plan.

We assume that Z 0 = X if the target moves on L1 and Z 0 = Y if the target moves on L2 such that P ( Z 0 = X ) + P ( Z 0 = Y ) = 1 . There is a known probability measure v 1 + v 2 = 1 on L 1 L 2 which describes the location of the target, where v1 is probability measure induced by the position of the target on L1, while v2 on L2. The first meeting time valued in I + defined as

τ ϕ ^ = inf { t : ϕ 1 ( t ) = X + S ( t ) or ϕ ¯ 1 ( t ) = X + S ( t ) or ϕ 2 ( t ) = Y + S ( t ) or ϕ ¯ 2 ( t ) = Y + S ( t ) } ,

where Z0 is a random variable representing the initial position of the target and valued in 2 I (or 2 I + 1 ) and independent of S ( t ) , t > 0 .

At the beginning of the search suppose that the lost target is existing on any integer point on L1 but more than H1 or less than H 1 or the lost target is existing on an integer point on L2 but more than H ¯ 1 or less than H ¯ 1 . Let τ ϕ 1 be the first meeting time between S1 and the target and τ ϕ ^ 1 be the first meeting time between S2 and the target and τ ϕ 2 be the first meeting time between S3 and the target and τ ϕ ^ 2 be the first meeting time between S4 and the target. The main objective is to find the search plan ϕ ^ = ( ϕ 0 , ϕ ¯ 0 ) Φ ^ such that E ( τ ϕ ^ ) < . In this case ϕ ^ is said to be a finite search plan, and if E ( τ ϕ ^ * ) < E ( τ ϕ ^ ) , ϕ ^ Φ ^ , where E terms to expectation value, then we call ϕ ^ * is an optimal search plan. Given n > 0 , if z is: 0 k 1 n + z 2 n , where k 1 is integer, then

p ( S ( n ) = k 1 ) = { ( n k 1 ) p k 1 q n k 1 0 , if k 1 doesnotexist

2.4. Finite Search Plan

Let λ 1 , λ 2 , ζ 1 , ζ 2 be positive integers such that ζ 1 , ζ 2 > 1 , λ 1 = k θ 1 , λ 2 = k θ 2 , where k = 1 , 2 , and θ 1 , θ 2 are the least positive integers and V 1 = V 2 = 1 .

We shall define the sequences { G i } i 0 , { H i } i 0 for the searcher S1 on the first line L1 and { G ¯ i } i 0 , { H ¯ i } i 0 for the searcher S3 on the second line L2 and the search plans with speeds 1 as follows:

G i = 2 1 2 [ 1 ( 1 ) i 1 ] λ 1 ( ζ 1 i 2 + 1 4 ( 1 ) i 1 4 1 ) , H i = G 2 i 1 , i 1 on L1,

G ¯ i = 2 1 2 [ 1 ( 1 ) i 1 ] λ 2 ( ζ 2 i 2 + 1 4 ( 1 ) i 1 4 1 ) , H ¯ i = G ¯ 2 i 1 , i 1 on L2.

We shall define the search path as follows:

for any t I + , if G i t < G i + 1 , then

ϕ 1 ( t ) = ( 1 2 H i + 1 2 ) + ( 1 ) i + 1 ( 1 2 H i + 1 2 ) + ( 1 ) i ( t G i ) ,

and

ϕ ¯ 1 ( t ) = ϕ 1 ( t ) .

Also, if G ¯ i t < G ¯ i + 1 , then

ϕ 2 ( t ) = ( 1 2 H ¯ i + 1 2 ) + ( 1 ) i + 1 ( 1 2 H ¯ i + 1 2 ) + ( 1 ) i ( t G ¯ i ) ,

and

ϕ ¯ 2 ( t ) = ϕ 2 ( t ) .

We define the notion

φ 1 ( t ) = S ( t ) t , φ ˜ 1 ( t ) = S ( t ) + t on L1,

φ 2 ( t ) = S ( t ) t , φ ˜ 2 ( t ) = S ( t ) + t on L2,

the searchers S1 and S2 return to the origin of L1 after searching successively common distances H 1 , H 2 , H 3 , , and H 1 , H 2 , H 3 , , respectively and the searchers S3 and S4 return to the origin of L2 after searching successively common distances H ¯ 1 , H ¯ 2 , H ¯ 3 , , and H ¯ 1 , H ¯ 2 , H ¯ 3 , , respectively until the target is found.

Theorem 1: If ϕ ^ = ( ϕ 0 , ϕ ¯ 0 ) Φ ^ is a search plan defined above, then the expectation E ( τ ϕ ^ ) if finite if

w 1 ( x ) = i = 1 ( ζ 1 i 1 ) p ( φ ˜ 1 ( G 2 i 1 ) < x ) ,

w 2 ( x ) = i = 1 ( ζ 1 i 1 ) p ( φ 1 ( G 2 i 1 ) > x ) ,

w 3 ( x ) = i = 1 ( ζ 1 i ( ζ 1 i 2 ) + 1 ) p ( φ ˜ 1 ( G 2 i ) < x ) ,

w 4 ( y ) = i = 1 ( ζ 1 i ( ζ 1 i 2 ) + 1 ) p ( φ 1 ( G 2 i ) > x ) ,

w 5 ( y ) = i = 1 ( ζ 2 i 1 ) p ( φ ˜ 2 ( G 2 i 1 ) < y ) ,

w 6 ( y ) = i = 1 ( ζ 2 i 1 ) p ( φ 2 ( G ˜ 2 i 1 ) > y ) ,

w 7 ( y ) = i = 1 ( ζ 2 i ( ζ 2 i 2 ) + 1 ) p ( φ ˜ 2 ( G ˜ 2 i ) < y ) ,

and

w 8 ( y ) = i = 1 ( ζ 2 i ( ζ 2 i 2 ) + 1 ) p ( φ 2 ( G ˜ 2 i ) > y ) . (3)

are finite.

Proof: Assume that X and Y are independent of S ( t ) , t > 0 , if X > 0 , then X + S ( t ) > ϕ 1 ( t ) until the first meeting between S1 and the target on L1, also if X < 0 , then X + S ( t ) < ϕ ^ 1 ( t ) until the first meeting between S2 and the target on L2. We can apply this assumption on the second line by replacing X by Y and ϕ 1 , ϕ ¯ 1 by ϕ 2 , ϕ ¯ 2 respectively. Hence, for any i 0

p ( τ ϕ ^ > t ) = p ( τ ϕ 0 > t or τ ϕ ^ 0 > t ) ,

hence

E ( τ ϕ ^ ) = 0 p ( τ ϕ ^ > t ) d t i = 0 [ G i G i + 1 p ( τ ϕ 0 > G i ) d t + G ˜ i G ˜ i + 1 p ( τ ϕ ^ 0 > G ˜ i ) d t ] = i = 0 ( 2 1 2 [ 1 ( 1 ) i + 2 ] λ 1 ( ζ 1 i + 1 2 + 1 4 ( 1 ) i + 1 1 4 1 )

2 1 2 [ 1 ( 1 ) i + 1 ] λ 1 ( ζ 1 i 2 + 1 4 ( 1 ) i 1 4 1 ) ) p ( τ ϕ ^ 0 > G i ) + ( 2 1 2 [ 1 ( 1 ) i + 2 ] λ 2 ( ζ 2 i + 1 2 + 1 4 ( 1 ) i + 1 1 4 1 )

2 1 2 [ 1 ( 1 ) i + 1 ] λ 2 ( ζ 2 i 2 + 1 4 ( 1 ) i 1 4 1 ) ) p ( τ ϕ ^ 0 > G ˜ i ) = λ 1 [ ( ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > 0 ) + ( ζ 1 1 ) p ( τ ϕ 0 > G 1 ) + ( ζ 1 ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > G 2 ) + ( ζ 1 2 1 ) p ( τ ϕ 0 > G 3 ) + ( ζ 1 2 ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > G 4 ) + ( ζ 1 3 1 ) p ( τ ϕ 0 > G 5 ) + ( ζ 1 3 ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > G 6 ) + ]

+ λ 2 [ ( ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > 0 ) + ( ζ 2 1 ) p ( τ ϕ ¯ 0 > G ¯ 1 ) + ( ζ 2 ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > G ¯ 2 ) + ( ζ 2 2 1 ) p ( τ ϕ ¯ 0 > G ¯ 3 ) + ( ζ 2 2 ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > G ¯ 4 ) + ( ζ 2 3 1 ) p ( τ ϕ ¯ 0 > G ¯ 5 ) + ( ζ 2 3 ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > G ¯ 6 ) + ] (4)

to solve Equation (4) we shall find the value of p ( τ ϕ 0 > G 2 i 1 ) , p ( τ ϕ ¯ 0 > G ¯ 2 i 1 ) , p ( τ ϕ 0 > G 2 i ) and the value of p ( τ ϕ ¯ 0 > G ¯ 2 i ) as the following

p ( τ ϕ 0 > G 2 i 1 ) 0 p ( x + S ( G 2 i 1 ) < H i / X = x ) v 1 ( d x ) + 0 p ( x + S ( G 2 i 1 ) > H i / X = x ) v 1 (dx)

We get

p ( τ ϕ 0 > G 2 i 1 ) 0 p ( φ ˜ 1 ( G 2 i 1 ) < x ) v 1 ( d x ) + 0 p ( φ 1 ( G 2 i 1 ) > x ) v 1 ( d x ) (5)

also,

p ( τ ϕ ¯ 0 > G ¯ 2 i 1 ) 0 p ( φ ˜ 2 ( G ¯ 2 i 1 ) < y ) v 2 ( d y ) + 0 p ( φ 2 ( G ¯ 2 i 1 ) > y ) v 2 ( d y ) (6)

p ( τ ϕ 0 > G 2 i ) 0 p ( X + S ( G 2 i ) < 2 H i ) v 1 ( d x ) + 0 p ( x + S ( G 2 i ) > 2 H i ) v 1 ( d x ) (7)

We get

p ( τ ϕ 0 > G 2 i ) 0 p ( φ ˜ 1 ( G 2 i ) < x ) v 1 ( d x ) + 0 p ( φ 1 ( G 2 i ) > x ) v 1 ( d x ) (8)

p ( τ ϕ 0 > G ¯ 2 i ) 0 p ( φ ˜ 1 ( G ¯ 2 i ) < y ) v 2 ( d y ) + 0 p ( φ 1 ( G ¯ 2 i ) > y ) v 2 ( d y ) (9)

substituting by (5), (6), (7) and (8) in (4) we can get

E ( τ ϕ ^ ) λ 1 [ ( ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > 0 ) + ( ζ 1 1 ) p ( τ ϕ 0 > G 1 ) + ( ζ 1 ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > G 2 ) + ( ζ 1 2 1 ) p ( τ ϕ 0 > G 3 ) + ( ζ 1 2 ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > G 4 ) + ( ζ 1 3 1 ) p ( τ ϕ 0 > G 5 ) + ( ζ 1 3 ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > G 6 ) + ]

+ λ 2 [ ( ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > 0 ) + ( ζ 2 1 ) p ( τ ϕ ¯ 0 > G ¯ 1 ) + ( ζ 2 ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > G ¯ 2 ) + ( ζ 2 2 1 ) p ( τ ϕ ¯ 0 > G ¯ 3 ) + ( ζ 2 2 ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > G ¯ 4 ) + ( ζ 2 3 1 ) p ( τ ϕ ¯ 0 > G ¯ 5 ) + ( ζ 2 3 ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > G ¯ 6 ) + ]

hence

E ( τ ϕ ^ ) λ 1 [ ( ( ζ 1 2 ) + 1 ) p ( τ ϕ 0 > 0 ) + { 0 w 1 ( x ) v 1 ( d x ) + 0 w 2 ( x ) v 1 ( d x ) } + { 0 w 3 ( y ) v 2 ( d y ) + 0 w 4 ( y ) v 2 ( d y ) } ] + λ 2 [ ( ( ζ 2 2 ) + 1 ) p ( τ ϕ ¯ 0 > 0 ) + { 0 w 5 ( y ) v 2 ( d y ) + 0 w 6 ( y ) v 2 ( d y ) } + { 0 w 7 ( y ) v 2 ( d y ) + 0 w 8 ( y ) v 2 ( d y ) } ]

where,

w 1 ( x ) = i = 1 ( ζ 1 i 1 ) p ( φ ˜ 1 ( G 2 i 1 ) < x ) ,

w 2 ( x ) = i = 1 ( ζ 1 i 1 ) p ( φ 1 ( G 2 i 1 ) > x ) ,

w 3 ( x ) = i = 1 ( ζ 1 i ( ζ 1 2 ) + 1 ) p ( φ ˜ 1 ( G 2 i ) < x ) ,

w 4 ( x ) = i = 1 ( ζ 1 i ( ζ 1 2 ) + 1 ) p ( φ 1 ( G 2 i ) > x ) ,

w 5 ( y ) = i = 1 ( ζ 2 i 1 ) p ( φ ˜ 2 ( G ¯ 2 i 1 ) < y ) ,

w 6 ( y ) = i = 1 ( ζ 2 i 1 ) p ( φ 2 ( G ¯ 2 i 1 ) > y ) ,

w 7 ( y ) = i = 1 ( ζ 2 i ( ζ 2 2 ) + 1 ) p ( φ ˜ 2 ( G ¯ 2 i ) < y ) ,

and

w 8 ( y ) = i = 1 ( ζ 2 i ( ζ 2 2 ) + 1 ) p ( φ 2 ( G ¯ 2 i ) > y ) .

Lemma 1: For any k 0 , let a n 0 for n 0 , and a n + 1 a n . Let { d n } n 0 be a strictly increasing sequence of integers with d 0 = 0 ,

n = k ( d n + 1 d n ) a d n + 1 k = d k a k n = k ( d n + 1 d n ) a d n ,

For more details see [1] .

Theorem 2: The chosen search plan satisfies

w 1 ( x ) w 9 ( | x | ) , w 2 ( x ) w 10 ( | x | ) ,

w 2 ( x ) w 11 ( | x | ) , w 4 ( x ) w 12 ( | x | ) ,

w 5 ( y ) w 13 ( | y | ) , w 6 ( y ) w 14 ( | y | ) ,

w 7 ( y ) w 15 ( | y | ) , and w 8 ( y ) w 16 ( | y | ) ,

where, w 9 ( | x | ) , w 10 ( | x | ) , w 11 ( | x | ) , w 12 ( | x | ) , w 13 ( | y | ) , w 14 ( | y | ) , w 15 ( | y | ) , and w 16 ( | y | ) are linear function.

Proof: This theorem will prove for w 2 ( x ) and w 6 ( y ) , and by similar way we can prove the other cases

w 2 ( x ) = i = 0 ( ζ 1 i 1 ) p ( φ 1 ( G 2 i 1 ) > x )

and

w 6 ( y ) = i = 0 ( ζ 2 i 1 ) p ( φ 2 ( G ¯ 2 i 1 ) > y )

1) if x 0 , then

w 2 ( x ) w 2 (0)

and if y 0 , then

w 6 ( y ) w 6 ( 0 ) ,

2) if x > 0 , then

w 2 ( x ) = w 2 ( 0 ) + i = 0 ( ζ 1 i 1 ) p ( x < φ 1 ( G 2 i 1 ) 0 ) ,

and if y > 0 , then

w 6 ( y ) = w 6 ( 0 ) + i = 0 ( ζ 2 i 1 ) p ( y < φ 2 ( G ¯ 2 i 1 ) 0 ) ,

from Theorem (2), see (Mohamed [1] ) we obtain

w 2 ( 0 ) = i = 0 ( ζ 1 i 1 ) p ( φ 1 ( G 2 i 1 ) > 0 ) i = 1 ( ζ 1 i 1 ) ε G 2 i 1 , 0 < ε < 1

and

w 6 ( 0 ) = i = 0 ( ζ 2 i 1 ) p ( φ 2 ( G ¯ 2 i 1 ) > 0 ) i = 1 ( ζ 2 i 1 ) ε G ¯ 2 i 1 , 0 < ε < 1

Let us define the following

1) V ( n ) = φ 1 ( n θ 1 ) / 2 = i = 1 n W i , where { W i } is a sequence of (i. i. d. r. v.) V ¯ ( n ) = φ 2 ( n θ 2 ) / 2 = i = 1 n W ¯ i , where { W ¯ i } is a sequence of (i. i. d. r. v.).

2) d n = G 2 n 1 / θ 1 = k ( ζ 1 n 1 ) , d ¯ n = G ¯ 2 n 1 / θ 2 = k ( ζ 2 n 1 ) .

3) a ( n ) = n n + k p ( x / 2 < V ( n ) 0 ) = i = 0 | x | / 2 p [ ( j + 1 ) < V ( n ) ( j ) ] , a ¯ ( n ) = n n + k p ( y / 2 < V ¯ ( n ) 0 ) = i = 0 | y | / 2 p [ ( j + 1 ) < V ¯ ( n ) ( j ) ] ,

4) m 1 is an integer such that d m 1 = b 1 | x | + b 2 , and m 2 is an integer such that d m 2 = b ¯ 1 | y | + b ¯ 2 ,

5) α 1 = ζ 1 ( ζ 1 1 ) k , and α 2 = ζ 2 ( ζ 2 1 ) k ,

and

6) U 1 ( j , j + 1 ) = n = 0 p [ ( j + 1 ) < V ( n ) < ( j ) ] , U ¯ 1 ( j , j + 1 ) = n = 0 p [ ( j + 1 ) < V ¯ ( n ) ( j ) ] ,

then U 1 ( j , j + 1 ) and U ¯ 1 ( j , j + 1 ) satisfies the condition of the renewal equation, for more details see [19] .

If n > d m 1 and n > d m 2 then by Theorem (2) see (Mohamed [1] ) a ( n ) and a ¯ ( n ) are non increasing and we can apply Lemma (2) to obtain

w 2 ( x ) w 2 ( 0 ) = i = 1 ( ζ 1 i 1 ) p ( x < φ 1 ( G 2 i 1 ) 0 ) = n = 1 n 1 ζ 1 n a ( d n ) + n = n 1 + 1 ζ 1 n a ( d n ) n = 1 n 1 ζ 1 n + α 1 n = n 1 + 1 ( d n d n 1 ) a ( d n ) n = 1 n 1 ζ 1 n + α 1 n = d m 1 a ( n ) n = 1 n 1 ζ 1 n + α 1 n = d m 1 i = 0 | x | / 2 p [ ( j + 1 ) < V ( n ) ( j ) ] n = 1 n 1 ζ 1 n + α 1 j = 0 | x | / 2 U 1 ( j , j + 1 )

and

w 6 ( x ) w 6 ( 0 ) = i = 0 ( ζ 2 i 1 ) p ( y < φ 2 ( G 2 i 1 ) 0 ) = n = 1 n 2 ζ 2 n a ( d ¯ n ) + n = n 2 + 1 ζ 2 n a ( d ¯ n ) n = 1 n 2 ζ 2 n + α 2 n = n 2 + 1 ( d ¯ n d ¯ n 1 ) a ( d ¯ n )

n = 1 n 2 ζ 2 n + α 2 n = d m 2 a ¯ ( n ) n = 1 n 2 ζ 2 n + α 2 j = 0 | y | / 2 U ¯ 1 ( j , j + 1 )

Since U 1 ( j , j + 1 ) and U ¯ 1 ( j , j + 1 ) satisfied the condition of the renewal equation, hence U 1 ( j , j + 1 ) and U ¯ 1 ( j , j + 1 ) is bounded for all j by a constant, so

w 2 ( x ) w 2 ( 0 ) + N 1 + N 2 | x | = w 10 ( | x | ) ,

and

w 6 ( x ) w 6 ( 0 ) + N ¯ 1 + N ¯ 2 | x | = w 14 ( | y | ) .

Theorem 3: If ϕ ^ = ( ϕ 0 , ϕ ¯ 0 ) Φ ^ is a finite search plan, then E | Z 0 | is finite.

Proof: If E ( τ ϕ ^ ) < , then p ( τ ϕ ^ isfinite ) = 1 and so

p ( τ ϕ 0 is finite ) + p ( τ ϕ ^ 0 isfinite ) = 1 ,

then, we conclude that

p ( τ ϕ 0 is finite ) = 1 and p ( τ ϕ ¯ 0 isfinite ) = 0 ,

or

p ( τ ϕ 0 is finite ) = 0 and p ( τ ϕ ¯ 0 isfinite ) = 1 .

On the first line L1 if p ( τ ϕ 0 is finite ) = 1 , then X 0 = ϕ ( τ ϕ 0 ) S ( τ ϕ 0 ) with probability one and hence

E | X 0 | E ( τ ϕ 0 ) + E | S ( τ ϕ 0 ) | .

If E ( τ ϕ 0 ) < , but | S ( τ ϕ 0 ) | τ ϕ 0 , then E | S ( τ ϕ 0 ) | E ( τ ϕ 0 ) and E | X 0 | < .

On the second line L2 if p ( τ ϕ ¯ 0 isfinite ) = 1 , then Y 0 = ϕ ( τ ϕ ¯ 0 ) S ( τ ϕ ¯ 0 ) with probability one, by the same way we can get E | Y 0 | is finite on the second line L2.

3. Existence of an Optimal Search Plan

Theorem 4: Let for any t I + , let S ( t ) be a process. The mapping ϕ ^ E ( τ ϕ ^ ) R + is lower semi-continuous on Φ ^ ( t ) .

Proof: Let I ( ϕ ^ , t ) be the indicator function of the set { τ ϕ ^ t } by the Fatou Lebesque theorem see (Stone [16] ) we get

E ( τ ϕ ^ ) = E [ t = 1 I ( ϕ ^ , t ) ] = E [ t = 1 lim i inf I ( ϕ ^ n , t ) ] lim i inf E ( τ ϕ ^ ) ,

for any sequence ϕ ^ n ϕ ^ in Φ ^ ( t ) is sequentially compact [20] , thus the mapping ϕ ^ E ( τ ϕ ^ ) is lower semi continuous on Φ ^ ( t ) , then this mapping attains its minimum.

4. Conclusions

We have described a new kind of search technique to find a lost moving target on one of two disjoint lines. The motion of the four searchers on the two lines in the quasi-coordinated search technique is independent, and this helps us to find the lost target without waste of time and cost, especially if this target is valuable as the search for lost children. Actually we calculated the finite search plan. Also; we proved the existence of an optimal search plan which minimizes the expected value of the first meeting time between one of the searchers and the target.

In the future work, we will introduce an important search problem, looking for a randomly moving target as a general case and the searchers will begin their mission from any point on the line.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Teamah, A. and Afifi, W. (2019) Quasi-Coordinate Search for a Randomly Moving Target. Journal of Applied Mathematics and Physics, 7, 1814-1825. doi: 10.4236/jamp.2019.78124.

References

[1] Mohamed, A.A. and El-Rayes, A.B. (1989) Search for a Randomly Moving Target. The Third ORMA Conference, Vol. 2, 323-329.
[2] Alpern, S. and Howard, J.V. (2000) Alternating Search at Two Locations. Dynamics and Control, 10, 319-339.
https://doi.org/10.1023/A:1011245715521
[3] El-Hadidy, M.A. and El-Bagoury, A.H. (2016) Optimal Search Strategy for a Three-Dimensional Randomly Located Target. International Journal of Operational Research, 29, 115-126.
http://www.inderscience.com/link.php?id=83178
https://doi.org/10.1504/IJOR.2017.10003932
[4] Mohamed, A.A. (2005) The Generalized Search for One Dimensional Random Walker. International Journal of Pure and Applied Mathematics, 19, 375-387.
[5] Mohamed, A.A. and Abou-Gabal, H.M. (2003) Linear Search with Multiple Searchers for a Randomly Moving Target. International Conference for Statistics, Computer Science and its Application, 115-124.
[6] Mohamed, A.A. and Abou-Gabal, H.M. (2004) Multiplicative Linear Search Problem. Egyptian Statistical Journal, Cairo University, 48, 34-45.
[7] Beck, A. and Warren, P. (1973) The Return of the Linear Search Problem. Israel Journal of Mathematics, 14, 169-183.
https://doi.org/10.1007/BF02762672
[8] Balkhi, Z.T. (1989) The Generalized Optimal Search Paths for Continuous Univariate Random Variable. Journal of the Operations Research, 23, 67-96.
https://doi.org/10.1051/ro/1989230100671
[9] Stone, L.D. (1975) Theory of Optimal Search. Academic Press, New York.
[10] Mohamed, A.A., Abou-Gabal, H.M. and Afifi, W.A. (2013) Double Coordinate Search Problem. International Journal of Contemporary Mathematical Science, 8.
[11] Mohamed, A.A., Abou-Gabal, H.M. and Afifi, W.A. (2016) Generalized Coordinated Search for a Randomly Located Target. Delta Journal of Science, 38.
[12] Reyniers, D.J. (1996) Coordinated Search for an Object on the Line. European Journal of Operational Research, 95, 663-670.
https://doi.org/10.1016/S0377-2217(96)00314-1
[13] Mohamed, A.A. and El-Hadidy, M. (2013) Coordinated Search for a Conditionally Deterministic Target Motion in the Plan. European Journal of Mathematical Sciences, 2, 272-295.
[14] Mohamed, A.A., Abou-Gabal, H.M. and El-Hadidy, M. (2009) Coordinated Search for a Randomly Located Target on the Plane. European Journal of Pure and Applied Mathematics, 2, 97-111.
[15] Mohamed, A.A., Fergany, H.A. and El-Hadidy, M. (2012) On the Coordinated Search Problem on the Plane. Istanbul University Journal of the School of Business Administration, 41, 80-102.
[16] Bourgault, F., Furukawa, T. and Durrant-Whyte, H. (2003) Coordinated Decentralized Search for a Lost Target in a Bayesian World. Proceedings IEEERSJ International Conference, Intelligent Robots and Systems, Vol. 1.
[17] Mohamed, A.A. and EL-Bagoury, A.H. (2019) Minimizing the Expected Time to Detect a Randomly Located Lost Target Using 3-Dimensional Search Technique. Journal of Communications in Statistics.
[18] Mohamed, A.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, 9.
https://doi.org/10.1504/IJCSM.2018.093152
[19] Feller, W. (1966) An Introduction to Probability Theory and Its Applications. Second Edition, Wiley, New York.
[20] Mohamed, A.A., El-Rayes, A.B. and Abou-Gabal, H.M. (2003) Linear Search for a Brownian Target Motion. Acta Mathematica Scientia, 23B, 321-327.
https://doi.org/10.1016/S0252-9602(17)30338-7

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.