# Search Path Planning Algorithm Based on the Probability of Containment Model

Authors: Jia Ren; Kun Liu; Yani Cui; Wencai Du
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The location of distress object in the maritime search area is difficult to determine, which has brought great difficulties to the search path planning. Aiming at this problem, a search path planning algorithm based on the probability of containment (POC) model for a distress object is proposed. This algorithm divides the area to be searched into several subareas by grid method and dynamically evaluates the POC of the distress object in each subarea using the Monte Carlo random particle method to build the POC model. On this basis, the POC is dynamically updated by employing the Bayes criterion within the constraint of the time window. Then, the sum of the POC of the object in the subareas is regarded as the weight of the search path. And the proposed algorithm dynamically executes the search path planning according to the maximum path weight. In comparison with the parallel line search path planning algorithm given in the “International Aeronautical and Maritime Search and Rescue Manual,” the simulation results show that the search path planning algorithm based on the POC model of the distress object can effectively improve the search efficiency and the probability of search success of the distress object.


---

## Body

## 1. Introduction

Search and rescue of maritime distress target is a high-risk, difficult, time-sensitive, and professional task, and it is also the only way to search and rescue survivors [1]. Its essence is to predict the drift trajectory of the distress target, estimate the search area accurately, plan the search path reasonably, and deploy the search platform for rapid search and rescue based on the characteristic information of the sea condition, the distress target, and the last known location information in the incident area [2, 3]. However, due to the influence of many factors, such as marine meteorology, hydrological environment, and geometric characteristics of distress target, the drift trajectory of distress target in the sea area is extremely uncertain, which greatly increases the difficulty of accurately estimating the search area [4, 5]. The traditional search area estimation method is mainly based on the final known location of the distress target and the sea conditions of the incident area. The drift trajectory of the distress target is estimated through expert experience, and the search area scope is determined by this method. However, it is difficult to fully consider the potential relationship between many factors affecting the drift process of the target in distress by expert experience alone, and the accuracy is low, which affects the success rate of search and rescue. For this reason, the researchers used statistical and stochastic theory frameworks to express the drift model of the distress target and used machine learning method to estimate the drift trajectory [6–8]. In [8], a statistical model of the drift path of the distress target is constructed according to the meteorological data of the incident sea area to obtain the search area. According to the drift model based on the random particle method proposed by Allen A A and Breivik Ø, field experiments were carried out in the Tyrrhenian Sea and Sicily Strait, respectively, to verify the accuracy of the drift model to predict the search area under different parameters. Besides being related to the meteorological and hydrological environment, the geometric characteristics of the distress target should be considered further [9]. Brushett et al. [10] carried out field tests in the accident-prone waters of the Pacific Ocean to complete the determination of the downwind and crosswind drift coefficients of three small vessels of different sizes for determining the search area. In [11], based on the information such as the debris location obtained during the search, a drift inverse model was established to predict the base position of the distress target, so as to predict the search area. The abovementioned references, while using meteorological and hydrological data in the incident area, also fully consider the geometric characteristics of the distress target and have reference significance for the construction of the drift path prediction model of the distress target. However, due to the uncertainty of time and space, the whole search area cannot be completely searched by the deployed search platform in a limited time window. If the target is drifting out of the predicted search area, the search mission will fail. Therefore, efficient search path planning becomes an effective way to improve the success rate of search and rescue after the search area is determined [12, 13].Maritime search path planning is essentially a problem of coverage path planning (CPP) [14, 15]. The traditional method is to use parallel line method, extended square method, and other regular search paths in the search area for full coverage search. However, this kind of regular search path assumes that the location of distress target in search area follows equal probability distribution, and the search platform must carry out full coverage search, which will not only cause the waste of search time but also reduce the success rate of search and rescue. Yu et al. [16] used Bayes criterion to calculate the probability distribution map of the location of the distress target in the search area, and the search path planning was completed by genetic simulated annealing algorithm. But the algorithm does not consider that the probability distribution map of the distress target position will change dynamically with time. The paper [17] regarded the search path planning task as a multiconstrained objective optimization problem based on fully considering the dynamic update of the probability distribution map of the distress target location, and the improved particle swarm optimization algorithm was used to realize the dynamic planning of the search path. However, the update of the search area using the above algorithm is based on the full coverage, that is, only after completing the full coverage search of the search area or reaching the next search time, the search area is updated, which may face the invalid search and rescue caused by the drift of the distress target out of the search area.Aiming at the above problems, this paper proposes a search path planning algorithm (search path planning algorithm based on the probability of containment of distress target, POC-SPPA) based on the probability of distress target inclusion. Firstly, the algorithm uses Monte Carlo random particle method to simulate the drift motion of the distress target and realize the evaluation of the search area. Secondly, the target inclusion probability of each subsearch area is evaluated using the number of particles after the grid processing of the search area; thus, the target inclusion probability model can be constructed, and then the dynamic update of the probability of containment (POC) model according to Bayes criterion is realized. Finally, the search path planning is transformed into the maximum weight path planning problem with POC as the model weights, and the dynamic programming of the search path is realized under the constraints of the search time window.The rest of the paper is organized as follows. Section2 introduces the task scenario and problem description. The POC model of the distress target is formulated in Section 3. Section 4 proposes a search path planning algorithm based on the POC model of distress targets. Simulation results and analysis are shown in Section 5. Section 6 draws the conclusions of the work.


## 2. Task Scenario Description

### 2.1. Problem Description

The probability of success (POS) of a distress target in maritime search-rescue is determined jointly by POC of the distress target within the search area and the probability of detection (POD) of the distress target:(1)pS=pC×pD,where pS, pC, and pD refer to POS, POC, and POD of the distress target, respectively. POC is the probability that the distress target exists in the search area, which is closely related to the accurate evaluation of the search area. POD of distress target refers to the probability of successful discovery by the search platform assuming that the distress target already exists within the detection range of the search platform. It is related to sea condition, geometric characteristics of distress target, search mode of search platform, sweep width, and so on. Considering visual searching, when the distance between the search platform and the target is less than 0.1n mile, the value of pD will be close to 1 and the POS of the distress target is mainly related to the POC. At the same time, the maritime search and rescue mission has the characteristics of strong timeliness, and reasonable search path planning is also the main factor affecting the POS. Therefore, in order to improve the success rate of search and rescue, the following issues need to be addressed:(1)
The POC model of the distress target in the search area should be constructed so as to accurately evaluate the drift trajectory of the distress target and improve the prediction accuracy of the search area2. Grid processing for the search area is used to realize the dynamic evaluation of the POC of distress target in each search subarea, and on this basis, the search path planning is carried out to improve the efficiency of search and rescue.


### 2.2. Process of Maritime Search and Rescue for Distress Targets at Sea

According to the above problem description, the process of maritime search and rescue for distress targets is shown in Figure1.(1)
In the event of a maritime accident, the ship in distress sends messages (including the time, place, and characteristics of the distress target) to the Maritime Search and Rescue Centre through satellite telephones on board, land networks, medium and high frequency (MF/HF), and very high frequency (VHF) systems.(2)
After receiving the distress information, the Maritime Search and Rescue Centre first retrieves the ocean currents and meteorological data of the incident area, in order to complete the study of search task according to the distress target characteristics, and then constructs the distress target POC model to estimate the distress target drift trajectory and search area, as well as determines the search platform type. Finally, the search task instruction and all relevant information are issued to the search platform (including distress target information, ocean currents and meteorological information, sea condition, estimated drift trajectory, and search area,).(3)
The search platform receives mission instructions to prepare for the search. At the same time, the search platform divides the search area into small meshes according to the relevant information sent by the Maritime Search and Rescue Centre and the effective detection range of the carrying equipment to further determine the probability distribution of the location of the target in distress in the search area.(4)
According to the probability distribution of the location of the distress target, the search platform carries out the search path planning and starts the search and rescue mission. During the execution of the mission, the search platform will interact with the Maritime Search and Rescue Centre in real time and continuously update the probability distribution of the location of the target in distress in the search area according to the search progress, so as to dynamically adjust the search path.Figure 1
Process of maritime search and rescue for distress targets.


## 2.1. Problem Description

