Navigation method, device, and system

Patent metadata

Field	Value
Publication number	US-12516942-B2
Application number	US-202318180164-A
Country	US
Kind code	B2
Filing date	Mar 8, 2023
Priority date	Sep 9, 2020
Publication date	Jan 6, 2026
Grant date	Jan 6, 2026

Abstract

A navigation method, device, and system are provided in this application. The method includes: obtaining a first target location and a second target location ( 101 ), where the first target location is a location closest to a start location on K road segments, the second target location is a location closest to an end location on the K road segments, and K is a positive integer; obtaining a first path from the first target location to the second target location based on a vector pathfinding algorithm and the K road segments ( 102 ); obtaining a second path from the start location to the first target location and a third path from the second target location to the end location ( 103 ); and determining a fourth path from the start location to the end location ( 104 ).

First claim

What is claimed is:

1 . A navigation method, comprising:
obtaining a first target location and a second target location, wherein the first target location is a location closest to a start location on K road segments, the second target location is a location closest to an end location on the K road segments, and K is a positive integer; obtaining a first path from the first target location to the second target location based on a vector pathfinding algorithm and the K road segments; obtaining a second path from the start location to the first target location and a third path from the second target location to the end location based on a raster pathfinding algorithm; and generating a fourth path from the start location to the end location based on the first path, the second path, and the third path, wherein the fourth path is for navigating to the end location, and displaying the fourth path for guiding a user to move along the fourth path toward the end location, wherein the obtaining the first target location comprises: determining, based on three-dimensional data of the start location and three-dimensional data of the K road segments, a road segment closest to the start location on the K road segments, and determining the first target location from the road segment closest to the start location.

2 . The method according to claim 1 , wherein the determining, based on three-dimensional data of the start location and three-dimensional data of the K road segments, the road segment closest to the start location on the K road segments comprises:
determining, from a plurality of layers of regions comprised in a walkable region and based on height data of the start location and height data of the walkable region, a target layer region in which the start location is located, wherein the target layer region is one of the plurality of layers of regions; determining, based on height data of the K road segments, V road segments comprised in the target layer region in which the start location is located, wherein V is a positive integer less than or equal to K; and determining, from the V road segments and based on data of a horizontal direction of the start location and data of a horizontal direction of the V road segments, a road segment closest to the start location.

3 . The method according to claim 2 , wherein the determining, based on three-dimensional data of the start location and three-dimensional data of the K road segments, the road segment closest to the start location on the K road segments comprises:
determining, from the K road segments and based on the data of the horizontal direction of the start location and the data of the horizontal direction of the K road segments, M road segments of which distances from the start location in a horizontal direction are less than a first threshold, wherein M is a positive integer less than or equal to K; determining, from the M road segments and based on the height data of the start location and height data of the M road segments, N road segments that meet a target condition, wherein N is a positive integer less than or equal to M; and determining, from the N road segments and based on the three-dimensional data of the start location and the three-dimensional data of the K road segments, the road segment closest to the start location.

4 . The method according to claim 3 , wherein the target condition comprises: a value of height data of a road segment is greater than a difference between a value of the height data of the start location and a third threshold, and is less than a sum of the value of the height data of the start location and a second threshold.

5 . The method according to claim 4 , wherein the second threshold is less than the third threshold.

6 . The method according to claim 1 , wherein the obtaining the second path from the start location to the first target location based on a raster pathfinding algorithm comprises repeatedly performing raster pathfinding operations until a raster corresponding to the first target location is connected, to obtain the second path from the start location to the first target location, and the raster pathfinding operations include:
obtaining P rasters constituting a walkable region, wherein the P rasters comprise a raster corresponding to the start location and a raster corresponding to the end location, and P is a positive integer greater than 2; selecting one candidate raster from Q candidate rasters as a raster corresponding to a third target location, wherein the Q candidate rasters belong to the P rasters, and Q is a positive integer less than P; connecting the raster corresponding to the start location and the raster corresponding to the third target location; selecting one candidate raster from L candidate rasters as a raster corresponding to a fourth target location, wherein the L candidate rasters belong to the P rasters, and L is a positive integer less than P; and connecting the raster corresponding to the third target location and the raster corresponding to the fourth target location.

7 . The method according to claim 6 , wherein the L candidate rasters do not comprise the Q candidate rasters, or at least one raster that meets a target location relationship with the Q candidate rasters.

8 . A navigation method, comprising:
obtaining a fourth path from a start location to an end location for navigating a user to the end location; displaying the fourth path for guiding the user to move along the fourth path toward the end location; and displaying a guiding line based on a location of the user and a location of the fourth path, wherein the guiding line indicates the user to move along the fourth path toward the end location, wherein the fourth path is formed by sequentially connecting a plurality of reference locations, a height of the guiding line at a fourth reference location is equal to a sum of a height of the fourth reference location and a specific height, and the fourth reference location is any one of the plurality of reference locations.

9 . The method according to claim 8 , wherein two adjacent reference locations are connected to form a subpath; and
the plurality of reference locations comprise a first reference location, a second reference location, and a third reference location that are sequentially connected, the first reference location is connected to the second reference location to form a first subpath, the second reference location is connected to the third reference location to form a second subpath, the first subpath and the second subpath form a target angle, the second reference location is a reference location closest to the location of the user in the plurality of reference locations, and the third reference location is located between the second reference location and the end location or is the end location; and the displaying the guiding line based on a location of the user and a location of the fourth path comprises: displaying the guiding line from the location of the user to the second reference location based on determination that the location of the user and the third reference location are on a same side of the first subpath and the location of the user is between an angle bisector of the target angle and the first subpath.

10 . The method according to claim 8 , wherein two adjacent reference locations are connected to form the subpath; and
the plurality of reference locations comprise a first reference location, a second reference location, and a third reference location that are sequentially connected, the first reference location is connected to the second reference location to form a first subpath, the second reference location is connecte

Assignees

• Huawei Tech Co Ltd

Inventors

• Kang Zehui
• Yang Hao
• Li Weiyang

Classifications

• G01C21/3632

  Guidance using simplified or iconic instructions, e.g. using arrows (G01C21/365 takes precedence) · CPC title

• G01C21/30

  Map- or contour-matching · CPC title

• G01C21/3492

  employing speed data or traffic data, e.g. real-time or historical (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968) · CPC title

• G01C21/3415

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title

• G01C21/3446 Primary

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title