Optimal search strategy of moving object in multichannel system
The analysis of signal search problem in a multi-channel communication system with one search device is carried out. An optimal strategy for moving the search appliance in a multi-channel system is constructed and a corresponding estimate of the search efficiency is obtained.  
Saved in:
| Date: | 2017 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут математики НАН України
2017
|
| Online Access: | https://trim.imath.kiev.ua/index.php/trim/article/view/61 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Transactions of Institute of Mathematics of NAS of Ukraine |
| Download file: |  |
Institution
Transactions of Institute of Mathematics of NAS of Ukraine| _version_ | 1872552589116047360 |
|---|---|
| author | Shlepakov, L. N. Шлепаков, Л. Н. Шлєпаков, Л. М. |
| author_facet | Shlepakov, L. N. Шлепаков, Л. Н. Шлєпаков, Л. М. |
| author_institution_txt_mv | [
{
"author": "L. N. Shlepakov",
"institution": "Institute of Mathematics"
}
] |
| author_sort | Shlepakov, L. N. |
| baseUrl_str | https://trim.imath.kiev.ua/index.php/trim/oai |
| collection | OJS |
| datestamp_date | 2018-02-13T11:57:10Z |
| description |
The analysis of signal search problem in a multi-channel communication system with one search device is carried out. An optimal strategy for moving the search appliance in a multi-channel system is constructed and a corresponding estimate of the search efficiency is obtained.
 
