Search

CN-121977597-A - Lung vessel targeting robot path planning method for improving RRT algorithm

CN121977597ACN 121977597 ACN121977597 ACN 121977597ACN-121977597-A

Abstract

The invention discloses a path planning method of a pulmonary vascular targeting robot with an improved RRT algorithm, and belongs to the technical field of robot path planning. The method comprises the steps of loading a pulmonary vascular STL model and initializing a space boundary, generating candidate sampling points by adopting a self-adaptive strategy, then carrying out accurate in-vivo collision detection to ensure that all nodes and path segments are strictly positioned in a vascular cavity, carrying out node expansion and progressive path optimization on the detected sampling points by utilizing a neighborhood search, optimal father node selection and reconnection optimization mechanism of an RRT algorithm, and finally carrying out post-processing on an initial path by adopting a greedy redundant node pruning strategy to delete unnecessary turning points so as to further shorten the path length. The invention effectively solves the problems of low sampling efficiency, slow convergence and poor path quality of the traditional RRT algorithm in intravascular planning, can quickly generate the safe, smooth and approximately optimal intravascular navigation path, and is suitable for preoperative planning of pulmonary interventional operation.

Inventors

  • LI ZHENGQUAN
  • WANG YUE
  • WU YANJUN
  • Wu Sijiong
  • LIU YINGHUA
  • ZHOU YANPING

Assignees

  • 江南大学
  • 无锡三捷医疗科技有限公司

Dates

Publication Date
20260505
Application Date
20260119

Claims (10)

  1. 1. A pulmonary vessel targeting robot path planning method for improving RRT algorithm, comprising the steps of: Step 1, loading an STL model file of a pulmonary blood vessel, carrying out space initialization, acquiring a space boundary of a model, and defining a starting point and an end point of a path; step 2, generating candidate sampling points by adopting a multi-strategy fusion sampling method; Step 3, performing in-vivo collision detection based on the ray intersection counting parity principle on the candidate sampling points generated in the step 2; step 4, node expansion and path optimization are carried out on the frames based on the RRT algorithm for sampling points passing through collision detection; And 5, carrying out post-processing on the path obtained in the step 4 by adopting a redundant node removal strategy, and deleting unnecessary nodes to optimize the path.
  2. 2. The method according to claim 1, wherein the step1 comprises: Reading all vertex coordinate sets of STL model ; Calculating a space starting point and a space length, width and height according to the vertex coordinates: Wherein, the Is a space starting point; is the length, width and height of the space.
  3. 3. The method according to claim 1, wherein the multi-strategy fusion sampling in the step 2 is an adaptive fusion of a global sampling strategy, a conical region sampling strategy and a circular sampling strategy, and the sampling method is as follows: According to preset weight coefficient 、 、 Wherein With probability at each sampling Selecting to execute a global sampling strategy to probability Selecting to execute a pyramid region sampling strategy to probability Selecting to execute a circular sampling strategy; the global sampling strategy is that uniformly and randomly sampling each coordinate axis in the space boundary defined by axisStart and axisLWH to generate sampling points ; The cone area sampling strategy is that the latest node of the current random tree is used Pointing to the target point The direction vector d of (a) is taken as a central axis to construct a conical sampling area, and an adaptive radius factor is adopted Dynamically adjusting a sampling range, wherein Randomly generating sampling points in the conical sampling area; the circular sampling strategy is that the starting point of the current optimal path is used And endpoint Midpoint of the connection line Is the center of sphere Is the sampling radius, wherein For the current optimal path length to be the most optimal, Random disturbance factor in interval 0.8, 1.2, and randomly generating sampling point in spherical area.
  4. 4. A method according to claim 3, wherein the weight coefficients 、 、 And respectively correspond to 0.3, 0.4 and 0.3.
  5. 5. The method according to claim 1, wherein the in vivo collision detection in step 3 includes constructing a ray for the point to be detected P and employing a ray-triangle intersection algorithm, and determining that the point P is located inside the model if the number of intersections of the ray with the STL model surface is an odd number.
  6. 6. The method of claim 5, wherein the step 3 further comprises segment-model collision detection, wherein the internal detection is performed by uniformly sampling multiple points on a segment connecting two points, and determining segment safety if all points are located inside the model.
  7. 7. The method according to claim 1, wherein the step 4 comprises: S4.1, searching distance sampling points in the random tree T Nearest node ; S4.2 from To the direction of Direction expansion step size Generating a new node ; S4.3 at the beginning Is of the center and the radius Searching a set of neighbor nodes within a neighborhood of (1) ; S4.4 from Selecting a node minimizing the path cumulative cost as Is the optimal parent node of (a) Wherein the accumulated cost is the cost from the root node to the node plus the node to the node Is a distance of (2); S4.5 pair The nodes in (a) perform reconnection optimization if via The path cost for reaching a certain neighbor node is smaller, and the parent node of the neighbor node is updated as 。
  8. 8. The method of claim 1, wherein the redundant node removal policy in step 5 is a greedy pruning policy, specifically comprising: Given an initial sequence of waypoints Wherein As a starting point, the position of the object is, Is the end point; From the starting point Initially, sequentially attempting nodes that are not immediately adjacent to a subsequent node Performing direct connection; From the slave Initially, it is checked whether it can be associated with a subsequent node in the sequence To achieve collision-free direct connection, wherein > Current index +1; If it is, delete And (3) with All intermediate nodes in between, and will As a new current node; repeating the checking and deleting processes until the current node is the end point And obtaining an optimized path.
  9. 9. An electronic device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, wherein the processor implements the pulmonary vessel targeting robot path planning method of improving RRT-algorithm of any one of claims 1 to 8 when the program is executed by the processor.
  10. 10. A computer readable storage medium having stored thereon a computer program, wherein the program when executed by a processor implements a pulmonary vessel targeting robot path planning method of improving RRT-algorithm according to any of claims 1 to 8.

