AM  Vol.10 No.5 , May 2019
Optimal Coordinated Search for a Discrete Random Walker
ABSTRACT
This paper presents the search technique for a lost target. A lost target is random walker on one of two intersected real lines, and the purpose is to detect the target as fast as possible. We have four searchers start from the point of intersection, they follow the so called Quasi-Coordinated search plan. The expected value of the first meeting time between one of the searchers and the target is investigated, also we show the existence of the optimal search strategy which minimizes this first meeting time.

1. Introduction

The search problem for a randomly moving target is very interesting because it may arise in many real world situations such as searching for lost persons on roads, the cancer cells in the human body and missing black box of a plane crash in the depth of the sea or ocean, also searching for a gold mine underground, Landmines and navy mines, a faulty unit in a large linear system such as electrical power lines, telephone lines, and mining system, and so on (see [1], [2], [3], [4] and [5]).

The aim of search, in many cases (see [6], and [7]) is to calculate the expected cost of detecting the target and is to obtain the search plan, which minimizes this expected cost. In the case of linear search for stationary or randomly moving targets many studies are made (see [8] - [26]).

The coordinated search method is one of the famous search methods which consider the searchers starting together from the origin and moving, seeking for a random walk target. Therefore, coordinated search technique is one of many techniques which studied previously on the line where the located targets have symmetric and unsymmetric distributions (see [27], [28], [29] and [30]), this technique has been illustrated on the circle with a known radius and the target equally likely to be anywhere on its circumference (see [31]), also this technique has been discussed in the plane when the located target has symmetric and asymmetric distribution (see [32] and [33]). There is obviously some similarity between this problem and the well known linear search problem.

In the present paper, we introduce the search problem for a random walk target motion on one of two intersected lines. This will happen by coordinating search between four searchers, all the searchers will start together at the same point of intersected their lines with zero as the starting and meeting point of the searchers. So that we may assume that two searchers always search to the right part and the other searchers search to the left part of intersected point. They return to zero after searching successively common distances until the target is found, we call this search as Quasi-Coordinated Linear Search Problem. We aim to minimize the expected value of the first meeting time between one of the searchers and the target. This paper is organized as follows. In Section 2 we formulate the problem and we give the conditions that make the expected value of the first meeting time between one of the searchers and the target which is finite. In Section 3 the existence of optimal search plan that minimizes the expected value of the first meeting time is presented. Finally, the paper concludes with a discussion of the results and directions for future research.

2. Problem Formulation

A target is assumed to move randomly on one of two intersected line according to a stochastic process { S ( t ) , t I + } , where I + is the set of non negative integers. Assume that { X i } i 0 is a sequence of independent and identically distributed random variables such that for any i 1 : P ( X i = 1 ) = p and P ( X i = 1 ) = 1 p = q , p , q > 0 . Thus, we have

S ( t ) = i = 1 t X i , t > 0 and S ( 0 ) = 0 (1)

as a Random Walk. Our aim is to calculate the expected value of the first meeting time between one of searcher and lost target, and investigate it, also we show the existence of a search plan which minimize this expected value.

In the present paper we take the search region to be the real lines. Assume that, we have four searchers S 1 , S 2 , S 3 and S 4 start together looking for the lost target from the intersected point H 0 = 0 on L 1 L 2 .The searchers coordinate their search to find the lost target, where each of the searchers S 1 and S 3 start search at H 0 and go to the right part of starting point as far as H 11 and H 21 respectively, and each of searchers S 2 and S 4 start search at H 0 and go the left part of the same lines as far as H 11 and H 21 respectively. Then, turn back to H 0 to tell the other searchers if the target is found or not. Retrace the steps again to explore the right (left) part of H j 1 ( H j 1 ) as far as H j 2 ( H j 2 ), j = 1 , 2 and so on, see Figure 1.

All the searchers S 1 , S 2 , S 3 and S 4 reach to H 11 , H 11 , H 21 and H 21 respectively in the same time G 1 , then they come back to H 0 again in the same time G 2 . If no one of the searchers do not find the lost target, then they begin their search from H 0 and reach to H 12 , H 12 , H 22 and H 22 in the time G 3 , then they come back to H 0 again in the same time G 4 and so on. A search plan ϕ r with speed V r is a function ϕ r : R + R , r = 1 , 2 , 3 , 4 , such that:

