CN116619355A - A global path planning method and system for a wall-climbing robot for weld detection - Google Patents

Abstract

The application discloses a global path planning method and a global path planning system for a welding seam detection wall climbing robot, which relate to petrochemical storage tank welding seam path planning, wherein the method comprises the following steps: establishing a kinematic modeling of the wall climbing robot; mapping three-dimensional weld stripes of a storage tank to be detected onto a two-dimensional plane, and creating a weld two-dimensional plane map; classifying and numbering the intersection points on the two-dimensional plane map, calibrating the length weight of the welding line, and dividing the detection area; establishing a path information mathematical model of the two-dimensional planar map by utilizing the classification and the numbering of the intersection points on the two-dimensional planar map, the length weight of the welding line and the detection area; and solving the path information mathematical model under the constraint condition of traversing all welding seams and the shortest path to obtain the optimal path. The application can greatly improve the efficiency of planning the shortest path of the global optimal path of the robot.

Description

A global path planning method and system for a wall-climbing robot for welding seam detection

technical field

The invention relates to path planning of weld seams of petrochemical storage tanks, in particular to a global path planning method and system for a wall-climbing robot for weld seam detection.

Background technique

Petrochemical storage tanks are an important tool for storing and transporting dangerous goods such as oil and natural gas. The tank body is welded by steel plates, and there are many welds on the inner wall. After long-term corrosion and impact, defects such as pores and cracks will appear on the surface of the weld. Weld defects in petrochemical storage tanks can cause oil leakage in light cases, and explosions in severe cases. Therefore, regular testing of welds is required. The traditional inspection of inner wall welds of petrochemical storage tanks is performed by manually carrying inspection tools into the tank body for inspection. This method not only has low detection efficiency and high missed detection rate, but also the working environment is extremely harmful to the health of inspectors. In recent years, with the continuous development of robot technology. In the field of petrochemical industry, it has become a major trend for crawling robots to replace manual inspections in various storage tanks. In order to realize the robot to complete the detection task quickly and efficiently, it is first necessary to plan a global optimal path for the robot. Under the condition of the optimal path, ensure that the robot can accurately complete the detection according to the planned path. Different from the path planning of ordinary mobile robots, the path distribution of the 3D storage tank inspection robot is a 3D map, and at the same time, it has two constraints of traversing all welds and the shortest path. There are a large number of intersections and obstacles in the map. Therefore, The map must be simplified and a reasonable model must be established for solution.

Most of the existing path planning methods for crawling robots are only suitable for ordinary two-dimensional planar mobile robots, and many methods are not applicable when encountering three-dimensional complex environments. And most of the research is on the global path planning for the point-to-point optimal path or the full traversal of the environment. There are relatively few global path planning methods for solving the two-constraint problem that passes through all known routes and has the shortest path.

Contents of the invention

Aiming at the deficiencies in the prior art, the present invention provides a global path planning method and system for a welding seam detection wall-climbing robot, which can solve the problem that there are a large number of intersections and obstacles in the three-dimensional path planning, and at the same time have the ability to traverse all welds and have the shortest path The global path planning problem with two constraints can greatly improve the efficiency of planning the shortest path for the global optimal path of the robot.

To achieve the above object, the present invention provides the following technical solutions:

In the first aspect, the present invention provides a global path planning method for a wall-climbing robot for weld detection, which includes:

Establish kinematics modeling of wall-climbing robot;

Create a two-dimensional map of the weld by mapping the three-dimensional weld stripes of the tank to be inspected onto a two-dimensional plane;

Classify and number the intersection points on the two-dimensional planar map and calibrate the length weight of the weld, and divide the detection area at the same time;

Using the classification and numbering of the intersection points on the two-dimensional planar map, the length weight of the weld and the detection area, the mathematical model of the path information of the two-dimensional planar map is established;

Under the constraints of traversing all welds and the shortest path, the path information mathematical model is solved to obtain the optimal path.

In the second aspect, the present invention provides a global path planning system for a wall-climbing robot for weld detection, which includes:

A first processor, which is used to establish the kinematics modeling of the wall-climbing robot;

a second processor configured to map the three-dimensional weld stripes of the storage tank to be inspected onto a two-dimensional plane, thereby creating a two-dimensional plane map of the weld;

