=Paper=
{{Paper
|id=Vol-2642/paper9
|storemode=property
|title=Search control at routes with risk
|pdfUrl=https://ceur-ws.org/Vol-2642/paper9.pdf
|volume=Vol-2642
|authors=Boris K. Nartov,,Andrey N. Poluyanov
}}
==Search control at routes with risk==
https://ceur-ws.org/Vol-2642/paper9.pdf
Search control at routes with risk
Boris K. Nartov Andrey N. Poluyanov
Sobolev Institute of Mathematics Sobolev Institute of Mathematics
SB RAS, Novosibirsk, Russia SB RAS, Novosibirsk, Russia
nartov@ofim.oscsbras.ru andrey.poluyanov@gmail.com
Abstract
The article defines the main tasks of optimal search control for targets
with the given coordinates distributions on routes with the specified
distributions of the risk of the search units loss. The tasks have been
investigated under maximized quality criteria: “the target detection
probability”and “the difference between the probabilities of target de-
tection and of a search unit’s loss”. Calculation formulae for the results
of non-optimized route scanning are obtained, as well as the tasks of
optimal interruption of the search in real time search planning and
control are formalized. Search tasks with the real time adjustment
of the initial target coordinate distributions and risk distributions are
discussed. Imitation experiments verifying the analytical results of the
work are described.
1 Introduction
The tasks of optimal search for stationary objects on the plane and in space have been intensively studied since
the 40s of the last century. The classical works of B. Kupman and V. I. Arkin should be mentioned as well as
the monograph afterwards published by O. Hellman [Hel80]. Contemporary papers on search theory, as a rule,
formulate and formalize the tasks of controlling dimensional search units (SU), which cover the corresponding
bands or tubes in the search area (see, for example, [Yan10]). The tasks of this type, including those with the risk
of controlled SU loss, are thoroughly investigated in our works [Nar15],[Mur18]. However, there are no known
works that more or less fully investigate the problems of searching for point targets using point SUs on the given
routes with the specified target coordinates distributions and risks of SUs loss. By risks we mean the given
coordinate distributions of point registering units (RU), at coincidence with any of those the corresponding SU
and RU being removed from the task. This article formulates and partially formalizes the basic search strategies
in the simplest task of this type with one goal, one SU and one RU. Calculation formulae for the results of
non-optimized route scanning are obtained and partially verified, as well as the tasks of optimal interruption of
the search in real time search planning and control are formalized.
The following main notations are used further:
(0, L) is a segmented specified search route;
∫L
f (x) is the target coordinates distribution on the route, f (x)dx ≡ 1;
0
Copyright ⃝
c by the paper’s authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
In: Sergei S. Goncharov, Yuri G. Evtushenko (eds.): Proceedings of the Workshop on Applied Mathematics and Fundamental
Computer Science 2020 , Omsk, Russia, 30-04-2020, published at http://ceur-ws.org
1
∫L
r(x) is the RU coordinates distribution on the route, r(x)dx ≡ 1;
0
Ji,i = 1, n, are control quality functionals.
2 Test case
Verifying imitation experiments (see below) were carried out for the test case with linearly decreasing and linearly
increasing distribution of the target and RU coordinates respectively. Figure 1 shows the route sampling used
and the probabilities of the objects’ presence at the points, given to the random coordinate generator.
Figure 1: Test case. Target and RU coordinates distribution.
Figure 2 shows an example of generating random target and RU coordinates for a hundred consecutive route
passes.
Figure 2: Test case. Target and RU coordinates generation.
3 Single-criterion search
Route (0, L) scanning before the target detection or the SU loss (if the target is detected, the scanning continues).
The probability of the target detection in this control strategy is:
2
∫L ∫x
J1 = (1− r(s)ds)f (x)dx, (1)
0 0
where the first multiplier of the sub-integral function describes the probability of the search unit reaching
coordinate x.
When substituting in (1) explicit forms f (x), r(x) of the test case, J1 = 5/6 = 0.83(3).
In imitation experiments (see Figure 3, Figure 4) at 106 passes, J1 = 0.834. In this case, not elementary formula
(1), obviously, was verified, but the accuracy of the test case and the imitation experiment. The discrepancy
between the theoretical and experimental values seems to be mainly explained not by the small number of route
passes (106 ), but by the roughness of its sampling (20 points).
Note to Figure 3, Figure 4: Abscissae of J1 values are assigned right search boundaries, and mathematical
expectations of the SU loss coordinates in all cases are less than the corresponding abscissae.
Figure 3: Experimental values of J1 at 102 passes.
Figure 4: Experimental values of J1 at 106 passes.
3
4 Bi-criteria search tasks
In contrast to the single-criterion task, the maximized quality criterion in this group of tasks is the difference
between the target detection probability and the SU loss probability.
4.1 Bi-criteria route scanning
Route (0, L) scanning before the target detection or the SU loss (if the target is detected, the scanning continues).
The difference between the target detection probability and the SU loss probability in this control strategy is:
∫L ∫x ∫L
J2 = (1− r(s)ds)f (x)dx − r(x)dx, (2)
0 0 0
which is a trivial modification of (1), since the second summand in (2) describes the full probability of the SU
loss (see Figure 5, Figure 6), i.e. J2 = J1 − 1. When explicit forms f(x), r(x) of the test case are substituted to
(2)
J2 = 56 − 1 = −0.16(6).
In imitation experiment at 106 passes
J2 = −0.166.
Figure 5: Modelling the SU loss at 102 passes.
4.2 Assigning the optimal SU end coordinate for bi-criteria route scanning
The above formalized strategy (2) generates the task of assigning the optimal final scanning coordinate l∗ ≤ L
that maximizes the difference in probabilities of the target detection and the SU loss:
J2 (l∗ ) = max J2 (l), (3)
l∈(0,L)
J2 (l∗ ) ≥ J2 .
Solving task (3) for explicit forms f (x), r(x) of the test case provides
J2 (l∗ ) = 0.454.
In imitation experiments (see Figure 7, Figure 8) at 106 passes
J2 (l∗ ) = 0.434.
It should be noted that even at linear distribution of the objects’ coordinates the analytical solution of the
simplest problem of search optimization (2), (3) turns out to be rather cumbersome. An imitation computer
program [Nar19] was developed by the authors, allowing the values of the specified search quality criteria to be
calculated and search parameters for arbitrary distributions f (x), r(x) to be optimized.
4
Figure 6: Modelling the SU loss at 106 passes.
Figure 7: Experimental values of J2 at 102 passes.
4.3 Bi-criteria route scanning with a stop at the target detection
The route (0, L) scanning before the target detection or the SU loss. When the target is detected, unlike strategy
(2), the scanning stops. The difference between the target detection probability and the SU loss probability in
this control strategy is:
∫L ∫x ∫L ∫x
J3 = (1 − r(s)ds)f (x)dx − (1 − f (s)ds)r(x)dx, (4)
0 0 0 0
where the first multiplier of the second summand is the probability of the target not being detected on the
interval (0, x). It should be noted:
J3 ≥ J2 which immediately follows from the comparison of the second summands (4) and (2).
5
Figure 8: Experimental values of J2 at 106 passes.
4.4 Assigning the optimal end coordinate of the SU for two-criteria route scanning with a stop
at the target detection
Let us strengthen strategy (4) by specifying the corresponding task of assigning the optimal final scanning
coordinate, maximizing the difference between the probabilities of the target detection and the SU loss:
J3 (l∗ ) = max J3 (l), (5)
l∈(0,L)
J3 (l∗ ) ≥ J3 .
It should be clarified that at strategy (5) the scanning can be interrupted before reaching l∗ , both when the
SU is lost and when the target is detected
5 Conclusion
1. The bi-criteria search problems (2) – (5) formalized in general form are connected with the following system
of inequalities:
{
J2 (l∗ ) ≥ J2
(6)
J3 (l∗ ) ≥ J3 ≥ J2
Formalizations (2) – (5), however, do not allow the full set of functions to be arranged in descending order,
since pair order (J2 (l∗ ), J3 ) already depends on the explicit forms f (x), r(x).
2. Search strategies (3) and (5) can be enhanced by introducing real-time coordinates correction of the target
and registering units f (x), r(x) (this does not mean revaluation of the initial hypotheses about target and RU
coordinate distributions, but recalculation of these distributions for the unscanned route section).
Acknowledgements
Sections 1-3 of the work were supported by the program of fundamental scientific researches of the SB RAS N
I.5.1., project N 0314-2019-0020. Sections 4, 5 of the work were supported by RFBR, projects N 18-08-01284, N
18-07-00526.
References
[Hel80] O. Hellman. Introduction to optimal search theory. Moscow: Nauka, 1980.
6
[Yan10] R. A. Yanusmetov, A. A. Strotsev. Mathematical model of search system with groups of search units.
Proceedings of higher educational establishments. North Caucasian Region. Series: Technical sciences,
2:17–23, 2010.
[Nar15] B. K. Nartov, S. G. Brattsev, F. A. Murzin, A. A. Puntus. Conflict of complex systems. Models and
control. Moscow: MAI Publishing House, 2015.
[Mur18] F. A. Murzin, B. K. Nartov. Problems of trajectory control. Formalization, surveillance, parallel calcu-
lations. Novosibirsk: SB RAS, 2018.
[Nar19] B. K. Nartov, A. N. Poluyanov. Computer software Modelling of search tasks with risk of loss. State
registration certificate No. 2019663920. 25 Oct. 2019.
7