| ϕ r ( t 1 ) ϕ r ( t 2 ) | = V r | t 1 t 2 | , t 1 , t 2 R + (2)

where ϕ r ( 0 ) = 0 , r = 1 , 2 , 3 , 4 . Let the search plan be represented by ϕ 0 = ( ϕ 1 , ϕ 2 , ϕ 3 , ϕ 4 ) , ϕ 0 Φ 0 where Φ 0 is the set of all search plan.

We assume that Z 0 is a random variable represented the initial position of the target and valued in 2I (or 2I + 1) and independent with S ( t ) , t > 0 . If Z 0 = Z 1 then the target moves on L 1 and if Z 0 = Z 2 the target moves on L 2 such that P ( Z 0 = Z 1 ) + P ( Z 0 = Z 2 ) = 1 . There is a known probability measures v j , such that v 1 + v 2 = 1 on L 1 L 2 , where v 1 is probability measure induced by the position of the target on L 1 , while v 2 on L 2 . The first meeting time is a random variable valued in I + defined as:

τ ϕ ^ 0 = inf { t , r = 1 2 | ϕ r ( t ) | = Z 1 + S ( t ) or r = 3 4 | ϕ r ( t ) | = Z 2 + S ( t ) } .

At the beginning of the search suppose that the lost target is existing on any integer point on L 1 but more than H 11 or less than H 11 or the lost target is existing on any integer point on L 2 but more than H 21 or less than H 21 . Let τ ϕ ^ 0 be the first meeting time between one of the searchers and the target. The main objective is to find the search plan such that E ( τ ϕ ^ 0 ) < and if E ( τ ϕ ^ 0 ) < E ( τ ϕ ^ 0 ) where E terms to expectation value, then we call ϕ ^ 0 is an optimal search plan. Given n > 0 , if x is:

Figure 1. The searchers S1 and S2 start from the origin of L1 after searching successively distances H11 and −H11, respectively, they return to the origin (note the black arrow) and then they search the distances H12 and −H12, respectively, they return to the origin (note the blue arrow) and so on also the same procedure for the searchers S3 and S4 on L2.

0 k 1 n + x 2 n

where k 1 is integer, then

P ( S ( n ) = k 1 ) = ( n k 1 ) p k 1 q n k 1 (3)

Existence of a Finite Search Plan

Assuming that λ , ζ be positive integers such that: ζ > 1 , λ = k θ , where k = 1 , 2 , and θ are positive integer numbers greater than one and V = 1 . We will shall define the following sequences { G i } i 1 and { H j i } i 1 , j = 1 , 2 , for all the searchers S r , r = 1 , 2 , 3 , 4 on the line L j , to obtain the distances which the searcher should do them as the functions of λ and ζ . In Figure 2 we can define

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

And

H j i = G 2 i 1 = 1 2 G 2 i (5)

Also, we shall define the search paths as follows: for any t I + , If G i t G i + 1 , i = 1 , 2 , 3 , , then

ϕ j ( t ) = ( 1 2 H j i + 1 2 ) + ( 1 ) i + 1 ( 1 2 H j i + 1 2 ) + ( 1 ) i ( t G i ) (6)

and ϕ k ( t ) = ϕ k + 1 ( t ) , k = 1 , 3 . We define the notations φ j ( t ) = S ( t ) t and φ ˜ j ( t ) = S ( t ) + t on L j , j = 1 , 2 , respectively, τ ϕ ^ 0 is the first meeting between one of the searcher and the target.

Figure 2. Plots the searched distances Hji and times Gi on L1.

Theorem 1. If ϕ r Φ 0 , r = 1 , 2 , 3 , 4 is a search plan, then the expectation E ( τ ϕ ^ 0 ) is finite if:

B 1 ( z 1 ) = i = 1 ( ζ i 1 ) p ( φ ˜ 1 ( G 2 i 1 ) < z 1 ) ,

B 2 ( z 1 ) = i = 1 ( ζ i 1 ) p ( φ 1 ( G 2 i 1 ) > z 1 ) ,

B 3 ( z 1 ) = i = 1 ( ζ i ( ζ 2 ) + 1 ) p ( φ ˜ 1 ( G 2 i ) < z 1 ) ,

B 4 ( z 1 ) = i = 1 ( ζ i ( ζ 2 ) + 1 ) p ( φ 1 ( G 2 i ) > z 1 ) ,