A third processor, which is used to classify and number the intersection points on the two-dimensional planar map and calibrate the length weight of the weld, and divide the detection area at the same time;

A fourth processor, which is used to establish a path information mathematical model of the two-dimensional plan map by using the classification and numbering of the intersection points, the length weight of the weld and the detection area on the two-dimensional plan map;

The fifth processor is configured to solve the mathematical model of the path information under the two constraints of traversing all welds and the shortest path to obtain an optimal path.

Compared with the prior art, the present invention has the beneficial effects of:

(1) The present invention constructs a global path planning system and method for a three-dimensional tank inner wall weld detection robot. Realize "quick mapping of two-dimensional weld map→quick creation of weld node mathematical model→improved shortest path planning algorithm→rapid global path planning" for crawling detection robots, and support real-time online planning of the shortest path of online detection robots.

(2) The present invention proposes a calculation method based on the weight wt(Li) of the robot walking path based on the length of the weld path, improves the calculation method and node search strategy of the cost value f(n) of the A* algorithm, and solves the problem of full traversal of the weld And the two-constraint global path planning problem of the shortest path, the algorithm development is fast, the magnitude is low, and it can quickly iterate the shortest path for the wall-climbing detection robot.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings that need to be used in the embodiments will be briefly introduced below. Obviously, the drawings in the following description are only some embodiments of the application. For Those of ordinary skill in the art can also obtain other drawings based on these drawings without making creative efforts.

Fig. 1 is a schematic diagram of the mapping relationship of weld seam maps of petrochemical storage tanks in an embodiment of the invention, Fig. 1(a) is a diagram of a three-dimensional distribution model of weld seams, and Fig. 1(b) is a two-dimensional map of weld seam distribution.

Fig. 2 is a distribution map of weld lines and intersection points in the embodiment of the invention.

Fig. 3 is a schematic diagram of a weld joint model in an embodiment of the invention.

Fig. 4 is an iterative flow chart of the path planning algorithm in the embodiment of the invention.

Fig. 5 is an illustration of the planning results of the global path planning in the embodiment of the invention, Fig. 5(a) is the shortest path connectivity graph, and Fig. 5(b) is an illustration of the shortest path two-dimensional map result.

Fig. 6 is a method flow chart of the global path planning method of the wall-climbing robot in the embodiment of the invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present application, not all of them. Based on the embodiments in this application, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the scope of protection of this application.

Example:

It should be noted that the terms "first" and "second" in the description and claims of the present invention and the above drawings are used to distinguish similar objects, but not necessarily used to describe a specific sequence or sequence. It is to be understood that the data so used are interchangeable under appropriate circumstances such that the embodiments of the invention described herein can be practiced in sequences other than those illustrated or described herein. In addition, the terms "comprising" and "having" and any variations thereof in the embodiments of the present invention are intended to cover a non-exclusive inclusion, for example, a process, method, system, product or device comprising a series of steps or units is not necessarily limited to Those steps or elements are not explicitly listed, but may include other steps or elements not explicitly listed or inherent to the process, method, product or apparatus.

The global path planning method proposed by the present invention is applied to crawling robots for all complex cross-weld detection tasks on the inner wall of large storage tanks, to find a shortest detection path for a two-wheeled differential crawling robot to traverse all welds, and accurately follow the planning path completion detection task. It can be understood that reasonable path planning can improve the efficiency of detection. Since the distribution of welds on petrochemical storage tanks is all known, this planning belongs to offline path planning. Different from the path planning of mobile robots in ordinary two-dimensional work environments, the path distribution of this problem is in a three-dimensional environment, and at the same time, it needs to meet the two constraints of traversing all welds and the shortest path, and there are intersections of partitions and obstacle. Therefore, the three-dimensional map must be simplified and a reasonable mathematical model of weld information must be established for solution.

Furthermore, the present invention first proposes a method for creating a two-dimensional map of the weld, and then proposes an improved A* algorithm cost value f(n) calculation method and search strategy to plan the global shortest path for the robot. The specific process includes: 1) Quickly map the 3D weld stripes to a 2D plane, and create a 2D plane map of the weld; 2) Propose a sorting method for weld stripes based on weight accumulation, and establish a mathematical model of the weld; 3) Propose the region The division method finds the shortest path, reduces the number of iterations, and efficiently plans the shortest path; 4) By establishing the Openlist() node set and the Closelist() node set, and then improving the calculation method of the cost value f(n) of the A* algorithm and the node search strategy , reducing the number of iterations, can quickly plan the shortest global route.

