=Paper=
{{Paper
|id=Vol-2534/30_short_paper
|storemode=property
|title=Localization of Point Sources with Random Spatial Position and Random Discipline of Pulse Generation
|pdfUrl=https://ceur-ws.org/Vol-2534/30_short_paper.pdf
|volume=Vol-2534
|authors=Alexander L. Reznik,Alexander V. Tuzikov,Andrey V. Torgov,Alexander A. Soloviev,Vasiliy A. Kovalev
}}
==Localization of Point Sources with Random Spatial Position and Random Discipline of Pulse Generation==
https://ceur-ws.org/Vol-2534/30_short_paper.pdf
Localization of Point Sources with Random Spatial Position and
Random Discipline of Pulse Generation
Alexander L. Reznik (1), Alexander V. Tuzikov (2), Andrey V. Torgov (1),
Aleksander A. Soloviev(1), Vasiliy A. Kovalev(2)
(1) Institute of Automation and Electrometry SB RAS, Novosibirsk
(2) United Institute of Informatics Problems, National Academy of Sciences, Minsk
Abstract. The methods and speed-optimal algorithms oriented to spatial localization of
pulsed-point sources manifesting themselves at random time by generation of
instantaneous delta pulses are discussed. Optimal search procedures have been proposed
that are focused on the localization of random pulsed-point objects in standard and
advanced search modes (for example, in the absence of a priori information about the
intensity of the source or when its density is unknown within the search interval).
Keywords: optimal search, random pulsed-point source, localization accuracy, receiver.
1 Introduction
Research on the optimal search for random pulse-point objects is subject of current interest for many scientific
and technical disciplines. The need to conduct them arises in the design of various electron-optical converters and
detectors [1]; in the tasks of the suppression of impulse noise on noisy and low-contrast images [2]; in the
development of methods for tech troubleshooting, appearing in a form of the alternating equipment failures [3]; in
problems of detecting radioactive sources using systems consisting of one or several sensors [4], in radio physics
and radio astronomy, when searching for sources of gravitational waves [5] and in many other applications. This
paper presents the methods and algorithms for the speed-optimal search for point Poisson sources that manifest
themselves at random time by generation of instantaneous delta pulses. The optimal search algorithm should, as a
rule, satisfy one of two requirements: minimize the total search effort required to detect an object; or maximize the
total probability of detection in the presence of limited search effort.
The point-pulsed source will be understood below as an object of negligibly small angular dimensions
(mathematical point), having a random distribution on the abscissa axis with a priori probability density f(x) and
radiating infinitely short pulses (-functions) with Poisson intensity λ. Thus, the time intervals between pulses are a
random variable t with an exponential probability density h(t) = λexp(-λt). The search for an object is carried out
with the help of a recording device having a tunable «window» with an arbitrarily time function. The pulse is fixed
if the active object that initiated the pulse is in the «view window» of the recording device. Otherwise, the pulse is
considered to be missed. When registering the pulse, the window narrows, and (as a result) the position of the source
is determined more accurately. It is required for the minimum (in statistical terms) time to find a source with an
accuracy of
2 Single-step search algorithms
Introducing the binary function x
1, if the point x at the time moment t is in
the view window of the receiving device ,
u ( x, t )
0, otherwise,
describing the view window at time t, we obtain the average time from the start of the search to the registration of
the first pulse:
t
dt dx tf ( x )u ( x, t ) exp( u ( x, ) d ) .
0 0 0
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0
International (CC BY 4.0).
For the random priori distribution of a pulsed source on the x-axis, the construction of even a one-step (which
ends immediately when the first pulse is registered) time-optimal search procedure causes considerable difficulties.
In one-step periodic search algorithms, the relative load φ(x) on the point x (that is, the relative time it’s located in
the view window) remains constant throughout the entire search time. With this approach, the problem is to find the
function φ(x), minimizing the average search time
1 f ( x)
( x)
dx (1)
when the following conditions are met
( x)dx , (2)
0 ( x ) 1. (3)
Optimization of expression (1) with constraints (2) - (3) belongs to non-linear programming problems [6-7]. To
solve it, we will use the method of Lagrange multipliers [8] and we will look for the function φ(x) minimizing the
expression
f ( x)
( x ) ( x )dx.
Differentiating by φ and taking into account the constraint (2), we obtain
( x) f ( x ) . (4)
f ( x )dx
If for any x condition (3) is not violated, then function (4) is a solution to the formulated extremal problem. If
there exist such domains x, where the solution φ(x)> 1, then inside these areas it is necessary to put φ(x) = 1, and to
recalculate (for the remaining points) the indefinite factor µ taking into account the already changed conditions (2)
and (3). After that, any binary function u(x, t) can be selected as the optimal search strategy if it satisfies the
relations
u ( x, t )dx ; u ( x, )d ( x)t.
In the general case, building an optimal (not necessarily periodic) one-step search algorithm is associated with
finding such a function φ(x, t) – the relative load on point x at time t, – which minimizes the average localization
time
t
dt dxf ( x ) exp( ( x, )d )
0
provided that
0 ( x, t ) 1 (5)
and for any t
( x, t )dx . (6)
t
To simplify further calculations, we introduce a function ( x, t ) ( x, )d corresponding to the total
0
time for point x stays in the view window (for the entire period from the beginning of the search to the time t). To
take into account constraints (5) and (6), we again introduce the Lagrange multiplier μ(t). Then the task of building
an optimal search strategy will be reduced to finding the function α(x,t) minimizing the functional
dt dxexp( ( x, t ) f ( x) (t ) ( x, t ) , provided that
( x, t )dx t ,
(7)
0 ( x, t ) t .
The solution to this variational problem is the function
1 f ( x )
0, ln (t ) 0;
(8)
1 f ( x ) 1 f ( x)
( x, t ) ln ,0 ln t;
( t ) (t )
1 f ( x )
t , t ln ,
(t )
where the multiplier μ(t) is determined from relation (7), and any binary function can be chosen as the optimal
search strategy u(x, t) that satisfies the conditions
t
u ( x, )d ( x, t );
0
u ( x, t )dx .
The use of optimal search algorithms in practice leads to certain difficulties. The fact is that in those cases when
source’s priori distribution density function differs from the uniform one, both of the proposed optimal one-step
search algorithms cannot be physically realized by moving the singly connected (non-separable) scanning window.
Therefore, in actual search procedures, it is advisable to perform a one-step procedure according to the following
scheme. The interval (0, L) is pre-divided into a series of discrete elements having a length ε, and the a priori given
density f(x) is “stepwise” approximated on each of them. The value of ε is considered to be sufficiently small (which
meets the high requirements for localization accuracy) so that the variation of the function f(x) within one discrete
can be neglected. The search must begin with “observation” of the highest “peak”, within which the amplitude
function f(x) is maximum, then after the time t1, the window is alternately set under the two highest “peaks”, then
after the time t2, three elements are alternately observed, etc. All switching moments ti are determined in exact
accordance with the above relation (8), which is the basis for constructing an optimal search strategy.
It should be noted that the search algorithm under discussion assumes that the intensity of the source λ is known
in advance. If such a priori information is not available, it is possible to recommend a periodic procedure that does
not depend on this intensity. In accordance with this strategy, the integrals of the density f(x) are initially calculated
in each ε-discrete. If the total number of ε-increments (into which the initial search interval is divided) is m, and the
“step” integrals over each of them are equal to P1,P2, ...,Pm, then the view window should cycle through all discretes
with relative load
m
i Pi P j , ( j 1,..., m ) .
j 1
These βi values are easy to obtain if the method of Lagrange multipliers is used again to minimize the average
search time:
(1 )( P1 1 P2 2 ... Pm m ) min, ( 1 ... m 1).
3 Multi-step search algorithms
With high requirements for localization accuracy, one-step algorithms are far from optimal. So, when
constructing an optimal search procedure, we cannot limit ourselves to one-step algorithms, and should consider a
search procedure consisting of several steps. For the average time of the m-step localization procedure, the ratio is
m
k dxf ( x ) ... t k
k 1 0
l
(9)
k ts
l s 1
dtl ul ( x, t s ,t1 ,..., t l 1 ) exp( ul ( x, , t1 ,...tl 1 )d ) ,
l 1 s 1 l 1
ts
s 1
u ( x, t , t ,...,t
m 1 m 1 ) dx ,
where ui(x,t,t1,…,ti-1) is the function that sets the view window at the i-th stage, provided that the intervals recorded
between the previous (i-1) pulses were respectively t1,t2,…,ti-1. It is not always possible to find extremals that deliver
a minimum to the localization time (9) in the general case (when the probability density f(x) is arbitrary). Therefore,
we have developed a universal procedure to search for a source in the case when there is no priori information about
the intensity of the source (so, we can assume that the source has a uniform distribution over the search interval).
Due to the limited scope of this message, only the resulting table summarizing the parameters of the optimal multi-
step search for a random uniformly distributed point source for systems with one receiver is given, and all necessary
analytical and numerical calculations are omitted. More detailed information on this can be found in [9-10].
Table 1. Parameters of the optimal procedure for finding a random uniformly distributed pulse source on the
interval (0,L) depending on the required localization accuracy ε.
( / L)
mopt Wm , m 1, mopt
(average time
(required localization accuracy)
(optimal number (system search window at each stage mopt of the
of steps) of localization)
optimal search)
1 1
( / L) 1 1 W1 ( / L) 1
4
1
6 W1 ( / L) 2 L
2
1
1 2
( / L) 2 ( / L ) 2
3 4
W2 ( / L) L
1
W1 ( / L) 3 L
12 6
3 2
( / L )
2
3 W2 ( / L) 3 L 3
1
4 3 ( / L) 3
W3 ( / L) L
1
W1 ( / L) m L
2
W2 ( / L) m L
m
m ( m 1)
m 1
m ( m 1) m m
1
( / L) ( / L) m
m 1 m i
Wi ( / L ) m L
m
Wm ( / L ) m L
Taking into account that
m
m 1
lim e
m m 1
when (ε/L) → 0, we get the following asymptotic relations for systems with one receiver:
e ln( L / )
mopt ln( L / ); Wi e i L, i 1, mopt ; opt .
The results presented above are the set of speed-optimal algorithms to localize random pulsed-point sources
using system with one receiver. The studies were carried out both for single-step search procedures (in the case of an
arbitrary probability density of the random source distribution on the search interval) and for multi-stage localization
algorithms (for those cases when a random point-impulse object has a uniform distribution on the search interval).
Acknowledgements. This work was supported by the Russian Foundation for Basic Research (grants No. 19-01-
128 and 18-51-00001) and the Ministry of Science and Higher Education (Project No. AAA-A17-117052410034-6).
References
[1] J.H. Barnes, G.M. Hieftje. Recent Advances in Detector-Array Technology for Mass Spectrometry // Int. J.
Mass Spectrom. 2004. V. 238. P. 33– 46.
[2] V.S. Kirichuk, K.Yu.Mokin, and A.L. Reznik. Algorithms for Processing of Series of Digital Aerospace Images
Based on Automatic Search for the Conjugate Points // Pattern Recognition and Image Analysis, 2001, vol.11,
No 1, pp. 192-194.
[3] B.V. Gnedenko, Yu.K. Belyayev, and A.D. Solovyev, Mathematical Methods of Reliability Theory (Nauka,
Moscow, 1965; Academic, New York, 1969).
[4] M. Mallick, V. Krishnamurthy, B. Vo. Integrated Tracking, Classification, and Sensor Management: Theory
and Applications. Wiley, 2012, 736 p.
[5] X. Zhu, L. Wen, G. Hobbs and oth. Detection and localization of single-source gravitational waves with pulsar
timing arrays // M.N. of the Royal Astronomical Society, Oxford Academic Press, v. 449, №2, 2015, p.1650–
1663.
[6] M.J.D. Powell. A Fast Algorithm for Nonlinearly Constrained Optimization Calculations. Numerical Analysis,
G.A.Watson ed., Lecture Notes in Mathematics, Springer Verlag, Vol. 630, 1978.
[7] R.E. Bellman, I.L. Glicksberg, and O.A. Gross. Some aspects of the mathematical theory of control processes.
Santa Monica, CA: RAND Corporation, 1958, 263p.
[8] D. Bertsekas. Constrained optimization and Lagrange multiplier methods. New York: Academic Press. 1982.
[9] A.L. Reznik, A.A. Solov’ev, and A.V. Torgov. The algorithms of optimum localization of random pulsed-point
source under the condition of its uniform distribution on a search interval // Pattern Recognition and Image
Analysis. Advances in Mathematical Theory and Applications, 2018, Vol.28, No. 2, pp.354-361.
[10] A.L. Reznik, A.V. Tuzikov, A.A. Solov’ev, and A.V. Torgov. Time-Optimal algorithms of searching for
pulsed-point sources for systems with several detectors // Optoelectronics, Instrumentation and Data Processing,
2017, Vol. 53, Issue 3, pp. 203-209.