|
| first_indexed | 2026-08-04T01:01:50Z |
| format | Article |
| fulltext |
Збiрник праць Iнституту математики НАН України 2016, т. 13, № 3, 281–292
УДК 519.6:519.2:519.95
𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐬𝐞𝐚𝐫𝐜𝐡 𝐬𝐭𝐫𝐚𝐭𝐞𝐠𝐲 𝐨𝐟 𝐦𝐨𝐯𝐢𝐧𝐠
𝐨𝐛𝐣𝐞𝐜𝐭 𝐢𝐧 𝐦𝐮𝐥𝐭𝐢𝐜𝐡𝐚𝐧𝐧𝐞𝐥 𝐬𝐲𝐬𝐭𝐞𝐦
L.N. Shlepakov
Institute of mathematics NAS of Ukraine, shlepakov@ imath. kiev. ua
Проведено аналiз задачi пошуку сигналу в багатоканальнiй системi
зв’язку з одним пошуковим пристроєм. Побудована оптимальна стра-
тегiя перемiщення пошукового пристрою в багатоканальнiй системi i
отримано вiдповiдну оцiнку ефективностi пошуку.
Проведён анализ задачи поиска сигнала в многоканальной системе свя-
зи с одним поисковым устройством. Построена оптимальная стратегия
перемещения поискового устройства в многоканальной системе и по-
лучено соответствующая оценка эффективности поиска.
𝐈𝐧𝐭𝐫𝐨𝐝𝐮𝐜𝐭𝐢𝐨𝐧
Mathematical apparatus used in the search theory is diverse [1, 2, 3,
10] although even for search tasks with simple parameters, finding the
optimal strategy in an analytical view is usually not possible. Thus find-
ing the solution that leads to the “simplest” problems of mathematical
programming, effectively solvable using quantitative methods is relevant.
Consider the following search problem. A given system consisting of N
channels with one dynamic signal and one search device (SD), where SD
is moving only through the first𝑀 channels while the signal is moving on
all N channels, 𝑁,𝑀 ≤ 𝑁 , in discrete time period 𝑡 = 0, 1, 2, . . . the sig-
nal and the SD are transitioning from channel to channel independently
from each other according the the Markov model. Assume that probabil-
ities 𝑎𝑖𝑗 , 𝑖, 𝑗 = 1, 𝑁 of signal transition from i -channel to j -channel and
the corresponding probabilities 𝐵𝑖𝑗 , 𝑖, 𝑗 = 1,𝑀 for the SD are time inde-
pendent. At the start moment t = 0 the signal is located in the channel
𝑗𝑜 (𝑗0 ≤ 𝑁) wile the SD is located in channel 𝑗1 (𝑗1 ≤𝑀).
c○ 𝐒𝐡𝐥𝐞𝐩𝐚𝐤𝐨𝐯 𝐋.𝐍., 𝟐𝟎𝟏𝟔
shlepakov@imath.kiev.ua
282 Shlepakov L.N.
The following rule is used to indicate the discovery of the impulse by
the SD: the signal located in the i -channel at the 𝑡1 time period and leav-
ing it at the 𝑡2 time period is considered disovered in the 𝑡 (𝑡1 ≤ 𝑡 ≤ 𝑡2) time
period, if the SD is also located in the i channel, the discovery is consid-
ered valid only if it occurred for the first time since the 𝑡1 time period.
Probability of signal discovery in the t time period is denoted as
𝐾𝑗𝑜,𝑗1(𝑡). The probability of the signal emergence in any of the con-
nection channels (transition in another channel) in the t time frame is
denoted as 𝐿𝑗0(𝑡), 𝐶𝑗𝑜,𝑗1 (𝑡) = 𝐾𝑗0,𝑗1(𝑡)/𝐿𝑗0 (𝑡) denotes the relationship
between. 𝐶𝑗𝑜,𝑗1 (𝑡) value where 𝑡0 is the given discrete time period is
referred to as search effectiveness coefficient, while 𝐶 = lim𝑡→∞ 𝐶𝑗0,𝑗1(𝑡)
value, if such limit exists it is referred to as a stationary effectiveness
coefficient.
Worth noting that these effectiveness coefficients have practical appli-
cations.
𝑡𝑜∑︁
𝑡=0
𝐾𝑗𝑜,𝑗1 (𝑡) ,
𝑡𝑜∑︁
𝑡=0
𝐾𝑗𝑜,𝑗1(𝑡)
The following values need to be determined: effectiveness coefficient
𝐶𝑗𝑜,𝑗1 (𝑡), stationary effectiveness coefficient C, probabilities 𝐵𝑖𝑗 , 𝑖, 𝑗 =
1,𝑀 of SD transition between channels where stationary effectiveness
coefficient is maximum.
𝟏 𝐌𝐚𝐢𝐧 𝐫𝐞𝐥𝐚𝐭𝐢𝐨𝐧𝐬𝐡𝐢𝐩𝐬 𝐟𝐨𝐫 𝐚 𝐧𝐨𝐧-𝐢𝐧fl𝐚𝐭𝐞𝐝 𝐬𝐲𝐬𝐭𝐞𝐦
The signal movement thorough the channel is described by a uniform
Markov chain 𝜉(𝑡) with discrete time and multitude of states {1, 2, . . . , 𝑁}
and a probability matrix of transitioning by 1 step𝐴 =
{︀
𝑎𝑖𝑗 : 𝑖, 𝑗 = 1, 𝑁
}︀
.
The initial state 𝜉 (0) = 𝑗0. 𝜉 (𝑡) = 𝑖 if at time period t the signal is
located in the i channel.
The SD movement thorough the channel is described by a uniform
Markov chain 𝜂(𝑡) with multitude of states {1, 2, . . . ,𝑀} and a probabil-
ity matrix of transitioning by 1 step 𝐵 =
{︀
𝑏𝑖𝑗 : 𝑖, 𝑗 = 1,𝑀
}︀
. The initial
state 𝜂 (0) = 𝑗1. 𝜂(𝑡) = 𝑖 if at time period t the SD is located in the i
channel.
Then
𝐾𝑗0𝑗1 (𝑡) = 𝒫
{︃
𝜉 (𝑡) = 𝑖, 𝜂 (𝑡) = 𝑖, 𝜂 (𝜏) ̸= 𝑖, 𝑡− 𝑢𝜉 (𝑡) < 𝜏 < 𝑡,
𝑖 = 1,𝑀
𝜉(0) = 𝑗0, 𝜂 (0) = 𝑗1
}︃
,
Optimal search strategy of moving object in multichannel system 283
Where 𝑢𝜉 (𝑡) is the underjump of the Markov chain
𝑢𝜉 (𝑡) = 𝑡− sup {𝜏 ≤ 𝑡 : 𝜉 (𝜏) ̸= 𝜉 (𝑡)} .
Let us introduce the notation:
𝑃𝜉 (𝑡, 𝑗, 𝑖) = 𝒫 {𝜉 (𝑡) = 𝑖/𝜉(0) = 𝑗} - probability of signal being located
in the i-th channel at time period t under condition that initially the
signal was located in the j -th channel.
𝑃𝜂 (𝑡, 𝑗, 𝑖) = 𝒫 {𝜂 (𝑡) = 𝑖/𝜂(0) = 𝑗} - probability of SD being located
in the i -th channel at time period t under condition that initially it was
located in the j -th channel.
𝑄𝜂 (𝑡, 𝑗, 𝑖) = 𝒫 {𝜂 (𝑡) = 𝑖, 𝜂 (𝜏) ̸= 𝑖, 0 < 𝜏 < 𝑡 |𝜂 (0) = 𝑗 } - probabil-
ity of SD being first located in the i-th channel at time t under condition
that initially it was located in the j -th channel, 𝑖 ̸= 𝑗, 𝑡 ≥ 1.
𝜉 (𝑡, 𝑗, 𝑖) = 𝒫 {𝜉 (𝑡) = 𝑖, 𝜉 (𝑡− 1) ̸= 𝑖 |𝜉 (0) = 𝑗 } – probability of sig-
nal transitioning in the i-th channel at time period t from any other
channel other than i, under condition that it was initially located in the
j-th channel, 𝑡 > 0.
𝐹𝜉 (𝑛, 𝑖) = 𝒫 {𝜉 (𝑡+ 1) = 𝑖, 𝜉 (𝑡+ 2) = 𝑖, . . . , 𝜉 (𝑡+ 𝑛) = 𝑖/𝜉 (𝑡) = 𝑖} -
probability that the signal stays in the i -th channel during the time period
[𝑡; 𝑡+ 𝑛], under condition that it was located in the i -th channel at time
period t.
The following relations are fair
𝑃𝜉 (𝑡, 𝑗, 𝑖) =
𝑁∑︁
𝑘=1
𝑎𝑗𝑘𝑃𝜉 (𝑡− 1, 𝑘, 𝑖) , 𝑡 ≥ 1, 𝑃𝜉 (𝑜, 𝑗, 𝑖) = 𝛿𝑗𝑖,
𝑃𝜂 (𝑡, 𝑗, 𝑖) =
𝑀∑︁
𝑘=1
𝛽𝑗𝑘𝑃𝜂 (𝑡− 1, 𝑘, 𝑖) , 𝑡 ≥ 1, 𝑃𝜂 (𝑜, 𝑗, 𝑖) = 𝛿𝑗𝑖,
𝑄𝜂 (𝑡, 𝑗, 𝑖) =
∑︁
𝑘 ̸=𝑖
𝛽𝑗𝑘𝑄𝜂 (𝑡− 1, 𝑘, 𝑖) , 𝑡 ≥ 2, 𝑄𝜂 (1, 𝑗, 𝑖) = 𝛽𝑗𝑖, 𝑗 ̸= 𝑖,
𝜉 (𝑡, 𝑗, 𝑖) =
∑︁
𝑘 ̸=𝑖
𝑎𝑘𝑖𝑃𝜉 (𝑡− 1, 𝑗, 𝑘) , 𝑡 ≥ 1,
𝐿𝑗𝑜(𝑡) =
𝑁∑︁
𝑖=1
𝜉 (𝑡, 𝑗0, 𝑖),
where
𝛿𝑗𝑖 =
{︂
1, 𝑤𝑒𝑛 𝑗 = 𝑖;
0, 𝑤𝑒𝑛 𝑗 ̸= 𝑖.
284 Shlepakov L.N.
𝐓𝐡𝐞𝐨𝐫𝐞𝐦 𝟏.𝟐. For probability of signal discovery in time frame t the
following relation is applicable
𝐾𝑗0𝑗1 (𝑡) =
𝑀∑︁
𝑖=1
{︀
𝜉 (𝑡, 𝑗𝑜, 𝑖)𝑃𝜂 (𝑡, 𝑗1, 𝑖) + 𝛿𝑗0𝑖𝐹𝜉 (𝑡, 𝑖)𝑄𝜂 (𝑡, 𝑗1, 𝑖)+
𝑡−1∑︁
𝑛=1
𝜉 (𝑡− 𝑛, 𝑗0, 𝑖)𝐹𝜉 (𝑛, 𝑖)
∑︁
𝑘 ̸=𝑖
𝑃𝜂 (𝑡− 𝑛, 𝑗, 𝑘)𝑄𝜂 (𝑛, 𝑘, 𝑖)
⎫⎬⎭ , 𝑡 > 0 (1)
Proof. The proof is based on the total probability formula, according to
which, the probability of event A out of total pool of events 𝐸1, . . . , 𝐸𝑛,
(𝐸𝑖 ̸= ∅, 𝑖 = 1, 𝑛) is
𝒫 (𝐴) =
𝑛∑︁
𝑖=1
𝒫 (𝐴 | 𝐸𝑖) · 𝒫(𝐸𝑖)
While constructing the relationships, it must be taken into account
that the signal and SD transitions are independent.
Consider the initial fixes conditions 𝜉 (0) = 𝑗0, 𝜂 (0) = 𝐽1.
Discovery of the signal in the I channel in the t time frame can occur:
1. In case if the signal transitioned into the i -th channel in the t time
period from any other channel other than i while the SD was located
in the i -th channel at the t time period (probability of the event
𝜉(𝑡, 𝑗𝑜, 𝑖)𝑃𝜂(𝑡, 𝑗1, 𝑖));
2. In case the signal transitioned into the i -th channel in time period
𝑡 − 𝑛 (1 ≤ 𝑛 ≤ 𝑡) and stayed there until time period t, inclusive,
while the SD, for the first time starting from the 𝑡− 𝑛 time period
transitioned into the I channel in the t time period.
If n = t the probability of the second event is
𝛿𝑗0𝑗1𝐹𝜉(𝑡, 𝑖)𝑄𝜂(𝑡, 𝑖1, 𝑖)
If 1 ≤ 𝑛 ≤ 𝑡−1, then the second event can occur with the probability
𝑄𝜂(𝑛, 𝑘, 𝑖)𝜉(𝑡−𝑛, 𝑗0, 𝑖)𝐹𝜉(𝑛, 𝑖) under the condition that at the moment
𝑡 − 𝑛 the SD was located in the k channel. The distribution of the
channel number, in which the SD was located at the 𝑡 − 𝑛 time period,
𝑃𝜂(𝑡− 𝑛, 𝑗1, 𝑘) using the full probability formula for a fixed n, 1 ≤ 𝑛 ≤
Optimal search strategy of moving object in multichannel system 285
𝑡− 1 and then adding upp the probabilities for all n, 1 ≤ 𝑛 ≤ 𝑡 will yield
the probability of discovering the signal in the i channel in the second
scenario.
Summing the probabilities of non interfering events, corresponding
to the two cases for all numbers of i channels which are used by the
transitioning SD, 1 ≤ 𝑖 ≤ 𝑚, will yield the the relationship (1)
𝐓𝐡𝐞𝐨𝐫𝐞𝐦 𝟏.𝟑. If 𝜉 (𝑡) , 𝜂 (𝑡) are irreducible Markov chains with stan-
dard distribution
{︀
𝑃𝜉 (𝑖) , 𝑖 = 1,𝑀
}︀
,
{︀
𝑃𝜂 (𝑖) , 𝑖 = 1, 𝑁
}︀
respectively, then
a limit exists
𝐾 = lim
𝑡−→∞
𝐾𝑗0𝑗1 (𝑡) =
=
𝑀∑︁
𝑖=1
𝜉(𝑖)
⎡⎣𝑃𝜂 (𝑖) + ∞∑︁
𝑛=1
𝐹𝜉(𝑛, 𝑖)
∑︁
𝑘 ̸=𝑖
𝑃𝜂(𝑘) ·𝑄𝜂(𝑛, 𝑘, 𝑖)
⎤⎦ (2)
independent of initial states of 𝑗0, 𝑗1, where
𝑃𝜉 (𝑖) = lim
𝑡→∞
𝑃𝜉 (𝑡, 𝑗0, 𝑖) ,
𝑃𝜂 (𝑖) = lim
𝑡→∞
𝑃𝜂 (𝑡, 𝑗1, 𝑖) ,
𝜉 (𝑖) = lim
𝑡→∞
(𝑡, 𝑗0, 𝑖) .
Proof. The proof is derived from theorem 1 and ergodic quality of stan-
dard distribution. While at the same time relationships [4, p, 8.30] are
fair
𝑃𝜉 (𝑖) =
𝑁∑︁
𝑗=1
𝛼𝑗𝑖𝑃𝜉 (𝑗) ,
𝑃𝜂 (𝑖) =
𝑀∑︁
𝑗=1
𝛽𝑗𝑖𝑃𝜂 (𝑗) ,
𝜉 (𝑖) =
∑︁
𝑗 ̸=1
𝛼𝑗𝑖𝑃𝜉 (𝑗) .
(3)
𝐂𝐨𝐫𝐨𝐥𝐥𝐚𝐫𝐲 𝟏.𝟏. If theorem 2 condition is fulfilled, the static coefficient
of effectiveness equals
𝐶 =
𝐾
𝐿
, (4)
286 Shlepakov L.N.
where
𝐿 = lim
𝑡→∞
𝐿𝑗0 (𝑡) =
𝑁∑︁
𝑖=1
𝜉 (𝑖) .
𝟏.𝟏 𝐂𝐨𝐧𝐬𝐭𝐫𝐮𝐜𝐭𝐢𝐨𝐧 𝐨𝐟 𝐞𝐧𝐥𝐚𝐫𝐠𝐞𝐝 𝐬𝐲𝐬𝐭𝐞𝐦𝐬
For the purpose of simplification of relationship (2) for large M a phase
enlargement method is used [5, 6]. As en example, a random channel is
fixed, for example c with number i, where the SD can be located. Markov
chain 𝜂(𝑡) multiple states {1, . . . ,𝑀} are broken into two classes {𝑖} and
𝑖 = {1, 2, . . . , 𝑖− 1, 𝑖+ 1,𝑀}.In this case the first class consists only from
I states, and the second one consists from other than I states.
𝐋𝐞𝐦𝐦𝐚 𝟏.𝟏. If the following relationships are fulfilled
max
𝑗 ̸=𝑖
𝛽𝑗𝑖/min
𝑗 ̸=𝑖
(1− 𝛽𝑗𝑖) ≪ 1, 𝛽𝑛𝑘 ̸= 0, 𝑛, 𝑘 = 1,𝑀, (5)
then the time of Markov chain 𝜂(𝑡) in multidute of states 𝑖 is closely
describes by a geometric law of distribution with parameter 1− 𝑦𝑖, where
𝑦𝑖 =
∑︁
𝑗 ̸=𝑖
𝑃𝜂 (𝑗)𝛽𝑗𝑖/
∑︁
𝑗 ̸=𝑖
𝑃𝜂 (𝑗) . (6)
Proof. If conditions (5) are fulfilled, then transition into the i state is
a rare condition, the process of transitioning amongst a multitude of 𝑖
states until departure from it can be considered established, which in
turn, on empirical level, justifies the use the phase enlargement method
[6].
Class 𝑖 is enlarged in a single state, which is also called 𝑖. The func-
tioning of the enlarged system according to the enlargement theorem is
closely described by the stationary Markov chain 𝜂(𝑖) with two possible
states 𝑖, 𝑖 and probability matrix of one step transitioning
Λ(𝑖) =
(︂
𝛽𝑖𝑖 1− 𝛽𝑖𝑖
𝑦𝑖 1− 𝑦𝑖
)︂
,
Where
𝑦𝑖 =
∑︁
𝑗 ̸=𝑖
𝑃𝜂 (𝑗)𝛽𝑗𝑖/
∑︁
𝑗 ̸=𝑖
𝑃𝜂 (𝑗) .
Hence, the lemma statement is proved.
Optimal search strategy of moving object in multichannel system 287
At the same time, the definition of “more less” and “closely described”
are discussed in [7]. The general limit theorems, on which the method
of phase enlargement in relation to Markov and half-Markov processes is
based upon, is being proved in [5].
𝟏.𝟐 𝐃𝐞fi𝐧𝐢𝐧𝐠 𝐭𝐡𝐞 𝐭𝐚𝐬𝐤 𝐦𝐚𝐭𝐡𝐞𝐦𝐚𝐭𝐢𝐜𝐚𝐥 𝐩𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠
𝐓𝐡𝐞𝐨𝐫𝐞𝐦 𝟏.𝟒. Under condition if geometric distribution of time spent
by SD in state 𝑖, 𝑖 = 1, 𝑀 , the problem of optimizing the stationary
coefficient of search effectiveness boils down to a non-linear programming
problem in relation to variables 𝑥𝑖, 𝑦𝑖, 𝑖 = 1,𝑀,
𝐶 =
1
𝐿
𝑀∑︁
𝑖=1
𝜉 (𝑖)𝑅 (𝑖) → max (7)
𝑀∑︁
𝑖=1
𝑦𝑖
𝑥𝑖 + 𝑦𝑖
= 1, (8)
0 ≤ 𝑥𝑖 ≤ 1, 0 ≤ 𝑦𝑖 ≤ 1, 𝑖 = 1,𝑀, (9)
𝑥𝑖𝑦𝑖
𝑥𝑖 + 𝑦𝑖
≤
∑︁
𝑗 ̸=𝑖
𝑥𝑗𝑦𝑗
𝑥𝑗 + 𝑦𝑗
, (10)
where
𝑅 (𝑖) =
⎧⎨⎩
𝑦𝑖
𝑥𝑖+𝑦𝑖
+ 𝑥𝑖𝑦𝑖
𝑥𝑖+𝑦𝑖
1
𝑑𝑖+𝑥𝑖
, 𝑖𝑓 𝑎𝑖𝑖 ̸= 0;
𝑦𝑖
𝑥𝑖+𝑦𝑖
, 𝑖𝑓 𝑎𝑖𝑖 = 0, 𝑦𝑖 ̸= 0;
0, 𝑖𝑓 𝑎𝑖𝑖 ̸= 0, 𝑦𝑖 = 0;
𝑑𝑖=
1
𝑎𝑖𝑖
− 1,
for probabilities 𝛽𝑖𝑗 transitions of SD from channel to channel for
optimal search strategy is calculated:
𝛽𝑖𝑖 = 𝑥*𝑖 , 𝑖 = 1, 𝑀
when 𝑖 ̸= 𝑗, 𝛽𝑖𝑗 can always be found as a solution to the system of
linear equations ⎧⎪⎪⎪⎨⎪⎪⎪⎩
𝑐
𝑦*𝑖 𝑥
*
𝑖
𝑦*𝑖 + 𝑥*𝑖
=
∑︁
𝑗 ̸=𝑖
𝑦*𝑗
𝑦*𝑗 + 𝑥*𝑗
𝑉 · 𝛽𝑗𝑖
𝑥*𝑖 =
∑︁
𝑗 ̸=𝑖
𝛽𝑖𝑗 ,
(11)
288 Shlepakov L.N.
where 𝑥*𝑖 , 𝑦
*
𝑖 , 𝑖 = 1, 𝑀 in turn are the solution to the problem of math-
ermatical programming (7)-(10).
Proof. Similar to proof of theorem 2, using Markov chain 𝜂(𝑖)(𝑡) instead
of Markov chain 𝜂(𝑡)for every fixed 𝑖, 𝑖 = 1, 𝑀 yields
𝐾 =
𝑀∑︁
𝑖=1
𝜉 (𝑖) [𝑃𝜂(𝑖) (𝑖) + 𝑃𝜂(𝑖)
(︀
𝑖
)︀ ∞∑︁
𝑛=1
𝐹𝜉(𝑛, 𝑖)𝑄𝜂(𝑖)(𝑛, 𝑖, 𝑖)], (12)
for reaching the probability of first encounter by Markov chain 𝜂(𝑖) (𝑡) of
i state the following relation
𝑄𝜂(𝑖)
(︀
𝑛, 𝑖, 𝑖
)︀
= 𝑦𝑖(1− 𝑦𝑖)
𝑛−1
(13)
Implemented denomination
𝑥𝑖 = 1− 𝛽𝑖𝑖
System of equations for stationary distribution 𝑃𝜂(𝑖) for Markov chain
𝜂(𝑖)(𝑡) is the following⎧⎪⎨⎪⎩
𝑐𝑃𝜂(𝑖) (𝑖) = 𝑃𝜂(𝑖) (𝑖) (1− 𝑥𝑖) + 𝑃𝜂(𝑖)(𝑖)𝑦𝑖
𝑃𝜂(𝑖) (𝑖) = 𝑃𝜂(𝑖) (𝑖)𝑥𝑖 + 𝑃𝜂(𝑖)(𝑖)(1− 𝑦𝑖)
𝑃𝜂(𝑖) (𝑖) + 𝑃𝜂(𝑖)
(︀
𝑖
)︀
= 1
(14)
Solving system (14) yields
𝑃𝜂(𝑖) (𝑖) = 𝑦𝑖/(𝑥𝑖 + 𝑦𝑖) (15)
From relations (4), (12), (15) taking into account denotations (13),(6) it
is possible to obtain the expression for effectiveness coefficient C, shown
previously in the left part of (7)
As SD is located in one of the M first channels
𝑀∑︁
𝑖=1
𝑃𝜂(𝑖) (𝑖) = 1
From this follows (15) and the limit (8)
Limit (9) – is the consequence of standard demands towards the prob-
ability of transition.
Optimal search strategy of moving object in multichannel system 289
System of linear equations (11) is the consequence of relations (6) with
(15), (8) taken into account and is denoted (13). It serves to determine
the probabilities 𝛽𝑖𝑗 , 𝑖 ̸= 𝑗, of SD transitions from channel to channel
using the given parameters 𝑥*𝑖 , 𝑦
*
𝑖 , 𝑖 = 1,𝑀 . But sustem (11) not always
yields a non negative solution.
Limitation (10) – is a needed and valuable condition of existence of
non-negative solution to the 𝛽𝑖𝑗 , 𝑖 ̸= 𝑗 system of linear equations (11).
Such solution is not singular [8, p.4] and must be chosen with conditions
from (5) taken into account for 𝑖 = 1,𝑀 .
Note, if the solution to the problems of mathematical programming
(7)-(10) some of the parameters 𝑦*𝑖 do not exist, then the probability of
the SD to be located in these channels is zero and as follow, for opti-
mal search strategy, the SD foes not transition into channels with these
numbers.
𝟏.𝟑 𝐂𝐚𝐬𝐞 𝐨𝐟 𝐦𝐮𝐥𝐭𝐢𝐩𝐥𝐞 𝐜𝐡𝐚𝐧𝐧𝐞𝐥𝐬 𝐰𝐢𝐭𝐡 𝐬𝐚𝐦𝐞 𝐩𝐫𝐨𝐛𝐚𝐛𝐢𝐥𝐢𝐭𝐲 𝐜𝐡𝐚𝐫𝐚𝐜-
𝐭𝐞𝐫𝐢𝐬𝐭𝐢𝐜𝐬 𝐢𝐧 𝐭𝐡𝐞 𝐬𝐚𝐦𝐞 𝐬𝐲𝐬𝐭𝐞𝐦 𝐨𝐟 𝐜𝐡𝐚𝐧𝐧𝐞𝐥𝐬.
Consider a real important case, of a multi channels system with channel
groups of the same type, meaning that the Markov chain 𝜉(𝑡)has the same
probability component types related to same type channels. In this case
if channels I and j are same type channels then 𝑎𝑖𝑘 = 𝑎𝑗𝑘,
𝑎𝑘𝑖 = 𝑎𝑘𝑗 , 𝑘 = 1,𝑀.
𝐓𝐡𝐞𝐨𝐫𝐞𝐦 𝟏.𝟓. If the first k channels of 1 < 𝑘 ≤𝑀 are of the same type,
then
1. for 𝑎11 ̸= 0 the solution to the problem of mathematical program-
ming (7)-(10) is showm t=by the relation
𝑦*𝑖 = 𝑦*𝑗 , 𝑖, 𝑗 = 1, 𝑘; 𝑥*𝑖 = 1, if 𝑦*𝑖 ̸= 0, 𝑖 = 1, 𝑘; (16)
or for optimal search strategy the stationary probabilities of SD be-
ing located is identical channels are equal, 𝑃𝜂(𝑖) (𝑖) = 𝑃𝜂(𝑖) (𝑗) , 𝑖, 𝑗 =
1, 𝑘 (if 𝑃𝜂 (𝑖) ̸= 0);
2. for 𝑎11 = 0 the optimal search strategy may be chosen in such a
manner, as to satisfy the relation (16).
290 Shlepakov L.N.
Proof. Let 𝑥*𝑖 , 𝑦
*
𝑖 , 𝑖 = 1,𝑀 be the solution to the problem of mathemat-
ical programing (7)-(10).
Consider the case 𝑎11 ̸= 0
Study the auxiliary problem of mathematical programming related to
variables 𝑥𝑖, 𝑃𝑖, where 𝑃𝑖 = 𝑦𝑖/(𝑥𝑖 + 𝑦𝑖) , 𝑖 = 1, 𝑘, while fixing the
remaining M-k variables in (7)-(10) in the following way: 𝑥𝑖 = 𝑥*𝑖 , 𝑃𝑖 =
𝑦*𝑖 /(𝑥
*
𝑖 + 𝑦*𝑖 ), 𝑖 = 𝑘 + 1,𝑀 ,
𝐶 ′ =
𝑘∑︁
𝑖=1
𝑥𝑖𝑃𝑖 (1− 𝑃𝑖)
𝑑𝑖 (1− 𝑃𝑖) + 𝑥𝑖𝑃𝑖
→ 𝑚𝑎𝑥 (17)
𝑘∑︁
𝑖=1
𝑃𝑖 = 𝐷, (18)
0 ≤ 𝑥𝑖 ≤ 1, 𝑃𝑖 ≥ 0, 𝑥𝑖 ≤
1− 𝑃𝑖
𝑃𝑖
(19)
𝑥𝑖𝑃𝑖 ≤
∑︁
𝑖 ̸=𝑗
𝑥𝑗𝑃𝑗 + 𝑆, (20)
Where
𝐷 = 1−
𝑀∑︁
𝑖=𝑘+1
𝑦*𝑖
𝑥*𝑖 + 𝑦*𝑖
, 𝑆 =
𝑀∑︁
𝑖=𝑘+1
𝑥*𝑖 𝑦
*
𝑖
𝑥*𝑖 + 𝑦*𝑖
Expression 𝑓 (𝑥𝑖, 𝑃𝑖) = 𝑥𝑖𝑃𝑖(1−𝑃𝑖)
𝑑𝑖(1−𝑃𝑖)+𝑥𝑖𝑃𝑖
under the sum sign in (17) with
fixed 𝑃𝑖 > 0 is an increasing fraction-linear function for 𝑥𝑖, and 𝑓 (𝑥𝑖, 0) =
0. Hence, taking into account the limitation 0 ≤ 𝑥𝑖 ≤ 1, with fixed 𝑃1,
𝑖 = 1, 𝑘, 𝐶 ′ reahces maximum with 𝑥𝑖 = 1, 𝑖 = 1, 𝑘.
On the other hand, its not hard to verify that 𝜕2(1,𝑃 )
𝜕𝑃 2 < 0, 𝑃 >
0. Therefore 𝑓(1, 𝑃 ) is strictly a convex upwardly function from P and
therefore the following relation from [9] holds true
𝑓
(︃
1,
𝑘∑︁
𝑖=1
𝑃𝑖/𝑘
)︃
≥ 1
𝑘
𝑘∑︁
𝑖=1
𝑓 (1, 𝑃𝑖) , 𝑃𝑖 > 0, 𝑖 = 1, 𝑘
the equality is achieved only in case 𝑃𝑖 = 𝑃𝑗 , 𝑖, 𝑗 = 1, 𝑘 i.e. tanking into
consideration the limitation (18), for 𝑃𝑖 = 𝐷/𝑘, 𝑖 = 1, 𝑘.
Note that as k>1, then the discovered 𝑃𝑖 < 1/2, 𝑖 = 1, 𝑘 and in-
equalities 1 ≤ 1−𝑃𝑖
𝑃𝑖
and (20) are solved automatically. Hence, solution to
(17)-(20) and therefore (7)-(10) in this case satisfy (16)
Optimal search strategy of moving object in multichannel system 291
Consider the case 𝑎11 = 0, 𝐷 > 0. Given:
𝐾 = 𝜉(1)
𝑘∑︁
𝑖=1
𝑦𝑖
𝑥𝑖 + 𝑦𝑖
+
𝑀∑︁
𝑖=𝑘+1
𝜉 (𝑖)𝑅 (𝑖) .
Then the values 𝑥**𝑖 , 𝑦
**
𝑖 , 𝑖 = 1,𝑀are related in the following way
𝑥**𝑖 = 1, 𝑖 = 1, 𝑘; 𝑥** = 𝑥*, 𝑖 = 𝑘 + 1,𝑀 ; 𝑦**𝑖 = 𝐷/𝑘
1−𝐷/𝑘 , 𝑖 =
1, 𝑘; 𝑦**𝑖 = 𝑦*𝑖 , 𝑖 = 𝑘 + 1,𝑀 and also are the solution to the problems of
mathematical programming (7)-(10).
𝐌𝐨𝐝𝐞𝐥 𝐞𝐱𝐚𝐦𝐩𝐥𝐞. Consider a case 𝑀 = 𝑁 = 2, 𝑎11 ̸= 0, 𝑎22 = 0.
Then 𝜉 (1) = 𝜉 (2) , 𝑥1 = 𝑦2, 𝑦1 = 𝑥2. Denote 𝑦 = 𝑦1, 𝑃 = 𝑦2
𝑥2+𝑦2
,
after transformation a simple problem os mathematical prograining is
obtaines, equivalent to problems (7)-(10).{︃
𝑃𝑦
𝑑1+𝑦
→ 𝑚𝑎𝑥
0 ≤ 𝑦 ≤ 1, 0 ≤ 𝑃 ≤ 1
1+𝑦
which has the solution
𝑦* =
{︂ √
𝑑1, 𝑖𝑓 0 < 𝑑1 ≤ 1,
1, 𝑖𝑓 𝑑1 > 1,
, 𝑃 * =
1
1 + 𝑦*
Therefore for optimal search strategy:
𝛽22 =
{︃
1−
√︁
1
𝑎11
− 1, 𝑤𝑒𝑛 𝑎11 ≥ 1
2 ;
0, 𝑤𝑒𝑛 𝑎11 <
1
2 .
There exists no analytical solution for the problem for 𝑁 > 2. For quan-
titative solution in case the quantity of channels is no less ten two an
algorithm was developed and a corresponding program.
[1] Abchuk V. A., Suzdal V. G. Search of objects – Moscow. :Sov. Radio,
1977. – p. 275
[2] Hellman O., Intoduction to the optimal search theory –Moscow.: Nauka
1985. – p. 248
[3] Tonkonogov U. M., Search for moving signal in a multichannel system –
Tomsk.: Tomsk university publishing 1989. – p. 196
[4] Koroluk V. S., Portneko N. I., Skorohod A.V., Turbin A.F., Reference
book on the theory of probability and mathematical statistics – Moscow.:
Nauka, 1985. – p. 640
292 Shlepakov L.N.
[5] Koroluk V. S., Turbin A.F., Mathematical basics of phase enlargement of
complex systems, - Kiev.: Naukova Dumka, 1978 – p. 219
[6] Koroluk V. S., Turbin A.F., Phase enlargement of complex systems, -
Kiev.: Vishya Shkola, 1978. – p. 109
[7] Koroluk V. S., Turbin A.F., Half-Markov processes and their applications.
– Kev.:Naukova Dumka, 1976. – p. 184
[8] Shlepakov L. N., Vovkodav N. G. Selective search for signal in multichan-
nel connection lines, - Kiev, 1995. – p. 84 (Reprinted / NAS of Ukraine.
Mathematics; 95.2)
[9] Lyashenko I. N., Linear and Nonlinear programming, Kiev.: Visha Shkola,
1975. – p. 372.
[10] Shlepakov L. N., Vovkodav N. G. Optimal search for moving objects in
discrete area. – Kiev: Works of institute of mathematics of Ukraine, 2008.
v.79 – p. 144.
1. Луковський І.О., Гаврилюк І.О., Василик В.Б., Ситник Д.О.
2. Біленко В. І., Божонок К. В., Дзядик С. Ю., Стеля О. Б.
Інтегро–апроксимаційний алгоритм
Вступ
Постановка задачі
Алгоритм
Похибка алгоритму
Застосування a–методу для алгебраїчно–нелінійних рівнянь гіперболічного типу
Задача Дирихле для алгебраїчно–нелінійних рівнянь еліптичного типу на прямокутнику
Наближений розв'язок початкової задачі для алгебраїчно–нелінійних рівнянь параболічного типу на прямокутнику
Сплайн–алгоритм
Монотонна схема для рівняння конвекції–дифузії
Висновки
3. Василик В.Б., Макаров В.Л., Ситник Д.О.
Вступ
Регуляризація та явне зображення розв'язку
Вибір контуру інтегрування
Чисельний метод
4. Веселовська Г.М.
5. Грушковская В.В.
Введение
Построение модельной системы
Условия устойчивости
Оценка скорости убывания решений
Пример: оценка скорости затухания колебаний маятниковой системы с частичной диссипацией
Выводы
6. Дзюбенко Г.А.
Вступ
Допоміжні факти
Доведення Теореми ??
7. Діденко Ю.Ф., Денисенко В.І.
8. Елишевич М.А.
Постановка задачи
Полученный результат
Пример
9. Константинов А.В., Лимарченко О.С., Кинебас К.В., Паранькина О.Ю.
Введение
Объект исследования и математическая модель
Результаты вычислительных экспериментов
Выводы
10. Мазко О.Г., Кусій С.М.
Вступ
Допоміжні твердження
Лінійні системи з керованими і спостережуваними виходами
Статичний регулятор по вимірюваному виходу
Динамічний регулятор
Алгоритм побудови динамічного регулятора
Приклад. Гасіння коливань лінійного осцилятора.
Висновок
11. Працьовитий М. В., Маслова Ю. П.
Вступ
Функція Радемахера і ряди Уолша
Узагальнення функцій Радемахера
Узагальнення функцій Уолша
12. Працьовитий М.В., Чуйков А.С.
Вступ
Оператори лівостороннього та правостороннього зсуву елементів ланцюгового дробу
Інші функції, пов'язані з оператором T(x)
13. Новицький В.В., Зінчук М.О., Коломійчук О.П., Тетерятник О.В.
Вступ
Оптимальне керування лінійними неперервними майже консервативними системами
Оптимальне керування лінійними дискретними майже консервативними системами
14. Осауленко Р. Ю.
Вступ
Перетворення, які зберігають хвости Qs–зображення чисел
Група перетворень, які зберігають частоти цифр Qs–зображення числа
Приклад функції, яка зберігає частоти, але не зберігає хвости зображення Qs-ірраціональних чисел
15. Слинько В.І., Кравчук С.В.
Постановка задачі.
Основний результат.
Умови стійкості
16. Солодун А. В.
Постановка задачи
Численные результаты
17. Ситник Д.О.
Вступ
Sinc–апроксимація
Sinc-апроксимація функції за її значеннями поза інтерполяційною сіткою
18. Сосницький С.П.
Вступ
Про рівняння збуреного руху в околі стаціонарних лагранжевих трикутників
Теорема про орбітальну нестійкість лагранжевих стаціонарних рухів у задачі трьох тіл
Висновок
19. Сосницький С.П.
Вступ
Про достатні умови відсутності осцилюючих симетричних рухів
20. Чернецька Л.О.
21. Timokha A.N.
Statement
Asymptotic steady-state solutions of (??)–(??)
The reciprocating excitation type
The axisymmetric elliptic excitation type
The oblique elliptic excitation type
Conclusions
22. Shlepakov L.N.
Main relationships for a non-inflated system
Construction of enlarged systems
Defining the task mathematical programming
Case of multiple channels with same probability characteristics in the same system of channels.
23. Shidlich A.L.
Approximative characteristics
Main results
Order estimates for some functionals and their applications
Proof of Theorems ?? and ??.
24. Луковський І.О., Стороженко В.О.
25. Луковський І.О., Пустовойтов М.О.
|
| id | oai:trim.imath.kiev.ua:article-61 |
| institution | Transactions of Institute of Mathematics of NAS of Ukraine |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-08-04T01:01:50Z |
| publishDate | 2017 |
| publisher | Інститут математики НАН України |
| record_format | ojs |
| resource_txt_mv | trimimathkievua/f1/526cb7de70005a8209774856fe8325f1.pdf |
| spelling | oai:trim.imath.kiev.ua:article-612018-02-13T11:57:10Z Optimal search strategy of moving object in multichannel system Стратегия оптимального поиска подвижного обьекта в мультиканальной системе Стратегія оптимального пошуку рухомого об’єкту в мультіканальній системі Shlepakov, L. N. Шлепаков, Л. Н. Шлєпаков, Л. М. The analysis of signal search problem in a multi-channel communication system with one search device is carried out. An optimal strategy for moving the search appliance in a multi-channel system is constructed and a corresponding estimate of the search efficiency is obtained. &nbsp; Проведён анализ задачи поиска сигнала в многоканальной системе связи с одним поисковым устройством. Построена оптимальная стратегия перемещения поискового устройства в многоканальной системе и получено соответствующая оценка эффективности поиска. Проведено аналiз задачi пошуку сигналу в багатоканальнiй системi зв’язку з одним пошуковим пристроєм. Побудована оптимальна стратегiя перемiщення пошукового пристрою в багатоканальнiй системi i отримано вiдповiдну оцiнку ефективностi пошуку. Інститут математики НАН України 2017-12-22 Article Article application/pdf https://trim.imath.kiev.ua/index.php/trim/article/view/61 Transactions of Institute of Mathematics, the NAS of Ukraine; Vol. 13 No. 3 (2016): Mathematical problems of mechanics and computational mathematics; 281-292 Сборник Трудов Института математики НАН Украины; Том 13 № 3 (2016): Математичні проблеми механіки та обчислювальної математики; 281-292 Збірник Праць Інституту математики НАН України; Том 13 № 3 (2016): Математичні проблеми механіки та обчислювальної математики; 281-292 3083-7529 1815-2910 en https://trim.imath.kiev.ua/index.php/trim/article/view/61/56 Авторське право (c) 2016 Праці Інституту математики НАН України |
| spellingShingle | Shlepakov, L. N. Шлепаков, Л. Н. Шлєпаков, Л. М. Optimal search strategy of moving object in multichannel system |
| title | Optimal search strategy of moving object in multichannel system |
| title_alt | Стратегия оптимального поиска подвижного обьекта в мультиканальной системе Стратегія оптимального пошуку рухомого об’єкту в мультіканальній системі |
| title_full | Optimal search strategy of moving object in multichannel system |
| title_fullStr | Optimal search strategy of moving object in multichannel system |
| title_full_unstemmed | Optimal search strategy of moving object in multichannel system |
| title_short | Optimal search strategy of moving object in multichannel system |
| title_sort | optimal search strategy of moving object in multichannel system |
| url | https://trim.imath.kiev.ua/index.php/trim/article/view/61 |
| work_keys_str_mv | AT shlepakovln optimalsearchstrategyofmovingobjectinmultichannelsystem AT šlepakovln optimalsearchstrategyofmovingobjectinmultichannelsystem AT šlêpakovlm optimalsearchstrategyofmovingobjectinmultichannelsystem AT shlepakovln strategiâoptimalʹnogopoiskapodvižnogoobʹektavmulʹtikanalʹnojsisteme AT šlepakovln strategiâoptimalʹnogopoiskapodvižnogoobʹektavmulʹtikanalʹnojsisteme AT šlêpakovlm strategiâoptimalʹnogopoiskapodvižnogoobʹektavmulʹtikanalʹnojsisteme AT shlepakovln strategíâoptimalʹnogopošukuruhomogoobêktuvmulʹtíkanalʹníjsistemí AT šlepakovln strategíâoptimalʹnogopošukuruhomogoobêktuvmulʹtíkanalʹníjsistemí AT šlêpakovlm strategíâoptimalʹnogopošukuruhomogoobêktuvmulʹtíkanalʹníjsistemí |