# US 2021/0333108 A1 · Path Planning Method And Device And Mobile Device

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

- Number: US 2021/0333108 A1
- Document ID: US20210333108A1
- Status: Published application
- Kind: A1
- Application number: 16/625,193
- Filed: 2019-01-08
- Published: 2021-10-28
- Earliest claimed: 2018-12-28
- Assignees: Goertek Inc.
- Applicants: Goertek Inc.
- Inventors: Baoming Li; Libing Zou; Tianrong Dai
- Web page: https://patentgrep.com/patent/US20210333108A1

## CPC

- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- G01C 21/206: {specially adapted for indoor navigation}
- G01C 21/005: {with correlation of navigation data from several sources, e.g. map or contour matching (G01C21/30 takes precedence)}
- G01C 21/3807: {characterised by the type of data}
- G01S 7/4808: {Evaluating distance, position or velocity data}
- G01S 17/42: Simultaneous measurement of distance and other co-ordinates (indirect measurement G01S17/46)
- G01S 17/89: for mapping or imaging
- G01S 17/93: for anti-collision purposes
- G01S 17/931: of land vehicles
- G06T 7/11: Region-based segmentation
- G06T 7/13: Edge detection
- G06T 7/579: from motion
- G06T 2207/20164: Salient point detection; Corner detection
- 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)
- G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

The present disclosure discloses a path planning method and device and a mobile device. The method comprises: collecting environmental information in a viewing angle by a sensor of a mobile device, processing the environmental information by using an SLAM algorithm, and constructing a grid map; dividing the grid map to obtain a plurality of pixel blocks, using an area constituted of pixel blocks not occupied by obstacles as a search area for path planning, and obtaining a processed grid map; determining reference points by using pixel points in the search area, and deploying topological points on the processed grid map according to the reference point determined and constructing a topological map; and calculating an optimal path from a starting point to a preset target point by using a predetermined algorithm according to the topological map constructed. The present disclosure improves path planning efficiency and saves storage resources.

## Claims

### Claim 1

A path planning method based on simultaneous localization and mapping, comprising:
collecting environmental information within a viewing angle by a sensor of a mobile device, processing the environmental information by using an simultaneous localization and mapping (SLAM) algorithm, and constructing a grid map;
dividing the grid map to obtain a plurality of pixel blocks, using an area constituted of pixel blocks not occupied by obstacles as a search area for path planning, and obtaining a processed grid map;
determining reference points by using pixel points in the search area, deploying topological points on the processed grid map according to the reference points determined, and constructing a topological map; and
calculating an optimal path from a starting point to a preset target point by using a predetermined algorithm according to the topological map constructed.

### Claim 2 (depends on 1)

The method according to claim 1, wherein calculating an optimal path from a starting point to a preset target point by using a predetermined algorithm according to the topological map constructed comprises:
calculating a shortest distance between any two topological points by using a predetermined algorithm, determining adjacency information of any two topological points, and storing the shortest distance information between any two topological points in a linked list;
calculating a shortest distance between the starting point and a topological point nearest to the starting point as a first distance;
calculating a shortest distance between the target point and a topological point nearest to the target point as a second distance;
looking up the linked list to obtain a shortest distance between the topological point nearest to the starting point and the topological point nearest to the target point as a third distance, and
obtaining an optimal path from the starting point to the target point by summing the first distance, the second distance, and the third distance.

### Claim 3 (depends on 1)

The method according to claim 1, wherein dividing the grid map to obtain a plurality of pixel blocks and using an area constituted of pixel blocks not occupied by obstacles as a search area for path planning comprises:
dividing the grid map to obtain a plurality of pixel blocks by using multiple block areas equal in area;
judging whether a pixel block is occupied by an obstacle, if yes, setting a gray value of pixel points in the pixel block to a first value, and if not, setting a gray value of pixel points in the pixel block to a second value.

### Claim 4 (depends on 3)

The method according to claim 3, wherein judging whether a pixel block is occupied by an obstacle comprises:
judging, for each pixel block, whether a central pixel point of the pixel block is occupied by an obstacle;
if the central pixel point is occupied, determining that the pixel block is occupied by an obstacle, and judging next pixel block until all the pixel blocks are traversed; and
if the central pixel point is not occupied by an obstacle, sequentially traversing other pixel points in the pixel block, and if none of other pixel point is occupied by an obstacle, determining that the pixel block is not occupied by an obstacle.

### Claim 5 (depends on 1)

The method according to claim 1, wherein determining reference points by using pixel points in the search area, and deploying topological points on the processed grid map according to the reference points determined comprises:
sorting pixel points, edge points or corner points in the search area, and determining points of a same sort as reference points;
calculating a centroid of an area constituted of the reference points, and deploying topological points at positions of centroids on the processed grid map.

### Claim 6 (depends on 5)

The method according to claim 5, wherein sorting pixel points specifically comprises:
sorting pixel points according to a distance and visible information between any two pixel points, if the visible information between the two pixel points indicates that there is no obstacle between the two pixel points and the distance between the two pixel points is less than or equal to a distance threshold, sorting the two pixel points as a same sort and obtaining points of a same sort.

### Claim 7 (depends on 5)

