Frontiers in Computing and Intelligent Systems 
ISSN: 2832-6024 | Vol. 8, No. 2, 2024 

 

29 

Research on Multi-Beam Line Finding Problem and 
Optimal Line Finding Path based on Exhaustion Method 

Yuxuan Lu * 

School of Finance, Central University of Finance and Economics, Beijing, China 

* Corresponding author Email: lyxcufe2022@126.com 

 

Abstract: In this paper, the multi-beam line measurement problem is studied, solving the relevant data of different seabed 

slope and line measurement, and establishing a multi-beam line measurement model based on it, simulating the work of multi-

beam line measurement, using ergodic and iterative algorithms, to achieve the best line measurement path design and calculation 

of uneven sea area. First of all, the mathematical model of multi-beam line surveying with variable direction of line surveying is 

obtained through geometric relation and sine and cosine theorem, etc., and the coverage width 𝑊, overlap rate between lines 𝜂 

and sea depth 𝐷 of measuring ships at different positions are solved. Secondly, the characteristics of sea terrain are analyzed, 

and the variation law of the coverage width 𝑊 of the measured line with the angle of the measured line direction 𝛽 is explored. 

Finally, whether the beginning and end points of the survey line reach the north and south banks is classified and discussed, and 

the traversal calculation method is designed to exhaustively explore all possible points and solve the minimum points.  

Keywords: Loop Traversal; Calculation Geometry; Multi-Beam Line Measurement. 

 

1. Introduction 

In the 1980s, multi-beam sounding technology emerged, 

and has been developed into the mainstream detection mode 

of seabed sounding. Multi-beam sounding is based on single 

beam sounding, which is characterized by full coverage and 

high precision. The multi-beam surveying line can change the 

angle of the transducer and send out dozens or even hundreds 

of beams in the vertical plane of the surveying line direction 

at a time, so as to enlarge the width of the surveying line and 

form the purpose of the full coverage of the water depth strip 

[1-3]. But at the same time, multi-beam sounding also faces 

the problem of seabed topography fluctuation. Based on the 

ergodic exhaustive algorithm, this paper studies how to 

calculate the coverage width and overlap rate of the survey 

line under different conditions and design a reasonable survey 

line direction in the face of the rolling seabed topography, 

which is of great significance for reducing the phenomenon 

of leakage and data redundancy in the sea area and improving 

the efficiency and accuracy of multi-beam sounding 

technology. 

2. Mathematical Model of Multi-beam 
Survey Line 

Assuming that the slope 𝛼, the opening angle of the multi-

beam transducer 𝛽 and the water depth 𝐷 of the center point 

of the sea area are known, this chapter establishes a 

mathematical model of the coverage width of the multi-beam 

sounding and the overlap rate of adjacent strips under these 

conditions, and uses the model to solve the seawater depth, 

coverage width and overlap rate of the lines with different 

distances from the center of the sea area. 

2.1. The Mathematical Model of Multi-Beam 

Line Measurement with Constant Line 

Direction 

2.1.1. Coverage Width Calculation Formula 

Set the edge and angle and construct the static plane 

geometry diagram when the surveying ship is in a certain 

position, as shown in Figure 1. 

As shown in Figure 1, according to the geometric 

relationship, the angles established meet the following 

requirements: 

