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
, where
is the set of non negative integers. Assume that
is a sequence of independent and identically distributed random variables such that for any
:
and
. Thus, we have
(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
and
start together looking for the lost target from the intersected point
on
.The searchers coordinate their search to find the lost target, where each of the searchers
and
start search at
and go to the right part of starting point as far as
and
respectively, and each of searchers
and
start search at
and go the left part of the same lines as far as
and
respectively. Then, turn back to
to tell the other searchers if the target is found or not. Retrace the steps again to explore the right (left) part of
(
) as far as
(
),
and so on, see Figure 1.
All the searchers
and
reach to
and
respectively in the same time
, then they come back to
again in the same time
. If no one of the searchers do not find the lost target, then they begin their search from
and reach to
and
in the time
, then they come back to
again in the same time
and so on. A search plan
with speed
is a function
,
, such that:
(2)
where
. Let the search plan be represented by
where
is the set of all search plan.
We assume that
is a random variable represented the initial position of the target and valued in 2I (or 2I + 1) and independent with
. If
then the target moves on
and if
the target moves on
such that
. There is a known probability measures
, such that
on
, where
is probability measure induced by the position of the target on
, while
on
. The first meeting time is a random variable valued in
defined as:
At the beginning of the search suppose that the lost target is existing on any integer point on
but more than
or less than
or the lost target is existing on any integer point on
but more than
or less than
. Let
be the first meeting time between one of the searchers and the target. The main objective is to find the search plan such that
and if
where E terms to expectation value, then we call
is an optimal search plan. Given
, 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.
where
is integer, then
(3)
Existence of a Finite Search Plan
Assuming that
be positive integers such that:
, where
and θ are positive integer numbers greater than one and
. We will shall define the following sequences
and
, for all the searchers
on the line
, to obtain the distances which the searcher should do them as the functions of
and
. In Figure 2 we can define
(4)
And
(5)
Also, we shall define the search paths as follows: for any
, If
,
, then
(6)
and
. We define the notations
and
on
, respectively,
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
is a search plan, then the expectation
is finite if:
and
are finite.
Proof:
The hypothesis
and
are valued in 2I (or 2I + 1) and independent of
, if
then
is greater than
until the first meeting between
and the target on
also if
, then
is smaller than
until the first meeting between
and the target on
. The same thing for the second line by replacing
by
in the second line
and
by
respectively.
Hence, for any
:
hence,
see ( [5]),
To solve this equation we shall find the value of
and the value of
as the following
We get
also we get
We get
Hence, we can get,
hence,
where,
and
lemma 1.
For any ≥ 0, if
for
, and
,
be a strictly increasing sequence of integer numbers with
, then
where
and
are vectors see [32] .
Theorem 2. For the two intersected lines the chosen search plan satisfies:
,
,
,
,
,
,
and
,
where
,
,
,
,
,
,
and
are linear functions.
Proof:
We shall prove the theorem for
and
since the other cases can be proved by similar ways.
and
Let us defined the following:
1) For
, we have
And for
, we have
.
2) but for
, we have
and for
, we have
from theorem 2 see [13], we obtain:
And
Let us defined the following:
1)
where
is a sequence of independent identically distributed random variable.
where
is a sequence of independent identically distributed random variable.
2)
3) m1 is an integer such that
, m2 is an integer such that
.
4)
5)
and
6)
Then
and
satisfies the condition of the renewal equation see [33] . Thus, from lemma (1) we have
and
are non increasing if
and
see [4], consequently,
and
Such that for any line
and
satisfies the condition of the renewal equation see [26], we have
and
are bounded for all j by a constant so
then
The necessary and sufficient condition for the existence of a finite search plan is
, that is sufficient from the consequence of Theorems 1,2 and the following Theorem 3.
Theorem. 3.
If there exists a finite search plan
, then
is finite, where
is a random variable representing the initial position of the target on a line
.
Proof
For
, we have
, and so
Therefore,
where
the first meeting time on the
and
, respectively, then,
.
we conclude that:
and
or
and
If
on the first line
, then
with probability one and hence
that leads to,
but
, then
.
If
, then
, and
is finite. On the second line
.
If
, then
with probability one, by the same way we can get
, and
is finite.
3. Existence of an Optimal Search Plan
Definition 1.
Let
be two sequences of search plans, we say that
converges to
as i tends to
if and only if for any
, converges to
uniformly on every compact subset see [13] .
Theorem 1.4.
Let for any
, and S(t) be a process(one dimensional random walk). The mapping
is lower semi-continuous on
.
Proof
Let
be the indicator function of the set
, by the fatou-lebesque theorem see [5] we get:
for any sequence
in
, where
is sequentially compact see [29] .Thus the mapping
is lower semi continuous on
, 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
where
and
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
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
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.