Radioactive source search problem and optimisation model based on meta-heuristic algorithm

Min Zhang; Xuewen Lu; Ettiene Hoffman; Radwan Kharabsheh; Qianghua Xiao

Détails du journal et du numéro

Applied Mathematics and Nonlinear Sciences

Détails du magazine

Format: Magazine
eISSN: 2444-8656
Première parution: 01 Jan 2016
Périodicité: 2 fois par an
Langues: Anglais

In the process of rational development and utilisation of nuclear energy, people often face nuclear accidents such as lost and stolen radioactive sources; so, the means of searching for these sources quickly in highly radioactive environments is an important security challenge. In the past, these jobs were limited to workers specialising in nuclear technology. They used gamma-ray detection equipment to search for radioactive sources, but the search efficiency was low. The main purpose of this article is to design a meta-heuristic algorithm based on imitating professional technicians to locate radioactive sources in a computer-aided manner. At the same time, due to the complexity that may characterise the actual search, the search strategy must be optimised. The article established an intelligent random search model with human thinking. Finally, it was proved based on the mathematical theory that the complexity of the model search algorithm is linear, and the simulation experiment results show that the optimisation algorithm has good efficiency and fault tolerance.

Keywords

nuclear radioactive source
random search algorithm
complexity

Article

Introduction

Every year, many commercial radioactive sources are used in medicine and industry in the world, which presents a potential hazard. In the case of losing radioactive sources, the means to quickly search and remove contaminated materials in the separate areas in the high-level environment of radioactive sources is an important security issue in the application of nuclear technology. Many researchers have contributed to the search for radioactive sources.

Some studies in the past have improved the sensitivity of nuclear detection instruments to improve the efficiency of searching for radioactive sources. Various types of γ radiation [1, 2, 3] are most commonly detected manually with a point sensor such as a Geiger counter or a scintillator. Due to their low cost and ubiquity, the use of detectors for radiation source localisation has been extensively studied. In this method, the detection is carried out by human beings, who are exposed to the irradiation environment.

Similarly, some scholars have applied mathematical methods to the study of nuclear technology-related issues. In 2000, Alpay and Shor [8] studied the use of point sensor measurements to locate point sources in a class of distributed systems described by partial differential equations (PDE). In 2007, Ristic et al. [9] published an article, in which the detection/estimation part of the radioactive material of unknown intensity of radiation in the Bayesian framework was solved using a particle filter. In 2010, Hamideen et al. [10] used the mathematical nonlinear equation to derive and use the mathematical nonlinear program to locate radioactive sources in one, two and three-dimensional space. Using mathematical methods ensures that it becomes possible to break the professional barriers and allows more researchers to study the problem, but the requirements of these methods are harsh and far removed from the actual situation.

However, there are also many scholars whose work is dedicated to the use of robots in radioactive search. In this way, experts in the mechanical field also join in the research. Redus et al. [4] developed an integrated imaging sensor system, which combined a gamma-ray image of the distribution of radioactivity with a video image of the area, allowing a rapid and intuitive determination of the source location. The CEA and CYBERIA [5] have worked together to develop the RICA robot, which can locate and measure the activity of radioactive sources. In 2017, Chen et al. [6] set up a computational fluid dynamics model of leakage for an indoor time-varying contaminant source, together with establishing a search strategy using multi-robot active olfaction. In 2019, Ardiny et al. [7] adapted and implemented behaviour-based and multi-criteria decision-making (MCDM) approaches on an autonomous robot. The core technology of robot search is algorithm design; so, a continuous optimisation algorithm is a key to improve robot search.

The search problem is a relatively conventional problem in algorithm design and has a good research foundation. In 1995, Wacholder et al. [11] established an optimisation artificial neural networks model, which was developed for solving the ill-posed inverse transport problem associated with localising radioactive sources in a medium with known properties and dimensions. In 2005, Presler et al. [12] and others developed a simple and practical algorithm to use two detectors to measure the emission of gamma rays from a huge sample, so that the ratio of the detector's counting rate can be used to locate the position of the point source of the bulk volume. In 2009, Vilim and Klann [13] published a paper describing advanced algorithms developed and implemented for real-time source detection, location and tracking. In 2015, Shixiang [14] designed the structure of the radiation source manipulator and proposed a source search algorithm based on Gaussian process regression. In 2015, Zhang [15] designed a heuristic search algorithm for line scanning, which can quickly search unknown sources in a short time. Liu [16] investigated a double Q-learning-based anomalous source searching algorithm to navigate the detector searching for sources. Gong et al. [17] developed the source localisation algorithm based on the inverse-square law and statistical methods in the region where the source is present, and the unmanned aircraft is used to locate the sources. Computation-assisted search has low cost and algorithm design has a good research foundation; so, this has become a relatively good research direction. Here a small amount of grid data and algorithms are used to locate the radioactive source.

In this article, the authors use a small amount of raster data and a simulated artificial search thinking design algorithm to locate radioactive sources, and theoretically prove that this method is linear in search time; so, this method provides a new way to efficiently search for radioactive sources.

Data collection

The rectangular area containing the radiation source is divided into a grid and the corresponding grid node data is collected. Consider horizontal square area with point source Ω = {(x, y)|0 ≤ x ≤ a,0 ≤ y ≤ b}. In the X axis, insert n − 1 points in range [0, a], x₁, x₂,…, x_n₋₁ and let x₀ = 0, x_n = a. In the Y axis, insert m − 1 points in range [0, b], y₁, y₂, … y_m₋₁ and let y₀ = 0, y_m = b; so, (Figure 1)

\begin{array}{l} E_{n + 1} : 0 = x_{0} < x_{1} < \dots < x_{n} = a, E_{m + 1} : 0 = y_{0} < y_{1} < \dots < y_{m} = b, \\ x_{i + 1} - x_{i} = \frac{a}{n}, i = 0, 1, 2, \dots, n - 1, y_{i + 1} - y_{i} = \frac{b}{m}, i = 0, 1, 2, \dots, m - 1 . \end{array}

\matrix{{{E_{n + 1}}:\;\;0 = {x_0} < {x_1} <\cdots< {x_n} = a,\quad {E_{m + 1}}:\;\;0 = {y_0} < {y_1} <\cdots< {y_m} = b,} \hfill\cr{{x_{i + 1}} - {x_i} = {a \over n}\;,\;i = 0,1,2, \cdots,n - 1,\quad {y_{i + 1}} - {y_i} = {b \over m}\;,\;i = 0,1,2, \cdots,m - 1.} \hfill\cr}

Then E_n₊₁ × E_m₊₁ = {(x_i, y_j)|i = 0,1,2, …n, j = 0,1,2, …m} is the rectangular point set (Figure 1), and the grid node value (x_i, y_j) is f_i_,j, i = 0,1,2, …,n, j = 0,1,2, …m. (Table 1).

Table 1

Radiation dosage at the grid nodes

	x₁	x₂	x₃	…	x_n

y₁	f₁₁	f₂₁	f₃₁	…	f_n₁
y₂	f₁₂	f₂₂	f₃₂	…	f_n₂
⋮	⋮	⋮	⋮		⋮
y_m	f_1m	f_2m	f_3m	…	f_nm

Random search model for a single radioactive source

When people search for radiation sources, they hold the detector to detect the direction of the maximum dosage horizontally and move towards the direction of the maximum dosage. Imitating the idea of human search results in a random search model.

From the grid in the rectangular area of the radiation source, we randomly generated the position coordinate of a single radiation source and selected a point as the starting point for searching. We compare the four dosages around the point, and then move to the point of maximum dosage; subsequently, we analyse the radiation dosage at the next grid node, and move to the location with the most significant amount until no further movement is warranted. Finally, the stop point is the radiation source.

Randomly generated source locations can be placed on grid nodes or within the grid. For the radiation source located within a grid, we determine the grid node whose radiation dosage is the closest to the radiation source according to the principle of adjacent radiation dosages comparison. Then we divide the small area centred on the node into smaller grids, and search for the maximum radiation dosage points on the smaller mesh. Then, we divide the small area centred on the maximum radiation dosage points into smaller spaces and search for the point with the maximum radiation dosage on the grid, and repeat the operation until the radiation source point is on the partitioned grid node (as shown in Figure 2) and until the radiation source is ascertained. We combine the hierarchical search with the random search algorithm to optimise the random search. In random search experiments, to simplify the problem and highlight the essence of random search, we can consider placing radioactive sources on the grid nodes. Next, we introduce the related algorithms needed in the random search of single-point radiation sources.

3.1

Random search model for radioactive source

Before the establishment of the model, it is necessary to mesh the area where the radiation source is located. A coarse grid is used for searching in a large area, but when approaching the target, higher accuracy is required. It is necessary to search on a finer grid to ensure accuracy. Consider the random search of a single-point radiation source. First, we divide the coarse grids, and then subdivide the networks in a small range. This operation can effectively improve the speed of the algorithm and save storage space. The means to effectively establish the grid is the most basic problem of search; the details of the grid algorithm are given below (Algorithm 1).

Algorithm 1: Regional Mesh Generation Algorithm

Step 1. Average the rectangular area D into n rows.

Step 2. Average the rectangular area D into m columns.

Step 3. Input the radiation dosage f_ij of all nodes on the grid.

Note: Mesh the area D, and divide the random search area into n rows and m columns. Obtain the dosage (f_ij) by a radiation detector. The data needed for a random search is ready.

When searching for radioactive sources randomly, select the searching path to find the sources on the grid. At the grid node, all dosages of surrounding points compare to the initial point, and the random initial point will move towards the location where the radiation dosage is highest in the surrounding four points. This cycle's steps continue until the point no longer moves and then we find out the maximum point to be the radioactive source. It is necessary to design a neighbour set search algorithm. See the neighbour set finding algorithm (Algorithm 2) for details.

Algorithm 2: Neighbour Set Finding Algorithm for Node

Step 1. Randomly produce the searching starting point (i, j).

Step 2. If i ≠ 1 or n, j ≠ 1 or m then get the adjacent points set of random point $(i, j + 1), (i, j + 1), (i - 1, j), (i + 1, j) .$ \left({i,j + 1} \right),\left({i,j + 1} \right),\left({i - 1,j} \right),\left({i + 1,j} \right).

Step 3. Search the adjacent points set of the four vertices of the rectangular region.

If i = 1, j = 1t then output the adjacent points are (1, 2), (2, 1).

If i = 1, j = m then output the adjacent points are (1, m − 1), (2, m).

If i = n, j = 1 then output the adjacent points are (n − 1, 1), (n, 2).

If i = n, j = m then output the adjacent points are (n, m − 1), (n − 1, m).

Step 4. Search the adjacent set of all points (except four vertices) on the edge of the rectangular area.

If i = 1, j ≠ 1 and j ≠ m get the adjacent set (1, j − 1), (1, j + 1), (2, j).

If i = n, j ≠ n and j ≠ m get the adjacent set (n, j − 1), (n, j + 1)(n − 1, j).

If j = 1, i ≠ 1 and i ≠ n get the adjacent set (i − 1,1), (i + 1, 1), (i, 2).

If j = m, i ≠ 1, and i ≠ n get the adjacent set (i − 1, m), (i + 1, m), (i, m − 1).

When searching for radiation sources, we usually compare the radiation dosage, and then determine the direction of walking, and search for radiation sources through continuous analysing. Therefore, we design a random search model by imitating the human search experience. The main idea of the random search algorithm is to select the maximum radiation dosage point around the node using the neighbour set comparison method. Compare the dosage of the four points around a random point with the point and move to the maximum point. Repeat until they are no longer more significant than other points. See Random Search Algorithms 3 for details.

Algorithm 3: Random Search Algorithm

Step 1. Input the grid nodes (x, y) of the search area D and the radiation dosage f (x_i, y_j).

Step 2. Randomly produce search starting point (x, y) and call Algorithm 2, and get the adjacent point set S.

Step 3. If f (x_i, y_j) ≥ f (S), then output the radiation source point (x, y).

