Method and system for map construction

Patent metadata

Field	Value
Publication number	US-11170230-B2
Application number	US-201916286287-A
Country	US
Kind code	B2
Filing date	Feb 26, 2019
Priority date	Feb 26, 2019
Publication date	Nov 9, 2021
Grant date	Nov 9, 2021

Abstract

A method of retrieving a map is disclosed. The method includes receiving a grid data of the map comprising lane segments, wherein the grid data includes an array of grids each associated with a list including none or at least one of the lane segments intersecting the respective grid; receiving coordinates of a location; identifying a first grid including the location based on the grid data; identifying a target grid that has an associated list including at least one of the lane segments as first lane segment; and outputting the first lane segment.

First claim

What is claimed is:

1. A method of retrieving a map, the method comprising:
receiving a grid data of the map comprising lane segments, the grid data comprising an array of grids, wherein each grid is associated with a list including none or at least one of the lane segments intersecting the respective grid;
receiving coordinates of a location;
identifying a first grid including the location based on the grid data;
identifying a target grid that has an associated list including at least one of the lane segments as a first lane segment;
determining a search radius, wherein a distance between the first grid and the target grid is less than the search radius; and
outputting the first lane segment.

2. The method according to claim 1 , wherein the distance is measured between respective vertices of the first grid and the target grid.

3. The method according to claim 1 , wherein the lane segments of the map are related to each other through a graph representation, further comprising identifying a second lane segment based on the first lane segment through the graph representation.

4. The method according to claim 3 , wherein the second lane segment is selected from at least one of a forward lane segment, a backward lane segment, a left lane segment and a right lane segment with respect to the first lane segment.

5. The method according to claim 1 , wherein the first lane segment in the target grid is closest to the location compared to other lane segments in the map.

6. The method according to claim 1 , wherein identifying the target grid comprises sorting the array of grids based on distances between each grid and the first grid and identifying the target grid based on an ascending order of the distances.

7. The method according to claim 1 , wherein receiving coordinates of the location comprises receiving a satellite positioning signal and converting the satellite positioning signal into the coordinates.

8. A system of retrieving a map, the system comprising:
a database including a grid data of the map comprising lane segments, the grid data comprising an array of grids each associated with a list including none or at least one of the lane segments intersecting the respective grid;
a positioning circuit configured to receive coordinates of a location;
a control circuit configured to:
identify a first grid including the location based on the grid data; and
identify a target grid that has an associated list including at least one of the lane segments as a first lane segment;
determine a search radius, wherein a distance between the first grid and the target grid is less than the search radius; and

an output circuit configured to output the first lane segment.

9. The method according to claim 8 , wherein the distance is measured between respective vertices of the first grid and the target grid.

10. The system according to claim 8 , wherein the lane segments of the map are related to each other through a graph representation, and the control circuit is further configured to identify a second lane segment based on the first lane segment through the graph representation.

11. The system according to claim 10 , wherein the second lane segment is one of a forward lane segment, a backward lane segment, a left lane segment and a right lane segment with respect to the first lane segment.

12. The system according to claim 8 , wherein the first lane segment in the target grid is closest to the location compared to other lane segments in the map.

13. The system according to claim 8 , wherein the control circuit is further configured to sort the array of grids based on distances between each grid and the first grid and to identify the target grid based on an ascending order of the distances.

14. The system according to claim 8 , wherein the positioning circuit is further configured to receive a satellite positioning signal and to convert the satellite positioning signal into the coordinates.

15. A system of retrieving a map comprising lane segments, the system comprising:
a storage device, arranged to store a programming code; and
a processor, wherein when the programming code is executed by the processor, following steps are performed:
receiving a grid data of the map, the grid data comprising an array of grids, wherein each grid is associated with a list including none or at least one of the lane segments intersecting the respective grid;
receiving coordinates of a location;
identifying a first grid including the location based on the grid data;
identifying a target grid that has an associated list including at least one of the lane segments as a first lane segment;
determining a search radius, wherein a distance between the first grid and the target grid is less than the search radius; and
outputting the first lane segment.

16. The system according to claim 15 , wherein the distance is measured between respective vertices of the first grid and the target grid.

17. The system according to claim 15 , wherein the lane segments of the map are related to each other through a graph representation, further comprising identifying a second lane segment based on the first lane segment through the graph representation.

18. The system according to claim 17 , wherein the second lane segment is selected from at least one of a forward lane segment, a backward lane segment, a left lane segment and a right lane segment with respect to the first lane segment.

19. The system according to claim 15 , wherein the first lane segment in the target grid is closest to the location compared to other lane segments in the map.

20. The system according to claim 15 , wherein identifying the target grid comprises sorting the array of grids based on distances between each grid and the first grid and identifying the target grid based on an ascending order of the distances.

Assignees

• Tusimple Inc

Inventors

• Jiang Minhao
• Lu Hsin
• Shi Genmao
• Liu Ziqi

Classifications

• G01S19/48

  by combining or switching between position solutions derived from the satellite radio beacon positioning system and position solutions derived from a further system · CPC title

• G06V20/588 Primary

  Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road · CPC title

• G08G1/167

  Driving aids for lane monitoring, lane changing, e.g. blind spot detection · CPC title

• G06F16/29 Primary

  Geographical information databases · CPC title

• G01C21/3815

  Road data · CPC title