B 5 ( z 2 ) = i = 1 ( ζ i 1 ) p ( φ ˜ 2 ( G 2 i 1 ) < z 2 ) ,

B 6 ( z 2 ) = i = 1 ( ζ i 1 ) p ( φ 2 ( G 2 i 1 ) > z 2 ) ,

B 7 ( z 2 ) = i = 1 ( ζ i ( ζ 2 ) + 1 ) p ( φ ˜ 2 ( G 2 i ) < z 2 )

and

B 8 ( z 2 ) = i = 1 ( ζ i ( ζ 2 ) + 1 ) p ( φ 2 ( G 2 i ) > z 2 ) ,

are finite.

Proof:

The hypothesis Z 1 and Z 2 are valued in 2I (or 2I + 1) and independent of S ( t ) , t > 0 , if Z 1 > 0 then Z 1 + S ( t ) is greater than ϕ 1 ( t ) until the first meeting between S 1 and the target on L 1 also if Z 1 < 0 , then Z 1 + S ( t ) is smaller than ϕ 2 ( t ) until the first meeting between S 2 and the target on L 1 . The same thing for the second line by replacing Z 1 by Z 2 in the second line L 2 and ϕ 1 ( t ) , ϕ 2 ( t ) by ϕ 3 ( t ) , ϕ 4 ( t ) respectively.

Hence, for any i > 0 :

p ( τ ϕ ^ 0 > t ) r = 1 4 p ( τ ϕ r > t )

hence,

E ( τ ϕ ^ 0 ) = 0 p ( τ ϕ ^ 0 > t ) d t

see ( [5]),

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

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

To solve this equation we shall find the value of p ( τ ϕ ^ 0 > G 2 i 1 ) and the value of p ( τ ϕ ^ 0 > G 2 i ) , i 1 as the following

p ( τ ϕ ^ 0 > G 2 i 1 ) 0 p ( Z 1 + S ( G 2 i 1 ) < H i | Z i = z 1 ) v 1 ( d z 1 ) + 0 p ( Z 1 + S ( G 2 i 1 ) > H i | Z i = z 1 ) v 1 ( d z 1 ) + 0 p ( Z 2 + S ( G 2 i 1 ) < H i | Z 2 = z 2 ) v 2 ( d z 2 ) + 0 p ( Z 2 + S ( G 2 i 1 ) > H i | Z 2 = z 2 ) v 2 ( d z 2 )

We get

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

also we get

p ( τ ϕ ^ 0 > G 2 i ) 0 p ( Z 1 + S ( G 2 i ) < 2 H i | Z 1 = z 1 ) v 1 ( d z 1 ) + 0 p ( Z 1 + S ( G 2 i ) > 2 H i | Z 1 = z 1 ) v 1 ( d z 1 ) + 0 p ( Z 2 + S ( G 2 i ) < 2 H i | Z 2 = z 2 ) v 2 ( d z 2 ) + 0 p ( Z 2 + S ( G 2 i ) > 2 H i | Z 2 = z 2 ) v 2 ( d z 2 )

We get

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

Hence, we can get,