The probability of success (POS) of a distress target in maritime search-rescue is determined jointly by POC of the distress target within the search area and the probability of detection (POD) of the distress target:(1)pS=pC×pD,where pS, pC, and pD refer to POS, POC, and POD of the distress target, respectively. POC is the probability that the distress target exists in the search area, which is closely related to the accurate evaluation of the search area. POD of distress target refers to the probability of successful discovery by the search platform assuming that the distress target already exists within the detection range of the search platform. It is related to sea condition, geometric characteristics of distress target, search mode of search platform, sweep width, and so on. Considering visual searching, when the distance between the search platform and the target is less than 0.1n mile, the value of pD will be close to 1 and the POS of the distress target is mainly related to the POC. At the same time, the maritime search and rescue mission has the characteristics of strong timeliness, and reasonable search path planning is also the main factor affecting the POS. Therefore, in order to improve the success rate of search and rescue, the following issues need to be addressed:(1)
The POC model of the distress target in the search area should be constructed so as to accurately evaluate the drift trajectory of the distress target and improve the prediction accuracy of the search area2. Grid processing for the search area is used to realize the dynamic evaluation of the POC of distress target in each search subarea, and on this basis, the search path planning is carried out to improve the efficiency of search and rescue.


## 2.2. Process of Maritime Search and Rescue for Distress Targets at Sea

According to the above problem description, the process of maritime search and rescue for distress targets is shown in Figure1.(1)
In the event of a maritime accident, the ship in distress sends messages (including the time, place, and characteristics of the distress target) to the Maritime Search and Rescue Centre through satellite telephones on board, land networks, medium and high frequency (MF/HF), and very high frequency (VHF) systems.(2)
After receiving the distress information, the Maritime Search and Rescue Centre first retrieves the ocean currents and meteorological data of the incident area, in order to complete the study of search task according to the distress target characteristics, and then constructs the distress target POC model to estimate the distress target drift trajectory and search area, as well as determines the search platform type. Finally, the search task instruction and all relevant information are issued to the search platform (including distress target information, ocean currents and meteorological information, sea condition, estimated drift trajectory, and search area,).(3)
The search platform receives mission instructions to prepare for the search. At the same time, the search platform divides the search area into small meshes according to the relevant information sent by the Maritime Search and Rescue Centre and the effective detection range of the carrying equipment to further determine the probability distribution of the location of the target in distress in the search area.(4)
According to the probability distribution of the location of the distress target, the search platform carries out the search path planning and starts the search and rescue mission. During the execution of the mission, the search platform will interact with the Maritime Search and Rescue Centre in real time and continuously update the probability distribution of the location of the target in distress in the search area according to the search progress, so as to dynamically adjust the search path.Figure 1
Process of maritime search and rescue for distress targets.


## 3. Construction of POC Model of Distress Target

### 3.1. Drift Prediction Model of Target in Distress

Accurate prediction of drift trajectory of distress target is a prerequisite for establishing the POC model. The drift motion of the target in distress is the result of the combined action of total current, sea surface wind pressure difference, wave, and other factors. When the size of the distress target is less than 30 m, the wave has little effect on the drift motion and the effect of the wave on drift motion can be ignored [18, 19]. At this point, the drift motion of the target in distress is mainly affected by the total current and wind pressure difference. Hence, its drift dynamics model is shown as follows:(2)12CdSρWVW−VTVW−VT=12CdSρCVT−VCVT−VC,where VW, VC, and VT refer to the wind pressure differential velocity on the sea surface, the total current velocity under the sea surface, and the drift velocity of the target in distress, respectively; Cd is the drag force coefficient; S denotes the cross-sectional area; ρW and ρC, respectively, denote the density of air and sea water. Assuming that the total current and wind pressure difference are independent of each other and follow the Gaussian distribution, VT satisfies equation (3).LettingCdSρW/CdSρC=λ2 and taking the absolute value of the expression in equation (2), we can get(3)λVW−VT=VT−VC.According to equation (4), equation (2) can be rewritten as(4)λVW−VT=VT−VC.Thus, the drift velocity of the distress target without considering the wave forces can be defined as(5)VT=11+λVC+λ1+λVW=fVC+1−fVW,where(6)f=11+λ=11+CdSρW/CdSρC.Equation (5) indicates that VT can be regarded as a weighted average of VC and VW, and thus, the mean and variance satisfy(7)EVT=f⋅EVC+1−f⋅EVW,VarVT=f2⋅VarVC+1−f2⋅VarVW.According to the above analysis, the total current and wind pressure difference are determined, that is, the drift velocity of the distress target can be obtained and then the drift trajectory of the distress target can be obtained as well. Because of the high randomness of total current and wind pressure difference in the drift process, the influence factors are complex and changeable, there is space-time uncertainty, and some influence factors have strong coupling between them, so they cannot be analysed positively. Therefore, the drift trajectory of the distress target can only be predicted by probability theory [6]. For this purpose, this paper uses the Monte Carlo stochastic particle method to simulate the drift motion of the distress target, and on this basis, the POC model of the distress target is constructed.


### 3.2. POC Model of the Distress Target

If the POC model of the distress target is constructed using the Monte Carlo random particle method, the distress target is abstracted asN particles, and assuming that the motion between the particles is independent of each other and has all the drift characteristics of the distress target, the probability distribution of the particle after a period of time represents the probability distribution of the distress target at sea after drifting in the same period of time.Let us mark the drift velocity and position ofN particles as VN and LN. VN=v1,…,vn,…,vNT, LN=l1,…,ln,…,lNT, and vn and ln=lngn,latn represent the drift velocity and position of n particles, respectively. The initialization of particles is placed at the last known position of the distress target, and the drift velocity VNt of the particle at time t is randomly simulated according to equations (5)–(7). On this basis, according to the position of the particle LNt−1 at time t−1, the position of the particle LNt at time t can be obtained. At this point, the smallest rectangular region Gt containing all particles is the search region, that is, the rectangle Gt has minlngnt,minlatnt, minlngnt,maxlatnt, maxlngnt,minlatnt, maxlngnt,maxlatnt, and n∈1,2,…,N as vertical.In order to obtain the probability distribution of the location of the distress target in the search areaGt, this paper uses the grid method to divide the search area Gt into Lit×Ljt square search subareas gi,jt with d as the length of each side, where i∈1,2,…,Lit and j∈1,2,…,Ljt. The POC of the distress target pCi,jt corresponding to the search subarea gi,jt is as follows:(8)pCi,jt=Ngi,jtN.In this formula,Ngi,jt refers to the number of particles which are searched at time t in the subarea gi,jt. According to each search subarea pCi,jt, we can obtain the POC model of the distress target at time t, including the search area Gt and its corresponding POC matrix PCt=pCi,jt.Because the location of the distress target will change greatly over time, the POC model of the distress target presents the characteristics of time sensitivity. As a result, based on the search task planned by the POC model of the distress target at timet, the search platform needs complete searching in the search area Gt within the time window t,t+T, where T is the search time window and its value is related to the drift velocity of the distress target VT and the length of the search subarea d. When the search time exceeds the search time window T and the search platform has not found the distress target, it is necessary to update the POC matrix of the search area Gt according to Bayes criterion. The updated POC matrix is recorded as PCt′. On this basis, the number of particles in each search subarea is updated, and the position of the particles is reinitialized. Then, the POC model at time t+T is established, so as to realize the adaptive update of the POC model. Due to the update of the POC of the distress target pCi,jt corresponding to the search subarea gi,jt is not only related to itself but also related to the probability of detection of the distress target pDi,jt, the general updated formula of the POC matrix is shown in equation (9), and the updated formula of the number of particles in each search subarea is shown in equation (10).(9)pCi,jt′=pCi,jt⋅1−pDi,jt1−pCi,jt+pCi,jt⋅1−pDi,jt,gi,jthas been searched,pti,j1−∑gi,jt∈ZselectedtpCi,jt+∑gi,jt∈ZselectedtpCi,jt⋅1−pDi,jt,gi,jtis not searched,(10)Ngi,jt′=N⋅pCi,jt′,where pCi,jt′ represents the POC of distress targets corresponding to the updated search subarea gi,jt; pDi,jt represents the POD of the search platform corresponding to the search subarea gi,jt; Zselectedt represents the search path at time t; Ngi,jt′ represents the number of particles corresponding to the search subarea gi,jt.Note that equation (9) is the general updated formula for the POC of distress target in each search subarea, and in Section 2.1, when explaining equation (1), we point out that if taking visual searching, the distance between the search platform and the distress target is less than 0.1 n mile, the value of pD will be close to 1, and the POS of the distress target is mainly related to the POC. Therefore, this paper mainly solves the POC problem, and when we update the POC of the distress target in each search subarea according to equation (9), the value of pDi,jt is 1.