The method according to claim 5, wherein sorting edge points specifically comprises:
sorting edge points according to a distance and visible information between any two edge points, if the visible information between the two edge points indicates that there is no obstacle between the two edge points and the distance between the two edge points is less than or equal to a distance threshold, sorting the two edge points as a same sort and obtaining points of a same sort, wherein the edge points refer to pixel points of the search area whose positions are adjacent to pixel points of a non-search area on the grid map.

### Claim 8 (depends on 5)

The method according to claim 5, wherein sorting corner points specifically comprises:
sorting corner points according to a distance and visible information between any two corner points, if the visible information between the two corner points indicates that there is no obstacle between the two corner points and the distance between the two corner points is less than or equal to a distance threshold, sorting the two corner points as a same sort and obtaining points of a same sort.

### Claim 9 (depends on 3)

The method according to claim 3, wherein dividing the grid map to obtain a plurality of pixel blocks by using multiple block areas equal in area comprises:
dividing the grid map by using the block area according to a dividing sequence, and when an area to be divided on the grid map has an area less than the area of the block area, obtaining a divided block area after filling an insufficient portion with a first value.

### Claim 10

A path planning device based on simultaneous localization and mapping, comprising:
a grid map construction unit, for collecting environmental information within a viewing angle by a sensor of a mobile device, processing the environmental information by using an simultaneous localization and mapping (SLAM) algorithm, and constructing a grid map;
a grid map processing unit, for dividing the grid map to obtain a plurality of pixel blocks, using an area constituted of pixel blocks not occupied by obstacles as a search area for path planning, and obtaining a processed grid map;
a topographic map construction unit, for determining reference points by using pixel points in the search area, deploying topological points on the processed grid map according to the reference points determined, and constructing a topological map; and
a path planning unit, for calculating an optimal path from a starting point to a preset target point by using a predetermined algorithm according to the topological map constructed.

### Claim 11 (depends on 10)

The device according to claim 10, wherein the path planning unit is specifically for
calculating a shortest distance between any two topological points by using a predetermined algorithm, determining adjacency information of any two topological points, storing the shortest distance information between any two topological points in a linked list;
calculating a shortest distance between the starting point and a topological point nearest to the starting point as a first distance;
calculating a shortest distance between the target point and a topological point nearest to the target point as a second distance;
looking up the linked list to obtain a shortest distance between the topological point nearest to the starting point and the topological point nearest to the target point as a third distance, and
obtaining an optimal path from the starting point to the target point by summing the first distance, the second distance, and the third distance.

### Claim 12 (depends on 10)

The device according to claim 10, wherein the grid map processing unit is specifically for
dividing the grid map to obtain a plurality of pixel blocks by using multiple block areas equal in area; and
judging whether a pixel block is occupied by an obstacle, if yes, setting a gray value of pixel points in the pixel block to a first value, and if not, setting a gray value of pixel points in the pixel block to a second value.

### Claim 13 (depends on 12)

The device according to claim 12, wherein the grid map processing unit is specifically for
judging, for each pixel block, whether a central pixel point of the pixel block is occupied by an obstacle;
if the central pixel point is occupied, determining that the pixel block is occupied by an obstacle, and judging next pixel block until all the pixel blocks are traversed; and
if the central pixel point is not occupied by an obstacle, sequentially traversing other pixel points in the pixel block, and if none of other pixel point is occupied by an obstacle, determining that the pixel block is not occupied by an obstacle.

### Claim 14 (depends on 10)

The device according to claim 10, wherein the topographic map construction unit is specifically for
sorting pixel points, edge points or corner points in the search area, and determining points of a same sort as reference points; and
calculating a centroid of an area constituted of the reference points, and deploying topological points at positions of centroids on the processed grid map.

### Claim 15 (depends on 14)

The device according to claim 14, wherein the topographic map construction unit is specifically for sorting pixel points according to a distance and visible information between any two pixel points, if the visible information between the two pixel points indicates that there is no obstacle between the two pixel points and the distance between the two pixel points is less than or equal to a distance threshold, sorting the two pixel points as a same sort and obtaining points of a same sort.

### Claim 16 (depends on 14)

The device according to claim 14, wherein the topographic map construction unit is specifically for sorting edge points according to a distance and visible information between any two edge points, if the visible information between the two edge points indicates that there is no obstacle between the two edge points and the distance between the two edge points is less than or equal to a distance threshold, sorting the two edge points as a same sort and obtaining points of a same sort, wherein the edge points refer to pixel points of the search area whose positions are adjacent to pixel point of a non-search area on the grid map.

### Claim 17 (depends on 14)

The device according to claim 14, wherein the topographic map construction unit is specifically for sorting corner points according to a distance and visible information between any two corner points, if the visible information between the two corner points indicates that there is no obstacle between the two corner points and the distance between the two corner points is less than or equal to a distance threshold, sorting the two corner points as a same sort and obtaining points of a same sort.

### Claim 18 (depends on 10)

The device according to claim 10, wherein the grid map processing unit is specifically for dividing the grid map by using the block area according to a dividing sequence, and when an area to be divided on the grid map has an area less than the area of the block area, obtaining a divided block area after filling an insufficient portion with a first value.

### Claim 19 (depends on 1)

A mobile device, comprising: a memory and a processor, wherein the memory and the processor are communicatively connected by an internal bus, the memory stores program instructions executable by the processor which enable to implement the path planning method based on simultaneous localization and mapping according to claim 1 when executed by the processor.