E ( τ ϕ ^ 0 ) λ { ( ( ζ 2 ) + 1 ) p ( τ ϕ ^ > 0 ) + ( ζ 1 ) [ 0 p ( φ ˜ 1 ( G 1 ) < z 1 ) v 1 ( d z 1 ) + 0 p ( φ 1 ( G 1 ) > z 1 ) v 1 ( d z 1 ) ] + ( ζ ( ζ 2 ) + 1 ) [ 0 p ( φ ˜ 1 ( G 2 ) < z 1 ) v 1 ( d z 1 )

+ 0 p ( φ 1 ( G 2 ) > z 1 ) v 1 ( d z 1 ) ] + ( ζ 2 1 ) [ 0 p ( φ ˜ 1 ( G 3 ) < z 1 ) v 1 ( d z 1 ) + 0 p ( φ 1 ( G 3 ) > z 1 ) v 1 ( d z 1 ) ] + ( ζ 2 ( ζ 2 ) + 1 ) [ 0 p ( φ ˜ 1 ( G 4 ) < z 1 ) v 1 ( d z 1 ) + 0 p ( φ 1 ( G 4 ) > z 1 ) v 1 ( d z 1 ) ] + ( ζ 3 1 ) [ 0 p ( φ ˜ 1 ( G 5 ) < z 1 ) v 1 ( d z 1 )

+ 0 p ( φ 1 ( G 5 ) > z 1 ) v 1 ( d z 1 ) ] + ( ζ 3 ( ζ 2 ) + 1 ) [ 0 p ( φ ˜ 6 ( G 2 ) < z 1 ) v 1 ( d z 1 ) + 0 p ( φ 1 ( G 6 ) > z 1 ) v 1 ( d z 1 ) ] } + λ { ( ( ζ 2 ) + 1 ) p ( τ ϕ ^ > 0 ) + ( ζ 1 ) [ 0 p ( φ ˜ 2 ( G 1 ) < z 2 ) v 2 ( d z 2 ) + 0 p ( φ 2 ( G 1 ) > z 2 ) v 2 ( d z 2 ) ] + ( ζ ( ζ 2 ) + 1 ) [ 0 p ( φ ˜ 2 ( G 2 ) < z 2 ) v 2 ( d z 2 ) + 0 p ( φ 2 ( G 2 ) > z 2 ) v 2 ( d z 2 ) ]

+ ( ζ 2 1 ) [ 0 p ( φ ˜ 2 ( G 3 ) < z 2 ) v 2 ( d z 2 ) + 0 p ( φ 3 ( G 2 ) > z 2 ) v 2 ( d z 2 ) ] + ( ζ 2 ( ζ 2 ) + 1 ) [ 0 p ( φ ˜ 4 ( G 2 ) < z 2 ) v 2 ( d z 2 ) + 0 p ( φ 2 ( G 4 ) > z 2 ) v 2 ( d z 2 ) ] + ( ζ 3 1 ) [ 0 p ( φ ˜ 5 ( G 2 ) < z 2 ) v 2 ( d z 2 ) + 0 p ( φ 5 ( G 2 ) > z 2 ) v 2 ( d z 2 ) ] + ( ζ 3 ( ζ 2 ) + 1 ) [ 0 p ( φ ˜ 2 ( G 6 ) < z 2 ) v 2 ( d z 2 ) + 0 p ( φ 6 ( G 2 ) > z 2 ) v 2 ( d z 2 ) ] + }

hence,

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

where,

B 1 ( z 1 ) = i = 1 ( ζ i 1 ) p ( φ ˜ 1 ( G 2 i 1 ) < z 1 ) ,

B 2 ( z 1 ) = i = 1 ( ζ i 1 ) p ( φ 1 ( G 2 i 1 ) > z 1 ) ,

B 3 ( z 1 ) = i = 1 ( ζ i ( ζ 2 ) + 1 ) p ( φ ˜ 1 ( G 2 i ) < z 1 ) ,

B 4 ( z 1 ) = i = 1 ( ζ i ( ζ 2 ) + 1 ) p ( φ 1 ( G 2 i ) > z 1 ) ,

B 5 ( z 2 ) = i = 1 ( ζ i 1 ) p ( φ ˜ 2 ( G 2 i 1 ) < z 2 ) ,

B 6 ( z 2 ) = i = 1 ( ζ i 1 ) p ( φ 2 ( G 2 i 1 ) > z 2 ) ,

B 7 ( z 2 ) = i = 1 ( ζ i ( ζ 2 ) + 1 ) p ( φ ˜ 2 ( G 2 i ) < z 2 )

and

B 8 ( z 2 ) = i = 1 ( ζ i ( ζ 2 ) + 1 ) p ( φ 2 ( G 2 i ) > z 2 ) ,

lemma 1.

For any ≥ 0, if a n 0 for n > 0 , and a n + 1 a n , { d n } n 0 be a strictly increasing sequence of integer numbers with d 0 = 0 , then

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 ,

where n = k ( d n + 1 d n ) a d n + 1 , k = d k a k and n = k ( d n + 1 d n ) a d n are vectors see [32] .

Theorem 2. For the two intersected lines the chosen search plan satisfies:

B 1 ( z 1 ) B 9 ( | z 1 | ) , B 2 ( z 1 ) B 10 ( | z 1 | ) , B 3 ( z 1 ) B 11 ( | z 1 | ) ,

B 4 ( z 1 ) B 12 ( | z 1 | ) , B 5 ( z 2 ) B 13 ( | z 2 | ) , B 6 ( z 2 ) B 14 ( | z 2 | ) ,