## 3.1. Drift Prediction Model of Target in Distress

Accurate prediction of drift trajectory of distress target is a prerequisite for establishing the POC model. The drift motion of the target in distress is the result of the combined action of total current, sea surface wind pressure difference, wave, and other factors. When the size of the distress target is less than 30 m, the wave has little effect on the drift motion and the effect of the wave on drift motion can be ignored [18, 19]. At this point, the drift motion of the target in distress is mainly affected by the total current and wind pressure difference. Hence, its drift dynamics model is shown as follows:(2)12CdSρWVW−VTVW−VT=12CdSρCVT−VCVT−VC,where VW, VC, and VT refer to the wind pressure differential velocity on the sea surface, the total current velocity under the sea surface, and the drift velocity of the target in distress, respectively; Cd is the drag force coefficient; S denotes the cross-sectional area; ρW and ρC, respectively, denote the density of air and sea water. Assuming that the total current and wind pressure difference are independent of each other and follow the Gaussian distribution, VT satisfies equation (3).LettingCdSρW/CdSρC=λ2 and taking the absolute value of the expression in equation (2), we can get(3)λVW−VT=VT−VC.According to equation (4), equation (2) can be rewritten as(4)λVW−VT=VT−VC.Thus, the drift velocity of the distress target without considering the wave forces can be defined as(5)VT=11+λVC+λ1+λVW=fVC+1−fVW,where(6)f=11+λ=11+CdSρW/CdSρC.Equation (5) indicates that VT can be regarded as a weighted average of VC and VW, and thus, the mean and variance satisfy(7)EVT=f⋅EVC+1−f⋅EVW,VarVT=f2⋅VarVC+1−f2⋅VarVW.According to the above analysis, the total current and wind pressure difference are determined, that is, the drift velocity of the distress target can be obtained and then the drift trajectory of the distress target can be obtained as well. Because of the high randomness of total current and wind pressure difference in the drift process, the influence factors are complex and changeable, there is space-time uncertainty, and some influence factors have strong coupling between them, so they cannot be analysed positively. Therefore, the drift trajectory of the distress target can only be predicted by probability theory [6]. For this purpose, this paper uses the Monte Carlo stochastic particle method to simulate the drift motion of the distress target, and on this basis, the POC model of the distress target is constructed.


## 3.2. POC Model of the Distress Target

If the POC model of the distress target is constructed using the Monte Carlo random particle method, the distress target is abstracted asN particles, and assuming that the motion between the particles is independent of each other and has all the drift characteristics of the distress target, the probability distribution of the particle after a period of time represents the probability distribution of the distress target at sea after drifting in the same period of time.Let us mark the drift velocity and position ofN particles as VN and LN. VN=v1,…,vn,…,vNT, LN=l1,…,ln,…,lNT, and vn and ln=lngn,latn represent the drift velocity and position of n particles, respectively. The initialization of particles is placed at the last known position of the distress target, and the drift velocity VNt of the particle at time t is randomly simulated according to equations (5)–(7). On this basis, according to the position of the particle LNt−1 at time t−1, the position of the particle LNt at time t can be obtained. At this point, the smallest rectangular region Gt containing all particles is the search region, that is, the rectangle Gt has minlngnt,minlatnt, minlngnt,maxlatnt, maxlngnt,minlatnt, maxlngnt,maxlatnt, and n∈1,2,…,N as vertical.In order to obtain the probability distribution of the location of the distress target in the search areaGt, this paper uses the grid method to divide the search area Gt into Lit×Ljt square search subareas gi,jt with d as the length of each side, where i∈1,2,…,Lit and j∈1,2,…,Ljt. The POC of the distress target pCi,jt corresponding to the search subarea gi,jt is as follows:(8)pCi,jt=Ngi,jtN.In this formula,Ngi,jt refers to the number of particles which are searched at time t in the subarea gi,jt. According to each search subarea pCi,jt, we can obtain the POC model of the distress target at time t, including the search area Gt and its corresponding POC matrix PCt=pCi,jt.Because the location of the distress target will change greatly over time, the POC model of the distress target presents the characteristics of time sensitivity. As a result, based on the search task planned by the POC model of the distress target at timet, the search platform needs complete searching in the search area Gt within the time window t,t+T, where T is the search time window and its value is related to the drift velocity of the distress target VT and the length of the search subarea d. When the search time exceeds the search time window T and the search platform has not found the distress target, it is necessary to update the POC matrix of the search area Gt according to Bayes criterion. The updated POC matrix is recorded as PCt′. On this basis, the number of particles in each search subarea is updated, and the position of the particles is reinitialized. Then, the POC model at time t+T is established, so as to realize the adaptive update of the POC model. Due to the update of the POC of the distress target pCi,jt corresponding to the search subarea gi,jt is not only related to itself but also related to the probability of detection of the distress target pDi,jt, the general updated formula of the POC matrix is shown in equation (9), and the updated formula of the number of particles in each search subarea is shown in equation (10).(9)pCi,jt′=pCi,jt⋅1−pDi,jt1−pCi,jt+pCi,jt⋅1−pDi,jt,gi,jthas been searched,pti,j1−∑gi,jt∈ZselectedtpCi,jt+∑gi,jt∈ZselectedtpCi,jt⋅1−pDi,jt,gi,jtis not searched,(10)Ngi,jt′=N⋅pCi,jt′,where pCi,jt′ represents the POC of distress targets corresponding to the updated search subarea gi,jt; pDi,jt represents the POD of the search platform corresponding to the search subarea gi,jt; Zselectedt represents the search path at time t; Ngi,jt′ represents the number of particles corresponding to the search subarea gi,jt.Note that equation (9) is the general updated formula for the POC of distress target in each search subarea, and in Section 2.1, when explaining equation (1), we point out that if taking visual searching, the distance between the search platform and the distress target is less than 0.1 n mile, the value of pD will be close to 1, and the POS of the distress target is mainly related to the POC. Therefore, this paper mainly solves the POC problem, and when we update the POC of the distress target in each search subarea according to equation (9), the value of pDi,jt is 1.


## 4. Search Path Planning Algorithm Based on the POC Model of Distress Targets

### 4.1. Description of Search Path Planning Algorithm Based on the POC Model of Distress Targets