Step 4. If f (x_i, y_j) < f (S), then let $f (x_{i}^{*}, y_{j}^{*}) = max f (S)$ f\left({x_i^*,y_j^*} \right) = \max f\left(S \right) , x = x^*, y = y^*, and then return to step 2.

The following are some explanations for the random search algorithm. In step 3 of the random search algorithm, if the random point is the maximum point in the set of adjacent points, then output the random point. If the point (x_i_, y_j) in adjacent set S is larger than the dosage of the point (x^*, y^*), then output the point (x^*, y^*) (Figure 2). The neighbourhood point comparing rule is the judgement basis of the moving direction of random search.

3.2

Random search optimisation model

3.2.1

Radiation dosage maximum correction

When searching for radiation sources, some problems often arise, such as misreading of grid data, large low concentration area in the radiation area and moving in small radiation dosage area for a long time by random searching, which result in low searching efficiency and even the problem of not searching for radiation sources. Therefore, to solve the issues that may arise in actual searching, it is necessary to optimise the random searching algorithm and increase the robustness of the random search model.

In the actual search and collection of grid node data, the collected data may be misread, resulting in deviation of search results. For enhancing the adaptability of the random search algorithm, it is necessary to increase the ability of the algorithm to resist data misreading interference. Generally, there are only two cases when data misreading occurs: The first is that of the searched maximum point being misinterpreted and enlarged. The second is that the maximum amount of the searched data is misread and reduced. If the dosage of the maximum point searched randomly is misread and reduced, it will not affect the fact that the node is the maximum point or even the radiation source point. However, if the dosage of the searched maximum point is misread and enlarged, then the point can still be the exact maximum point, or may not be the maximum point. To determine whether the point is the maximum point of the real field, we need some judgement rules with which to distinguish. It is necessary to optimise the Random Search Algorithm.

Let S be a set of adjacent points around an arbitrary node (x, y), and A represents all points within and around the region D^′. f (D^′) and f (S) are, respectively, radiation dosage set of regional D^′ grid nodes and radiation dosage set of all points in S. max f (S) is the maximum radiation dosage of all points in set S. S^* is the set S of all grid nodes (including boundary points) in region D^′ deleted from point set S, i.e. $S^{*} = \frac{S}{D^{'}} = {(x, y) | (x, y) \in S and (x, y) \notin D^{'}}$ {S^*} = {S \over {{D^{'}}}} = \left\{{\left({x,y} \right)|\left({x,y} \right) \in S\,{\rm{and}}\,\left({x,y} \right) \notin {D^{'}}} \right\} .

Algorithm 4: Radiation Dosage Maximum Correction Algorithm

Step 1. Input area maximum point (x, y) and f (x, y) ≥ f (S).

Step 2. Produce a rectangular area centred on (x, y)D^′ ≥ 4|E|, |E| is thenit grid length).

Step 3. Find all boundary points (x, y) of region D^′.

Step 4. Calculate the radiation dosage rate at each boundary point (x, y).

Step 4.1. The set of all boundary points in region D^′ is set A, and find the adjacent of set S for $\forall (x, y) \in A .$ \forall \left({x,y} \right) \in A.

Step 4.2. Let $S^{*} = \frac{S}{D^{'}}$ {S^*} = {S \over {{D^{'}}}} .

Step 4.3. For ∀(x^*, y^*) ∈ S^*, ∀(x, y) ∈ A

If x^* = x, then $f_{(x, y, x^{*}, y^{*})}^{'} = \frac{f (x^{*}, y^{*}) - f (x, y)}{| y^{*} - y |}$ f_{\left({x,y,{x^*},{y^*}} \right)}^{'} = {{f\left({{x^*},{y^*}} \right) - f\left({x,y} \right)} \over {\left| {{y^*} - y} \right|}} ,

If y^* = y, then $f_{(x, y, x^{*}, y^{*})}^{'} = \frac{f (x^{*}, y^{*}) - f (x, y)}{| x^{*} - x |}$ f_{\left({x,y,{x^*},{y^*}} \right)}^{'} = {{f\left({{x^*},{y^*}} \right) - f\left({x,y} \right)} \over {\left| {{x^*} - x} \right|}} .

Step 4.4. If $M = \max_{\begin{matrix} (x, y) \in A \\ (x^{*}, y^{*}) \in S^{*} \end{matrix}} f (x, y, x^{*}, y^{*}) > 0$ M = \mathop {\max}\limits_{\matrix{{\left({x,y} \right) \in A}\cr{\left({{x^*},{y^*}} \right) \in {S^*}}\cr}} f\left({x,y,{x^*},{y^*}} \right) > 0 , then output the modified search initial point (x^*, y^*), otherwise output the maximum point (x, y).

Here are some explanations for the radiation dosage maximum correction algorithm. The size of D^′ is controlled by one parameter. Generally, it contains at least four grids centred on the point (x, y). Sometimes, eight grids or sixteen grids may be required.

In the real search, the situation in the search area is complex. Near a certain maximum value, data misreading results in high and low fluctuation of data, which may lead to a dead cycle when the radiation dosage correction algorithm is called. Dead cycles may occur when calling the Radiation Dosage Maximum Correction Algorithm. In order to avoid a dead cycle, it is necessary to limit each point to a maximum of one search. If the node is found again, it is necessary to forcibly output the starting point of the first radiation dosage correction. This considers implementation of the maximum correction algorithm in a large field grid area D^″ of the centre of the point (x, y).

When there is only one grid distance between the misread point data and the radiation source, the dosage correction algorithm may fail. However, it can make up for the defect of correction. By further subdividing the mesh by hierarchical search, it becomes possible to judge the real radiation source with maximum characteristics by the fine mesh nodes in a small area, so that the accuracy and efficiency of the whole algorithm are not affected.

Misreading variable large correction diagram of radiation dosage maximum

3.2.2

Rapidly escape from local low radiation area

When searching the maximum point, we locate the random search point in a flat area far from the radiation source, where the radiation dosage changes little or even does not change. Then, a random search in this low radiation dosage area will cause unnecessary waste and might even stop the search. It is also possible that the small fluctuation of data in the flat area will search for a local maximum point, which will interfere with random search. Therefore, for data in a low radiation dosage area, it is necessary to jump out quickly and reduce unnecessary random search time. Thus, we design an algorithm for quick jump out of regions with similar radiation dosage. The details are shown in Algorithm 5 for a quick escape from the low radiation area.

Here are some explanations for a fast escape algorithm in a low radiation dosage area. In step 4 of the algorithm, the radiation dosage threshold of the fourth step of the algorithm can be the average of the measured dosage of the whole area.

Sometimes the low radiation dosage area is too large. When using the escape strategy of Algorithm 5, it is possible to enter the small radiation dosage area again when randomly selecting a new search starting point outside the escape circle, which makes the escape effect unsatisfactory. At this time, the method of increasing the random moving step can result in quickly escaping the low radiation dosage area. The specific idea of quick escape pseudo-area is as if random. The starting point of the search is in the little radiation dosage area, and we choose the horizontal direction of the left (right) to calculate the radiation dosage differences one by one. If the radiation dosage difference exceeds a certain threshold, the random point will move to that point so that the cycle can quickly escape the pseudo-area. See local fast escape (Algorithm 6).

Algorithm 5: Local Low Radiation Area Escape Algorithm

Step 1. Random generation of search starting point (x, y).

Step 2. Produces a rectangular region D^′ centred on (x, y)(D^′ ≥ 4|E|, |E| is the unit grid length).

Step 3. Calculate average dosage V_{D_′} of the area D^′.

Step 4. If V_{D_′} ≥ M^* (threshold of radiation dosage), then output (x, y).

Step 5. If V_{D_′} < M^* (threshold of radiation dosage), (x, y) point is taken as the centre, and the shortest distance from (x, y) point to the four edges of the search area is taken as the radius to make a circular region. After selecting a new search starting point randomly outside the circle, the random search algorithm (Algorithm 3) is called.

Algorithm 6: Fast Escape Algorithms for Local Low Radiation Areas

Step 1. Input search starting point (x, y) and adjustment parameter K.

Step 2. Produce a rectangular region D^′ centred on (x, y)(D^′ ≥ 4|E|, |E| is the unit grid length).

Step 3. Calculate average dosage V_{D_′} of the area D.

Step 4. If V_{D_′} ≥ M^* (threshold of radiation dosage), then output (x, y).

Step 5. If V_{D_′} < M^* (threshold of radiation dosage), (x, y) point is taken as the centre; compare the dosage of nodes one by one on the left (or right) of the horizontal line where point (x, y) is located.

From s = ||x|| + 1 to n, If (x, y) − f (s, y) > k, i = s output (x, y) (Search initial Point).

Following are some explanations for the fast escape algorithm in local low radiation region.

In Algorithm 6, |||| stands for an integral function in step 5. A quick escape pseudo-zone algorithm breaks the general random search rule. Instead of using the strategy of moving a grid step by comparing radiation dosages at one time, it first compares radiation dosages until the radiation dosages of nodes exceed a threshold standard at the starting point, and then moves a giant step to achieve fast search. By analogy, it can quickly find the maximum location.

For the threshold selection of a significant step, we determine that the criteria can be according to the specific situation of the actual radiation dosage field. If a giant step is required, the threshold criteria can be adjusted appropriately. Otherwise, the threshold criteria can be lower.

3.2.3

Judgement of radiation sources

Sometimes the biggest point found in this area is not a true source of radiation. For example, data misreading causes a certain amount of data to be particularly large. Therefore, it is necessary to identify and distinguish between the real and erroneous sources of radiation. Therefore, after searching for the maximum point, it is necessary to determine whether the point is a radioactive source.

Assuming that the activity of point source is A (Bq), the formula for calculating the specific kinetic energy release rate in the air at R (m) is as follows [18]: (1) ${\dot{K}}_{a} = \frac{A τ_{K}}{R^{2}}$ {\dot K_a} = {{A{\tau _K}} \over {{R^2}}} where the unit of ${\dot{K}}_{a}$ {\dot K_a} is Gy/S (convertible to Cy/h, mGy/h).

How to judge whether the point is a radioactive source? What is the basis? Nuclear physics tells us that the radiation dosage at any point in a radioactive particle field is inversely proportional to the square of the distance of the radioactive source [18]. Therefore, the radiation field of the radioactive source is characterised by a sharp concave function. The concavity and convexity of the radiation dosage curve near the radiation source are judged by the trend of radiation dosage variation near the radiation source. See Algorithm 7.

Algorithm 7: Radioactive Source Judgement Algorithms

Step 1. Input the maximum point judged.

Step 2. Judge the feature of the maximum point in X and Y directions.

If {f (x_i, y_j) − f (x_i₋₁, y_j)} > {f (x_i₋₁, y_j)} − f (x_i₋₂, y_j)} and {f (x_i, y_j) − f (x_i, y_j₋₁)} > {f (x_i, y_j₋₁) − f (x_i, y_j₋₂)} then (x_i, y_j) is a radiation source point; otherwise (x_i, y_j) is not a radiation source point.

3.2.4

Optimised random search model

The design of random search algorithm for single-point radioactive source is mainly configured for improving the running speed, and to reduce the storage space and enhance the adaptability of the random search algorithm; its function is mainly to improve the running speed and reduce the storage space. Moreover, the random search algorithm is closer to the blind search in the actual hunt, and it is a useful, simple and easy-to-operate random search algorithm. We add the algorithm of maximum point correction and low radiation dosage escape to the random search algorithm, and obtain the optimised random search algorithm. See random search optimisation algorithm (Algorithm 8) for details.

Algorithm 8: Random Search Optimisation Algorithms

Step 1. Input the search rectangular area D (call Algorithm 4).

Step 2. Randomly search in the area D.

Step 2.1. Randomly select the search starting point (x, y), and specify the search call Algorithm 2 to find the neighbour set of (x, y).