B 7 ( z 2 ) B 15 ( | z 2 | ) and B 8 ( z 2 ) B 16 ( | z 2 | ) ,

where B 9 ( | z 1 | ) , B 10 ( | z 1 | ) , B 11 ( | z 1 | ) , B 12 ( | z 1 | ) , B 13 ( | z 2 | ) , B 14 ( | z 2 | ) , B 15 ( | z 2 | ) and B 16 ( | z 2 | ) are linear functions.

Proof:

We shall prove the theorem for B 2 ( z 1 ) and B 6 ( z 2 ) since the other cases can be proved by similar ways.

B 2 ( z 1 ) = i = 1 ( ζ i 1 ) p ( φ 1 ( G 2 i 1 ) > z 1 )

and

B 6 ( z 2 ) = i = 1 ( ζ i 1 ) p ( φ 2 ( G 2 i 1 ) > z 2 )

Let us defined the following:

1) For z 1 0 , we have B 2 ( z 1 ) B 2 (0)

And for z 2 0 , we have B 6 ( z 2 ) B 6 ( 0 ) .

2) but for z 1 > 0 , we have

B 2 ( z 1 ) = B 2 ( 0 ) + i = 1 ( ζ i 1 ) p ( z 1 < φ 1 ( G 2 i 1 ) 0 ) ,

B 2 ( z 1 ) B 2 ( 0 ) = i = 1 ( ζ i 1 ) p ( z 1 < φ 1 ( G 2 i 1 ) 0 ) .

and for z 2 > 0 , we have

B 6 ( z 2 ) = B 6 ( 0 ) + i = 1 ( ζ i 1 ) p ( z 2 < φ 2 ( G 2 i 1 ) 0 ) ,

B 6 ( z 2 ) B 2 ( 0 ) = i = 1 ( ζ i 1 ) p ( z 2 < φ 2 ( G 2 i 1 ) 0 ) .

from theorem 2 see [13], we obtain:

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

And

B 6 ( 0 ) = i = 0 ( ζ i 1 ) p ( G 2 i 1 > 0 ) i = 1 ( ζ i 1 ) ε G 2 i 1 , 0 < ε < 1

Let us defined the following:

1)

V 1 ( n ) = φ 1 ( n θ 1 ) 2 = i = 1 n B 1 (i)

where { B 1 i } is a sequence of independent identically distributed random variable.

V 2 ( n ) = φ 2 ( n θ 2 ) 2 = i = 1 n B 2 i

where { B 2 i } is a sequence of independent identically distributed random variable.

2)

d 1 ( n ) = G 2 n 1 θ 1 = K ( ζ n 1 )

d 2 ( n ) = G 2 n 1 θ 2 = K ( ζ n 1 )

3) m1 is an integer such that d m 1 = b 1 | z 1 | + b 2 , m2 is an integer such that d m 2 = b 1 | z 2 | + b 2 .

4)

a 1 ( n ) = n n + k p ( z 1 / 2 < V 1 ( n ) 0 ) = i = 0 ( | z 1 | / 2 ) p [ ( i + 1 ) < V 1 ( n ) ( i ) ]

a 2 ( n ) = n n + k p ( z 2 / 2 < V 2 ( n ) 0 ) = i = 0 ( | z 2 | / 2 ) p [ ( i + 1 ) < V 2 ( n ) ( i ) ]

5)

α 1 = ζ ( ζ 1 ) K ,

α 2 = ζ ( ζ 1 ) K

and

6)

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

U 2 ( j , j + 1 ) = n = 0 p [ ( j + 1 ) < V 2 ( n ) ( j ) ] .

Then U 1 ( j , j + 1 ) and U 2 ( j , j + 1 ) satisfies the condition of the renewal equation see [33] . Thus, from lemma (1) we have α 1 ( n ) and α 2 ( n ) are non increasing if n > d m 1 and n > d m 2 see [4], consequently,

B 2 ( z 1 ) B 2 ( 0 ) = i = 1 ( ζ i 1 ) p ( z 1 < φ 1 ( G 2 i 1 ) 0 ) = i = 1 n 1 ( ζ i 1 ) p ( z 1 < φ 1 ( G 2 i 1 ) 0 ) + i = n 1 + 1 ( ζ i 1 ) p ( z 1 < φ 1 ( G 2 i 1 ) 0 ) = n = 1 n 1 ζ n a 1 ( d 1 ( n ) ) + n = n j + 1 ζ n a 1 ( d 1 (n) )

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