Because the POC model of the distress targets is time sensitive, the search path planning needs to be carried out within the constraints of the time windowT. At the same time, in order to improve the success rate of search and rescue, the planned search path must cover the area where the POC is as high as possible and give the priority to the search subarea with high probability. Therefore, based on the constructed POC model of distress targets, the POC is taken as the weight of each search subarea, and the sum of the POC of all search subareas is regarded as the weight of the search path. Then, the search path planning is transformed into the maximum weight path planning problem based on the POC model of distress target, so as to build the search path planning model which can be expressed as follows:(11)Zselectedt=argmaxZrt∈ZRmt∑q=1mγm−1pCirq,jrqt,where the specified path step is represented as m, that is, the number of search subareas that can be searched by the search platform in the time window T, whose expression is shown in equation (12); Zselectedt represents the search planning path at time t; ZRmt represents the collection of all optional search paths at time t; Zrt represents one of the search paths in ZRmt; pCirq,jrqt refers to the POC of the distress targets corresponding to the search subarea girq,jrqt covered by the search path Zrt; and γ∈0,1 represents the discount factor.Assuming that the search platform travels at a constant speedVss and can turn in four directions ss=4, that is, up, down, left, and right, the number of searchable subareas m within the time window T is fixed and satisfies (12)m=Vss⋅Td.After the modeling of the search path planning problem is completed, the dynamic programming algorithm is used to obtain the best search pathZselectedt. The main idea of solving the path planning problem by using dynamic programming algorithm is that, in the process of search path planning, after calculating the weights of search path with the same starting point and end point, only the search path with the maximum sum of weights is retained, and others are deleted. Besides, the weights are only calculated once for repeated path points in the same search path.An example is given to illustrate the process of solving the search path planning problem based on the POC model of distress target by using dynamic programming algorithm, as shown in Figure2. Figure 2(a) represents the POC model of the distress target, that is, the search area is divided into 5×5 search subareas by grid method, and the number within each search subarea represents the corresponding POC. Assuming that the search platform is located in the search subarea g2,2, that is, the search path to be planned starts with the search subarea g2,2, the search path step m that needs to be planned in the time window T and discount factor γ=0.98. Figure 2(b) presents the first two steps. In Figure 2, the possible path points are placed in the circles, the number in each box represents the sum of the current weights of the path, the solid line denotes the existing path, and the dotted line stands for the deleted path.Figure 2
Calculating process of the search path planning model based on the POC model. (a) the POC model of distress target. (b) the path planning process of the first two step.
(a)(b)Firstly, the search path planning of step 1 is carried out. The search platform is currently located in the search subareag2,2 and can be turned up, down, left, and right, so the first set ZP1 of path points is optional, that is, g2,3,g2,1,g1,2,g3,2 and all the alternative search path sets ZR1 are g2,2,g2,3,g2,2,g2,1,g2,2,g1,2,g2,2,g3,2. Because there is no duplicate path point in all the optional search paths, the set including the corresponding path weights is {0.0711 + 0.0889, 0.0711 + 0.0101, 0.0711 + 0.0050, 0.0711 + 0.0826}, that is, {0.1600, 0.0816, 0.0761, 0.1537}. Because there is no search path with the same starting and ending points in all the optional search paths, it is unnecessary to do the deletion of the optional path and directly plan the next step size.Secondly, the search platform takes the first optional path point as the starting point for the second step of the search path planning. At this time, the optional path point setZP2 is g2,4,g2,2, g1,3,g3,3,g1,1,g3,1,g4,2 and all the optional search path sets ZR2 are g2,2,g2,3,g2,4,g2,2,g2,3,g2,2,g2,2,g2,3,g1,3,g2,2,g2,3,g3,3,g2,2,g2,1,g2,2,g2,2,g2,1,g1,1,g2,2,g2,1,g3,1,g2,2,g1,2,g2,2,g2,2,g1,2,g1,3,g2,2,g1,2,g1,1,g2,2,g3,2,g2,2,g2,2,g3,2,g3,3,g2,2,g3,2,g3,1,g2,2,g3,2,g4,2. Among all the optional search path sets ZR2, some search paths contain duplicate path points whose weights can only be calculated once. For example, the search path contains duplicate path point g2,2,g2,3,g2,2. Therefore, the sum of the weights of this search path is 0.0711 + 0.0889 + 0.98 × 0 = 0.1600. According to this method, the sum of the weights corresponding to all optional search paths can be calculated as {0.206452, 0.160000, 0.193516, 0.260548, 0.081600, 0.081600, 0.101396, 0.109616, 0.076100, 0.076100, 0.254248, 0.173496, 0.153700, 0.233864}. At the same time, because there are five groups of search paths with the same starting point and end point in all the optional search path sets, which are g2,2,g2,3,g2,2,g2,2,g2,1,g2,2,g2,2,g1,2,g2,2,g2,2,g3,2,g2,2, g2,2,g2,3,g1,3,g2,2,g1,2,g1,3, g2,2,g2,3,g3,3,g2,2,g3,2,g3,3, g2,2,g2,1,g1,1,g2,2,g1,2,g1,1, g2,2,g2,1,g3,1,g2,2,g3,2,g3,1, respectively, we need to delete the optional path according to the sum of the path weights, and only the search path with the maximum sum of the weights is retained, which are g2,2,g2,3,g2,2, g2,2,g2,3,g1,3, g2,2,g2,3,g3,3, g2,2,g2,1,g1,1, g2,2,g3,2,g3,1. At this point, the sets of all the alternative paths ZR2 are g2,2,g2,3,g2,4,g2,2,g2,3,g2,2, g2,2,g2,3,g1,3,g2,2,g2,3,g3,3,g2,2,g2,1,g1,1, g2,2,g3,2,g3,1,g2,2,g3,2,g4,2, and the sum of the corresponding path weights is {0.206452, 0.160000, 0.193516, 0.260548, 0.081600, 0.173496, 0.233864}.Then, the search platform takes the second step optional path point as the starting point and carries on the third step size plan, which has the same processes as the second step. The planning will not stop until it completesm steps, and the set ZRm containing all the optional path planning is obtained. Finally, the path with the largest weight will be chosen, that is, Zselected.


### 4.2. Implementation of Search Path Planning Algorithm Based on the POC Model of Distress Targets

According to the above description and calculation process of solving search path planning problem by dynamic programming algorithm, the search path planning algorithm based on the POC model of distress target is mainly realized by the following seven steps:Step 1: it uses the Monte Carlo random particle method and the grid method to obtain the POC model of distress target at timet, that is, the search area Gt and its corresponding POC matrix PCt=pCi,jt.Step 2: the search platform calculates the required path stepm in the current time window T according to equation (12).Step 3: the search platform takes the current optional path point as the starting point and uses the dynamic programming algorithm to carry out thekth step search path planning. According to the directions that the search platform can choose, we obtain the selected path point set ZPkt and all the optional search path sets ZRkt.Step 4: the sum of the weights of each search path in all the optional search path setsZRkt is computed according to equation (11). In the process of the calculation, it is necessary to judge whether there are repeated path points in the search path, and if so, the weights of repeated path points can only be calculated once.Step 5: it determines whether there is a search path with the same starting and ending points in the setZRkt including all the optional search paths, and if so, the optional path is deleted according to the sum of the path weights. For the search path with the same starting point and end point, only the search path with the maximum sum of weights is retained, and then the updated set ZRkt containing optional search paths is obtained.Step 6: it determines whetherk is greater than m, that is, whether the search platform completes the search path planning within the step size m and returns Step 3 if it is not satisfied; otherwise, the iteration terminates, and in all the optional search paths, the search path with the maximum sum of the path weights is selected according to equation (11), which is the best search path Zselectedt.Step 7: it determines whether the search platform finds a distress target, and if the target is found, the search task ends; otherwise, it determines whether the search time exceeds the search time windowT, and if not, the platform continues to perform the search task according to the currently planned search path. Otherwise, the POC model of the distress target is updated according to equations (9) and (10) and returns Step 2 to replan the search path. Then, the search platform performs the search task according to the reprogrammed search path.


## 4.1. Description of Search Path Planning Algorithm Based on the POC Model of Distress Targets