Referring to Figure 6, a global path planning method for a wall-climbing robot for large-scale storage tank weld detection may include the following steps:

Step 1: Establish the kinematics modeling of the wall-climbing robot.

In this step, the wall-climbing robot needs to complete the traversal inspection of the inner wall weld of the storage tank, and it needs to analyze its motion state and motion force, so that the robot can plan the detection path and robot control. In the embodiment of the present invention, the robot is regarded as a rigid body in the process of analyzing the crawling detection robot, and lateral slippage is not considered.

Step 2: Map the 3D weld stripes of the tank to be inspected onto a 2D plane to create a 2D plane map of the weld.

In this step, since the welds of large storage tanks are three-dimensional maps according to the absolute coordinate system, in order to plan the shortest path, the first thing to find out is the relative positional relationship between each weld and the length of each weld, through algorithm iteration Find the shortest path for the robot. Therefore, the first thing to be solved is to map the weld seam on the petrochemical storage tank to a two-dimensional plane map. The embodiment of the present invention uses a two-dimensional equivalent expansion method to equivalently transform the circular weld seam on the curved surface to a two-dimensional plane, thereby quickly A two-dimensional planar map is established; then, the planning of the weld detection path is established on the basis of the two-dimensional planar map of the weld.

As shown in Figure 1(a), the detection object of the embodiment of the present invention is a large-scale petrochemical storage tank. Specifically, the tank body is welded by annular steel plates, and the annular cylinder is welded into the tank body, and a The baffle, wherein a through hole is opened in the baffle, and the through hole is used as the only passage for the detection robot to enter the inside.

Based on the above analysis, the tank weld information is converted into a two-dimensional map as shown in Figure 1(b). The dark black thick line is the weld; the light black line separator is the shortest path connecting the regions at both ends of the through hole. That is, the robot can walk the path; the dotted line is the baffle in the tank; in addition, the big black dot represents the starting point and the end point of the robot; the hollow dot is the through hole of the baffle, indicating that it is passable; the small black dot represents the welding seam The intersection point with the baffle indicates that it is impassable, thus converting the three-dimensional route into a two-dimensional route.

Step 3: Classify and number the intersection points on the two-dimensional planar map, calibrate the length weight of the weld, and divide the detection area at the same time.

In this step, it is then necessary to classify, number and calibrate the length weights of the welds and intersection points on the two-dimensional planar map, so as to facilitate subsequent algorithm iterations. Among them, the intersection points are divided into girth weld breakpoint A _n , obstacle point B _n , passable point C _n (at the baffle opening), weld intersection D _n , weld and path intersection E _n , and the marking results are as follows Figure 2 shows. Due to the difference between the surface distance and the space Euclidean distance between nodes, errors will occur when the traditional path planning algorithm based on the space Euclidean distance between nodes is used to calculate the optimal path on the surface. Therefore, after expansion, the length of the weld seam will be proposed for weighting, and the weight value et() of each weld seam length satisfies the formula (1).

A ₁ A ₁ =A ₂ A ₂ =A ₃ A ₃ =A ₄ A ₄ >B ₁ B ₂ >D ₁ B ₁ =B ₂ D ₄ >D ₃ B ₂ =B ₁ D ₂ (1)

In addition, in order to reduce the number of algorithm iterations in the later stage, improve the efficiency of path planning, and reduce the repetition rate. The embodiment of the present invention adopts the "proximity principle" to divide the detection area into zone I, zone II and zone III, and plan and connect them one by one.

Step 4: Using the classification and numbering of the intersection points on the two-dimensional planar map, the length weight of the weld and the detection area, a mathematical model of the route information of the two-dimensional planar map is established.

In this step, the embodiment of the present invention is not a simple point-to-point optimal path problem, but a problem similar to the "Chinese courier problem on an undirected graph". All streets in the area and back to the post office, how to walk to make the shortest distance. Constraints include the two conditions of traversing all weld paths and the shortest path.

Based on this, the graph theory language description of the path planning problem is as follows:

Suppose the undirected connected graph H={L _n ,E,wt(L _i )}, all the edges L _i form the set network E, and the weight value wt(L _i ) of the path traveled by the robot is calculated uniformly from the length of the weld seam , and wt(L _i )≥0, find a path π including all edges, and Σ _a∈L wt(L _i ) is the smallest.

1) First, we analyze the two-dimensional map, and calculate and mark the weight of the weld. Since the dotted line in the map is the impassable area, from Zone I to Zone II, and from Zone II to Zone III, you can only pass through the baffle opening (C).

2) Each point can only walk along the calibrated straight line in the two-dimensional planar map (the shortest path requirement), and the corresponding weights are accumulated.

3) Establish the mathematical model of weld stripe nodes as shown in Figure 3, and iterate through the algorithm to find the minimum series sequence of Σ _a∈L wt(L _i ), which is the shortest path π.

Step 5: Under the constraints of traversing all welds and the shortest path, solve the path information mathematical model to obtain the optimal path.

In this step, after the mathematical model of the weld joint is established, it is necessary to propose a suitable method for finding a short path for iteration, and then complete the global path planning of the wall-climbing robot. Specifically, by analyzing the advantages and disadvantages of the existing methods, the application of the A* algorithm is more flexible and the convergence speed is fast. The embodiment of the present invention proposes an optimal path planning method for the full traversal of the wall-climbing detection robot weld seam by improving the A ^* algorithm.

Wherein, in the embodiment of the present invention, the starting point and the ending point of the path are set as the same point, and then, the cost value f(n) from each weld node Ln to the starting point and the ending point is calculated, and the comprehensive priority of a single node in the A* algorithm is given by Formula (2) decides.

f(n)=g(n)+h(n) (2)

In the formula, f(n) is the comprehensive priority of weld node Ln; g(n) is the minimum cost of node Ln from the starting point; h(n) is the minimum cost of node Ln from the end point. In the embodiment of the present invention, g(n) and h(n) can be calculated by formula (3) by calculating the minimum weights from the current weld node to the start point and the end point respectively. Furthermore, the cost value from the node to the target point can be estimated by the Euclidean distance to meet the shortest path requirement, so as to obtain the shortest path weight Σ _a∈L wt(L _i ). Further, through algorithm iteration, after planning the shortest path, the robot returns to the end point according to the set route, as shown in Figure 5, which shows the diagram of the global path planning planning results in the embodiment of the invention, Figure 5(a) The shortest path connectivity graph is shown, and Fig. 5(b) shows the result diagram of the shortest path two-dimensional map.

g(n)=h(n)=∑ _a∈L wt(L _i-1 ) (3)

In the above embodiment, as shown in Figure 4, the algorithm iteration method is specifically:

Step 101: create an open list (open list) and a closed list (closed list),

Step 102: Put all nodes Ln into an open list (open list), and judge whether the open list (open list) is empty;

Step 103: judging whether the open list (open list) is empty, if so, jump to execution step 108, otherwise execute step 104;

Step 104: put the node with the smallest f(n) in the open list (open list) into the closed list (closed list);

Step 105: judge whether f(n) is empty, if so, execute step 106, otherwise return to execute step 104;

Step 106: determine whether the open list (open list) is empty, if so, execute step 107, otherwise return to execute step 104;

Step 107: Return to the starting point according to the preset route.

Step 108: End iteration.

To sum up, the global path planning method proposed by the present invention is applied to crawling robots for all complex cross weld detection tasks on the inner wall of large storage tanks, to find a shortest detection path for a two-wheeled differential crawling robot to traverse all welds, And accurately complete the detection task according to the planned path. Reasonable path planning can improve the efficiency of detection. Since the distribution of welds on petrochemical storage tanks is all known, this planning belongs to offline path planning. Different from the path planning of mobile robots in ordinary two-dimensional work environments, the path distribution of this problem is in a three-dimensional environment, and at the same time, it needs to meet the two constraints of traversing all welds and the shortest path, and there are intersections of partitions and obstacle. Therefore, the three-dimensional map must be simplified and a reasonable mathematical model of weld information must be established for solution.