and

B 6 ( z 2 ) B 6 ( 0 ) = i = 1 ( ζ i 1 ) p ( z 2 < φ 2 ( G 2 i 1 ) 0 ) = i = 1 n 2 ( ζ i 1 ) p ( z 2 < φ 2 ( G 2 i 1 ) 0 ) + i = n 2 + 1 ( ζ i 1 ) p ( z 2 < φ 2 ( G 2 i 1 ) 0 ) = n = 1 n 2 ζ n a 2 ( d 2 ( n ) ) + n = n 2 + 1 ζ n a 2 ( d 2 (n) )

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

Such that for any line U 1 ( j , j + 1 ) and U 2 ( j , j + 1 ) satisfies the condition of the renewal equation see [26], we have U 1 ( j , j + 1 ) and U 2 ( j , j + 1 ) are bounded for all j by a constant so

B 2 ( z 1 ) B 2 ( 0 ) + M 1 + M 2 | z 1 | = B 10 ( | z 1 | ) ,

then

B 6 ( z 1 ) B 6 ( 0 ) + M 1 + M 2 | z 2 | = B 14 ( | z 2 | ) .

The necessary and sufficient condition for the existence of a finite search plan is E | Z j | < , j = 1 , 2 , that is sufficient from the consequence of Theorems 1,2 and the following Theorem 3.

Theorem. 3.

If there exists a finite search plan ϕ ^ 0 Φ ^ 0 , then E | Z j | is finite, where Z j is a random variable representing the initial position of the target on a line L j , j = 1 , 2 .

Proof

For E ( τ ϕ ^ 0 ) < , we have p ( τ ϕ ^ 0 is finite ) = 1 , and so

r = 1 4 p ( τ ϕ r is finite ) = 1

Therefore,

p ( τ ϕ ^ 01 is finite ) + p ( τ ϕ ^ 02 is finite ) = 1

where τ ϕ ^ 01 , τ ϕ ^ 02 the first meeting time on the L 1 and L 2 , respectively, then,

p ( τ ϕ ^ 01 is finite ) = 1 .

we conclude that:

p ( τ ϕ ^ 01 is finite ) = 1 and p ( τ ϕ ^ 02 is finite ) = 0

or p ( τ ϕ ^ 01 is finite ) = 0 and p ( τ ϕ ^ 02 is finite ) = 1

If p ( τ ϕ ^ 01 is finite ) = 1 on the first line L 1 , then Z 1 = ϕ ( τ ϕ ^ 01 ) S ( τ ϕ ^ 01 ) with probability one and hence

| Z 1 | | ϕ ( τ ϕ ^ 01 ) | + | S ( τ ϕ ^ 01 ) | τ ϕ ^ 01 + | S ( τ ϕ ^ 01 ) | ,

that leads to,

E | Z 1 | E ( τ ϕ ^ 01 ) + E | S ( τ ϕ ^ 01 ) | .

but | S ( τ ϕ ^ 01 ) | τ ϕ ^ 01 , then E | S ( τ ϕ ^ 01 ) | E ( τ ϕ ^ 01 ) .

If E ( τ ϕ ^ 01 ) < , then E | S ( τ ϕ ^ 01 ) | < , and E | Z 1 | is finite. On the second line L 2 .

If p ( τ ϕ ^ 02 is finite ) = 1 , then Z 2 = ϕ ( τ ϕ ^ 02 ) S ( τ ϕ ^ 02 ) with probability one, by the same way we can get E | ( τ ϕ ^ 02 ) | < , and E | Z 2 | is finite.

3. Existence of an Optimal Search Plan

Definition 1.

Let ϕ ^ j i Φ ^ ( t ) , j = 1 , 2 be two sequences of search plans, we say that ϕ ^ j i converges to ϕ ^ j as i tends to if and only if for any t I + , converges to ϕ ^ j uniformly on every compact subset see [13] .

Theorem 1.4.

Let for any t I + , and S(t) be a process(one dimensional random walk). The mapping ϕ ^ = ( ϕ 1 , ϕ 2 , ϕ 3 , ϕ 4 ) E ( τ ϕ ^ ) R + E ( τ ϕ ^ ) R + is lower semi-continuous on Φ ^ ( t ) .