Because the POC model of the distress targets is time sensitive, the search path planning needs to be carried out within the constraints of the time windowT. At the same time, in order to improve the success rate of search and rescue, the planned search path must cover the area where the POC is as high as possible and give the priority to the search subarea with high probability. Therefore, based on the constructed POC model of distress targets, the POC is taken as the weight of each search subarea, and the sum of the POC of all search subareas is regarded as the weight of the search path. Then, the search path planning is transformed into the maximum weight path planning problem based on the POC model of distress target, so as to build the search path planning model which can be expressed as follows:(11)Zselectedt=argmaxZrt∈ZRmt∑q=1mγm−1pCirq,jrqt,where the specified path step is represented as m, that is, the number of search subareas that can be searched by the search platform in the time window T, whose expression is shown in equation (12); Zselectedt represents the search planning path at time t; ZRmt represents the collection of all optional search paths at time t; Zrt represents one of the search paths in ZRmt; pCirq,jrqt refers to the POC of the distress targets corresponding to the search subarea girq,jrqt covered by the search path Zrt; and γ∈0,1 represents the discount factor.Assuming that the search platform travels at a constant speedVss and can turn in four directions ss=4, that is, up, down, left, and right, the number of searchable subareas m within the time window T is fixed and satisfies (12)m=Vss⋅Td.After the modeling of the search path planning problem is completed, the dynamic programming algorithm is used to obtain the best search pathZselectedt. The main idea of solving the path planning problem by using dynamic programming algorithm is that, in the process of search path planning, after calculating the weights of search path with the same starting point and end point, only the search path with the maximum sum of weights is retained, and others are deleted. Besides, the weights are only calculated once for repeated path points in the same search path.An example is given to illustrate the process of solving the search path planning problem based on the POC model of distress target by using dynamic programming algorithm, as shown in Figure2. Figure 2(a) represents the POC model of the distress target, that is, the search area is divided into 5×5 search subareas by grid method, and the number within each search subarea represents the corresponding POC. Assuming that the search platform is located in the search subarea g2,2, that is, the search path to be planned starts with the search subarea g2,2, the search path step m that needs to be planned in the time window T and discount factor γ=0.98. Figure 2(b) presents the first two steps. In Figure 2, the possible path points are placed in the circles, the number in each box represents the sum of the current weights of the path, the solid line denotes the existing path, and the dotted line stands for the deleted path.Figure 2
Calculating process of the search path planning model based on the POC model. (a) the POC model of distress target. (b) the path planning process of the first two step.
(a)(b)Firstly, the search path planning of step 1 is carried out. The search platform is currently located in the search subareag2,2 and can be turned up, down, left, and right, so the first set ZP1 of path points is optional, that is, g2,3,g2,1,g1,2,g3,2 and all the alternative search path sets ZR1 are g2,2,g2,3,g2,2,g2,1,g2,2,g1,2,g2,2,g3,2. Because there is no duplicate path point in all the optional search paths, the set including the corresponding path weights is {0.0711 + 0.0889, 0.0711 + 0.0101, 0.0711 + 0.0050, 0.0711 + 0.0826}, that is, {0.1600, 0.0816, 0.0761, 0.1537}. Because there is no search path with the same starting and ending points in all the optional search paths, it is unnecessary to do the deletion of the optional path and directly plan the next step size.Secondly, the search platform takes the first optional path point as the starting point for the second step of the search path planning. At this time, the optional path point setZP2 is g2,4,g2,2, g1,3,g3,3,g1,1,g3,1,g4,2 and all the optional search path sets ZR2 are g2,2,g2,3,g2,4,g2,2,g2,3,g2,2,g2,2,g2,3,g1,3,g2,2,g2,3,g3,3,g2,2,g2,1,g2,2,g2,2,g2,1,g1,1,g2,2,g2,1,g3,1,g2,2,g1,2,g2,2,g2,2,g1,2,g1,3,g2,2,g1,2,g1,1,g2,2,g3,2,g2,2,g2,2,g3,2,g3,3,g2,2,g3,2,g3,1,g2,2,g3,2,g4,2. Among all the optional search path sets ZR2, some search paths contain duplicate path points whose weights can only be calculated once. For example, the search path contains duplicate path point g2,2,g2,3,g2,2. Therefore, the sum of the weights of this search path is 0.0711 + 0.0889 + 0.98 × 0 = 0.1600. According to this method, the sum of the weights corresponding to all optional search paths can be calculated as {0.206452, 0.160000, 0.193516, 0.260548, 0.081600, 0.081600, 0.101396, 0.109616, 0.076100, 0.076100, 0.254248, 0.173496, 0.153700, 0.233864}. At the same time, because there are five groups of search paths with the same starting point and end point in all the optional search path sets, which are g2,2,g2,3,g2,2,g2,2,g2,1,g2,2,g2,2,g1,2,g2,2,g2,2,g3,2,g2,2, g2,2,g2,3,g1,3,g2,2,g1,2,g1,3, g2,2,g2,3,g3,3,g2,2,g3,2,g3,3, g2,2,g2,1,g1,1,g2,2,g1,2,g1,1, g2,2,g2,1,g3,1,g2,2,g3,2,g3,1, respectively, we need to delete the optional path according to the sum of the path weights, and only the search path with the maximum sum of the weights is retained, which are g2,2,g2,3,g2,2, g2,2,g2,3,g1,3, g2,2,g2,3,g3,3, g2,2,g2,1,g1,1, g2,2,g3,2,g3,1. At this point, the sets of all the alternative paths ZR2 are g2,2,g2,3,g2,4,g2,2,g2,3,g2,2, g2,2,g2,3,g1,3,g2,2,g2,3,g3,3,g2,2,g2,1,g1,1, g2,2,g3,2,g3,1,g2,2,g3,2,g4,2, and the sum of the corresponding path weights is {0.206452, 0.160000, 0.193516, 0.260548, 0.081600, 0.173496, 0.233864}.Then, the search platform takes the second step optional path point as the starting point and carries on the third step size plan, which has the same processes as the second step. The planning will not stop until it completesm steps, and the set ZRm containing all the optional path planning is obtained. Finally, the path with the largest weight will be chosen, that is, Zselected.


## 4.2. Implementation of Search Path Planning Algorithm Based on the POC Model of Distress Targets

According to the above description and calculation process of solving search path planning problem by dynamic programming algorithm, the search path planning algorithm based on the POC model of distress target is mainly realized by the following seven steps:Step 1: it uses the Monte Carlo random particle method and the grid method to obtain the POC model of distress target at timet, that is, the search area Gt and its corresponding POC matrix PCt=pCi,jt.Step 2: the search platform calculates the required path stepm in the current time window T according to equation (12).Step 3: the search platform takes the current optional path point as the starting point and uses the dynamic programming algorithm to carry out thekth step search path planning. According to the directions that the search platform can choose, we obtain the selected path point set ZPkt and all the optional search path sets ZRkt.Step 4: the sum of the weights of each search path in all the optional search path setsZRkt is computed according to equation (11). In the process of the calculation, it is necessary to judge whether there are repeated path points in the search path, and if so, the weights of repeated path points can only be calculated once.Step 5: it determines whether there is a search path with the same starting and ending points in the setZRkt including all the optional search paths, and if so, the optional path is deleted according to the sum of the path weights. For the search path with the same starting point and end point, only the search path with the maximum sum of weights is retained, and then the updated set ZRkt containing optional search paths is obtained.Step 6: it determines whetherk is greater than m, that is, whether the search platform completes the search path planning within the step size m and returns Step 3 if it is not satisfied; otherwise, the iteration terminates, and in all the optional search paths, the search path with the maximum sum of the path weights is selected according to equation (11), which is the best search path Zselectedt.Step 7: it determines whether the search platform finds a distress target, and if the target is found, the search task ends; otherwise, it determines whether the search time exceeds the search time windowT, and if not, the platform continues to perform the search task according to the currently planned search path. Otherwise, the POC model of the distress target is updated according to equations (9) and (10) and returns Step 2 to replan the search path. Then, the search platform performs the search task according to the reprogrammed search path.


## 5. Simulation and Analysis

### 5.1. Simulation Assumptions and Parameter Setting

Based on the search and rescue work of people in distress in Qiongzhou Strait as the simulation scene, we conduct the following experiments to study the effectiveness of the POC-SPPA algorithm. The parameters are set as follows:(1)
Assume that the person in distress falls into the water, and its location is110°30′36″E,20°13′48″N, 20nmile east and 10nmile north of the Maritime Search and Rescue Centre(2)
At the time of the incident, the total current of the Qiongzhou Strait was from west to east,VC=1kn, and the direction of the wind pressure difference was southwest, VW=15kn(3)
After receiving a search mission, the search platform will travel from the Search and Rescue Centre to search, the speed isVss=15kn, and the scan radius is sw=0.1nmile(4)
In order to ensure that the probability of detectionpD of the distress target in the search area is close to 1, the side length of the search subarea is set at d=0.14nmile(5)
Simulation particlesN=50000 and time window T=0.9h.


### 5.2. Establishment and Updating of the POC Model of Distress Target

Monte Carlo random particle method and grid method are used to compute the update of the POC of the distress target. A coordinate system is established with the drowning position of the person in distress as the origin. The constructed POC model of the distress target is shown in Figure3. Figures 3(a) and 3(b) represent the POC model at time t and time t+T, respectively. Each square in Figure 3 represents the search subarea gi,j. The different colors in the square indicate the varying values of the POC, pCi,j, corresponding to the search subarea gi,j.Figure 3
Construction and update of the POC model: (a) POC model at timet. (b) POC model at time t+T.
(a)(b)From Figure3, it can be seen that compared with the POC model of distress target at time t, the POC model at time t+T is updated, that is, the search area and the POC of the distress target have changed. At time t, within the constraint of the search time window T, the platform starts to execute the search task according to the current planning path. When the search time exceeds the time window T, since the platform fails to find the distress target, the POC in the search area is adaptively updated using Bayes criterion, and thus the POC in the area has been already searched. And then, the POC model can be updated at time t+T by resimulating the drift motion of the distress target so as to realize the adaptive update of the POC matrix. Furthermore, because the drift motion of the target in distress is the result of the combined action of total current, sea surface wind pressure difference, wave, and other factors, the location uncertainty of the distress target increases as the time goes by, making the search area larger as shown in Figure 3(b).


### 5.3. Comparison of Search Path Planning Algorithms

#### 5.3.1. Validation of POC-SPPA