Further, the present invention constructs a global path planning system and method for a three-dimensional tank inner wall weld detection robot. Realize "quick mapping of two-dimensional weld map→quick creation of weld node mathematical model→improved shortest path planning algorithm→rapid global path planning" for crawling detection robots, and support real-time online planning of the shortest path of online detection robots. In addition, the present invention proposes a calculation method for the weight wt(Li) of the robot's walking path based on the length of the weld path, improves the calculation method of the cost value f(n) of the A* algorithm and the node search strategy, and solves the problem of full traversal of the weld and The two-constraint global path planning problem of the shortest path, the algorithm development is fast, the magnitude is low, and the shortest path can be quickly iterated for the wall-climbing detection robot.

Furthermore, the global path planning system and method for the three-dimensional tank wall-climbing robot proposed by the present invention solves the problem that the existing path planning method is not suitable for solving the two-constraint problem of passing through all known routes and the shortest path, and can quickly convert the three-dimensional map Information is mapped to a two-dimensional plane; a mathematical model of the map path is established. It will greatly improve the planning efficiency of the global path, which has important scientific and engineering significance.

Based on the same inventive concept, an embodiment of the present invention also provides a global path planning system for a wall-climbing robot for large-scale storage tank weld detection, which includes a first processor, a second processor, a third processor, a fourth processor and a Five processors, specifically, the first processor is used to establish the kinematics modeling of the wall-climbing robot; the second processor is used to map the three-dimensional weld stripes of the storage tank to be detected to a two-dimensional plane, and create a two-dimensional welding seam Plane map; the third processor is used to classify and number the intersection points on the two-dimensional planar map and calibrate the length weight of the weld, and divide the detection area at the same time; the fourth processor is used to classify and number the intersection points on the two-dimensional planar map , the length weight of the weld and the detection area, and establish the path information mathematical model of the two-dimensional plane map; the fifth processor is used to solve the path information mathematical model under the two constraints of traversing all welds and the shortest path, and obtain the most optimal path.

Since this system is a system corresponding to the global path planning method of a wall-climbing robot for large-scale storage tank weld seam detection in the embodiment of the present invention, and the problem-solving principle of this system is similar to this method, so the implementation of this system can refer to the above-mentioned method embodiment The implementation process will not be repeated here.

In the description of this specification, descriptions referring to the terms "one embodiment", "some embodiments", "example", "specific examples", or "some examples" mean that specific features described in connection with the embodiment or example , structure, material or characteristic is included in at least one embodiment or example of the present invention. In this specification, the schematic representations of the above terms are not necessarily directed to the same embodiment or example. Furthermore, the described specific features, structures, materials or characteristics may be combined in any suitable manner in any one or more embodiments or examples. In addition, those skilled in the art can combine and combine different embodiments or examples and features of different embodiments or examples described in this specification without conflicting with each other.

The above-mentioned embodiments are only to illustrate the technical concept and characteristics of the present invention, and its purpose is to enable those of ordinary skill in the art to understand the content of the present invention and implement it accordingly, and cannot limit the protection scope of the present invention. All equivalent changes or modifications made according to the essence of the content of the present invention shall fall within the protection scope of the present invention.

Claims (10)

1. The global path planning method of the welding seam detection wall climbing robot is characterized by comprising the following steps of:

establishing a kinematic modeling of the wall climbing robot;

mapping three-dimensional weld stripes of a storage tank to be detected onto a two-dimensional plane, thereby creating a two-dimensional plane map of the weld;

classifying and numbering the intersection points on the two-dimensional plane map and calibrating the length weight of the welding line, and dividing a detection area;

establishing a path information mathematical model of the two-dimensional planar map by utilizing the classification and the numbering of the intersection points on the two-dimensional planar map, the length weight of the welding line and the detection area;

and solving the path information mathematical model under the constraint conditions of traversing all welding seams and the shortest path to obtain an optimal path.

2. The global path planning method of a weld seam detection wall climbing robot according to claim 1, wherein the wall climbing robot is regarded as a rigid body and lateral slippage is not considered when establishing a kinematic model of the wall climbing robot.

3. The method for global path planning of a weld seam detection wall climbing robot of claim 1, wherein the path on the two-dimensional planar map comprises a weld seam, a robot walkable path, and a robot non-walkable path; the intersection points comprise a starting point, a terminal point, a girth joint breakpoint, an obstacle point, a passable point, a welding joint intersection point and a welding joint and path intersection point; the divided detection areas are serially connected one by one.