Description

Lung vessel targeting robot path planning method for improving RRT algorithm Technical Field The invention belongs to the technical field of robot path planning, and particularly relates to a pulmonary vessel targeting robot path planning method for improving an RRT algorithm. Background Intravascular site-directed targeting is an important tool in modern medicine for treating vascular diseases such as heart, brain, lung and the like, in particular pulmonary diseases such as pulmonary thrombosis. In such procedures, a physician needs to navigate a drug or catheter or other instrument to a focal site via a vascular path. Accurate path planning is performed before surgery, and is important for improving the success rate of surgery, reducing the surgery time and reducing the surgery cost and risk. The rapid random tree algorithm (RRT) is a commonly used path planning algorithm, and is widely used in the robot field with its probabilistic completeness and asymptotic optimality. However, conventional RRT algorithms face a number of challenges when applied to intravascular path planning: 1. The sampling efficiency is low, the traditional RRT samples randomly and uniformly in a wide free space, and the blood vessel cavity channel only occupies a small part of the whole space, so that a large number of sampling points can fall in an invalid area, and the waste of calculation resources is serious. 2. The convergence speed is low, because the sampling is blind, the algorithm needs a large number of iterations to find a feasible path, and a longer time is needed to find the optimal path, so that the clinical real-time requirement is difficult to meet. 3. Lacking specific adaptation to anatomy, traditional collision detection methods have difficulty accurately handling complex, unstructured biomedical anatomies like STL models, and easily planning "through-the-wall" invalid paths. 4. The path quality is unstable, namely in a complex and narrow vascular network, an algorithm is easy to be trapped into local optimization, a far-winding or uneven path is generated, and the actual requirement of clinical operation is not met. While the conventional RRT algorithm guarantees progressive optimality by reselecting the parent node and reconnecting two mechanisms, the tree structure part needs to be frequently reconfigured, so that the calculation cost is increased, and the local optimum is very easy to fall into. Thus, there is a great need in the art for a new method that enables efficient and accurate path planning within a three-dimensional pulmonary vascular model. Disclosure of Invention [ Problem ] The invention aims to overcome the defects that the prior RRT algorithm has blind sampling and low efficiency, and the RRT algorithm has slow convergence speed, high calculation cost and easy sinking into local optimum caused by global random sampling when pursuing the gradual optimum when carrying out path planning in a pulmonary vascular cavity, thereby rapidly and stably generating a high-quality path which is strictly positioned in the vascular cavity and has approximate optimum length. [ Technical solution ] In order to solve the technical problems, the invention provides a path planning method of a pulmonary vascular targeting robot for improving an RRT algorithm, which is characterized by combining a strategy of fusing a plurality of sampling methods with accurate in-vivo collision detection, and specifically comprises the following steps: Step 1, loading an STL model file of a pulmonary blood vessel, carrying out space initialization, acquiring a space boundary of a model, and defining a starting point and an end point of a path; step 2, generating candidate sampling points by adopting a multi-strategy fusion sampling method; Step 3, performing in-vivo collision detection based on the ray intersection counting parity principle on the candidate sampling points generated in the step 2; step 4, node expansion and path optimization are carried out on the frames based on the RRT algorithm for sampling points passing through collision detection; And 5, carrying out post-processing on the path obtained in the step 4 by adopting a redundant node removal strategy, and deleting unnecessary nodes to optimize the path. Optionally, the step 1 includes: Reading all vertex coordinate sets of STL model ; Calculating a space starting point and a space length, width and height according to the vertex coordinates: Wherein, the Is a space starting point; is the length, width and height of the space. Optionally, the multi-strategy fusion sampling in the step 2 is an adaptive fusion of a global sampling strategy, a conical region sampling strategy and a circular sampling strategy, and the sampling method is as follows: According to preset weight coefficient 、、WhereinWith probability at each samplingSelecting to execute a global sampling strategy to probabilitySelecting to execute a pyramid region sampling strategy to probabilitySelecting to