Firstly, the parallel line search path planning algorithm (PL-SPPA) [14, 20], specified in the International Aeronautical and Maritime Search and Rescue Manual, is used as a comparison algorithm to verify the effectiveness of the POC-SPPA.PL-SPPA takes a corner of the search area as the search starting point, and the search path is parallel to the boundary of the search area. The distance between the first search path and the boundary of the search area closest to the search starting point is 1/2 of the search line spacing, that is, a scan radius. And the subsequent search paths remain parallel to each other and are separated by a search line spacing.Under the simulation conditions and parameters set in Section5.1, the drift motion of the distress target is simulated by Monte Carlo random particle method. And based on this, search path planning is carried out by using two different algorithms, including POC-SPPA and PL-SPPA. The simulation results are shown in Figures 4 and 5, where the red lines represent the simulated drift trajectory of the distress target, the blue lines stand for the search path planned by POC-SPPA, and the green lines represent the search path planned by PL-SPPA. Figure 4 shows the search path planned by the two algorithms from alarm to time t1.Figure 4
Results of POC-SPPA and PL-SPPA in time period0,t1.Figure 5
Results of POC-SPPA and PL-SPPA in time periodt1,t3. (a) Search path in time period t1,t2 (POC-SPPA). (b) Search path in time period t1,t2 (PL-SPPA). (c) Distress target and search platform location. (d) Distress target and search platform location at time t2 (POC-SPPA) and at time t2 (PL-SPPA). (e) Search path in time period t2,t3 (POC-SPPA). (f) Search path in time period t2,t3 (PL-SPPA).
(a)(b)(c)(d)(e)(f)Figures5(a) and 5(b) represent the search path planned by the two algorithms in time period t1,t2, respectively. On the basis of the POC model of the distress target, POC-SPPA carries on the search path planning according to the POC of each search subarea. However, PL-SPPA holds that the distress target follows the equal probability distribution in the search area, and the regular search path planning is carried out according to the full coverage search.Figures5(c) and 5(d) represent the location of the distress target and the search platform at time t2t2=t1+T using the above two methods. We can see from Figure 5(c) that POC-SPPA fully considers the time-sensitive characteristics of the search task under the constraints of the time window, and the POC model of the distress target is dynamically updated, so that the distress target is still in the search area, and the search path is replanned on this basis. PL-SPPA does not consider the time window constraint and the dynamic update of search area. It performs the search task according to the estimated search area and search path at time T. Hence, the distress target has drifted out of the search area, as shown in Figure 5(d).Figures5(e) and 5(f) represent the search path planned by the two algorithms in time period t2,t3 employing two methods, respectively. POC-SPPA gives the priority to the search subarea with higher probability and successfully finds the distress target at time t3, while PL-SPPA can only update the search area at the next search time t+1t2<t+1<t3 and still cannot find the distress target at time t3.In order to compare the search effect of the two algorithms in different marine environments, the search success rate and the average search time are taken as the evaluation metrics, and the simulation results are shown in Table1. As a result, POC-SPPA can effectively improve the search success rate and search speed, especially in the harsh marine environment, where the drift speed and uncertainty of the target are high. POC-SPPA maintains a high search success rate since it is able to dynamically update within the constraint of the time window, while PL-SPPA can hardly find the target because it has to carry out full coverage search and the update speed is slow.Table 1
Comparison of search results of two search path planning algorithms in different marine environments.
Serial numberVCknVWknSearch success rate (%)Average search time (h)POC-SPPAPL-SPPAPOC-SPPAPL-SPPA111597.980.12.944.1821.52090.051.64.157.02322585.624.34.849.6042.53073.418.46.0510.20


#### 5.3.2. Effectiveness Verification of Updating the POC Matrix Based on Bayes Criterion

On the basis of verifying the effectiveness of POC-SPPA with PL-SPPA, it is further compared with the search path planning algorithm based on the static probability of distress target containment (SPOC-SPPA) to verify the necessity and effectiveness of dynamic update of the POC model based on Bayes criterion in the POC-SPPA.SPOC-SPPA means that, under the time window constraint, the dynamic update of the POC matrix and the dynamic evaluation of the search area do not use Bayes criterion, but only use Monte Carlo random particle method to simulate the drift trajectory of the distress target according to the initial distress position of the distress target and then replan the search path.From the above analysis of the simulation results shown in Figure5, it can be seen that, in the time period t1,t3, POC-SPPA updates the POC model based on the Bayes criterion at time t2t2=t1+T according to equation (9), ensuring that the distress target is still in the estimated search area. In order to fully and effectively illustrate the effectiveness of updating the POC model based on the Bayes criterion, on the basis of the experimental data obtained from the simulation experiment using POC-SPPA in Section 5.3.1, we use SPOC-SPPA to simulate the search and rescue process of the search platform in time period t2,t3. The simulation results are shown in Figure 6, where the red lines represent the simulated drift trajectory of the distress target, the magenta lines stand for the search path planned by SPOC-SPPA, and red “∗” and magenta “∗” represent the location of the distress target and the search platform, respectively.Figure 6
Results of SPOC-SPPA in time periodt2,t3. (a) The updated POC model at time t2. (b) Search path in time period t2,t3.
(a)(b)Since SPOC-SPPA also takes into account the time-sensitive characteristics of the search task, it also updates the POC model at timet2t2=t1+T. The updated POC model is shown in Figure 6(a). From it, we can see that SPOC-SPPA fully considers the time-sensitive characteristics of the search task, and the POC model of the distress target is dynamically updated under the time window constraint so that the distress target is still in the updated search area. However, when SPOC-SPPA updates the POC model, it only simulates the drift motion of the distress target relied on the initial distress position of the target and the marine environment data information in time period 0,t2 and does not consider the influence of the search platform execution of search and rescue task on the POC of the distress target in the search area, that is, it does not consider the correlation between the POC model at the updated time before and after, which makes the POC of the distress target in the searched area in time period t1,t2 still relatively high. Unlike SPOC-SPPA, when POC-SPPA algorithm updates the POC model, it uses the POC model at time t1 as prior information, obtains the posterior information of the probability area of the distress target appearance at time t2t2=t1+T by using the probability propagation characteristic of Bayes criterion, and realizes the probability propagation of the distress target position in the time window before and after, which makes the distress target located in the search area with relatively high probability, as shown in Figure 5(c).Figure6(b) represents the search path planned by SPOC-SPPA in time period t2,t3. From it, we can observe that although SPOC-SPPA also gives the priority to the search subarea with higher probability, the correlation between the POC model at the updated time before and after is not considered in the update of the POC model, which leads to the search task in time period t2,t3 has nothing to do with the search results in time period 0,t2. Namely, the current search tasks a brand new search task. The search platform researched the distress target according to the planned search path (indicated by blue lines in Figure 6(b)), resulting in failure to find the distress target at time t3. And at this time, the search platform based on the POC-SPPA successfully finds the distress target, as shown in Figure 5(e).From the above simulation experiments, it can be seen that the POC model update mechanism based on Bayes criterion fully considers the influence of the search platform execution of search and rescue task on the POC of the distress target in the search area and realizes the probability propagation of the distress target position in the time window before and after by using the probability propagation characteristic of Bayes criterion. This makes it possible to make full use of the existing search result information during the entire search process to provide positive feedback information for subsequent searches, effectively improving the accuracy and precision of the search area estimation, thereby increasing the search and rescue success rate.


## 5.1. Simulation Assumptions and Parameter Setting

Based on the search and rescue work of people in distress in Qiongzhou Strait as the simulation scene, we conduct the following experiments to study the effectiveness of the POC-SPPA algorithm. The parameters are set as follows:(1)
Assume that the person in distress falls into the water, and its location is110°30′36″E,20°13′48″N, 20nmile east and 10nmile north of the Maritime Search and Rescue Centre(2)
At the time of the incident, the total current of the Qiongzhou Strait was from west to east,VC=1kn, and the direction of the wind pressure difference was southwest, VW=15kn(3)
After receiving a search mission, the search platform will travel from the Search and Rescue Centre to search, the speed isVss=15kn, and the scan radius is sw=0.1nmile(4)
In order to ensure that the probability of detectionpD of the distress target in the search area is close to 1, the side length of the search subarea is set at d=0.14nmile(5)
Simulation particlesN=50000 and time window T=0.9h.


## 5.2. Establishment and Updating of the POC Model of Distress Target