{
 
 

 
 

𝜃1 =
𝜋

2
+ 𝛼

𝜃2 =
𝜋

2
− 𝛼

𝜃3 =
𝜋

2
−

𝜃

2
− 𝛼

𝜃4 =
𝜋

2
−

𝜃

2
+  𝛼

                (1) 

Therefore, according to the law of sine and the law of 

cosine, the covering width 𝑊 can be expressed as: 

𝑊 = 𝐷𝑐𝑜𝑠2𝛼√
1

𝑐𝑜𝑠2(
𝜃

2
−𝛼)

+
1

𝑐𝑜𝑠2(
𝜃

2
+𝛼)

−
2𝑐𝑜𝑠𝜃

𝑐𝑜𝑠(
𝜃

2
−𝛼)𝑐𝑜𝑠 (

𝜃

2
+𝛼)

 (2) 

2.1.2. Formula for Calculating Overlap Rate 

Assuming that the opening angle of the transducer is 

unchanged, the schematic diagram of two adjacent multi-

beam survey lines on two different positions 𝐴 and 𝐵 from 

the center of the sea area is constructed by the survey ship as 

shown in Figure 2.  

According to the sine theorem: 

𝐿1

𝑠𝑖𝑛(
𝜋

2
+
𝜃

2
)
=

𝑙1

𝑠𝑖𝑛𝛼
                (3) 

𝐿2

𝑠𝑖𝑛(
𝜋

2
−𝛼)

=
𝐷

𝑠𝑖𝑛𝛼
                (4) 

According to the proportional relationship between parallel 

lines, the sea surface height  𝐷′ at the second line can be 

measured. 

𝐷′

𝐷
=

𝐿2−𝑑

𝐿2
                    (5) 

Then the overlapping area 𝑋 is: 

𝑋 = 𝑊 − 𝑥3                                        (6) 



 

30 

  

 

Figure 1. Static plane geometry diagram 

 

Figure 2. Diagram of adjacent multi-beam line measurement 

Get the overlap rate 𝜂  between the second measurement 

and the first measurement as: 

𝜂 =
𝑋

𝑊
                     (7) 

In summary, the expression obtained is as follows: 

𝜂 =
𝐷

𝐷−𝑑𝑡𝑎𝑛𝛼
−

𝑑
𝜃

2

𝑑𝑐𝑜𝑠(
𝜃

2
+𝛼)𝑡𝑎𝑛𝛼√

1

𝑐𝑜𝑠2(
𝜃
2−𝛼

)
+

1

𝑐𝑜𝑠2(
𝜃
2+𝛼

)
−

2𝑐𝑜𝑠𝜃

𝑐𝑜𝑠(
𝜃
2−𝛼

)𝑐𝑜𝑠 (
𝜃
2+𝛼)

   (8) 

Therefore, 𝜂  is a function related to the depth and the 

distance between the two measurement lines. 

2.2. Multi-beam Line Measurement 

Mathematical Model with Variable 

Direction of Line Measurement 

2.2.1. Coverage Width Solution 

As shown in Figure 3, when the angle between the survey 

line direction and the direction of ship navigation is 𝛽, the 

inclination angle 𝜃1
′
  in the cross-sectional view 

perpendicular to the survey line direction (as shown in Figure 

3) differs from 𝜃1 (as shown in Figure 1) because the slope 

also changes when viewed from this section. The new slope 

𝛼′ can be calculated from the geometric relationships shown 

in the figure, satisfying the following equation: 

𝑡𝑎𝑛𝛼′ = 𝑡𝑎𝑛𝛼𝑠𝑖𝑛𝛽                  (9) 

By replacing the original slope 𝛼 with the new slope 𝛼′, 
the coverage width of multi-beam sounding can be obtained: 

 𝑊′ =

𝐷𝑐𝑜𝑠2 𝛼′√
1

𝑐𝑜𝑠2(
𝜃

2
− 𝛼′)

+
1

𝑐𝑜𝑠2(
𝜃

2
+ 𝛼′)

−
2𝑐𝑜𝑠𝜃

𝑐𝑜𝑠(
𝜃

2
− 𝛼′)cos (

𝜃

2
+ 𝛼′)

 (10) 

2.2.2. Seawater Depth Solution 

According to the proportionality relationship between 
parallel lines, the sea surface height (𝐷𝑖) measured at the 𝑖 −
𝑡ℎ survey line can be obtained as follows: 

 𝐷𝑖

𝐷
=

𝐿2−𝑑

𝐿2
                    (11) 

Where the positive direction 𝑑  is the direction from the 

depth of water to the shallow water, the value 𝐿2 is obtained 

from the following formula: 

𝐿2

sin(
𝜋

2
−𝛼)

=
𝐷

𝑠𝑖𝑛𝛼
                   (12) 

However, it is important to note that different values of the 

angle 𝛽 require separate considerations. Figure 4 illustrates a 

plan view of the measurement of the ship's survey line 

direction for different values of 𝛽. 

 

Figure 3. A geometric diagram in the direction of an angular 

line 

 

Figure 4. Top view of line direction 

In the first scenario, when the angle 𝛽 between the survey 

line directions is 0°, and when 𝛽𝑖 = 0 , the cross-sectional 

triangle no longer has a slope, and 𝛼′ is also 0°, making the 

equation unable to be solved. When the slope is 0°, the cross-

section forms an equilateral triangle with a vertex angle 𝜃 of 

120°. When the depth is 𝐷𝑖
′, the width 𝑊 is  2√3𝐷𝑖. For 180°, 

the reverse situation of 0°, the calculation is similar. 



 

31 

The second case, when the angle is 90° or 270°. When the 

survey boat is traveling along the survey line, it is parallel to 

the slope and the depth remains the same. 

Other angles can be calculated normally. 

3. Build the Optimal Line Path Design 
Model Based on Exhaustion 

Based on the established mathematical model of the 

coverage width of multi-beam sounding, a set of multi-beam 

surveying line is designed for the rectangular sea area, so that 

the total measuring length of the surveying line is shortest, and 

the whole sea area to be measured can be completely covered. 

3.1. Establishment of target model 

To explore the relationship between variables, with 

coverage width 𝑊as the dependent variable, and the angle 𝛽 

of the sounding line direction and the distance s of the 

measurement vessel from the shore as the independent 

variables. The study found that when the distance 𝑠 from the 

shore of the measuring ship is constant, the function image of 

𝑊  is an image of trigonometric function class, its value 

changes periodically with the change of 𝛽, the amplitude 𝐴 

is determined by the corresponding distance s from the shore 

of the measuring ship, and the period 𝑇 is constant 𝜋.When 

the angle of the direction of the control line is constant 𝛽, 𝑊 

is proportional to the distance from the measuring ship to the 

shore, and the farther away from the shore, the larger the 

coverage width. Therefore, it can be inferred that the surveying 

line will be denser at the shallow water and sparse at the deep 

water; 𝛽𝑖  near 90°, the overall length of the line will be 

smaller. 

According to the above conjecture, the optimal solution is 

obtained when the 𝛽𝑖  is fixed at 90°, and the approximate 

range of the total number 𝑛  and the total length of the 

measured lines is determined [4]. Set the coast length of the 

east and west coasts as 𝑚1, and the coast length of the north 

and south coasts as 𝑚2, and simulate the survey line process 

between the north and south coasts as a top view, as shown in 

Figure 5, then the voyage of the survey ship in the following 

figure can be divided into two situations: first, it starts from 

the north bank and stops from the south bank, and the survey 

line reaches both sides completely; The second is the north 

coast, but did not reach the south coast, the end of the east or 

West coast. 

3.2. Algorithm Construction 

As shown in Figure 6, the total length of the measured 

distance at this time is [5]: 

𝐿(𝛽) = ∑ 𝐿𝑖
𝑛
𝑖=1                  (13) 

The length of the 𝑖 − 𝑡ℎ line  𝐿𝑖 satisfies the equation: 

𝐿𝑖 =
𝑚1

𝑠𝑖𝑛𝛽𝑖
                   (14) 

Suppose that the overlap rate between adjacent strips is 

required to be between 10% and 20%, that is: 

10% ≤ 𝜂𝑖 ≤ 20%, 𝑖 = 2,… , 𝑛          (15) 

Where, 𝜂𝑖  refers to the overlap rate between the 𝑖 − 𝑡ℎ 

measurement line and the 𝑖 − 1 right measurement line. Since 

there is overlap between adjacent strips, if you want the survey 

line to completely cover the entire sea area to be measured, 

you need the survey line to cover the width of the north and 

south sides of the bank greater than the width of the shore, that 

is: 

 

Figure 5. Top view of simulated line process between north 

and south coasts 

 

Figure 6. Top view of the survey line reaching the north and south 

sides of the starting and ending points 

∑ 𝑊𝑁(𝛽𝑖 , 𝑛) > 𝑚1
𝑛
𝑖=1             (16) 

∑ 𝑊𝑆(𝛽𝑖 , 𝑛) > 𝑚1
𝑛
𝑖=1             (17) 

By calculating the number of measurements when the 

direction of the survey line is always 90°, the number of 

measurements under the direction of other survey lines can be 

roughly estimated. At this time, the measurement length is 

only related to the number of measurements, in order to 

minimize the number of measurements, we should try to 

ensure the maximum gap, that is, the minimum overlap rate, 

so the overlap rate is set at 10%. Since the west is deep and the 

east is shallow, the measurement starts from the West Bank, 

and the area that the measurement strip cannot cover when it 

reaches the east coast is much smaller than the area starting 

from the east coast, and through programming verification, the 

number of measurements starting from the West Bank is less 

than the east side, so it is assumed that the survey ship starts 

from the West Bank. Through calculation, at least 34 

measurements are obtained, and the measurement line can 

completely cover the entire sea area. At this time, the total 

length of the measurement line is 125936m. 

At this time, the length of one measurement is the smallest, 

so if the measurement length is less than the direction of the 

measurement line is 90°, the number of measurements should 

be less than 34 times, so the objective function is as follows: 

𝐿(𝛽) = ∑
𝑚1

𝑠𝑖𝑛𝛽𝑖
, 𝑛 < 34𝑛

𝑖=1             (18) 



 

32 

According to the above conditions, use the exhaustive 

method for all possible traversal, and iteratively find the 

optimal solution [6]. 

𝑖  represents the cycle of angle 𝛽 , with the angle value 

range of (90, 153) For convenience, set the value range of 𝑖 
to (1, 64). 𝑗 represents the 𝑗 − 𝑡ℎ line of the ship moving 

forward when the angle is 𝑖. 𝛽𝑖,𝑗 represents the line angle of 

the 𝑗 − 𝑡ℎ line determined from the previous line after the 

angle represented by the first ship value is 𝑖. 
(1) When  𝑗 = 1 ,  the angle of pinch 𝛽𝑖,𝑗 is 91. 

In order to ensure that the total length of the measuring line 

is minimum and the number of measuring lines is small, the 

distance between each measuring line should be as far as 

possible. It is necessary to ensure that the distance between the 

north end of the initial position of the ship and the west bank 

can be fully covered and the distance from the left side is 

farthest. Based on the mathematical model of multi-beam 

measuring line, the farthest 𝑑 is solved under this fixed angle. 

At the same time, when the ship is in the initial position, the 

geometric model is established, as shown in Figure 7, to solve 

the total coverage length 𝑤𝑆𝑖,𝑗  and uncovered length 𝑥0 of the 

south bank of the initial position survey line. 

Suppose the distance from the bow to the west bank 𝑥𝑖,𝑗, 

which can be obtained from the knowledge of geometric 

relations and trigonometric functions: 

𝑥𝑖,𝑗 = 𝑑 +
𝑚1

𝑡𝑎𝑛𝛽𝑖,𝑗
               (19) 

Based on the mathematical model of strip coverage width, 

𝑊𝑆, 𝑊𝑆𝐿 and 𝑊𝑆𝑅 are obtained without coverage: 

𝑥0 = 𝑥1 −𝑊𝑆𝐿                  (20) 

Then, the total coverage length of the south bank is: 

𝑊𝑆 = 𝑥1 +𝑊𝑆𝑅                 (21) 

(2) Let 𝑗 =  𝑗 +  1. 

The overlap rate  𝜂𝑖,𝑗  between this line and the previous 

line 𝑗 − 1 is calculated according to the mathematical model 

of multi-beam line measurement, so that it meets the extreme 

value 𝜂𝑖,𝑗 = 0.1 . Subsequently, the unique line angle 𝛽𝑖,𝑗 

corresponding to the ship under this line of survey can be 

calculated. The geometric model of the ship under the survey 

line was established as shown in Figure 8, and the total 

coverage length of all the survey lines measured by the ship on 

the north and south banks was solved respectively. 

 

Figure 7. A geometric diagram of the ship's initial position 

 

Figure 8. Article 𝑗 Geometric diagram under the 

measurement line 

As shown in the figure, the distance from the measuring ship 

to the west bank is 𝑋𝑊(𝑖,𝑗), the total coverage length of the 

previous measuring strip on the north bank is 𝑊𝑛(𝑖,𝑗−1), the 

coverage length of the right side of the previous measuring 

strip is 𝑋𝑅(𝑖,𝑗−1), and the distance between the two measuring 

ships is 𝑑𝑖,𝑗, then: 

𝑋𝑊(𝑖,𝑗) = 𝑊𝑛(𝑖,𝑗−1) −𝑊𝑅(𝑖,𝑗−1) + 𝑑𝑖,𝑗        (22) 

According to the mathematical model of multi-beam 

measurement line, the depth of the sea water where the 

measurement ship is at this time and the coverage width of the 

measured strip here, as well as its left and right coverage width, 

𝑑𝑖,𝑗  can be obtained. 

The distance from the measuring ship on the south bank to 

the west bank can be obtained according to the geometric 

relationship: 

𝑋𝑆(𝑖,𝑗) = 𝑊𝑆(𝑖,𝑗−1) −𝑊𝑆𝑅(𝑖,𝑗−1) + 𝑑𝑖,𝑗 +
𝑚1

𝑡𝑎𝑛𝛽𝑖,𝑗
 (23) 

From this, we can solve 𝛽𝑖,𝑗 . According to this, the 

covering length of the south bank and the north bank can be 

solved as follows: 

𝜔𝑆 = 𝑋𝑆(𝑖,𝑗) +𝑊𝑆𝑅(𝑖,𝑗−1)           (24) 

𝜔𝑁 = 𝑋𝑁(𝑖,𝑗) +𝑊𝑁𝑅(𝑖,𝑗−1)           (25) 

Determine whether the ship has completed the survey of the 

sea area at this time. According to the obtained total coverage 

length 𝑋𝑆(𝑖,𝑗) and 𝑋𝑁(𝑖,𝑗) of the north and south coasts, if the 

coverage length of the sea area greater than that of the north 

and south coasts is satisfied as follows, then the cycle is 

withdrawn and a set of survey line scheme covering the entire 

sea area is obtained, and the total length of survey line 𝐿𝑖,𝑗 at 

this time is recorded. 

𝑋𝑆(𝑖,𝑗) ≥ 𝑚2 ∥ 𝑋𝑁(𝑖,𝑗) ≥ 𝑚2             (26) 

(3) The end of the cycle 𝑖 = 1. 

Let 𝑖 =  𝑖 +  1, iterate to solve the next set of test lines that 

meet the conditions.   
(4) Loop through until 𝑖 =  64 ends.  
According to the above model and code calculation, it is 

found that there is no direction of the survey line except 90°, 

so that the survey ship can complete the measurement of the 

entire sea area when only passing the north and south banks. 

3.3. Model Solution Results 

After model establishment, constraint conditions were 

selected, objective function was established, and different 

cases were classified and discussed, loop traversed, and the 



 

33 

total measurement length at this time was obtained through 

programming calculation. It was found that the minimum 

value of the total measurement length appeared in the range of 

102°-104°. Therefore, we adjusted the accuracy of the 

program to 0.01°, and found that the minimum appeared when 

the initial  𝛽𝑖,𝑗  was 103.88°, and there were 36 measuring 

lines with a total length of 124414.50 meters. 

4. Conclusion 

In this paper, the working principle and measuring process 

of multi-beam line are analyzed theoretically, and the 

mathematical model of multi-beam line is constructed. It is 

found that the coverage width of the line is affected by the 

depth of the sea water, the slope of the seabed and the angle of 

the line when the opening angle of the transducer is fixed. 

Based on the law, the optimal layout of the line is designed. 

After model establishment and solution, it can be seen that 

when the angle of the first measuring line is, the optimal 

situation is obtained, the number of measuring lines is  

𝛽𝑖, 1  =  103.88
。, and the total length is 124414.5m. At this 

time, the measurement lines are more densely distributed in 

the shallow part of the sea bottom, and less distributed in the 

deep part of the sea water, and the angle of the measurement 

lines 𝛽 gradually becomes larger as the sea water goes from 

shallow to deep. In the same way, the model can be extended 

to ship surveying, defense and other fields. 

References 

[1] Futian Xie, Zehua Li, Chunlei Wang, Jianing Hou. Research on 
multi-beam line measurement based on differential algorithm 
[A]. 2023 IEEE International Conference on Electrical, 
Automation and Computer Engineering (ICEACE) [C], 2023. 

[2] Xiaochen Yan, Lingfeng Lv, Rui Xi. Line Measurement of 
Multi-Beam Sounding System Based on Annealing Algorithm 
[A]. 2023 IEEE International Conference on Electrical, 
Automation and Computer Engineering (ICEACE) [C], 2023. 

[3] Hsi-Tseng Chou, Danai Torrungrueng. Development of 2-D 
Generalized Tri-Focal Rotman Lens Beamforming Network to 
Excite Conformal Phased Arrays of Antennas for General 
Near/Far-Field Multi-Beam Radiations[J]. IEEE Access,2021, 
Vol.9: 49176-49188. 

[4] Zakir Ullah, Xiaopeng Chen; Siyuan Gou, Yang Xu, 
Muhammad Salam. FNUG: Imperfect Mazes Traversal Based 
on Detecting and Following the Nearest-to-Final-Goal and 
Unvisited Gaps[J]. IEEE Robotics and Automation Letters, 
2022, Vol.7(2): 5175-5182. 

[5] Roman Barth, Biswajit Pradhan, Eugene Kim, Iain F Davidson, 
Jaco van der Torre, Jan-Michael Peters, Cees Dekker. Testing 
pseudotopological and nontopological models for SMC-driven 
DNA loop extrusion against roadblock-traversal experiments 
[J]. Scientific reports,2023, Vol.13(1): 8100. 

[6] Canesche M, Menezes M, Carvalho W, et al. Traversal: A fast 
and adaptive graph-based placement and routing for cgras[J]. 
IEEE Transactions on Computer-Aided Design of Integrated 
Circuits and Systems, 2020, Vol.40(8): 1600-1612.