Step 2.2. Call the random search Algorithm 3 to search for grid nodes with more significant dosage. If f (x, y) ≥ f (s), then output maximum point (x, y),

If f (x, y) < f (s), then let f (x^*, y^*) = max f (S), otherwise x = x^*, y = y, return to step 2.2 for the new (x, y) until the end of the loop.

Step 3. Correct maximum point.

For output point (x, y), call the radiation dosage maximum correction Algorithm 4.

If $M = \max_{\begin{matrix} (x, y) \in A \\ (x^{*}, y^{*}) \in S^{*} \end{matrix}} f (x, y, x^{*}, y^{*}) > 0$ M = \mathop {\max}\limits_{\matrix{{\left({x,y} \right) \in A}\cr{\left({{x^*},{y^*}} \right) \in {S^*}}\cr}} f\left({x,y,{x^*},{y^*}} \right) > 0 , then output the point (x, y).

If $M = \max_{\begin{matrix} (x, y) \in A \\ (x^{*}, y^{*}) \in S^{*} \end{matrix}} f (x, y, x^{*}, y^{*}) \leq 0$ M = \mathop {\max}\limits_{\matrix{{\left({x,y} \right) \in A}\cr{\left({{x^*},{y^*}} \right) \in {S^*}}\cr}} f\left({x,y,{x^*},{y^*}} \right) \le 0 , then let f (x^*, y^*) = max f (D^′), and x = x^*, y = y^*, return to step 2.2 for point (x, y).

Step 4. Determine whether the output point (x, y) is a radioactive source point. Call Algorithm 3.7 for point (x, y).

Here are some explanations of the random search optimisation algorithm. When the search area is large, the hierarchical search algorithm and the random search algorithm can be used together to improve the search efficiency. See Algorithm 8 for details.

We have improved the search algorithm. If data misreading occurs, the maximum point correction algorithm should be called to help identify whether the maximum point of the search is a radioactive source. See maximum dosage correction algorithm (Algorithm 7) for details.

For preventing the search from wasting the search time in the flat area of the radiation dosage, it is also possible to call Algorithm 6 to escape the low radiation dosage low area and start a new random search in a flat area where the radiation dosage is small. The above explanations all indicate that random search has strong adaptability and is of an intelligent type. Different algorithms can make the random search algorithm more effective in solving problems encountered in the actual search.

3.3

The hierarchical random search algorithm

When the number of radioactive sources in the search area is small, or even only one, performing a global random search in the search area may waste the search time. In such cases, it becomes necessary to pursue a strategy of finding a radioactive source to remove one. To reduce unnecessary search, improve the speed and efficiency of the random search model and design a search algorithm with less time and space complexity, we have developed the random search strategy and adopted a hierarchical search strategy. First, we divide the coarse mesh in the searching area. According to the random search principle of single-point radioactive sources, we search several nodes with large radiation dosage and then take the four small grids of small area D^′ as the centre. We mesh the area D^′, search for the maximum radiation dosage according to the random search strategy, find out the maximum point and then elaborate mesh area D″ of the four fine meshes centred on the maximum node and repeat until the position accuracy of the radiation source meets the requirement. Finally, we ascertain the radiation source, repeatedly search for the second and third sources by the above method and then discover all the radioactive sources.

Assume that a random search area D is a rectangle. There is an interval [0, a] on the X-axis, equally divide interval [0, a] and insert s−1 point in the interval [0, a]. This is expected to be similar to inserting t interior points into the interval [0, b] on the Y-axis. Then we obtain the set of points E_s × E_t = {(x_i, y_j)|i = 1,2,… s, j = 1,2, … t} of the area D, 0 ≤ s ≤ m, 0 ≤ t ≤ n. Using the k-level hierarchical search strategy, we divide the area D into D_{s × t} with S rows and t columns. The first-level random search under the coarse grid is carried out, and it becomes possible to ascertain the maximum point (x, y). We select the four networks (x, y)-centred as region D^′ and then mesh region D^′ into $D_{s \times t}^{'}$ D_{s \times t}^{'} .

Second-level Random Search is used to determine the maximum point (x₁, y₁) in the region $D_{s \times t}^{'}$ D_{s \times t}^{'} , and then we select the four grids centred on (x₁, y₁) as area D^″. We divide D^″ into $D_{s \times t}^{″}$ D_{s \times t}^{''} , and then find out the maximum point (x₂, y₂); this cyclical strategy continues until we are able to ascertain the radiation source. Output the maximum point (x_k₋₁, y_k₋₁). The schematic diagram is shown in Figure ??.

Algorithm 9: Hierarchical Random Search Algorithm

Step 1. Divide the D area into D_{s × t}, 0 ≤ s ≤ m, 0 ≤ t ≤ n.

Step 2. Radiation dosage maximum point (x, y) for region D_{s × t} (call Algorithm 8)

Step 3. Perform a fine search for each of the maximum point (x, y).

Step 3.1. Select (x, y) to cover the area D^′, with (x, y) as the centre, select the Area D^″ in the D_{s × t}.

Step 3.2. Return to step 1 for area D^″ until the division reaches the required m × n.

Step 4. Output all the source point coordinates.

Schematic diagram of K-level hierarchical random search

Here are some explanations for the hierarchical random search. Under the fine mesh, sometimes, the dosage changes a little or might even remain without change. It may cause the neighbour set comparison algorithm to fail, and since the distance between adjacent grid nodes is large and the radiation dosage data of the grid node changes significantly, the random search of the neighbouring radiation dosage comparison is facilitated. The hierarchical random search uses fewer grid nodes; so, the time complexity and space complexity are small.

3.4

Analysis of time complexity of random search

3.4.1

Time complexity of the random search

There are two kinds of algorithm complexity, time complexity and space complexity. Time complexity refers to the computational effort required to execute an algorithm. Space complexity refers to the memory space needed to implement the algorithm. (The complexity of the algorithm is reflected in the number of resources required by the computer when running the algorithm. The most important among computer resources are the time and space [i.e. storage] resources; so, the complexity is divided into time and space complexity).

The random search algorithm is simple and feasible, and it has strong operability and conforms to the actual search situation. Now we analyse the complexity, running time and storage space of the algorithm. We randomly generate the position coordinate of the search starting point (i, j); and the average time complexity of the random search of the single-point radioactive source is $θ (\frac{m + n}{3})$ \theta \left({{{m + n} \over 3}} \right) , where mmmm m is the number of rows and nnnn n is the number of columns in the grid.

Theorem 1

The average time complexity of random search for single-point radioactive source is $θ (\frac{m + n}{3})$ \theta \left({{{m + n} \over 3}} \right) , and the average space complexity is θ (m + n).

Proof

$\frac{\sum_{i^{*} = 1}^{n} \sum_{j^{*} = 1}^{m} \sum_{i = 1}^{n} \sum_{j^{*} = 1}^{m} {| i^{*} - i | + | j^{*} - j |}}{{(mn)}^{2}} = \frac{m^{2} \sum_{i^{*} = 1}^{n} \sum_{i = 1}^{n} | i^{*} - i | + n^{2} \sum_{j^{*} = 1}^{m} \sum_{j = 1}^{m} | j^{*} - j |}{{(mn)}^{2}}$ {{{\sum_{{i^*} = 1}^n }{\sum_{{j^*} = 1}^m }{\sum_{i = 1}^n }{\sum_{{j^*} = 1}^m } \left\{ {\left| {{i^*} - i} \right| + \left| {{j^*} - j} \right|} \right\}} \over {{{\left({mn} \right)}^2}}} = {{{m^2}{\sum_{{i^*} = 1}^n }{\sum_{i = 1}^n }\left| {{i^*} - i} \right| + {n^2}{\sum_{{j^*} = 1}^m }{\sum_{j = 1}^m }\left| {{j^*} - j} \right|} \over {{{\left({mn} \right)}^2}}}

First, we calculte the summation in the horizontal direction, as follows: $\begin{array}{l} \sum_{i^{*} = 1}^{n} \sum_{i = 1}^{n} | i^{*} - i | & = \sum_{i^{*} = 1}^{n} [(i^{*} - 1) + (i^{*} - 2) + \dots + 1 + 0 + 1 + 2 + \dots (n - i^{*})] \\ = \sum_{i^{*} = 1}^{n} {[1 + 2 + \dots + (i^{*} - 1)] + [1 + 2 + \dots + (n - i^{*})]} \\ = \sum_{i^{*} = 1}^{n} {\frac{[(i^{*} - 1) + 1] (i^{*} - 1)}{2} + \frac{(n - i^{*} + 1) (n - i^{*})}{2}} \\ = \sum_{i^{*} = 1}^{n} [\frac{i^{*} (i^{*} - 1)}{2} + \frac{(n - i^{*} - 1) (n - i^{*})}{2}] \\ = \sum_{i^{*} = 1}^{n} \frac{i^{*}^{2}}{2} - \sum_{i^{*} = 1}^{n} \frac{i^{*}}{2} + \sum_{i^{*} = 1}^{n} \frac{n^{2}}{2} - \sum_{i^{*} = 1}^{n} n i^{*} + \sum_{i^{*} = 1}^{n} \frac{i^{*}^{2}}{2} - \sum_{i^{*} = 1}^{n} \frac{i^{*}}{2} + + \sum_{i^{*} = 1}^{n} \frac{n}{2} \\ = \sum_{i^{*} = 1}^{n} i^{*}^{2} - \sum_{i^{*} = 1}^{n} i^{*} + \sum_{i^{*} = 1}^{n} \frac{n^{2} + n}{2} - \sum_{i^{*} = 1}^{n} n i^{*} = \frac{n^{3} - n}{3} . \end{array}$ \matrix{{{\sum_{{i^*} = 1}^n}{\sum\limits_{i = 1}^n}\left| {{i^*} - i} \right|} \hfill & {= {\sum_{{i^*} = 1}^n}\left[ {\left({{i^*} - 1} \right) + \left({{i^*} - 2} \right) +\cdots+ 1 + 0 + 1 + 2 +\cdots \left({n - {i^*}} \right)} \right]} \hfill\cr{} \hfill & {= {\sum\limits_{{i^*} = 1}^n}\left\{{\left[ {1 + 2 +\cdots+ \left({{i^*} - 1} \right)} \right] + \left[ {1 + 2 +\cdots+ \left({n - {i^*}} \right)} \right]} \right\}} \hfill\cr{} \hfill & {= {\sum\limits_{{i^*} = 1}^n}\left\{{{{\left[ {\left({{i^*} - 1} \right) + 1} \right]\left({{i^*} - 1} \right)} \over 2} + {{(n - {i^*} + 1)\left({n - {i^*}} \right)} \over 2}} \right\}} \hfill\cr{} \hfill & {= {\sum\limits_{{i^*} = 1}^n}\left[ {{{{i^*}\left({{i^*} - 1} \right)} \over 2} + {{(n - {i^*} - 1)\left({n - {i^*}} \right)} \over 2}} \right]} \hfill\cr{} \hfill & {= {\sum\limits_{{i^*} = 1}^n}{{{i^*}^2} \over 2} - {\sum\limits_{{i^*} = 1}^n}{{{i^*}} \over 2} + {\sum\limits_{{i^*} = 1}^n}{{{n^2}} \over 2} - {\sum\limits_{{i^*} = 1}^n}n{i^*} + {\sum\limits_{{i^*} = 1}^n}{{{i^*}^2} \over 2} - {\sum\limits_{{i^*} = 1}^n}{{{i^*}} \over 2} ++ {\sum\limits_{{i^*} = 1}^n}{n \over 2}} \hfill\cr{} \hfill & {= {\sum\limits_{{i^*} = 1}^n}{i^*}^2 - {\sum\limits_{{i^*} = 1}^n}{i^*} + {\sum\limits_{{i^*} = 1}^n}{{{n^2} + n} \over 2} - {\sum\limits_{{i^*} = 1}^n}n{i^*} = {{{n^3} - n} \over 3}.} \hfill\cr}