Proof

Let I ( ϕ ^ j , t ) be the indicator function of the set { τ ϕ ^ j t } , by the fatou-lebesque theorem see [5] we get:

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

for any sequence ϕ ^ j i ϕ ^ j in Φ ^ ( t ) , where Φ ^ ( t ) is sequentially compact see [29] .Thus the mapping ϕ ^ j E ( τ ϕ ^ j ) is lower semi continuous on Φ ^ ( t ) , then this mapping attains its minimum.

4. Conclusions and Future Work

We illustrated that the quasi coordinated linear search technique for a random walk target on one of two intersected real lines has been presented, where the target initial position is given by a random variable. We introduced the proof of conditions that make the search plan which is finite in Theorem 1 based on the continuity of the search plan. In Theorems 2 we showed that the search plan is finite if the conditions, where

B 1 ( z 1 ) B 9 ( | z 1 | ) , B 2 ( z 1 ) B 10 ( | z 1 | ) , B 3 ( z 1 ) B 11 ( | z 1 | ) , B 4 ( z 1 ) B 12 ( | z 1 | ) , B 5 ( z 2 ) B 13 ( | z 2 | ) , B 6 ( z 2 ) B 14 ( | z 2 | ) , B 7 ( z 2 ) B 15 ( | z 2 | ) and B 8 ( z 2 ) B 16 ( | z 2 | ) ,

where B 9 ( | z 1 | ) , B 10 ( | z 1 | ) , B 11 ( | z 1 | ) , B 12 ( | z 1 | ) , B 13 ( | z 2 | ) , B 14 ( | z 2 | ) , B 15 ( | z 2 | ) and B 16 ( | z 2 | ) are linear functions. We use Theorem 3 to show that if there exists a finite search plan then the expected value of the target initial position E | Z j | is finite. It will also be interesting to see a direct consequence of Theorems 1, 2, and 3 satisfying the existence of a finite search plan if and only if E | Z j | is finite. We pointed to the existence of an optimal search plan in Theorem 4. The effectiveness of this model is illustrated using a real life application.

In future research, we have interesting search problems, study the coordinated search problem using multiple searchers, when the searchers star from any point on more lines rather than the origin.

Cite this paper
Teamah, A. and Elbery, A. (2019) Optimal Coordinated Search for a Discrete Random Walker. Applied Mathematics, 10, 349-362. doi: 10.4236/am.2019.105025.
References
[1]   Abd El-Moneim, A.M. (1999) Search for a Randomly Moving Target with Unrestricted Effort. The Annual Conference (Cairo) ISSR, Math Statistics, 34, 48-56.

[2]   El-Rayes, A.B. and Abd El-Moneim, A.M. (1997) Oscillating Search for a Randomly Located Target. The Annual Conference (Cairo) ISSR, 32, 35-44.

[3]   Ohsumi, A. (1991) Optimal Search for a Markovian Target. Naval Research Logistics, 38, 531-554.
https://doi.org/10.1002/1520-6750(199108)38:4<531::AID-NAV3220380407>3.0.CO;2-L

[4]   Washburn, A.R. (1989) Search and Detection. 2nd Edition, ORSA Books, Arlington.

[5]   Stone, L.D. (1975) Theory of Optimal Search. Academic Press, New York.

[6]   Balkhi, Z.T. (1989) Generalized Optimal Search Paths for Continuous Univariate Random Variables. Recherche Oprationnelle/Operations Research, 23, 67-96.
https://doi.org/10.1051/ro/1989230100671

[7]   Balkhi, Z.T. (1987) The Generalized Linear Search Problem, Existence of Optimal Search Paths. Journal of the Operations Research Society of Japan, 30, 339-420.

[8]   Stone, L.D., Royset, J.O. and Washburn, A.R. (2016) Optimal Search for Moving Targets. Springer, Cham.
https://doi.org/10.1007/978-3-319-26899-6

[9]   Fristedt, B. and Heath, D. (1974) Searching for a Particle on the Real Line. Advances in Applied Probability, 6, 79-102.
https://doi.org/10.2307/1426208

[10]   Frank, W. (1965) An Optimal Search Problem. Society for Industrial and Applied Mathematics Review, 7, 503-5122.
https://doi.org/10.1137/1007106