Monte Carlo random particle method and grid method are used to compute the update of the POC of the distress target. A coordinate system is established with the drowning position of the person in distress as the origin. The constructed POC model of the distress target is shown in Figure3. Figures 3(a) and 3(b) represent the POC model at time t and time t+T, respectively. Each square in Figure 3 represents the search subarea gi,j. The different colors in the square indicate the varying values of the POC, pCi,j, corresponding to the search subarea gi,j.Figure 3
Construction and update of the POC model: (a) POC model at timet. (b) POC model at time t+T.
(a)(b)From Figure3, it can be seen that compared with the POC model of distress target at time t, the POC model at time t+T is updated, that is, the search area and the POC of the distress target have changed. At time t, within the constraint of the search time window T, the platform starts to execute the search task according to the current planning path. When the search time exceeds the time window T, since the platform fails to find the distress target, the POC in the search area is adaptively updated using Bayes criterion, and thus the POC in the area has been already searched. And then, the POC model can be updated at time t+T by resimulating the drift motion of the distress target so as to realize the adaptive update of the POC matrix. Furthermore, because the drift motion of the target in distress is the result of the combined action of total current, sea surface wind pressure difference, wave, and other factors, the location uncertainty of the distress target increases as the time goes by, making the search area larger as shown in Figure 3(b).


## 5.3. Comparison of Search Path Planning Algorithms

### 5.3.1. Validation of POC-SPPA

Firstly, the parallel line search path planning algorithm (PL-SPPA) [14, 20], specified in the International Aeronautical and Maritime Search and Rescue Manual, is used as a comparison algorithm to verify the effectiveness of the POC-SPPA.PL-SPPA takes a corner of the search area as the search starting point, and the search path is parallel to the boundary of the search area. The distance between the first search path and the boundary of the search area closest to the search starting point is 1/2 of the search line spacing, that is, a scan radius. And the subsequent search paths remain parallel to each other and are separated by a search line spacing.Under the simulation conditions and parameters set in Section5.1, the drift motion of the distress target is simulated by Monte Carlo random particle method. And based on this, search path planning is carried out by using two different algorithms, including POC-SPPA and PL-SPPA. The simulation results are shown in Figures 4 and 5, where the red lines represent the simulated drift trajectory of the distress target, the blue lines stand for the search path planned by POC-SPPA, and the green lines represent the search path planned by PL-SPPA. Figure 4 shows the search path planned by the two algorithms from alarm to time t1.Figure 4
Results of POC-SPPA and PL-SPPA in time period0,t1.Figure 5
Results of POC-SPPA and PL-SPPA in time periodt1,t3. (a) Search path in time period t1,t2 (POC-SPPA). (b) Search path in time period t1,t2 (PL-SPPA). (c) Distress target and search platform location. (d) Distress target and search platform location at time t2 (POC-SPPA) and at time t2 (PL-SPPA). (e) Search path in time period t2,t3 (POC-SPPA). (f) Search path in time period t2,t3 (PL-SPPA).
(a)(b)(c)(d)(e)(f)Figures5(a) and 5(b) represent the search path planned by the two algorithms in time period t1,t2, respectively. On the basis of the POC model of the distress target, POC-SPPA carries on the search path planning according to the POC of each search subarea. However, PL-SPPA holds that the distress target follows the equal probability distribution in the search area, and the regular search path planning is carried out according to the full coverage search.Figures5(c) and 5(d) represent the location of the distress target and the search platform at time t2t2=t1+T using the above two methods. We can see from Figure 5(c) that POC-SPPA fully considers the time-sensitive characteristics of the search task under the constraints of the time window, and the POC model of the distress target is dynamically updated, so that the distress target is still in the search area, and the search path is replanned on this basis. PL-SPPA does not consider the time window constraint and the dynamic update of search area. It performs the search task according to the estimated search area and search path at time T. Hence, the distress target has drifted out of the search area, as shown in Figure 5(d).Figures5(e) and 5(f) represent the search path planned by the two algorithms in time period t2,t3 employing two methods, respectively. POC-SPPA gives the priority to the search subarea with higher probability and successfully finds the distress target at time t3, while PL-SPPA can only update the search area at the next search time t+1t2<t+1<t3 and still cannot find the distress target at time t3.In order to compare the search effect of the two algorithms in different marine environments, the search success rate and the average search time are taken as the evaluation metrics, and the simulation results are shown in Table1. As a result, POC-SPPA can effectively improve the search success rate and search speed, especially in the harsh marine environment, where the drift speed and uncertainty of the target are high. POC-SPPA maintains a high search success rate since it is able to dynamically update within the constraint of the time window, while PL-SPPA can hardly find the target because it has to carry out full coverage search and the update speed is slow.Table 1
Comparison of search results of two search path planning algorithms in different marine environments.
Serial numberVCknVWknSearch success rate (%)Average search time (h)POC-SPPAPL-SPPAPOC-SPPAPL-SPPA111597.980.12.944.1821.52090.051.64.157.02322585.624.34.849.6042.53073.418.46.0510.20


### 5.3.2. Effectiveness Verification of Updating the POC Matrix Based on Bayes Criterion

On the basis of verifying the effectiveness of POC-SPPA with PL-SPPA, it is further compared with the search path planning algorithm based on the static probability of distress target containment (SPOC-SPPA) to verify the necessity and effectiveness of dynamic update of the POC model based on Bayes criterion in the POC-SPPA.SPOC-SPPA means that, under the time window constraint, the dynamic update of the POC matrix and the dynamic evaluation of the search area do not use Bayes criterion, but only use Monte Carlo random particle method to simulate the drift trajectory of the distress target according to the initial distress position of the distress target and then replan the search path.From the above analysis of the simulation results shown in Figure5, it can be seen that, in the time period t1,t3, POC-SPPA updates the POC model based on the Bayes criterion at time t2t2=t1+T according to equation (9), ensuring that the distress target is still in the estimated search area. In order to fully and effectively illustrate the effectiveness of updating the POC model based on the Bayes criterion, on the basis of the experimental data obtained from the simulation experiment using POC-SPPA in Section 5.3.1, we use SPOC-SPPA to simulate the search and rescue process of the search platform in time period t2,t3. The simulation results are shown in Figure 6, where the red lines represent the simulated drift trajectory of the distress target, the magenta lines stand for the search path planned by SPOC-SPPA, and red “∗” and magenta “∗” represent the location of the distress target and the search platform, respectively.Figure 6
Results of SPOC-SPPA in time periodt2,t3. (a) The updated POC model at time t2. (b) Search path in time period t2,t3.
(a)(b)Since SPOC-SPPA also takes into account the time-sensitive characteristics of the search task, it also updates the POC model at timet2t2=t1+T. The updated POC model is shown in Figure 6(a). From it, we can see that SPOC-SPPA fully considers the time-sensitive characteristics of the search task, and the POC model of the distress target is dynamically updated under the time window constraint so that the distress target is still in the updated search area. However, when SPOC-SPPA updates the POC model, it only simulates the drift motion of the distress target relied on the initial distress position of the target and the marine environment data information in time period 0,t2 and does not consider the influence of the search platform execution of search and rescue task on the POC of the distress target in the search area, that is, it does not consider the correlation between the POC model at the updated time before and after, which makes the POC of the distress target in the searched area in time period t1,t2 still relatively high. Unlike SPOC-SPPA, when POC-SPPA algorithm updates the POC model, it uses the POC model at time t1 as prior information, obtains the posterior information of the probability area of the distress target appearance at time t2t2=t1+T by using the probability propagation characteristic of Bayes criterion, and realizes the probability propagation of the distress target position in the time window before and after, which makes the distress target located in the search area with relatively high probability, as shown in Figure 5(c).Figure6(b) represents the search path planned by SPOC-SPPA in time period t2,t3. From it, we can observe that although SPOC-SPPA also gives the priority to the search subarea with higher probability, the correlation between the POC model at the updated time before and after is not considered in the update of the POC model, which leads to the search task in time period t2,t3 has nothing to do with the search results in time period 0,t2. Namely, the current search tasks a brand new search task. The search platform researched the distress target according to the planned search path (indicated by blue lines in Figure 6(b)), resulting in failure to find the distress target at time t3. And at this time, the search platform based on the POC-SPPA successfully finds the distress target, as shown in Figure 5(e).From the above simulation experiments, it can be seen that the POC model update mechanism based on Bayes criterion fully considers the influence of the search platform execution of search and rescue task on the POC of the distress target in the search area and realizes the probability propagation of the distress target position in the time window before and after by using the probability propagation characteristic of Bayes criterion. This makes it possible to make full use of the existing search result information during the entire search process to provide positive feedback information for subsequent searches, effectively improving the accuracy and precision of the search area estimation, thereby increasing the search and rescue success rate.