Similarly, we calculate the summation in the vertical direction, as follows: $\sum_{j^{*} = 1}^{n} \sum_{j = 1}^{n} | j^{*} - j | = \frac{m^{3} - m}{3};$ {\sum_{{j^*} = 1}^n}{\sum_{j = 1}^n}\left| {{j^*} - j} \right| = {{{m^3} - m} \over 3}; then the complexity of average search time S(n) of a single-point source is given by (2) $\frac{\sum_{i^{*} = 1}^{n} \sum_{j^{*} = 1}^{m} \sum_{i = 1}^{n} \sum_{j^{*} = 1}^{m} {| i^{*} - i | + | j^{*} - j |}}{{(mn)}^{2}} = \frac{m + n}{3} - \frac{1}{3} (\frac{1}{n} + \frac{1}{m}) = \frac{\frac{m^{2} (n^{3} - n)}{3} + \frac{n^{2} (m^{3} - m)}{3}}{{(mn)}^{2}}$ {{{\sum\nolimits_{{i^*} = 1}^n }{\sum\nolimits_{{j^*} = 1}^m }{\sum\nolimits_{i = 1}^n }{\sum\nolimits_{{j^*} = 1}^m }\left\{ {\left| {{i^*} - i} \right| + \left| {{j^*} - j} \right|} \right\}} \over {{{\left({mn} \right)}^2}}} = {{m + n} \over 3} - {1 \over 3}\left({{1 \over n} + {1 \over m}} \right) = {{{{{m^2}\left({{n^3} - n} \right)} \over 3} + {{{n^2}\left({{m^3} - m} \right)} \over 3}} \over {{{\left({mn} \right)}^2}}}

Therefore, the complexity of running time average T (n) of the random search is $θ (\frac{m + n}{3})$ \theta \left({{{m + n} \over 3}} \right) , and the average running space complexity is θ (m + n).

If n = max {m, n}, then $θ (\frac{m + n}{3}) \leq θ (\frac{2 n}{3})$ \theta \left({{{m + n} \over 3}} \right) \le \theta \left({{{2n} \over 3}} \right) and the average time that the random search algorithm runs is linear. To verify the time of the random search algorithm, we design a simulation experiment of the random search algorithm to test the complexity. The number of random search steps can indicate the complexity of the random search algorithm. The simulation results can better reflect the linearity of the random search algorithm complexity.

3.4.2

Spatial complexity analysis of random search algorithm

The following analysis analyses the storage space required to search for humans when randomly searching for radioactive sources. The spatial complexity of a program is the amount of memory needed to run a program. In addition to the instructions, constants, variables and input data used by the storage space and the storage itself, a program needs some work units that operate on the data and an auxiliary space that stores some information required for real-world calculations. The storage space required for program execution includes the following two parts.

Fixed space: The size of this part of space is independent of the number of data input/output and the dosage. It mainly includes the space occupied by code space and data space. This part is a static space.

Variable space: This part of the space mainly includes the space allocated dynamically, and the space required for the recursive stack.

In the process of imitating the real artificial random search, it is not necessary to collect the radiation dosage of all the mesh nodes in the search area. At the randomly generated search starting point, we only compare the four points around the point and the dosage. As the subsequent nodes continue to be compared, we only compare the dosage of three points around the point. The step is continued iteratively until we are able to ascertain the location of the radiation dosage maximum point. Simulated random search requires the real-time dynamic call of radiation dosage at three points around the point; so, the simulated random search process does not require static storage space, only dynamic storage space. The average space for a single source is three times the time complexity; so, the space complexity S (n) is linear θ (n + m). If n = max{m, n}, the average space complexity S (n) is θ (2n).

Theorem 2

The complexity of average time of the k-level search for a single-point source is $θ (\frac{s + t}{3} \log_{s} n)$ \theta \left({{{s + t} \over 3}{{log}_s}n} \right) , and, the average complexity of space is θ ((s + t)log_sn).

Proof

Let s^k = n, t^k = m, then k = log_sn = log_tm. Since the hierarchical search is performed K times, and each level of random search is searched in s × t grids, the average running time complexity T (n) of each level of random search is $θ (\frac{s + t}{3})$ \theta \left({{{s + t} \over 3}} \right) ; so, K-level hierarchical random search of the average running time complexity T (n) is $θ (\frac{s + t}{3} \log_{s} n)$ \theta \left({{{s + t} \over 3}{{log}_s}n} \right) , and it is logarithmic that the average storage space complexity S (n) is θ ((s + t)log_sn).

Random search for two-point radioactive sources

If there are two point sources in the search area, the radiation field will become slightly more complex. If the two radiation sources are far away, whether the fields of the two radiation sources interfere with each other minimally or not at all, the two different radiation sources can be searched by searching one radiation source and clearing one radiation source by random searching twice. If two radiation sources are relatively close, or there are obstacles between them, the mapping results in the overlapping area of radiation measurement of two radiation sources. The overlapping regions may produce local maximum (as shown in Figure 5), but the local maximum are not radiation sources. Therefore, it is necessary to discuss the overlapping regions and how they are judged in the search of two radiation sources.

4.1

Definition and judgement of radiation field pseudo-zone of two-point radiation source

Since the radiation fields of the two radiation sources will overlap with each other, the radiation measurement value in the overlapping area will increase correspondingly, resulting in the formation of a new local maximum in the area. However, the real radiation source will not appear in the overlapping area; so, it is necessary to avoid entering the overlapping area or eliminating the random searched maximum radiation metering points after entering the field. Therefore, we define the overlapping space of the radiation source as a pseudo-area, and then give the judgement method of eliminating the maximum radiation metering points in the overlapping area.

Radiometric values near the radiation source will increase dramatically and rapidly, but in the overlapping area, the increase of radiation measurement values is relatively flat and slow, i.e. the trend of the change rate of radiation measurement is characterised by monotonous decrease. We use this feature to define the pseudo-zone of the overlapping area of the radiation measurement field.

If there are two radiation sources in the searched rectangular region D, we can set them as S₁ and S₂ respectively, which can produce strong radiation areas of overlapping pseudo-regions; and region D₁ is the overlapping areas of radiation fields of two radiation sources in region D (as shown in Figure 6). Let the radiation dosage function on the plane region D, and the second-order partial derivatives exist and are $\frac{\partial^{2} f (x, y)}{\partial y^{2}}$ {{{\partial ^2}f\left({x,y} \right)} \over {\partial {y^2}}} and $\begin{array}{l} \frac{\partial^{2} f (x, y)}{\partial x^{2}} = \lim_{x \to 0} \frac{\partial f (x + x, y) - \partial f (x, y)}{x}, \\ \frac{\partial^{2} f (x, y)}{\partial y^{2}} = \lim_{y \to 0} \frac{\partial f (x, y + y) - \partial f (x, y)}{y} \end{array}$ \matrix{{{{{\partial ^2}f\left({x,y} \right)} \over {\partial {x^2}}} = \mathop {\lim}\limits_{x \to 0} {{\partial f\left({x + x,y} \right) - \partial f\left({x,y} \right)} \over x},} \hfill\cr{{{{\partial ^2}f\left({x,y} \right)} \over {\partial {y^2}}} = \mathop {\lim}\limits_{y \to 0} {{\partial f\left({x,y + y} \right) - \partial f\left({x,y} \right)} \over y}} \hfill\cr} , respectively.

\frac{\partial^{2} f (x, y)}{\partial x^{2}}

{{{\partial ^2}f\left({x,y} \right)} \over {\partial {x^2}}}

Schematic diagram of fields from two near sources radiation superposition field

Definition 1

Let f (x, y) be the dosage distribution function in the area D. ∀(x, y) ∈ D₁, if D₁ ∈ D, there are $\frac{\partial^{2} f (x, y)}{\partial x^{2}} \leq 0 and \frac{\partial^{2} f (x, y)}{\partial y^{2}} \leq 0,$ {{{\partial ^2}f\left({x,y} \right)} \over {\partial {x^2}}} \le 0\;{\rm{and}}\;{{{\partial ^2}f\left({x,y} \right)} \over {\partial {y^2}}} \le 0, where the region D₁ is the pseudo-region corresponding to the radiation dosage field D, referred to as the radiation field pseudo-region. We call all points as pseudo-points in a pseudo-region (Figure 6).

Since the search only knows the radiation dosage of grid nodes, the radiation dosage function in the search area is unknown. In practice, it is difficult to get the analytic expression of radiation dosage function; so, it is impossible to use Definition 1 to judge the pseudo-region directly. In this paper, we construct the differential expression to approximate the pseudo-region by using the radiation dosage of the collected discrete grid nodes. The we proceed to give the definition of pseudo-region.

Definition 2

Assume that the set of points consisting of grid nodes in overlapping area D₁ is E; if the radiation dosage f (i, j) of ∀(i, j) ∈ E satisfies $f (i, j) - f (i - 1, j) > f (i + 1, j) - f (i, j),$ f\left({i,j} \right) - f\left({i - 1,j} \right) > f\left({i + 1,j} \right) - f\left({i,j} \right), then D₁ is called the pseudo-region corresponding to the radiation dosage field D.

If there are multiple radiation sources in the area, the radiation dosage fields of numerous radiation sources will be superimposed to form multiple pseudo-regions. The means to avoid entering the pseudo-regions or to jump out of the pseudo-regions after entering the pseudo-regions must be considered in a random search. To enable random search to adopt multiple radiation sources, we design the pseudo-point discrimination algorithm, as follows. We form all the pseudo-points in the pseudo-area corresponding to the radiation dosage field.

Algorithm 10: Distinguish Pseudo-point Algorithm

Step 1. Input the maximum point (i, j) ∈ D.

Step 2. If f (i − 1, j) − f (i − 2, j) > f (i, j) − f (i − 1, j) then output the pseudo-zone (i, j) and mark as 1, otherwise output (i,j) is not pseudo-dot and marked as 0.

4.2

Search area division of two-point radioactive sources

We completely cover the searching region D by two radiation sources; the locations of (i, j) and (i^′, j^′) in the figure are randomly generated two radiation point sources, the region is D₁ a pseudo-region of radiation dosage field of two radiation sources and the searching region D is divided into two parts, H₁ and H₂, by the straight line AB in the pseudo-region D₁. $H_{1} \cup H_{2} = D, H_{1} \cap H_{2} = \emptyset,$ {H_1} \cup {H_2} = D,\quad {H_1} \cap {H_2} = \emptyset,

Then H₁, H₂ is a division of region D (Figure 7).

Diagram of two-point Radiation Source Division

Schematic diagram of improved markup random search algorithm

4.2.1

Two-point radiation source search algorithms and probability analysis

For the search of multiple sources, we first study the search of two points and then extend the search method to the search of numerous sources after clarifying the search method of two sources. For the case that there are two radiation sources in the area, we use a single-point random search strategy to search for two different radiation sources through discovery of two points.

Probability Analysis of Two-point Radiation Source Search

First, in the search area of two radiation sources, we discuss the probability of success of searching one radiation source at a time. For the problem of searching two radioactive sources, since we generate the starting point randomly, any point of the starting point in the searching area is equally possible. According to the geometric probability model, the probability that a random search can find a radioactive source at a time is $p = \frac{| D | - | D_{1} |}{| D |}$ p = {{\left| D \right| - \left| {{D_1}} \right|} \over {\left| D \right|}} ; among them, |D| and |D₁|, respectively, indicate the area of D, D₁.

We discuss the relationship between the size of pseudo-region and the probability of search success as follows (Table 2).

Table 2

The influence of the size of pseudo-region in the whole search area on the probability of search success

D₁	\|D₁\|<=0.5\|D\|	\|D₁\|<=0.2\|D\|	\|D₁\|<=0.05\|D\|	\|D₁\|=0
P	>=0.5	>=0.8	>=0.95	1

From the above analysis, we infer that as the proportion of pseudo-regions in the whole search area decreases, the probability of successful search for radioactive sources will gradually increase. In the actual radiation field, although there is a case of radiation field superposition, in general |D₁| ≤ 0.05|D|; so, the probability of success of random search in the area of two radiation sources is higher.

