# US 2025/0155895 A1 · Path planning method and apparatus and readable storage medium

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0155895 A1
- Document ID: US20250155895A1
- Status: Published application
- Kind: A1
- Application number: 18/839,883
- Filed: 2023-02-21
- Published: 2025-05-15
- Earliest claimed: 2022-02-21
- Assignees: Zte Corporation
- Applicants: Zte Corporation
- Inventors: Dan WU; Ruishan XIN
- Web page: https://patentgrep.com/patent/US20250155895A1

## CPC

- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- G05D 1/622: Obstacle avoidance (predicting or avoiding probable or impending collision of road vehicles B60W30/08)
- B25J 9/1666: {Avoiding collision or forbidden zones}
- G01C 21/3407: {specially adapted for specific applications}
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G05B 2219/40476: Collision, planning for collision free path
- G05B 2219/40519: Motion, trajectory planning
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50})
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)

## Abstract

Disclosed are a path planning method and apparatus, and a computer-readable storage medium. The path planning method may include: acquiring a motion space, a starting position, and an end position of a moving object, and information of an obstacle; constructing a first exploration tree starting from the starting position and constructing a second exploration tree starting from the end position in the motion space, the first exploration tree and the second exploration tree grow toward each other according to the information of the obstacle; and in response to a distance between a first tree node grown on the first exploration tree and a second tree node grown on the second exploration tree being not greater than a preset step length, connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object.

## Claims

### Claim 1

A path planning method, comprising:
acquiring a motion space, a starting position, and an end position of a moving object, and information of an obstacle;
constructing a first exploration tree starting from the starting position and constructing a second exploration tree starting from the end position in the motion space, wherein the first exploration tree and the second exploration tree grow toward each other according to the information of the obstacle; and
in response to a distance between a first tree node grown on the first exploration tree and a second tree node grown on the second exploration tree being not greater than a preset step length, connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object, wherein the second tree node is grown in the following manner:
selecting a tree node nearest to a target sampling point as a third tree node from a node set of the second exploration tree, and selecting a tree node on the first exploration tree nearest to the second exploration tree as a target tree node, wherein the target sampling point is obtained by extending sampling along the second tree node previously grown; and
in response to a minimum distance between the third tree node and the obstacle being not less than a preset distance threshold, growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node.

### Claim 2 (depends on 1)

The path planning method of claim 1, wherein growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node comprises:
growing a random learning vector along the direction from the third tree node to the target sampling point;
growing a targeted learning vector along the direction from the third tree node to the target tree node;
adding the random learning vector and the targeted learning vector to obtain a comprehensive learning vector; and
growing a tree node as the second tree node according to a preset step length along a direction of the comprehensive learning vector.

### Claim 3 (depends on 1)

The path planning method of claim 1, wherein the second tree node is further grown in the following manner:
in response to the minimum distance between the third tree node and the obstacle being less than the preset distance threshold, growing a tree node as the second tree node according to the preset step length along the direction from the third tree node to the target sampling point.

### Claim 4 (depends on 1)

The path planning method of claim 1, wherein constructing a second exploration tree starting from the end position comprises:
in response to determining that the second tree node collides with the obstacle, discarding the second tree node and growing the first tree node of the first exploration tree.

### Claim 5 (depends on 4)

The path planning method of claim 4, wherein constructing a second exploration tree starting from the end position further comprises:
in response to determining that the second tree node does not collide with the obstacle, adding the second tree node to the node set of the second exploration tree.

### Claim 6 (depends on 1)

The path planning method of claim 1, further comprising generating the target sampling point in an obstacle-free region; and generating the target sampling point in an obstacle-free region comprises:
generating a target sampling probability according to a uniform probability distribution;
in response to the target sampling probability being less than a first preset probability threshold, selecting the target tree node as the target sampling point; and
in response to the target sampling probability being greater than or equal to the first preset probability threshold, randomly selecting the target sampling point along the second tree node previously grown.

### Claim 7 (depends on 1)

The path planning method of claim 1, wherein the first tree node is grown in the following manner:
determining a tree node nearest to a starting sampling point as a fourth tree node from a node set of the first exploration tree, wherein the starting sampling point is obtained by extending sampling along the first tree node previously grown; and
growing a tree node as the first tree node according to the preset step length along a direction from the fourth tree node to the starting sampling point.

### Claim 8 (depends on 7)

The path planning method of claim 7, further comprising generating the starting sampling point in an obstacle-free region; and generating the starting sampling point in an obstacle-free region comprises:
generating a starting sampling probability according to a uniform probability distribution;
in response to the starting sampling probability being less than a second preset probability threshold, selecting a starting tree node as the starting sampling point from the node set of the second exploration tree, wherein the starting tree node is a tree node on the second exploration tree nearest to the first exploration tree; and
in response to the starting sampling probability being greater than or equal to the second preset probability threshold, randomly selecting the starting sampling point along the first tree node previously grown.

