CN-121980717-A - Cable dynamic planning method and system based on triangular subdivision and graph neural network

CN121980717ACN 121980717 ACN121980717 ACN 121980717ACN-121980717-A

Abstract

The invention discloses a cable dynamic planning method and system based on triangular subdivision and graph neural network, wherein the system comprises an equipment layout module, a routing function module, a routing result module and a graph convolution neural network-based routing module, wherein the equipment layout module is used for inputting equipment data of routing operation, carrying out equipment nodulation and equipment automatic alignment on the equipment data, the routing module based on a triangulation algorithm is used for routing, adding auxiliary points and auxiliary triangles, continuously judging whether edges are local Delaunay edges in the adding process, simultaneously carrying out edge overturning operation and local optimization to obtain a routing graph, the routing module based on the graph convolution neural network is used for constructing and initializing a graph model according to the routing graph, constructing a graph convolution neural network, processing routing graph characteristics in the graph model through the graph convolution neural network, calculating errors, constructing a routing loss function, calculating the loss function and updating weights through a plurality of iterative processes, and outputting a final routing result. The invention realizes intelligent planning and automatic generation of wiring paths, and improves wiring efficiency and precision.

Inventors

LUO WEI
WU SHENG
Lin Pinhui
LIU LEYUAN
LIU YUANYUAN
FAN HUILI

Assignees

中国舰船研究设计中心

Dates

Publication Date: 20260505
Application Date: 20251226

Claims (10)