## 5.3.1. Validation of POC-SPPA

Firstly, the parallel line search path planning algorithm (PL-SPPA) [14, 20], specified in the International Aeronautical and Maritime Search and Rescue Manual, is used as a comparison algorithm to verify the effectiveness of the POC-SPPA.PL-SPPA takes a corner of the search area as the search starting point, and the search path is parallel to the boundary of the search area. The distance between the first search path and the boundary of the search area closest to the search starting point is 1/2 of the search line spacing, that is, a scan radius. And the subsequent search paths remain parallel to each other and are separated by a search line spacing.Under the simulation conditions and parameters set in Section5.1, the drift motion of the distress target is simulated by Monte Carlo random particle method. And based on this, search path planning is carried out by using two different algorithms, including POC-SPPA and PL-SPPA. The simulation results are shown in Figures 4 and 5, where the red lines represent the simulated drift trajectory of the distress target, the blue lines stand for the search path planned by POC-SPPA, and the green lines represent the search path planned by PL-SPPA. Figure 4 shows the search path planned by the two algorithms from alarm to time t1.Figure 4
Results of POC-SPPA and PL-SPPA in time period0,t1.Figure 5
Results of POC-SPPA and PL-SPPA in time periodt1,t3. (a) Search path in time period t1,t2 (POC-SPPA). (b) Search path in time period t1,t2 (PL-SPPA). (c) Distress target and search platform location. (d) Distress target and search platform location at time t2 (POC-SPPA) and at time t2 (PL-SPPA). (e) Search path in time period t2,t3 (POC-SPPA). (f) Search path in time period t2,t3 (PL-SPPA).
(a)(b)(c)(d)(e)(f)Figures5(a) and 5(b) represent the search path planned by the two algorithms in time period t1,t2, respectively. On the basis of the POC model of the distress target, POC-SPPA carries on the search path planning according to the POC of each search subarea. However, PL-SPPA holds that the distress target follows the equal probability distribution in the search area, and the regular search path planning is carried out according to the full coverage search.Figures5(c) and 5(d) represent the location of the distress target and the search platform at time t2t2=t1+T using the above two methods. We can see from Figure 5(c) that POC-SPPA fully considers the time-sensitive characteristics of the search task under the constraints of the time window, and the POC model of the distress target is dynamically updated, so that the distress target is still in the search area, and the search path is replanned on this basis. PL-SPPA does not consider the time window constraint and the dynamic update of search area. It performs the search task according to the estimated search area and search path at time T. Hence, the distress target has drifted out of the search area, as shown in Figure 5(d).Figures5(e) and 5(f) represent the search path planned by the two algorithms in time period t2,t3 employing two methods, respectively. POC-SPPA gives the priority to the search subarea with higher probability and successfully finds the distress target at time t3, while PL-SPPA can only update the search area at the next search time t+1t2<t+1<t3 and still cannot find the distress target at time t3.In order to compare the search effect of the two algorithms in different marine environments, the search success rate and the average search time are taken as the evaluation metrics, and the simulation results are shown in Table1. As a result, POC-SPPA can effectively improve the search success rate and search speed, especially in the harsh marine environment, where the drift speed and uncertainty of the target are high. POC-SPPA maintains a high search success rate since it is able to dynamically update within the constraint of the time window, while PL-SPPA can hardly find the target because it has to carry out full coverage search and the update speed is slow.Table 1
Comparison of search results of two search path planning algorithms in different marine environments.
Serial numberVCknVWknSearch success rate (%)Average search time (h)POC-SPPAPL-SPPAPOC-SPPAPL-SPPA111597.980.12.944.1821.52090.051.64.157.02322585.624.34.849.6042.53073.418.46.0510.20


## 5.3.2. Effectiveness Verification of Updating the POC Matrix Based on Bayes Criterion

On the basis of verifying the effectiveness of POC-SPPA with PL-SPPA, it is further compared with the search path planning algorithm based on the static probability of distress target containment (SPOC-SPPA) to verify the necessity and effectiveness of dynamic update of the POC model based on Bayes criterion in the POC-SPPA.SPOC-SPPA means that, under the time window constraint, the dynamic update of the POC matrix and the dynamic evaluation of the search area do not use Bayes criterion, but only use Monte Carlo random particle method to simulate the drift trajectory of the distress target according to the initial distress position of the distress target and then replan the search path.From the above analysis of the simulation results shown in Figure5, it can be seen that, in the time period t1,t3, POC-SPPA updates the POC model based on the Bayes criterion at time t2t2=t1+T according to equation (9), ensuring that the distress target is still in the estimated search area. In order to fully and effectively illustrate the effectiveness of updating the POC model based on the Bayes criterion, on the basis of the experimental data obtained from the simulation experiment using POC-SPPA in Section 5.3.1, we use SPOC-SPPA to simulate the search and rescue process of the search platform in time period t2,t3. The simulation results are shown in Figure 6, where the red lines represent the simulated drift trajectory of the distress target, the magenta lines stand for the search path planned by SPOC-SPPA, and red “∗” and magenta “∗” represent the location of the distress target and the search platform, respectively.Figure 6
Results of SPOC-SPPA in time periodt2,t3. (a) The updated POC model at time t2. (b) Search path in time period t2,t3.
(a)(b)Since SPOC-SPPA also takes into account the time-sensitive characteristics of the search task, it also updates the POC model at timet2t2=t1+T. The updated POC model is shown in Figure 6(a). From it, we can see that SPOC-SPPA fully considers the time-sensitive characteristics of the search task, and the POC model of the distress target is dynamically updated under the time window constraint so that the distress target is still in the updated search area. However, when SPOC-SPPA updates the POC model, it only simulates the drift motion of the distress target relied on the initial distress position of the target and the marine environment data information in time period 0,t2 and does not consider the influence of the search platform execution of search and rescue task on the POC of the distress target in the search area, that is, it does not consider the correlation between the POC model at the updated time before and after, which makes the POC of the distress target in the searched area in time period t1,t2 still relatively high. Unlike SPOC-SPPA, when POC-SPPA algorithm updates the POC model, it uses the POC model at time t1 as prior information, obtains the posterior information of the probability area of the distress target appearance at time t2t2=t1+T by using the probability propagation characteristic of Bayes criterion, and realizes the probability propagation of the distress target position in the time window before and after, which makes the distress target located in the search area with relatively high probability, as shown in Figure 5(c).Figure6(b) represents the search path planned by SPOC-SPPA in time period t2,t3. From it, we can observe that although SPOC-SPPA also gives the priority to the search subarea with higher probability, the correlation between the POC model at the updated time before and after is not considered in the update of the POC model, which leads to the search task in time period t2,t3 has nothing to do with the search results in time period 0,t2. Namely, the current search tasks a brand new search task. The search platform researched the distress target according to the planned search path (indicated by blue lines in Figure 6(b)), resulting in failure to find the distress target at time t3. And at this time, the search platform based on the POC-SPPA successfully finds the distress target, as shown in Figure 5(e).From the above simulation experiments, it can be seen that the POC model update mechanism based on Bayes criterion fully considers the influence of the search platform execution of search and rescue task on the POC of the distress target in the search area and realizes the probability propagation of the distress target position in the time window before and after by using the probability propagation characteristic of Bayes criterion. This makes it possible to make full use of the existing search result information during the entire search process to provide positive feedback information for subsequent searches, effectively improving the accuracy and precision of the search area estimation, thereby increasing the search and rescue success rate.


## 6. Conclusions

A search path planning algorithm (POC-SPPA) based on the POC model of the distress target is proposed in this paper to solve the path planning problem in the search and rescue process of a distress target at sea. The algorithm uses Monte Carlo random particle method to simulate the drift motion of the distress target and realizes the evaluation of the search area. On this basis, grid processing is employed for the search area. POC-SPPA evaluates the POC of each subsearch area target through the number of particles to construct the POC model of the distress target and realizes the dynamic update of the POC model according to Bayes criterion under the time window constraint. Besides, the sum of the POC of distress target in the search subarea is used as the weight of the search path so that the search path planning is transformed into the maximum weight path planning problem based on the POC model, and the dynamic programming algorithm is used to complete the search path planning. The simulation results show that the proposed algorithm can realize the dynamic prediction of search area and improve the speed and success rate of search and rescue for maritime distress target.



---

*Source: 7459239-2021-01-28.xml*