### Claim 9 (depends on 1)

The path planning method of claim 1, wherein constructing a first exploration tree starting from the starting position comprises:
in response to determining that the first tree node collides with the obstacle, discarding the first tree node and growing the second tree node of the second exploration tree.

### Claim 10 (depends on 9)

The path planning method of claim 9, wherein constructing a first exploration tree starting from the starting position further comprises:
in response to determining that the first tree node does not collide with the obstacle, adding the first tree node to a node set of the first exploration tree.

### Claim 11 (depends on 1)

The path planning method of claim 1, wherein connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object comprises:
respectively connecting the first exploration tree and the second exploration tree according to a growth sequence of tree nodes, and connecting the first tree node and the second tree node to obtain the planned path of the moving object.

### Claim 12

A path planning apparatus, comprising:
a memory, a processor, and a computer program stored in the memory and executable by the processor, wherein the computer program, when executed by the processor, causes the processor to carry out a path planning method, the path planning method comprising:
acquiring a motion space, a starting position, and an end position of a moving object, and information of an obstacle;
constructing a first exploration tree starting from the starting position and constructing a second exploration tree starting from the end position in the motion space, wherein the first exploration tree and the second exploration tree grow toward each other according to the information of the obstacle; and
in response to a distance between a first tree node grown on the first exploration tree and a second tree node grown on the second exploration tree being not greater than a preset step length, connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object, wherein the second tree node is grown in the following manner:
selecting a tree node nearest to a target sampling point as a third tree node from a node set of the second exploration tree, and selecting a tree node on the first exploration tree nearest to the second exploration tree as a target tree node, wherein the target sampling point is obtained by extending sampling along the second tree node previously grown; and
in response to a minimum distance between the third tree node and the obstacle being not less than a preset distance threshold, growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node.

### Claim 13

A non-transitory computer-readable storage medium, storing computer-executable instructions which, when executed by a processor, cause the processor to carry out a path planning method, the path planning method comprising:
acquiring a motion space, a starting position, and an end position of a moving object, and information of an obstacle;
constructing a first exploration tree starting from the starting position and constructing a second exploration tree starting from the end position in the motion space, wherein the first exploration tree and the second exploration tree grow toward each other according to the information of the obstacle; and
in response to a distance between a first tree node grown on the first exploration tree and a second tree node grown on the second exploration tree being not greater than a preset step length, connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object, wherein the second tree node is grown in the following manner:
selecting a tree node nearest to a target sampling point as a third tree node from a node set of the second exploration tree, and selecting a tree node on the first exploration tree nearest to the second exploration tree as a target tree node, wherein the target sampling point is obtained by extending sampling along the second tree node previously grown; and
in response to a minimum distance between the third tree node and the obstacle being not less than a preset distance threshold, growing a tree node as the second tree node according to a direction from the third tree node to the target sampling point and a direction from the third tree node to the target tree node.

### Claim 14 (depends on 2)

The path planning method of claim 2, wherein connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object comprises:
respectively connecting the first exploration tree and the second exploration tree according to a growth sequence of tree nodes, and connecting the first tree node and the second tree node to obtain the planned path of the moving object.

### Claim 15 (depends on 3)

The path planning method of claim 3, wherein connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object comprises:
respectively connecting the first exploration tree and the second exploration tree according to a growth sequence of tree nodes, and connecting the first tree node and the second tree node to obtain the planned path of the moving object.

### Claim 16 (depends on 4)

The path planning method of claim 4, wherein connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object comprises:
respectively connecting the first exploration tree and the second exploration tree according to a growth sequence of tree nodes, and connecting the first tree node and the second tree node to obtain the planned path of the moving object.

### Claim 17 (depends on 5)

The path planning method of claim 5, wherein connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object comprises:
respectively connecting the first exploration tree and the second exploration tree according to a growth sequence of tree nodes, and connecting the first tree node and the second tree node to obtain the planned path of the moving object.

### Claim 18 (depends on 6)

The path planning method of claim 6, wherein connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object comprises:
respectively connecting the first exploration tree and the second exploration tree according to a growth sequence of tree nodes, and connecting the first tree node and the second tree node to obtain the planned path of the moving object.

### Claim 19 (depends on 7)

The path planning method of claim 7, wherein connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object comprises:
respectively connecting the first exploration tree and the second exploration tree according to a growth sequence of tree nodes, and connecting the first tree node and the second tree node to obtain the planned path of the moving object.

### Claim 20 (depends on 8)

The path planning method of claim 8, wherein connecting the first exploration tree and the second exploration tree to obtain a planned path of the moving object comprises:
respectively connecting the first exploration tree and the second exploration tree according to a growth sequence of tree nodes, and connecting the first tree node and the second tree node to obtain the planned path of the moving object.