1. The cable dynamic planning method based on the triangular subdivision and the graph neural network is characterized by comprising the following steps of: s1, inputting equipment data to be subjected to wiring operation, and preprocessing the equipment data, wherein the preprocessing operation comprises equipment nodulation and automatic equipment alignment; S2, wiring the preprocessed equipment data by adopting a triangulation algorithm, adding auxiliary points and auxiliary triangles, continuously judging whether the edges are local Delaunay edges or not in the adding process, and simultaneously performing edge overturning operation and local optimization to obtain a wiring diagram; S3, constructing and initializing a graph model according to the wiring diagram, regarding elements as graph vertices and connections between the elements as edges of the graph, constructing a graph convolution neural network, processing wiring diagram features in the graph model through the graph convolution neural network, calculating errors, constructing a wiring loss function, calculating the loss function through a plurality of iterative processes, updating weights, and outputting a final wiring result.
2. The method for dynamically planning cables based on triangular subdivision and graph neural network according to claim 1, wherein the method of step S1 specifically comprises: s11, inputting equipment data; s12, equipment nodalization, namely traversing all input equipment, extracting a rectangle corresponding to each equipment, and taking the first point coordinate of the upper left corner as a topological node to enable physical equipment to be abstract as a point; S13, automatically aligning the equipment, wherein the alignment modes comprise horizontal reference alignment and vertical reference alignment, and optimizing layout of the equipment through a self-adaptive dynamic adjustment algorithm according to the selected alignment mode.
3. The method for dynamic planning of cables based on triangular split and graph neural network according to claim 2, wherein the device data input in step S11 includes: The specific position of the equipment is fixed in advance and is displayed in a certain arrangement mode in the figure; Based on the data of unknown device positions, only the number of devices and their connection relation to each other.
4. The method for dynamically planning cables based on the triangular section and graph neural network according to claim 2, wherein the method of step S13 specifically comprises: In a horizontal reference alignment mode, the self-adaptive dynamic adjustment algorithm adopts a horizontal axis equidistant constraint algorithm, and all selected devices are equidistantly arranged along a horizontal axis; In the vertical reference alignment mode, the self-adaptive dynamic adjustment algorithm adopts a vertical axis reference line constraint algorithm to align the reference lines of all selected devices along the vertical axis.
5. The method for dynamically planning cables based on triangular subdivision and graph neural network according to claim 2, wherein the method in step S2 specifically comprises: S21, adding auxiliary points and triangles, namely abstracting preprocessed equipment data into a point set Pn represents an nth topological node, the problem of searching a proper path is converted into the problem of constructing a proper triangle, and a triangle set meeting the condition is generated ; S22, judging whether the edge is a local Delaunay edge, namely traversing each edge e in the triangle set T, judging whether each edge e meets the local Delaunay condition, namely checking whether the circumscribed circle of two triangles to which the edge e belongs contains any other vertex in the two triangles, and executing the step S23 if a certain circumscribed circle does not meet the condition; S23, edge turning operation and local optimization, wherein the edge e is assumed to belong to two triangles, a quadrangle is formed by a collection of the two triangles, one of the quadrangle is e, two new triangles are obtained by replacing e with the other diagonal, the two new triangles are used for replacing corresponding parts in the original triangulation, so that a new triangulation is generated, the quality of the triangulation is optimized locally to enable the triangulation to be more similar to an ideal Delaunay triangulation every time the edge turning operation is executed, the edge turning operation is repeatedly executed on the triangle collection T, the quality of the whole triangulation is improved, the global optimization result is obtained, and the optimal path is output as a wiring diagram.
6. The method for dynamically planning cables based on triangular subdivision and graphic neural network according to claim 5, wherein the method for generating the triangle set satisfying the condition in step S21 specifically includes: the endpoints of all triangles just make up the set P; the sides of any two triangles are not intersected; the collection of all triangles forms a convex hull of P; Since the set P is not unique, the optimal triangulation is chosen by the following quality assessment criteria: The minimum angle is the minimum angle among the inner angles of all triangles; Wherein, the Representing the smallest interior angle in triangle delta, triangulation Is such that Maximum triangulation; aspect ratio: the ratio of the shortest side to the longest side of the triangle; Radius ratio is the ratio of twice the radius of the triangle inscribed circle to the radius of the circumscribed circle.
7. The method for dynamically planning cables based on triangular subdivision and graph neural network according to claim 1, wherein the method of step S3 specifically comprises: S31, building and initializing a graph model, namely building the graph model according to a wiring diagram, wherein each node V represents a wiring connection point or equipment, each side E represents physical connection between nodes Constructing a graph convolutional neural network, which comprises 6 graph roll layers; S32, constructing a loss function, namely obtaining total loss by calculating the weighted sum of the intersection loss, the length loss and the bending loss as a wiring loss function; S33, weight updating and iteration, namely optimizing towards the direction of decreasing a loss function by taking total loss as a measure, wherein in the single iteration process, the graph convolution neural network adopts a self-adaptive momentum optimizer to carry out counter propagation, and related parameters of the graph convolution neural network are synchronously updated after each iteration, so that the geometric arrangement and the electrical performance of the cable wiring are cooperatively optimized; and S34, outputting a wiring result, namely when the total loss value of n continuous iterations is reduced by less than a threshold epsilon, ending the iteration by the graph convolution neural network, and finally outputting an electric wiring result graph conforming to various specifications.
8. The method for dynamically planning cables based on triangular dissection and graph neural network according to claim 7, wherein the method for constructing the graph convolutional neural network in step S31 specifically comprises the following steps: The graph convolutional neural network comprises 6 graph roll layers; In the first layer of graph convolution layer, the model only considers the characteristics of the direct neighbor nodes, while in the second layer of graph convolution layer, the model extends to consider the characteristics of the second-order neighbor nodes, and so on until the sixth layer of graph convolution layer, an activation function is used after each layer of graph convolution layer operates to introduce nonlinear characteristics in the data propagation process, and the description of the graph convolution layer is the following mathematical equation: Where Z represents the output of the graph convolutional layer, A' is the normalized graph adjacency matrix, F is the node feature matrix, W is the trainable weight matrix, b is the bias vector, and σ is the activation function.
9. The method for dynamic planning of cables based on triangular split and graph neural network according to claim 7, wherein the method for calculating the total loss in step S32 comprises: The calculation formula of the intersection point loss is as follows: Wherein, the Indicating the number of crossing points in the connection, Indicating the number of "must-intersect links" among these links, Representing the total number of lines when When 0, it indicates that there is no intersection of the links, or that all intersection are necessary and unavoidable, and the index value is calculated 100%, I.e. the desired ideal case; the calculation formula of the length loss is as follows: Wherein, the An index value indicating that the total length of the wiring exceeds the theoretical length is generated, and the smaller the value is, the more desirable is, Indicating the actual length of the wiring, Representing the theoretical maximum length threshold of the wiring when When 0, this means that the wiring length reaches the theoretical length, and the index value is calculated Calculating an index value generated by the length of each wiring line being greater than a theoretical length maximum threshold value to obtain a final index value; The calculation formula of the bending loss is as follows: Wherein, the Representation of The number of all bending points on the wiring, Indicating the minimum number of bends of this wire, Index value indicating that the number of bending times of the wiring exceeds the minimum number of bending times when When the value is 0, meaning that all bending points on the wiring reach theoretical minimum values, calculating an index value generated by the fact that the actual bending times are larger than the minimum bending times on each wiring, and obtaining a final index value; The total loss is based on the intersection loss, the length loss and the bending loss, and is obtained by calculating the weighted sum of the three: Wherein, the The value of the total loss is indicated, In order for the intersection point to be lost, In order for the length to be lost, In order for the bending loss to occur, 、、 Is the weight of each loss.
10. The cable dynamic planning system based on the triangular subdivision and graph neural network is characterized by comprising the following modules: the device layout module is used for inputting device data to be subjected to wiring operation and preprocessing the device data, and comprises device nodulation and device automatic alignment; The wiring module based on the triangulation algorithm is used for wiring the preprocessed equipment data, adopting the triangulation algorithm to add auxiliary points and auxiliary triangles, continuously judging whether the edges are local Delaunay edges or not in the adding process, and simultaneously performing edge overturning operation and local optimization to obtain a wiring diagram; The wiring module based on the graph convolution neural network is used for constructing and initializing a graph model according to a wiring diagram, regarding elements as graph vertices and connections between the elements as edges of the graph, constructing the graph convolution neural network, processing wiring diagram features in the graph model through the graph convolution neural network, calculating errors, constructing a wiring loss function, calculating the loss function through a plurality of iterative processes, updating weights and outputting a final wiring result.