4. The global path planning method of a weld seam detection wall climbing robot according to claim 1, wherein the path information mathematical model of the two-dimensional planar map includes: undirected connectivity graph h= { L _n ,E,wt(L _i ) All paths L _i Forms a collective network E, and the weight value of the path of the wall climbing robot (L _i ) Is uniformly calculated from the length of the weld, and the weight (L _i ) Not less than 0, find a path pi containing all edges, and Σ _a∈L wt(L _i ) The minimum, wherein, the detection area divided can only pass through the passable point; only straight lines marked in a two-dimensional plane map can be run between each two-dimensional plane map, corresponding weights are accumulated, iteration is carried out through an algorithm, and sigma is found out _{a∈ L} wt(L _i ) The minimum series order is the shortest path pi.

5. The global path planning method of a welding seam detection wall climbing robot according to claim 4, wherein a start point and an end point of a path are set to be the same point, and then a comprehensive priority f (n) from each welding seam node Ln to the start point and the end point is calculated by using an a-x algorithm, wherein the comprehensive priority of a single node in the a-x algorithm is determined by the following formula:

f(n)＝g(n)+h(n)

wherein f (n) is the comprehensive priority of the weld joint node Ln; g (n) is the minimum cost of the node Ln from the start point; h (n) is the minimum cost of the node Ln from the end point; g (n) and h (n) calculate the minimum weights of the current weld joint node to the starting point and the end point through the following formulas respectively:

g(n)＝h(n)＝∑ _a∈L wt(L _i-1 )。

6. a weld detection wall climbing robot global path planning system, comprising:

a first processor for establishing a kinematic model of the wall climbing robot;

a second processor for mapping three-dimensional weld stripes of the storage tank to be detected onto a two-dimensional plane, thereby creating a two-dimensional plane map of the weld;

the third processor is used for classifying and numbering the intersection points on the two-dimensional plane map and calibrating the length weight of the welding line, and dividing a detection area;

the fourth processor is used for establishing a path information mathematical model of the two-dimensional plane map by utilizing the classification and the number of the intersection points on the two-dimensional plane map, the length weight of the welding line and the detection area;

and the fifth processor is used for solving the path information mathematical model under the constraint condition of traversing all welding seams and the shortest path to obtain the optimal path.

7. The weld inspection wall climbing robot global path planning system of claim 6, wherein the wall climbing robot is considered a rigid body and lateral slip is not considered when establishing the kinematic modeling of the wall climbing robot.

8. The weld inspection wall climbing robot global path planning system of claim 6, wherein the path on the two-dimensional planar map comprises a weld, a robot walkable path, and a robot non-walkable path; the intersection points comprise a starting point, a terminal point, a girth joint breakpoint, an obstacle point, a passable point, a welding joint intersection point and a welding joint and path intersection point; the divided detection areas are serially connected one by one.

9. The weld inspection wall climbing robot global path planning system according to claim 6, wherein the path information mathematical model of the two-dimensional planar map comprises: undirected connectivity graph h= { L _n ,E,wt(L _i ) All paths L _i Forms a collective network E, and the weight value of the path of the wall climbing robot (L _i ) Is uniformly calculated from the length of the weld, and the weight (L _i ) Not less than 0, find a path pi containing all edges, and Σ _a∈L wt(L _i ) The minimum, wherein, the detection area divided can only pass through the passable point; only straight lines marked in a two-dimensional plane map can be run between each two-dimensional plane map, corresponding weights are accumulated, iteration is carried out through an algorithm, and sigma is found out _{a∈ L} wt(L _i ) The minimum series order is the shortest path pi.

10. The global path planning system of a weld inspection wall climbing robot according to claim 6, wherein the start point and the end point of the path are set to the same point, and then the comprehensive priority f (n) from each weld node Ln to the start point and the end point is calculated by using an a-algorithm, wherein the comprehensive priority of a single node in the a-algorithm is determined by the following formula:

f(n)＝g(n)+h(n)

wherein f (n) is the comprehensive priority of the weld joint node Ln; g (n) is the minimum cost of the node Ln from the start point; h (n) is the minimum cost of the node Ln from the end point; g (n) and h (n) calculate the minimum weights of the current weld joint node to the starting point and the end point through the following formulas respectively:

g(n)＝h(n)＝∑ _a∈L wt(L _i-1 )。