4.2.2

Multiple independent random searches for radioactive sources

We discuss two search strategies for radioactive sources. When there are two radiation sources in the radiation field, the random search will become more complex, and the pseudo-region generated by the interference superposition of radiation fields will make the search difficult. To search two radiation sources effectively, we need to design several kinds of search algorithms, among which multiple independent random searches is a simple and effective search method.

For the random search of two-point radiation sources, we adopt multiple random searches strategies, and each random search is independent of every other. Let H_ij denote that the starting point of the first random search is in the region H_j (i, j = 1,2), H_D₁ denote that the starting point of the random throwing search is D₁ and ${\bar{H}}_{D_{1}}$ {\bar H_{{D_1}}} denote that the starting point of the random search is out of the region D₁.

Consider the following two situations when K-time searching for two radiation sources:

If one source is found, the source will be removed, and the remaining one will be searched for as a single radiation source; then the probability of searching for the second radiation source for the first time is 1; so, the first radiation source will be searched only after analysing the k-1 independent repetition.

Independent repeated k(k > 2) searches can find two different sources, i.e. each source is searched at least once in the second search.

4.2.3

Random search algorithms for clearing two-point radioactive sources and their probability analysis

The idea of random searching for two-point radioactive source is to search independently and randomly for K times, and then remove the radioactive source immediately after searching for a radioactive source, and then search for the second radioactive source. Since the pseudo-region disappears after removing one radioactive source, the search for the second radioactive source is the search for a single radioactive source. However, note that when searching for the first radiation source, it is possible to enter the pseudo-zone, and the maximum point searched may be a pseudo-radiation source; so, it is necessary to judge its authenticity. See Clear Multiple Independent Random Search (Algorithm 11) for details.

Algorithm 11: Clearing Multiple Independent Random Search Algorithms

Step 1. Randomly select a point (i, j) in the area as the starting point of random search.

Step 2. For (i, j), call random search algorithm (Algorithm 8) and output termination point.

Step 3. Call the pseudo-point judgement algorithm to judge the output termination point (i, j) and –

Step 3.1. If the output point (i, j) is a radiation source, then enter to step 4.

Step 3.2. If the output point (i, j) is a radiation source, then return to step 1.

Step 4. Clearance of the First Radiation Source Point (i, j).

Step 5. Call the random search algorithm (Algorithm 8) and output termination point (i, j) that is the second radiation source.

The advantage of adding a pseudo-point judgement algorithm to the single-point random search algorithm is that the interference of the first radiation source can be used to eliminate the second radiation source after removing the first radiation source.

In the actual search, we mainly consider the number of independent random searches to find two different sources. When the number of searches is unknown, it is necessary to analyse the probability of successful searches. For two radiation source search problems, the probability that one radiation source can be successfully searched by random search at a time is $p = \frac{| D | - | D_{1} |}{| D |}$ p = {{\left| D \right| - \left| {{D_1}} \right|} \over {\left| D \right|}} .

If the independent random search is carried out k times, then we find the first radioactive source in the first search, and after clearing the radioactive source, we search for the second radioactive source for k times with probability 1. According to the knowledge of probability theory, the number of successful searches for the first source by multiple independent random searches X obeys X ~ B(k − 1, p) binomial distribution, i.e. the second search to the source is an inevitable event.

Let event A be the first radioactive source by independent k − 1 repeated searches under the clearance search strategy; then the probability of occurrence of event A is as follows: $p (A) = {(1 - p)}^{k - 2} p = {(\frac{| D_{1 |}}{| D |})}^{k - 2} \frac{| D | - | D_{1} |}{| D |} .$ p\left(A \right) = {\left({1 - p} \right)^{k - 2}}p = {\left({{{|{D_{1|}}} \over {\left| D \right|}}} \right)^{k - 2}}{{\left| D \right| - \left| {{D_1}} \right|} \over {\left| D \right|}}.

