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