[11]   Rousseeuw, P.J. (1983) Optimal Search Paths for Random Variables. Journal of Computational and Applied Mathematics, 9, 279-286.
https://doi.org/10.1016/0377-0427(83)90020-1

[12]   McCabe, B. (1974) Searching for One-Dimensional Random Walker. Journal of Applied Probability, 11, 86-93.
https://doi.org/10.1017/S0021900200036421

[13]   Mohamed, A.A. (2005) The Generalized Search for One Dimensional Random Walker. International Journal of Pure and Applied Mathematics, 19, 375-387.

[14]   Beck, A. (1965) More on the Linear Search Problem. Israel Journal of Mathematic, 3, 61-70.
https://doi.org/10.1007/BF02760028

[15]   Beck, A. and Newman, D. (1970) Yet More on The Linear Search Problem. Israel Journal of Mathematic, 8, 419-429.
https://doi.org/10.1007/BF02798690

[16]   Beck, A. and Warren, P. (1972) The Return of the Linear Search Problem. Israel Journal of Mathematic, 14, 169-183.
https://doi.org/10.1007/BF02762672

[17]   Beck, A. and Beck, M. (1984) Son of the Linear Search Problem. Israel Journal of Mathematic, 48, 109-122.
https://doi.org/10.1007/BF02761156

[18]   Beck, A. and Beck, M. (1986) The Linear Search Problem Rides Again. Israel Journal of Mathematic, 53, 365-372.
https://doi.org/10.1007/BF02786568

[19]   Beck, A. and Beck, M. (1992) The Revenge of the Linear Search Problem. SIAM Journal on Control and Optimization, 30, 112-122.
https://doi.org/10.1137/0330008

[20]   Beck, A. (2011) On the Linear Search Problem. Israel Journal of Mathematic, 2, 221-228.
https://doi.org/10.1007/BF02759737

[21]   Abd El-Moneim, A.M. and El-Hadidy, M. (2013) Optimal Multiplicative Generalized Linear Search Plan for a Discrete Random Walker. Journal of Optimization, 2013, Article ID: 706176.
https://doi.org/10.1155/2013/706176

[22]   El-Rayes, A.B., Abd El-Moneim, A.M. 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

[23]   Abd El-Moneim, A.M., Kassem, M. and El-Hadidy, M. (2011) Multiplicative Linear Search for a Brownian Target Motion. Applied Mathematical Modelling, 35, 4127-4139.
https://doi.org/10.1016/j.apm.2011.03.024

[24]   El-Hadidy, M. (2016) Searching for a D-Dimensional Brownian Target with Multiple Sensors. International Journal of Mathematics in Operational Research, 9, 279-301.
https://doi.org/10.1504/IJMOR.2016.10000114

[25]   El-Rayes, A.B. and Abd El-Moneim, A.M. (1989) Searching for a Randomly Moving Target. The Third ORMA Conference, 2, 323-329.

[26]   Feller, W. (1966) An Introduction to Probability Theory and Its Applications. Vol. II, Wiley, New York.

[27]   Abd El-Moneim, A.M., Hamdy, M., Gabal, A. and Afifi, W.A. (2007) On the Coordinated Search Problem. International Journal of Pure and Applied Mathematics, 25, 627-636.

[28]   Reyniers, D.J. (1996) Coordinated Search for an Object on the Line. European Journal of Operation Research, 95, 663-670.
https://doi.org/10.1016/S0377-2217(96)00314-1

[29]   Elbery, A.A. (2007) Generalized and Multiplicative Linear Search Problem for Lost Targets. M.Sc. Thesis, Tanta University, Egypt.

[30]   Reyniers, D. (1995) Coordinated Two Searchers for an Object Hidden on an Interval. Journal of Operational Research Society, 46, 1386-1392.
https://doi.org/10.1057/jors.1995.186

[31]   Thomas, L. (1992) Finding Your Kids When They Are Lost. Journal of Operational Research Society, 43, 637-639.

[32]   Abd El-Moneim, A.M., Hamdy, M., Gabal, A. and El-Hadidy, M.A. (2009) Coordinated Search for a Randomly Located Target on the Plane. European Journal of Pure and Applied Mathematics, 2, 97-111.

[33]   Abd El-Moneim, A.M., Fergany, H.A. and El-Hadidy, M.A. (2012) On the Coordinated Search Problem on the Plane. Istanbul University Journal of the School of Business Administration, 41, 80-102.

 
 
Top