The probability of event A can also be expressed as the probability of the following events, $\begin{array}{l} P (A) & = P {{({\bar{H}}_{D_{1}})}^{k - 2} [(H_{11} {\bar{H}}_{D_{1}}) \cup (H_{22} {\bar{H}}_{D_{1}})] \\ = P (H_{11} {\bar{H}}_{D_{1}}) P ({\bar{H}}_{D_{1}}^{k - 2}) P (H_{22} {\bar{H}}_{D_{1}}) \\ = {(\frac{| D_{1} |}{| D |})}^{k - 2} \frac{| D | - | D_{1} |}{| D |} . \end{array}$ \matrix{{P\left(A \right)} \hfill & {= P\{{{\left({{{\bar H}_{{D_1}}}} \right)}^{k - 2}}\left[ {\left({{H_{11}}{{\bar H}_{{D_1}}}} \right) \cup \left({{H_{22}}{{\bar H}_{{D_1}}}} \right)} \right]} \hfill\cr{} \hfill & {= P\left({{H_{11}}{{\bar H}_{{D_1}}}} \right)P({{\bar H}_{{D_1}}}^{k - 2})P\left({{H_{22}}{{\bar H}_{{D_1}}}} \right)} \hfill\cr{} \hfill & {= {{\left({{{\left| {{D_1}} \right|} \over {\left| D \right|}}} \right)}^{k - 2}}{{\left| D \right| - \left| {{D_1}} \right|} \over {\left| D \right|}}.} \hfill\cr}

The probability results of event A obtained by the two methods are the same, which shows that the results are correct. Next, we will analyse the probability of success of the clearance random search algorithm. If $| H_{1} | = | H_{2} | = \frac{1}{2} | D |$ \left| {{H_1}\left|=\right|{H_2}} \right| = {1 \over 2}\left| D \right| and |D₁| = 0.05|D|, then the results would be as follows (Table 3).

As can be seen from the above table, if k = 2, the probability of finding two different radioactive sources is 0.95, which indicates that two random searches can be successfully found. If k = 3, the probability of random searching equals 0.0475, which means the probability of finding the second source is very small. From the above analysis, it is possible to infer that the random clearance search to the second radioactive source does not need to go to the third search at all. The second source is found in almost random search, and the probability of finding the source after the third searching is minimal. Therefore, the probability of finding the radioactive source is minimal at the tenth search. The number of machine searches is small and close to two.

In k independent random searches, the number of successful searches for the first source is X ~ B(k − 1, p), and we search for the first radioactive source by the k − 1 search; so, k needs to be satisfied. $(k - 1) p = 1, k = \frac{1}{p} + 1 .$ \left({k - 1} \right)p = 1,\quad k = {1 \over p} + 1.

For ∀p ∈ [0,1], we discuss the relationship between the number of random search times and the size of pseudo-region, which is indicated as follows (Table 4).

Table 3

Probability relationship between two times of independent random search and search success

K	K=2	K=3	K=4	K=10
P	0.95	0.0475	2.375^*10⁻³	<=3.71^*10⁻¹¹

Table 4

The number of random searches and the size of pseudo-regions

\|D₁\|	\|D₁\|<=0.5\|D\|	\|D₁\|<=0.2\|D\|	\|D₁\|<=0.05\|D\|	\|D₁\|=0

P	>=0.5	>=0.8	>=0.95	1
K	<=3	<=2.25	<=2.053	2

From the above analysis, we infer that with the decrease of the proportion of pseudo-area to the whole search area, the probability of successful search increases gradually. In the actual radiation field, although there is a case of radiation field superposition, in general |D₁| ≤ 0.5|D|, and the number of successful searches for a radiation source is not more than twice (the number of radiation sources), which is consistent with the results of previous random search success probability analyses.

Time complexity analysis of multiple independent random search is performed as follows:

If ∀P ∈ [λ₁,λ₂] ⊂ [0,1], $\frac{1}{λ_{2}} \leq \frac{1}{p} \leq \frac{1}{λ_{1}}$ 1 \over {{\lambda _2}}} \le {1 \over p} \le {1 \over {{\lambda _1}}} , then (3) $(\frac{1}{λ_{2}} + 1) \frac{m + n}{3} \leq (\frac{1}{p} + 1) \frac{m + n}{3} \leq (\frac{1}{λ_{1}} + 1) \frac{m + n}{3}$ \left({{1 \over {{\lambda _2}}} + 1} \right){{m + n} \over 3} \le \left({{1 \over p} + 1} \right){{m + n} \over 3} \le \left({{1 \over {{\lambda _1}}} + 1} \right){{m + n} \over 3} (4) $T (n) = k (\frac{m + n}{3}) = (\frac{1}{p} + 1) \frac{m + n}{3} \leq (\frac{1}{λ_{1}} + 1) \frac{m + n}{3} .$ T\left(n \right) = k\left({{{m + n} \over 3}} \right) = \left({{1 \over p} + 1} \right){{m + n} \over 3} \le \left({{1 \over {{\lambda _1}}} + 1} \right){{m + n} \over 3}.

Therefore, the time complexity T (n) and spatial complexity analysis S (n) of clearing multiple independent random searches are also linear.

4.2.4

Random search algorithms for marked two-point radioactive sources

4.2.4.1

Random search algorithms for marked two-point radioactive sources

When two radioactive sources search randomly for many times independently, the radiation dosage of nodes in the area will change correspondingly after removal of one radioactive source and update the grid node data. In the independent repeated search, we only label the searched radiation source and continue the random search. See the marked random search algorithm (Algorithm 12) for details.

Algorithm 12: Marked Random Search Algorithms

Step 1. n = 1

Step 2. Random selection of a point (i, j) in the search area is the starting point of random search.

Step 3. For (i, j), call random search optimisation algorithm (Algorithm 8), output the first radiation source point (i_n, j_n) and mark this point.

Step 4. n = n + 1

Step 5. Invoke random search optimisation algorithm (Algorithm 8) for the search area, and the output termination point (i_n, j_n) is given.

Step 6. Determine whether (i_n, j_n) is the first source of radiation,

If (i₀, j₀) = (i_n, j_n), then return to step 5.

If (i₀, j₀) ≠ (i_n, j_n), then output the second source (i_n, j_n).

It shows that the marked random search can remove the radioactive source without searching for a radioactive source. Therefore, we add a link facilitating comparison of the newly searched radioactive source with the first searched radioactive source to make up for the obstacle of searching caused by not clearing the radioactive source. Of course, we carry out the second random search after finding the first source. We enable the second search to approach the second source quickly and avoid repeating the search for the first source or entering the pseudo-area. Further, we generate the random starting point far away from the first source, so that the possibility of the second search for the second source is increased. This is shown by the algorithm of marked random search optimisation (Algorithm 13).

Algorithm 13: Marked Random Search Optimisation Algorithm

Step 1. Random selection of a point (i, j) in the search area is the starting point of random search.

Step 2. For (i, j), call random search optimisation algorithm (Algorithm 8), output the first radiation source point (i_n, j_n) and mark this point.

Step 3. With (i, j) as the centre and the shortest distance from the four edges of (i, j) to the boundary of the search area as the radius, intersect the circle with the three other segments d₂, d₃, d₄ at A, B, C, respectively.

Step 4. Taking the maximum radiation dosage points of A, B, C as the starting point of random search (i, j), invoke the random search optimisation algorithm (Algorithm 8) for (i, j); and the output termination point (i, j) is the second radiation source.

Compared with the general marker random search algorithm, the marker random search optimisation algorithm enhances the design of jumping out of the search to get the first radiation region. To avoid the second search entering the range of the first source or the low dosage area, let Order d₁, d₂, d₃, d₄ be the distance from the first radiation source to the four edges of the search area. We choose the shortest d₁ as the radius to draw a circle, and intersect the other three lines at points A, B and C. We select the maximum radioactive dosage point of the three points as the starting point of the random search to continue searching for the second one.

In the random search experiment, we hope to find the probability of success of two different radioactive sources under the given search times. In the marker independent sub-random search, we discuss two cases separately: Finding the two various radioactive sources only after conducting the possible search several times; and finding the two different radioactive sources after the search times.

4.2.4.2

Probability analysis of search k times

(1) The first radioactive source was searched only once in the first k − 1 search

In this case, the search for the first source is once in the first k − 1 search, and in the kth search we happened to find the second source. Let the probability of finding the first radiation source be p₁ and the probability of searching the second radiation source be p₂. Applying the knowledge of binomial distribution in probability theory, it is easy to know the probability of successful searching; thus $p = 2 C_{k - 1}^{1} {(1 - p)}^{k - 2} p_{1} p_{2} = 2 (k - 1) {(\frac{| D_{1} |}{| D |})}^{k - 2} \frac{| H_{1} | - \frac{1}{2} | D_{1} |}{| D |} \frac{| H_{1} | - \frac{1}{2} | D_{1} |}{| D |} .$ p = 2C_{k - 1}^1{\left({1 - p} \right)^{k - 2}}{p_1}{p_2} = 2\left({k - 1} \right){\left({{{\left| {{D_1}} \right|} \over {\left| D \right|}}} \right)^{k - 2}}{{\left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{{\left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}.

Similarly, we regard K searches as independent events to calculate the probability of successful searches. $\begin{array}{l} p = & \sum_{i = 1}^{k - 1} P ((H_{i 1} {\bar{H}}_{D_{1}}) H_{D_{1}}^{k - 2} (H_{k 2} {\bar{S}}_{D_{1}})) + \sum_{i = 1}^{k - 1} P ((H_{i 2} {\bar{H}}_{D_{1}}) H_{D_{1}}^{k - 2} (H_{k 1} {\bar{H}}_{D_{1}})) \\ = \sum_{i = 1}^{k - 1} P (H_{i 1} {\bar{H}}_{D_{1}}) P (H_{D_{1}}^{k - 2}) P (H_{k 2} {\bar{S}}_{D_{1}}) + \sum_{i = 1}^{k - 1} P (H_{i 2} {\bar{H}}_{D_{1}}) P (H_{D_{1}}^{k - 2}) P (H_{k 1} {\bar{H}}_{D_{1}}) \\ = 2 (k - 1) {(\frac{| D_{1} |}{| D |})}^{k - 2} \frac{| H_{1} | - \frac{1}{2} | D_{1} |}{| D |} \frac{| H_{2} | - \frac{1}{2} | D_{1} |}{| D |} . \end{array}$ \matrix{{p =} \hfill & {\mathop {\sum\limits_{i = 1}^{k - 1}}\limits_ P\left({\left({{H_{i1}}{{\bar H}_{{D_1}}}} \right)H_{{D_1}}^{k - 2}\left({{H_{k2}}{{\bar S}_{{D_1}}}} \right)} \right) + \mathop {\sum\limits_{i = 1}^{k - 1}}\limits_ P\left({\left({{H_{i2}}{{\bar H}_{{D_1}}}} \right)H_{{D_1}}^{k - 2}\left({{H_{k1}}{{\bar H}_{{D_1}}}} \right)} \right)} \hfill\cr{} \hfill & {= \mathop {\sum\limits_{i = 1}^{k - 1}}\limits_ P\left({{H_{i1}}{{\bar H}_{{D_1}}}} \right)P\left({H_{{D_1}}^{k - 2}} \right)P\left({{H_{k2}}{{\bar S}_{{D_1}}}} \right) + \mathop {\sum\limits_{i = 1}^{k - 1}}\limits_ P\left({{H_{i2}}{{\bar H}_{{D_1}}}} \right)P\left({H_{{D_1}}^{k - 2}} \right)P\left({{H_{k1}}{{\bar H}_{{D_1}}}} \right)} \hfill\cr{} \hfill & {= 2\left({k - 1} \right){{\left({{{|{D_1}|} \over {\left| D \right|}}} \right)}^{k - 2}}{{\left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{{\left| {{H_2}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}.} \hfill\cr}

If $| H_{1} | = | H_{2} | = \frac{1}{2} | D |$ \left| {{H_1}} \right| = \left| {{H_2}} \right| = {1 \over 2}\left| D \right| , |D₁| = 0.1|D|, then the probability of randomly searching for two different sources is shown in the table below (Table 5).

Table 5

The relationship between the increase in random search times and the probability of successful search

K	k=2	k=3	k=10
P	0.405	0.081	3.645 × 10⁻⁸

When k = 2, the probability of randomly searching for two different sources is 0.405. When k = 10, the probability of randomly searching for two different sources is 3.645 × 10⁻⁸; it shows that the probability that the starting point of eight searches in 10 random searches falls in the pseudo-area is very small.

(2) In the first k − 1 search, the first radioactive source was searched m (2 ≤ m ≤ k − 1) times

If we find one source in the k − 1 search and the first source is repeatedly searched m times in the k − 1 search, and the second different source is exactly searched in the k − 1 search, the probability of successful searching for the two sources is as follows: $\begin{array}{l} p & = \sum_{m = 1}^{k - 1} C_{k - 1}^{m} P ({(H_{m 1} {\bar{H}}_{D_{1}})}^{m} H_{D_{1}}^{k - 1 - m} (H_{k 2} {\bar{H}}_{D_{1}})) + \sum_{m = 1}^{k - 1} C_{k - 1}^{m} P ({(H_{i 2} {\bar{H}}_{D_{1}})}^{i} H_{D_{1}}^{k - 1 - m} (H_{k 1} {\bar{H}}_{D_{1}}) \\ = (k - 1) (\frac{| H_{1} | - \frac{1}{2} | D_{1} |}{| D |} \frac{| H_{2} | - \frac{1}{2} | D_{1} |}{| D |} {(\frac{| H_{1} | + \frac{1}{2} | D_{1} |}{| D |})}^{k - 2} + (\frac{| H_{1} | - \frac{1}{2} | D_{1} |}{| D |} \frac{| H_{2} | - \frac{1}{2} | D_{1} |}{| D | - | D_{1} |} {(\frac{| H_{2} | + \frac{1}{2} | D_{1} |}{| D |})}^{k - 2}) . \end{array}$ \matrix{p \hfill & {= {\sum\limits_{m = 1}^{k - 1}}C_{k - 1}^mP\left({{{\left({{H_{m1}}{{\bar H}_{{D_1}}}} \right)}^m}H_{{D_1}}^{k - 1 - m}\left({{H_{k2}}{{\bar H}_{{D_1}}}} \right)} \right) + {\sum\limits_{m = 1}^{k - 1}}C_{k - 1}^mP({{\left({{H_{i2}}{{\bar H}_{{D_1}}}} \right)}^i}H_{{D_1}}^{k - 1 - m}\left({{H_{k1}}{{\bar H}_{{D_1}}}} \right)} \hfill\cr{} \hfill & {= \left({k - 1} \right)({{\left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{{\left| {{H_2}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{{\left({{{\left| {{H_1}} \right| + {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}} \right)}^{k - 2}} + \left({{{\left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{{\left| {{H_2}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right| - \left| {{D_1}} \right|}}{{\left({{{\left| {{H_2}} \right| + {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}} \right)}^{k - 2}}} \right).} \hfill\cr} due to $p \geq \sum_{i = 1}^{k - 1} P ((H_{i 1} {\bar{H}}_{D_{1}}) D_{1}^{k - 2} (H_{k 2} {\bar{H}}_{D_{1}}) + \sum_{i = 1}^{k - 1} P ((H_{i 2} {\bar{H}}_{D_{1})} D_{1}^{k - 2} (H_{k 1} {\bar{H}}_{D_{1}})$ p \ge \mathop {\sum\limits_{i = 1}^{k - 1}}\nolimits_ P(\left({{H_{i1}}{{\bar H}_{{D_1}}}} \right)D_1^{k - 2}\left({{H_{k2}}{{\bar H}_{{D_1}}}} \right) + \mathop {\sum\limits_{i = 1}^{k - 1}}\nolimits_ P(({H_{i2}}{\bar H_{{D_1})}}D_1^{k - 2}\left({{H_{k1}}{{\bar H}_{{D_1}}}} \right) ; so, $p \geq 2 \frac{| H_{1} | - \frac{1}{2} | D_{1} |}{| D |} \frac{| H_{2} | - \frac{1}{2} | D_{1} |}{| D |} {(\frac{| D_{1} |}{| D |})}^{k - 2}$ p \ge 2{{\left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{{\left| {{H_2}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{\left({{{\left| {{D_1}} \right|} \over {\left| D \right|}}} \right)^{k - 2}} .

We analyse the complexity of markup independent random search. We find the two different sources only after searching; so, the search time complexity T (n) of successful searching for two sources is $θ (k \frac{m + n}{3})$ \theta \left({k{{m + n} \over 3}} \right) . Spatial complexity S(n) is θ (k (m + n)); so, the number of data points collected in the actual search is about k (m + n).

4.2.4.3

Probability analysis of finding two different sources

In the actual search process, we are concerned about not only how many independent searches are needed to search for the radioactive source but also the probability of searching for two different radioactive sources in the case of k searches, i.e. of having each radioactive source searched at least once as part of these k searches.

The probability of finding two different radiation sources by calculating k times is as follows: from the perspective of opposing events, the probability of successful search is given by $p = 1 - C_{k}^{1} \frac{| H_{1} | - \frac{1}{2} | D_{1} |}{| D |} {(\frac{| H_{1} | + \frac{1}{2} | D_{1} |}{| D |})}^{k - 1} - C_{k}^{1} \frac{| H_{2} | - \frac{1}{2} | D_{1} |}{| D |} {(\frac{| H_{2} | + \frac{1}{2} | D_{1} |}{| D |})}^{k - 1} - {(\frac{| D |}{| D |})}^{k} .$ p = 1 - C_k^1{{\left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{\left({{{\left| {{H_1}} \right| + {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}} \right)^{k - 1}} - C_k^1{{\left| {{H_2}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{\left({{{\left| {{H_2}} \right| + {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}} \right)^{k - 1}} - {\left({{{\left| D \right|} \over {\left| D \right|}}} \right)^k}.

Next, we discuss the probability of finding two different sources by searching k times independently when k takes different values.

When $| H_{1} | = | H_{2} | = \frac{1}{2} | D |$ \left| {{H_1}} \right| = \left| {{H_2}} \right| = {1 \over 2}\left| D \right| , if |D₁| ≤ 0.1|D|, then the probability of randomly searching for two different sources is as shown below (Table 6).

Table 6

The relationship between the increase in random search times and the probability of successful search

K	k=3	k=4	k=5
P	0.182	0.588	0.959

It can be seen from the table that as long as the number of searches is increased, the probability of successful search will increase, thereby ensuring that all radioactive sources can be searched for probabilistic analysis. We perform the random search twice to ascertain the probability of two different sources. $p = 2 \frac{| D | - | H_{1} | - \frac{1}{2} | D_{1} |}{| D |} \frac{| H_{1} | - \frac{1}{2} | D_{1} |}{| D |},$ p = 2{{\left| D \right| - \left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}{{\left| {{H_1}} \right| - {1 \over 2}\left| {{D_1}} \right|} \over {\left| D \right|}}, and ${\begin{array}{l} 0 \leq | D_{1} | \leq | D | \\ 0 \leq \frac{1}{2} | D_{1} | \leq | H_{1} | \\ | H_{1} | + \frac{1}{2} | D_{1} | \leq | D |, \end{array} then {\begin{array}{l} 0 \leq | D_{1} | \leq | H_{1} | \\ 2 | H_{1} | + | D_{1} | \leq 2 | D | \end{array} .$ \left\{{\matrix{{0 \le \left| {{D_1}} \right| \le \left| D \right|} \hfill\cr{0 \le {1 \over 2}\left| {{D_1}} \right| \le \left| {{H_1}} \right|} \hfill\cr{\left| {{H_1}} \right| + {1 \over 2}\left| {{D_1}} \right| \le \left| D \right|,} \hfill\cr}} \right.\;{\rm{then}}\;\left\{{\matrix{{0 \le \left| {{D_1}} \right| \le \left| {{H_1}} \right|} \hfill\cr{2\left| {{H_1}} \right| + \left| {{D_1}} \right| \le 2\left| D \right|} \hfill\cr}} \right..

Order |D₁| = x, |H₁| = y, |D| = d, then ${\begin{array}{l} 0 \leq x \leq 2 y \\ x + 2 y \leq 2 d \neq 0, \end{array}$ \left\{{\matrix{{0 \le x \le 2y} \hfill\cr{x + 2y \le 2d \ne 0,} \hfill\cr}} \right. so $p = 2 \frac{(d - y - \frac{1}{2} x) (y - \frac{1}{2} x)}{d^{2}} .$ p = 2{{\left({d - y - {1 \over 2}x} \right)\left({y - {1 \over 2}x} \right)} \over {{d^2}}}.

We then find partial derivatives for X and Y, respectively, as $\begin{array}{l} \frac{\partial p}{\partial x} = \frac{2}{d^{2}} (\frac{x}{2} - \frac{d}{2}) = 0 \\ \frac{\partial p}{\partial y} = \frac{2}{d^{2}} (- 2 y + d) = 0, \end{array}$ \matrix{{{{\partial p} \over {\partial x}} = {2 \over {{d^2}}}\left({{x \over 2} - {d \over 2}} \right) = 0} \hfill\cr{{{\partial p} \over {\partial y}} = {2 \over {{d^2}}}\left({- 2y + d} \right) = 0,} \hfill\cr} so $\begin{matrix} x = d \\ y = \frac{d}{2} \end{matrix}$ \matrix{{x = d}\cr{y = {d \over 2}}\cr}

This means that there is no stagnation point in the area D, as shown in Figure 9.

Schematic diagram of the selection of random probability extreme points and when $y = \frac{d}{2}$ y = {d \over 2} , let $p^{*} = \frac{{(x - d)}^{2}}{2 d^{2}}$ {p^*} = {{{{\left({x - d} \right)}^2}} \over {2{d^2}}} . For 0 ≤ x ≤ d, so $0 \leq p^{*} \leq \frac{1}{2}$ 0 \le {p^*} \le {1 \over 2}

From the above probability analysis, it can be seen that the probability of two random searches to get two different radioactive sources generally does not exceed 0.5. In the same way, the probability that independent random search K times can search k different radioactive sources is relatively small; so, in order to improve the probability of search success, we need to optimise the random search. The related optimisation strategies will be shown in future research.

The time complexity of finding two different radioactive sources by independent random search K times is $T (n) \leq θ (k \frac{m + n}{3})$ T\left(n \right) \le \theta \left({k{{m + n} \over 3}} \right) , whereas the spatial complexity is S (n) ≤ θ (k (m + n)).

Random search for multiple point sources

There are multiple point sources of radiation coexisting in the search area. A search algorithm similar to that of two sources can be used to search for radioactive sources. At the same time, a clear search algorithm can be used to remove multiple point sources of radiation one by one until all the node radiation dosage is 0. When the clearing random search finds the radioactive source, the corresponding radiometric dosage of the radioactive source at each grid node needs to be subtracted when removing the source, and the computational complexity will increase.

The main idea of the random search optimisation algorithm for multiple radioactive sources is that the random search algorithm for a single point is used to find a radioactive source and clear one.

In order to avoid entering into the pseudo-area formed by the superposition of radiation fields of the remaining radiation sources, and quickly enter into the strong radiation field of the next radiation source, we take the previous radioactive source point as the centre, and select the shortest distance d₁ from the previous radioactive source point to the four boundaries of the search area as the radius to make a circle. The circle intersects the four vertical lines from the radioactive source at four points A, B, C, D. The starting point of the next round of random search is the maximum radiometric value point in the four points, which can effectively enter the strong radiation range of the next radiation source, and the next radiation source can be quickly searched by continuing random search (as shown in Figure 10). If the radioactive source searched randomly from this point is the discovered radioactive source, then the random search returns to the previous radioactive source point and selects the second largest radiation measurement point as the search starting point to continue the search. If the discovered radioactive source is still found, it still returns to the previous radioactive source point and selects the third largest radiation measurement point as the search starting point to continue the search. If the radiation source is still found, it returns to the upper level radiation source point, and selects the minimum radiation measurement point as the search starting point to continue the search. If all the optimised search starting points search the radiation sources that have been searched, then the search is terminated, so that all the linked radiation source points can be searched (Figure 11). Refer to the random search algorithm of single chain multiple point radioactive source (Algorithm 14) for details.

Starting point for escape from radioactive source

Algorithm 14: Random search algorithm for multiple point radioactive source

Step 1. n = 1n = 1n = 1n = 1n = 1.

Step 2. Select a random point (i, j) in the search area as the starting point of random search.

Step 3. Call random search optimisation algorithm (Algorithm 8) for (i, j), output the nth radioactive source and when the point (i_n, j_n) is obtained, mark this point.

Step 4. n = n + 1n = n + 1n = n + 1n = n + 1n = n + 1

Step 5. Search the nth radiation source and optimise the starting point of the n+1 th random search.

Step 5.1. Let the distance from (i_n, j_n) to the boundary be d₁, d₂, d₃, d₄, respectively. Use D₁ as the centre of the circle and d₁ as the radius to make a circle, and the circle intersects the four point vertical line at A, B, C, D. The order of four point radiometry is f₁ < f₂ < f₃ < f₄.

Step 5.2. Optimise the starting point of the n+1 th random search.

Step 5.2.1. Call Algorithm 8 with f₄ as random starting point, and output search result (i_n, j_n).

If point (i_n, j_n) is repeated with the previous n − 1 search result, the random search will be returned to the previous radioactive source point (i_n₋₁, j_n₋₁), and then the point f₃ will be selected as the search starting point; and outputs the results (i_n, j_n).

If (i_n, j_n) is not a searched source, then (i_n, j_n) is used as the search starting point.

Step 5.2.2. If the search result (i_n, j_n) with f₃ as the starting point is also in the previous n − 1 searches result, it will return to the previous source point (i_n₋₁, j_n₋₁); then select f₂ as the search starting point to continue searching.

If the search result (i_n, j_n) is repeated with the previous n − 1 search result, the search will be returned to the previous radioactive source (i_n₋₁, j_n₋₁). If there is no repetition, then take point (i_n, j_n) as the search starting point.

Step 5.2.3. If the search result (i_n, j_n) with f₂ as the starting point is also in the previous n − 1 searches result, it will return to the previous source point (i_n₋₁, j_n₋₁); then select f₂ as the search starting point to continue searching.

Step 5.2.4. Stop the search if the corresponding point of f₁ is the starting point of the search and the search result is still n − 1 times.

Step 5.3. Return to step 4 for the search starting point found in step 5.2.

Step 6. Output all the radioactive sources.

When the first radiation source is found, the remaining radiation field may be composed of multiple point radiation sources coexisting. Therefore, when a new radiation source is found, it is necessary to repeatedly compare with the already searched radiation source to confirm whether it is a new radiation source.

If a pseudo-radiation source point is randomly found, it is necessary to jump out of this area and generate a new search starting point outside the pseudo-area. It is possible that the minimum distance d₁ as radius is used to draw a circle and it will not be able to jump out of the pseudo-zone, so that the starting point of the new random search may enter the pseudo-zone again. When choosing the jump radius, we select the minimum radius to draw a circle that may not jump out of the pseudo-zone, so that the starting point of the new random search may enter the pseudo-zone again. So, in the actual operation, the jump radius can be flexibly selected; the second longest distance d₂ is used as the radius of jumping out of the pseudo-area to ensure escape from the pseudo-area and improve search efficiency (as shown in Figure 12).

Schematic diagram of radius selection for escaping

Orphan radiation sources out of control in the area

Next, a search starting point is generated, each starting point is tested for four times at most and the remaining k − 1 radiation sources are searched for 4(k − 1) times at most. The number of radiation sources k should be far less than n and m; so, the search running time complexity of multiple point radiation sources is $T (n) \leq θ (k \frac{m + n}{3})$ T\left(n \right) \le \theta \left({k{{m + n} \over 3}} \right) , and the space complexity is S (n) ≤ θ (k (m + n)). Since k is far less than n and m, the random search algorithm of multiple point radioactive source is also linear.

From the above discussion, it can be seen that the probability model method of random search is applicable to the search of single-point, double-point or even multiple point radioactive sources. In addition, the time and space complexity of the search for radioactive sources in all three cases are linear levels θ (m + n); so, the random search algorithm is of great help to improve the search speed and storage space of operation.

Simulation experiment

6.1

Random search simulation experiment

Random search simulation experiment of a single-point radiation source uses data of grid 1000 × 1000. The radiation source is located at (500,500), and the radiation dosage is 5.3 × 10¹¹ units (Figure 10).

In order to verify the simulation experiment effect of the random search algorithm, the algorithm is executed 100 times; the coordinate position of the searched radiation source is (500,500) in the networks, 100 starting points are randomly selected and every search result is the same. The following table gives the coordinates of 100 the random search starting points (i, j) generated randomly. The simulation experiment verifies that the design of the random search algorithm meets the actual search requirement.

6.2

The maximum correction algorithm experiment

Random search experiment of single-point radiation source maximum correction uses 1000 × 1000 as grid. The radiation source is located at (500,500) and dosage is 5.3 × 10¹¹ units. Figure 14 indicates the flow of the single-point random optimisation search.

In order to verify the maximum correction algorithm, we carry out the random search at any point, and add a circle of 0 data around the grid data. In order to verify the recognition function of the random search for data with larger misreading, especially near the peak point (20,20), the radiation dosage was increased to 5.5 × 10¹¹ unit. The point is verified by the maximum correction algorithm as the maximum point with the characteristics of a radiation source. Therefore, the design of the maximum correction algorithm meets practical needs.

6.3

Experiment of average search times of single-point radioactive source

In order to verify that the complexity of random search time is linear, we designed an experiment involving random search times and verified the correctness of the conclusion by the number of steps of random search of the radioactive source.

The verification test uses 1000 × 1000 grid data. The source is located at location (500,500), and the radiation measurement of the source is 5.3 × 10¹¹ units. A search starting point is randomly generated on the search area plane, and starting from the starting point, the random search is stopped until the movement is stopped, the number of steps of the search movement of the record is output, and the average number of random search moving steps in the experiment is obtained. The experiment was done in three groups. Each group randomly generated 1000, 10000, 100000 search starting points; the number of steps for each random search movement was recorded and from the results thus obtained, Table 7 was generated.

Table 7

Random search to find the average search step for the source

Experiment	Number of staring point	Number of searches	The average number of steps for a successful search

1	1000	1000	494
2	10000	10000	497
3	100000	100000	499

Based on the experiment, it can be ascertained that the number of moving steps of the average search success is stable at about 496 steps. According to the time complexity formula for random search based on theory, $θ (\frac{m + n}{3})$ \theta \left({{{m + n} \over 3}} \right) , the average number of moving steps is about 667 times. The actual average number of moving steps is significantly different from the calculated result. In the simulation experiment, since the source is fixed at (500, 500) and is randomly generated at the theoretical derivation, all the points of the grid need to be considered; so, the experimental search number of moving steps is 667 times larger than the experimental 496 times.

6.4

Simulation experiment of hierarchical random search

The single-point source grading search experiment uses data grid 1051 × 1051, where the source is located at (529,529), and the radiation measurement of the source is A unit. In order to verify the effectiveness of the hierarchical search experiment, the grid is divided into three levels of 1051 × 1051 in the experiment:

The first level of coarse mesh is divided into grids in the radiation field area. A data line is collected for each interval of 30 cm for x, y, and the dosages are 30, 60, 90,…, 1020, 1050, and the values are simultaneously rendered. The first-level coarse grid is obtained for 30, 60, 90,…, 1020, 1050, respectively. The coordinates of the source points randomly searched under the coarse grid are (540,540).

In the second-level meshing, at the grid node of the radioactive source obtained by the first-level random search, the field character centred on the point is selected, and a data line is collected for each interval of 10 cm for x, y in the field character lattice to obtain a local part. The grid of the second-level search represents the coordinates of the radio source point, which are (530,530), and obtained by random search under the second-level coarse grid.

In the third-level meshing, at the grid node of the radioactive source obtained by the second-level random search, the field character centred on the point is selected, and a data line is collected for each interval of 1 cm in the field character lattice to obtain a local part. The grid of the second-level search represents the coordinates of the radio source point, which are (529,529), and obtained by random search under the second-level coarse grid.

Conclusion

In this paper, we searched out-of-control point radioactive sources, adopted a human-like search experience, established random search models for single-point and multi-point radioactive sources and optimised the model for the problems that may be encountered in actual search. Theory proves that this random search algorithm has linear running speed and linear storage space. Simulation experiments prove that the algorithm is feasible.

This article discusses the search of a single-point radioactive source in detail and theoretically proves that the search algorithm is linear. Theoretical proof is not available for two-point and multi-point at present; so, future research is expected to discuss in detail the role of multi-point radioactive sources as a theoretical part of the search. At the same time, the method will be based on a two-dimensional plane search strategy. In the future, a random search strategy in three-dimensional space can be considered, and the search strategy will be more accurate.

Figures et tableaux

Schematic diagram of the selection of random probability extreme points and when

y=d2
y = {d \over 2}

, let

p*=(x−d)22d2
{p^*} = {{{{\left({x - d} \right)}^2}} \over {2{d^2}}}

. For 0 ≤ x ≤ d, so

0≤p*≤12
0 \le {p^*} \le {1 \over 2} — Schematic diagram of the selection of random probability extreme points and when y=d2 y = {d \over 2} , let p*=(x−d)22d2 {p^*} = {{{{\left({x - d} \right)}^2}} \over {2{d^2}}} . For 0 ≤ x ≤ d, so 0≤p*≤12 0 \le {p^*} \le {1 \over 2}

The relationship between the increase in random search times and the probability of successful search

K	k=3	k=4	k=5
P	0.182	0.588	0.959

Radiation dosage at the grid nodes

	x₁	x₂	x₃	…	x_n

y₁	f₁₁	f₂₁	f₃₁	…	f_n₁
y₂	f₁₂	f₂₂	f₃₂	…	f_n₂
⋮	⋮	⋮	⋮		⋮
y_m	f_1m	f_2m	f_3m	…	f_nm

Probability relationship between two times of independent random search and search success

K	K=2	K=3	K=4	K=10
P	0.95	0.0475	2.375^*10⁻³	<=3.71^*10⁻¹¹

The number of random searches and the size of pseudo-regions

\|D₁\|	\|D₁\|<=0.5\|D\|	\|D₁\|<=0.2\|D\|	\|D₁\|<=0.05\|D\|	\|D₁\|=0

P	>=0.5	>=0.8	>=0.95	1
K	<=3	<=2.25	<=2.053	2

The influence of the size of pseudo-region in the whole search area on the probability of search success

D₁	\|D₁\|<=0.5\|D\|	\|D₁\|<=0.2\|D\|	\|D₁\|<=0.05\|D\|	\|D₁\|=0
P	>=0.5	>=0.8	>=0.95	1

Random search to find the average search step for the source

Experiment	Number of staring point	Number of searches	The average number of steps for a successful search

1	1000	1000	494
2	10000	10000	497
3	100000	100000	499

Références

[1] Gladilkin, A.H., et al., Scale Installation for Radiobiological Researches (Design and Results of Experimental Researches), Energoatom, Moscow (1981) 60 pp. (in Russian). RADIOACTIVE SOURCES IN THE RUSSIAN ECONOMY 469 470 NESTEROV et al. GladilkinA.H. Scale Installation for Radiobiological Researches (Design and Results of Experimental Researches) Energoatom Moscow 1981 60 (in Russian). RADIOACTIVE SOURCES IN THE RUSSIAN ECONOMY 469 470 NESTEROV et al. Search in Google Scholar

[2] Pugachev, A.A., et al., Radioisotope Devices of Technological Control: Directory, Atomizdat, Moscow (1980) 95 pp. (in Russian). PugachevA.A. Radioisotope Devices of Technological Control: Directory Atomizdat Moscow 1980 95 (in Russian). Search in Google Scholar

[3] Stadnikia K, Henderson K, Martin A, et al. Data fusion for a vision-aided radiological detection system: Calibration algorithm performance[J]. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 2018, 890: 8–17. StadnikiaK HendersonK MartinA Data fusion for a vision-aided radiological detection system: Calibration algorithm performance[J] Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 2018 890 8 17 10.1016/j.nima.2018.01.102 Search in Google Scholar

[4] Redus R, Squillante M, Gordon J, et al. A combined video and gamma ray imaging system for robots in nuclear environments[J]. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 1994, 353(1–3): 324–327. RedusR SquillanteM GordonJ A combined video and gamma ray imaging system for robots in nuclear environments[J] Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 1994 353 1–3 324 327 10.1016/0168-9002(94)91667-5 Search in Google Scholar

[5] Ducros C, Hauser G, Mahjoubi N, et al. RICA: A tracked robot for sampling and radiological characterization in the nuclear field[J]. Journal of Field Robotics, 2017, 34(3): 583–599. DucrosC HauserG MahjoubiN RICA: A tracked robot for sampling and radiological characterization in the nuclear field[J] Journal of Field Robotics 2017 34 3 583 599 10.1002/rob.21650 Search in Google Scholar

[6] Chen Y, Cai H, Chen Z, et al. Using multi-robot active olfaction method to locate time-varying contaminant source in indoor environment[J]. Building and Environment, 2017, 118: 101–112. ChenY CaiH ChenZ Using multi-robot active olfaction method to locate time-varying contaminant source in indoor environment[J] Building and Environment 2017 118 101 112 10.1016/j.buildenv.2017.03.030 Search in Google Scholar

[7] Ardiny H, Witwicki S, Mondada F. Autonomous Exploration for Radioactive Hotspots Localization Taking Account of Sensor Limitations[J]. Sensors, 2019, 19(2): 292. ArdinyH WitwickiS MondadaF Autonomous Exploration for Radioactive Hotspots Localization Taking Account of Sensor Limitations[J] Sensors 2019 19 2 292 10.3390/s19020292635885630642085 Search in Google Scholar

[8] Alpay M E, Shor M H. Model-based solution techniques for the source localization problem[J]. Control Systems Technology IEEE Transactions on, 2000, 8(6):895–904. AlpayM E ShorM H Model-based solution techniques for the source localization problem[J] Control Systems Technology IEEE Transactions on 2000 8 6 895 904 10.1109/CDC.1998.760787 Search in Google Scholar

[9] Ristic B, Morelande M, Gunatilaka A, et al. Search for a Radioactive Source: Coordinated Multiple Observers[C]//Intelligent Sensors, Sensor Networks and Information, 2007. ISSNIP 2007. 3rd International Conference on IEEE, 2007:239–244. RisticB MorelandeM GunatilakaA Search for a Radioactive Source: Coordinated Multiple Observers[C] Intelligent Sensors, Sensor Networks and Information, 2007. ISSNIP 2007. 3rd International Conference on IEEE 2007 239 244 10.1109/ISSNIP.2007.4496850 Search in Google Scholar

[10] Hamideen M S, Sharaf J M, Alkam O. Radioactive point source localization in one, two, and three dimensions within a bulky medium[J]. Applied Radiation & Isotopes, 2010, 68(6):1160–1168. HamideenM S SharafJ M AlkamO Radioactive point source localization in one, two, and three dimensions within a bulky medium[J] Applied Radiation & Isotopes 2010 68 6 1160 1168 10.1016/j.apradiso.2010.02.00720188580 Search in Google Scholar

[11] Wacholder, E., E. Elias, and Y. Merlis, “Artificial neural networks optimization method for radioactive source localization”, Nuclear Technology, vol. 110, no. 2, pp. 228–237, 1995.J. WacholderE. EliasE. MerlisY. “Artificial neural networks optimization method for radioactive source localization” Nuclear Technology 110 2 228 237 1995 J. 10.13182/NT95-A35120 Search in Google Scholar

[12] Presler O, German U, Alfassi Z B. Radioactive point source localization in a bulky volume[J]. Nuclear Instruments & Methods in Physics Research, 2005, 547(2):628–637. PreslerO GermanU AlfassiZ B Radioactive point source localization in a bulky volume[J] Nuclear Instruments & Methods in Physics Research 2005 547 2 628 637 10.1016/j.nima.2005.03.152 Search in Google Scholar

[13] Vilim R, Klann R, RadTrac: A system for detecting, localizing, and tracking radioactive sources in real time[J], Nuclear Technology, vol. 168, no. 1, pp. 61–73, 2009. VilimR KlannR RadTrac: A system for detecting, localizing, and tracking radioactive sources in real time[J] Nuclear Technology 168 1 61 73 2009 10.13182/NT168-61 Search in Google Scholar

[14] Shixiang Ni. Single Robot Radiation Field Source Seeking Algorithms for Outdoor Environment [J]. Machinery & Electronics, 2015(9):67–71. ShixiangNi Single Robot Radiation Field Source Seeking Algorithms for Outdoor Environment [J] Machinery & Electronics 2015 9 67 71 Search in Google Scholar

[15] Zhang M, Xu Z H, liang Zou S, et al. Heuristic Search for an Unknown Nuclear Source[J]. International Journal of Simulation – Systems, Science & Technology, 2015, 16(2). ZhangM XuZ H liang ZouS Heuristic Search for an Unknown Nuclear Source[J] International Journal of Simulation – Systems, Science & Technology 2015 16 2 10.5013/IJSSST.a.16.02.12 Search in Google Scholar

[16] Liu Z. Reconstruction of urban radiation landscape using machine learning methods[D]. University of Illinois at Urbana-Champaign, 2019. LiuZ Reconstruction of urban radiation landscape using machine learning methods[D] University of Illinois at Urbana-Champaign 2019 Search in Google Scholar

[17] Gong P, Tang X B, Huang X, et al. Locating lost radioactive sources using a UAV radiation monitoring system[J]. Applied radiation and isotopes, 2019, 150: 1–13. GongP TangX B HuangX Locating lost radioactive sources using a UAV radiation monitoring system[J] Applied radiation and isotopes 2019 150 1 13 10.1016/j.apradiso.2019.04.03731108333 Search in Google Scholar

[18] Nuclear Technology Teaching and Research Department. Radiation Diametry [M]. Hengyang: University of South China, 2015:82. Nuclear Technology Teaching and Research Department Radiation Diametry [M] Hengyang University of South China 2015 82 Search in Google Scholar

Applied Mathematics and Nonlinear Sciences

Radioactive source search problem and optimisation model based on meta-heuristic algorithm

Min Zhang,Min Zhang,Xuewen Lu,Xuewen Lu,Ettiene Hoffman,Ettiene Hoffman,Radwan Kharabsheh etRadwan Kharabsheh etQianghua XiaoQianghua Xiao

Publié en ligne: 31 Mar 2022

Volume & Edition: AHEAD OF PRINT

Pages: -

Reçu: 05 May 2021

Accepté: 29 Jul 2021

Applied Mathematics and Nonlinear Sciences

Keywords

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Fig. 14

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Fig. 14

The relationship between the increase in random search times and the probability of successful search

Radiation dosage at the grid nodes

Probability relationship between two times of independent random search and search success

The number of random searches and the size of pseudo-regions

The influence of the size of pseudo-region in the whole search area on the probability of search success

Random search to find the average search step for the source

Min Zhang,
Min Zhang,
Xuewen Lu,
Xuewen Lu,
Ettiene Hoffman,
Ettiene Hoffman,
Radwan Kharabsheh et
Radwan Kharabsheh et
Qianghua Xiao
Qianghua Xiao