Probability of detection of an extraneous mobile object by autonomous unmanned underwater vehicles as a solution of the Buffon problem Guzev M.A., Tsitsiashvili G.Sh., Osipova M.A.,  1 Sporyshev M.S. Institute for Applied mathematics, Far Eastern Branch of Russian Academy Sciences, 690041, Vladivostok, Radio str. 7, IAM FEB RAS,  1 Far Eastern Federal University, 690950, Vladivostok, Sukhanov str. 8 e-mails: guzev@iam.dvo.ru, guram@iam.dvo.ru, mao1975@list.ru, coockoombra@gmail.com  MSC2000 60J30+60J60  Abstract.   Underwater robotics addresses the problem of object detection apparatus.   Offers a probabilistic formulation of the problem, which uses the re- duction of the detection task to a classical task of Buffon. This formulation arises naturally in the formulation of the problem in the coordinate system associated with the apparatus. It is shown that the problem allows analysis in the presence of an asymptotic parameter, determined by the ratio of the local scan size of the apparatus to the global size of the problem under consideration.  Keywords:   extraneous mobile object, autonomous unmanned underwater ve- hicle, detection probability, Buffon problem.  Introduction  To calculate the probability of detection of an extraneous mobile object by autonomous unmanned underwater vehicles (AUUV) is the important problem in modern underwater robotic technique. In the initial formulation, this problem relates to the tasks of the target capturing, to the differential games [1]. Various variants of this problem formulation are possible. The first option is based on the definition of the shortest trajectory, after which the 1  arXiv:1801.10318v1 [cs.RO] 31 Jan 2018
robot or a group of robots will cover with their scope all the given territory [2]. The second option involves the search for a minimum number of robots that provide a guarantee of the object capture [3]. In the early works [1-3], the goal of target capturing was formulated in terms of random graphs [4], and not in terms of random sets, which led to the disappearance of the initial geometric formulation of the problem. This drawback can be overcome by addressing to one of the key problems of the theory of geometric probability - the Buffon problem.   The Buffon problem (see Figure 1) is the determination of the probability of intersection of a needle with length l, which is randomly thrown onto a plane ruled by equally spaced parallel lines a distance L apart, with any one of these lines. This problem formed the basis for stochastic geometry and was widely used in applied statistics.  Fig. 1.   The Buffons needle problem. The main elements of the probabilistic model in the Buffon problem are the random variables that determine the mutual position of the segment, occupied on the plane by needle, and the equally spaced horizontal lines [5], [6].   The distance   z   from the segment lower end to the first overlying line, and the angle   φ < π   between this line and the segment are such random variables. Knowing the distribution law of the random vector ( z, φ ) ,   formed by these random variables, we can determine the probability of the event  P   ( l   sin   φ   ≥   z ) of the needle intersection with one of the parallel straight lines.   For this event happening, it is necessary and sufficient the segment intersect with a straight line lying directly above its lower end. As well as the authors of [7], we consider the problem of computing the probability of detection an extraneous mobile object by AUUV in terms of the Buffon problem as follows. Let   n   vehicles move along a circle of radius   R   with a fixed linear velocity  v   and at an equal distance each other. Each of these devices is equipped with circular radar with scanning radius of   r.   The circular radar can be understood 2
as a device that rotates a beam with an angular velocity large enough for the linear velocity of the beam notably exceeds the linear speed of the vehicle. It is required to calculate the probability of detection of a mobile object by means of locators installed on the devices (see Figure 2).   Under the detection, we mean here the object falling into a circle, which is scanned by any of the devices. This work is an expanded version of the report at the VII All-Russian Scientific and Technical Conference ”Technical Problems of World Ocean Exploration” [8].  1.   Buffon problem in the coordinate system associated with vehicles moving round a circle  The peculiarity of the task of calculating the probability of detecting a mobile object in a stationary coordinate system, associated with an external observer, is that both the vehicle and the object are moving, and therefore some transition to the Buffon problem, in which at least parallel straight lines are fixed, is required.  Fig. 2.   The vehicles movement round a circle in a stationary coordinate system. Such a transition is realized when the motion of the objects under study is considered in a coordinate system associated with devices rotating around a certain point   O   round a circle   C   of radius   R . In this coordinate system, the radar scan circles with radius r become fixed. To be detected by the vehicle, the object trajectory should intersect one of these circles. 3
In order to simplify the study of this problem, we suppose that, in a stationary coordinate system, the mobile object moves along a segment con- necting the starting point of its movement with the center   O   of the circle  C .  Fig. 3.   The trajectory of the object movement of in a Cartesian coordinate system associated with vehicles moving round a circle. In a rotating coordinate system, the shape of the object trajectory   A ψ  differs from the segment (see Figure 3): it is a certain curve starting at a random point   ψ   of the circle   C ∗   with radius   R   +   r   centered at the point   O.  Thus, in the system coordinates associated with the vehicles moving round a circle, circles of radius r play the role of parallel lines, and the curves   A ψ   - the role of the segment in the Buffon problem. In a rotating coordinate system, the shape of the trajectory   A ψ   of the object differs from the cut (see Fig. 3): it will be some curve that starts at a random point   ψ   of the circle   C ∗ ,   with the radius   R   +   r   and with center at  O.   Thus, in the coordinate system, associated with the orbiting space crafts, circles of radius   r   are playing the role of parallel lines, and curves   A ψ   – the role of the segments in the problem of Buffon. We further assume everywhere in this paper that the random angle   ψ   has a uniform distribution on the segment [0 ,   2 π ] .   The transition from the curve  A ψ ′   to the curve   A ψ ′′   is carried out by rotation of the curve   A ψ ′   around the point   O   by the angle   ψ ′′   −   ψ ′ .   It should be noted that, on the circle   C ∗ ,   each circle   D i   with radius   r   allocates an arc   F i   bounded by two curves   A ψ ′  i   , A ψ ′′  i   ,  that touch the circle   D i , i   =   l, ..., n,   from the outside (see Figure 4). 4
Fig. 4.   The control area of one circle of radar scan in the Cartesian coordinate system ( x, y ) associated with moving vehicles. Thus, on the circle   C ∗ ,   the scan circle   D i   with the center at the point, where the apparatus   i   is located, allocates the arc   F i ,   i   = 1 , ..., n.   Now we can calculate the probability of detection of a mobile object by circular view radars installed on vehicles.   Let the set   F   be the union of the arcs  F i   :   F   =   ∪ n i =1 F i .   This set is the union of a finite number of disjoint arcs (maybe less than   n ).   Then the total angular length of these arcs   s ( F ) ,  divided by 2 π   :   s ( F ) 2 π   −   is the required probability of detection a mobile object by radar locators installed on the vehicles. Therefore, if the arcs   F i , i   = 1 , ..., n,   do not intersect, the probability of the object detection by the vehicles is   P   =   ns ( F i ) 2 π   ,   where   s ( F i ) is the angular length of the arc   F i .   In the general case,   P   = min  (  1 , ns ( F i ) 2 π  )  .  2.   The Buffon problem in the polar coordinate system  The task of determining the curves   A ψ   and finding of the arcs   F i   is solved, as a rule, numerically. However, at some additional assumptions, it is possible to obtain analytical formulas. Let us transit from the rectangular coordinate system ( x, y ) associated with the device rotating around point   O   to the polar coordinate system (see Figure 5) with the vertical coordinate   ρ   =   √ x 2   +   y 2  and the horizontal coordinate   φ   =   arctg   x y   .  5
In a rectangular coordinate system ( x, y ) ,   a circle of radius   r   centered at ( O, R ) is described by equations  x   =   x ( ψ ) =   r   cos   ψ, y   =   y ( ψ ) =   R   +   r   sin   ψ   0   ≤   ψ   ≤   2 π,  giving a parametric definition of the circle:   ψ   is a parameter. In the polar coordinate system ( ρ, φ ) this circle is given parametrically by the equations  ρ R   =  (   r 2  R 2   cos 2   ψ   +  (  1 +   r R   sin   ψ  ) 2 ) 1 / 2  , φ   =   arctg  r R   cos   ψ  1 +   r R   sin   ψ ,  since   ψ   remains a parameter.   A typical image of circle with a radius   r   in this polar coordinate system looks like an oval with pointed upper end (see Figure 5).  Fig. 5.   The control area of one circle of radar scan in the polar coordinate system associated with moving vehicles. For small values of the parameter   r/R      1 ,   the last system of equations can be approximated as follows:  ρ R   ≈   1 +   r R   sin   ψ, φ   ≈   r R   cos   ψ.  Thus, a circle of radius   r   in the coordinate system ( x, y ) ,   rotating with the apparatus, transfers into almost a circle of radius   r/R   in a normalized polar coordinate system ( ρ/R, φ ) (see Figure 6). 6
Fig. 6.   The control area of one circle of radar scan in the normalized polar coordinate system associated with moving vehicles. When the asymptotic condition   r/R      1 is satisfied, the trajectory   A ψ  transforms into a straight line. If the linear speed of the vehicle is   v,   and the speed of the mobile object in the fixed coordinate system is   u,   then, in the polar coordinate system associated with the moving vehicles, the speed of the mobile object is approximately equal to   √ v 2 /R 2   +   u 2 /R 2   and makes an angle   α   =   arctg   u v   with a horizontal line that is the image of circle   C ∗ .   There- fore, each circle representing the control area of the radar locator overlaps a segment of length   l   =   2 n R   sin   α   for the mobile object (see Figure 6). Let’s move from the probability of the object detection to the minimum number of devices   M   = min  (  n   :   ns ( F i ) 2 π   ≥   1  )  ,   at which the probability of a mobile object detection is equal to one, then   M   = min  (  n   :   nr πR   sin   α   ≥   1  )  .  If the number of devices is   n   =   M,   then the distance between the centers of the neighboring survey circles can be obviously less than   l.  Let   k −   <   1   < k + ,   max( | 1   −   k − | ,   | 1   −   k + | )      1 and a probability dis- tribution   p ( dk ) on the segment [ k − , k + ] is given such that  ∫   k +  k −  kp ( dk ) = 1 .  We replace the radius   R   on   kR.   Then in the polar coordinate system, in virtue of the asymptotic condition   r/R      1 ,   an image of scan circle becomes approximately a circle of radius   r kR .  7
Fig. 7.   The stochastization of the movement radius of the vehicles. The function   r kR   is convex downward by   k,   hence, from Jensen’s inequal- ity [9, p. 207], we obtain the following inequality  r R  ∫   k +  k −  p ( dk )  k   ≥   r R   ·   1  ∫   k +  k −   kp ( dk ) =   r R .   (2.1) Thus, the probability of the object detection with a random distribution of the parameter   k   increases in comparison with the probability of the object detection with an average value of the multiplier   k.  3.   Possible generalizations of the model of the vehicles movement  Assume that vehicles move by variable courses with a linear velocity   v  along a trajectory with a variable radius   k ( t ) R, k −   ≤   k ( t )   ≤   k + ,   (see Fig. 8). This trajectory consists of segments along the radius and along the arcs of circles. Moreover, the total length of the arcs is small in comparison with the total length of segments along the radius. Let the process   k ( t ) obeys the hypothesis of ergodicity - ”the ensemble average coincides with the trajectory average”, and has at   t   → ∞   the limit distribution   p ( dk ) , k −   ≤   k   ≤   k + .   Then inequality (2.1) is fulfilled, which characterizes the probability of detection during the vehicles movement along a trajectory with a variable radius. Now let the vehicles move along a segment   BA   of length   R   in one direction and, after reaching its end, turn and move in the opposite direction (see Fig. 9).   We believe that the distance between neighboring vehicles is 2 R/n,   a similar model was considered in [10]. 8
Fig. 8.   The vehicle movement along a trajectory with a variable radius. Then the scan circles associated with the vehicle locators move along the cylindrical surface   S   with the generatrix   A ∗ A ∗∗   of length 2 r   and the directrix  B ∗ A ∗ B ∗   of length 2 R.   Strictly speaking, this surface is a strongly elongated elliptical cylinder (the mechanical analogue is a metal blank after complete deformation under the press).  Fig. 9.   Movements of the vehicles and the object in a fixed coordinate system (the bold arrow indicates the direction of the object movement). In a fixed coordinate system, the object moves vertically, and its hori- zontal coordinate at the time of crossing the strip is   a,   0   ≤   a   ≤   R.   Let transit to the coordinate system associated with the vehicles moving along the cylindrical surface   s,   and denote as   b   the distance from point   B   to the nearest vehicle in the movement direction (from right to left in Figure 9). Let the probabilistic distribution of the random vector ( a, b ) be uniform on the rectangle [0 , R ]   ×   [0 ,   2 R/n ] .   Then, in the coordinate system associated with moving vehicles, we can specify sub-segments of length   l   = 2 r/   sin   α   on the segment   A ∗ B ∗ , where the object can be detected (see Figure 10). The task of calculating the probability of the object detection is more complicated when the vehicles are moving along straight line, but not along a circle. 9
Fig. 10.   The object movement in the coordinate system associated with moving vehicles. A relatively simple solution to this problem was obtained by transition from the probability of the object detection to the minimum number of   M  apparatuses, in which the probability of the object detection is equal to one, namely,   M   = min  (  n   :   nr R   sin   α   ≥   1  )  .   Such a technique can be applied for multiagent systems, considered in [11]. It should be emphasized in conclusion that we considered a dynamic ver- sion of the Buffon problem, which includes such characteristics as the trajec- tories and speeds of the mobile extraneous object and unmanned underwater vehicles. This circumstance leads to the necessity of transition to coordinate systems associated with moving vehicles and to additional, not always obvi- ous, geometric constructions and application of the small parameter method. The authors are grateful to corresponding member of Russian Academy Sciences A. F. Shcherbatyuk for valuable discussion of the paper. Supported by Far Eastern Branch of Russian Academy Sciences, Program “Far East“ (projects 18-5-050, 18-5-083).  References  [1] T. H. Chung, G. A. Hollinger, V. Isler. Search and pursuit-evasion in mobile robotics// Autonomous Robots. 2011. Vol 31, issue 4. P. 299–316. [2] E. Galceran,   M. Carreras. A survey on coverage path planning for robotics?// Robotics and Autonomous Systems. 2013. Vol 61, issue 12. P. 1258–1276. [3] B. Alspach. Searching and sweeping graphs: a brief survey// Le Matem- atiche. 2006. Vol 59, issue 1, 2. P. 5–37. 10
[4] P. Kafka, J. Faigl, P. Vana. Random Inspection Tree Algorithm in visual inspection with a realistic sensing model and differential constraints// IEEE International Conference on Robotics and Automation (ICRA). 2016. P. 2782–2787. [5] M.G. Kendall, P.A.P. Moran. Geometrical probabilities. London. Griffin and Co. 1963. [6] R.V. Ambartzumian. Combinatorial integral geometry. Chichester. J. Wi- ley and Sons. 1982. [7] C.M. Monasterio, G. Oshanin, G. Schehr. First passages for a search by a swarm of independent random searchers// Journal of Statistical Mechanics: Theory and Experiment. 2011. Vol 2011, issue 6. P. 6–22. [8] M. A. Guzev, G. Sh. Tsitsiashvili, M.A. Osipova. Probability of detecting extraneous mobile object by Autonomous unmanned underwater vehicles is as solution of Buffon problem// Proceedings of the 7-th All-Russian Scientific-Technical Conference ”Technical Problems of World Ocean Ex- ploration”. 2017. P. 426–433. [9] Walter Rudin. Real and Complex Analysis. McGraw-Hill. 1987. [10] I. V. Kozhemyakin, D. V., Nikishenko, V. A. Ryzhov, N. N. Semenov, M. N. Chemodanov. Development the system of Autonomous group management for heterogeneous surface and underwater unmanned vehi- cles// Proceedings of the 7-th All-Russian Scientific-Technical Conference ”Technical Problems of World Ocean Exploration”. 2017. P. 48–57. [11] M. Maggio, E. Bini, C. Georgios et al. A Game-Theoretic Resource Man- ager for RT Application// Proceedings of the 25-th Euromicro Conference on Real-Time Systems. 2013. P. 57–66. 11