Description

Cable dynamic planning method and system based on triangular subdivision and graph neural network Technical Field The invention relates to the technical field of computer graphics, in particular to a cable dynamic planning method and system based on triangular subdivision and graph neural network. Background With the acceleration of new urbanization processes and the upgrade of intelligent manufacturing industry, modern urban infrastructure and industrial systems put higher dimensional demands on cable routing technology. As a key technical support for power transmission and digital communication systems, maximizing the benefits of implementing cable network topology design work has become particularly important in engineering practice. Cabling problems often involve multiple objectives such as minimizing cable length, reducing crossovers, avoiding obstructions, ensuring a clear and clean cable lay-out, etc. Optimizing global cable layout by combining geometric knowledge in traditional graphics with deep learning optimization strategies is a popular direction of current research. In recent years, triangulation algorithms based on computational geometry have received attention because of their ability to efficiently process complex spatial data. The triangulation algorithm not only can help engineers to quickly find an optimal or near-optimal wiring scheme, but also can improve the safety and reliability of wiring, reduce engineering cost and improve the economic and social benefits of the whole engineering through simulation and optimization. Conventional routing algorithms generally assume that the environment is simple and regular, such as a two-dimensional plane or grid. However, in practical engineering, the cabling environment is often very complex, with a variety of obstacles and a variety of constraints. The graph convolutional neural network algorithm can directly process the complex topological structure without simplifying the problem into a regular grid, so that the actual environment is modeled more accurately. This patent needs to solve following technical problem: The traditional cable wiring method depends on experience and simple geometric rules, and can meet basic requirements, but is insufficient in a complex environment: (1) Insufficient degree of automation The existing cable routing system has certain defects in terms of automation and intelligence. Many operations still rely on manual intervention, resulting in inefficiency and susceptibility to human error, increasing operational risk and cost. (2) Group intelligent algorithm is easy to fall into local optimum They can effectively address complex problems with multiple constraints and objectives, and perform better in particular when solving wiring problems in multi-objective optimization and complex environments. However, such methods have the disadvantages of high computational overhead, possibly long computation time, unstable algorithm results due to the selection of parameter settings, and problems of local optimal solutions. (3) Deep learning techniques require higher computational resources Deep learning and reinforcement learning are emerging technologies that perform path optimization and constraint handling in cabling problems by training neural network models or using reinforcement learning algorithms. While these methods have potential in handling complex, dynamically changing wiring environments, they currently face problems of high computational resource requirements, difficult data set construction, long training time, etc., and adaptability to different scenarios still requires further exploration and improvement. In conclusion, the advantages of the interdisciplinary are utilized, and the prior knowledge of the calculation geometry is combined with the deep learning algorithm, so that complex spatial data can be processed more efficiently. Disclosure of Invention Aiming at the defects in the prior art, the invention provides a cable dynamic planning method and system based on triangular sectioning and graph neural network. The technical scheme adopted for solving the technical problems is as follows: the invention provides a cable dynamic planning method based on triangular subdivision and graph neural network, which comprises the following steps: s1, inputting equipment data to be subjected to wiring operation, and preprocessing the equipment data, wherein the preprocessing operation comprises equipment nodulation and automatic equipment alignment; S2, wiring the preprocessed equipment data by adopting a triangulation algorithm, adding auxiliary points and auxiliary triangles, continuously judging whether the edges are local Delaunay edges or not in the adding process, and simultaneously performing edge overturning operation and local optimization to obtain a wiring diagram; S3, constructing and initializing a graph model according to the wiring diagram, regarding elements as graph vertices and connections between th