Autonomous vehicle relative atlas incorporating hypergraph data structure

Patent metadata

Field	Value
Publication number	US-11526538-B2
Application number	US-202217674510-A
Country	US
Kind code	B2
Filing date	Feb 17, 2022
Priority date	Mar 29, 2018
Publication date	Dec 13, 2022
Grant date	Dec 13, 2022

Abstract

A relative atlas graph maintains mapping data used by an autonomous vehicle. The relative atlas graph may be generated for a geographical area based on observations collected from the geographical area, and may include element nodes corresponding to elements detected from the observations along with edges that connect pairs of element nodes and define relative poses between the elements for connected pairs of element nodes, as well as relations that connect multiple element nodes to define logical relationships therebetween.

First claim

What is claimed is:

1. A method comprising:
determining a vehicle pose for an autonomous vehicle within a geographical area using at least one sensor;
accessing a relative atlas graph to identify a tile node in the geographical area, wherein the tile node corresponds to a tile representing a region of the geographical area;
accessing the relative atlas graph to identify a plurality of element nodes, each element node representing an element in the geographical area;
accessing the relative atlas graph to identify a plurality of edges, each identified edge connecting the tile node to an element node from the plurality of element nodes and defining a relative pose between the region of the geographical area represented by the tile and the element for the connected element node; and
laying out the plurality of elements within a digital map using the determined relative poses such that the autonomous vehicle is operated autonomously in the geographical area using the digital map.

2. The method of claim 1 , wherein the tile node is a first tile node, the tile is a first tile and the region is a first region, the method further comprising:
accessing the relative atlas graph to identify a second tile node in the geographical area, the second tile node corresponding to a second tile representing a second region of the geographical area; and
accessing the relative atlas graph to identify a tile-to-tile edge connecting the first tile node to the second tile node and defining a relative pose between the first and second regions.

3. The method of claim 2 , wherein laying out the plurality of elements within the digital map using the determined relative poses includes laying out a first element among the plurality of elements at a first position in the digital map using a relative pose defined between the first region and the first element in a first edge among the plurality of edges that connects the first tile node to a first element node for the first element.

4. The method of claim 3 , wherein laying out the plurality of elements within the digital map using the determined relative poses further includes laying out a second element among the plurality of elements at a second position in the digital map using a relative pose defined between the first region and the second element in a second edge among the plurality of edges that connects the first tile node to a second element node for the second element.

5. The method of claim 3 , wherein laying out the plurality of elements within the digital map using the determined relative poses further includes laying out a second element among the plurality of elements at a second position in the digital map using a relative pose defined between the first element and the second element in a second edge among the plurality of edges that connects a first element node for the first element to a second element node for the second element.

6. The method of claim 1 , wherein determining the vehicle pose includes determining the vehicle pose within a frame of reference of the tile, wherein the tile node includes geometry data defining a surface model for at least a portion of the region of the geographical area represented by the tile, and wherein determining the vehicle pose includes:
assembling received sensor data into a point cloud;
aligning the point cloud with the surface model; and
determining the vehicle pose based on the alignment of the point cloud with the surface model.

7. The method of claim 1 , further comprising determining an active tile node for the autonomous vehicle, including:
determining a location of the autonomous vehicle based upon a satellite navigation sensor; and
selecting the tile node from among a plurality of tile nodes as the active tile node using the determined location.

8. The method of claim 1 , wherein the plurality of element nodes are stored in a node table of a relational database and the plurality of edges are stored in an edge table of the relational database.

9. The method of claim 1 , wherein each of the plurality of element nodes includes an identifier field including an identifier for the element thereof, a type field specifying a type that characterizes the respective element node, and a payload field including element-specific data, and wherein each of the plurality of edges includes first and second identifier fields including identifiers for the elements for the pair of element nodes connected thereby, a type field specifying a type that characterizes the respective edge, and a payload field including edge-specific data.

10. An autonomous vehicle, comprising:
a memory storing a relative atlas graph; and
an autonomous vehicle control system coupled to the memory and configured to generate a digital map by:
determining a vehicle pose for the autonomous vehicle within a geographical area using at least one sensor;
accessing the relative atlas graph to identify a tile node in the geographical area, wherein the tile node corresponds to a tile representing a region of the geographical area;
accessing the relative atlas graph to identify a plurality of element nodes, each element node representing an element in the geographical area;
accessing the relative atlas graph to identify a plurality of edges, each identified edge connecting the tile node to an element node from the plurality of element nodes and defining a relative pose between the region of the geographical area represented by the tile and the element for the connected element node; and
laying out the plurality of elements within the digital map using the determined relative poses such that the autonomous vehicle control system operates the autonomous vehicle autonomously in the geographical area using the digital map.

11. A method comprising:
receiving a plurality of observations for a geographical area; and
using one or more processors coupled to a memory, generating and storing in the memory, based on the plurality of observations for the geographical area, a relative atlas graph representing mapping data for the geographical area and usable by an autonomous vehicle control system of an autonomous vehicle to operate the autonomous vehicle autonomously in the geographical area, wherein generating and storing the relative atlas graph includes:
generating a tile node corresponding to a tile that represents a region of the geographical area;
generating a plurality of element nodes for a plurality of elements detected from the plurality of observations, each element node having an element from the plurality of elements;
generating a plurality of edges, each edge connecting the tile node to an element node from the plurality of element nodes and defining a relative pose between the region of the geographical area represented by the tile and the element for the connected element node; and
storing the tile node, the plurality of element nodes and the plurality of edges in the relative atlas graph stored in the memory to logically organize the mapping data represented by the relative atlas graph in the memory.

12. The method of claim 11 , wherein the tile node is a first tile node, the tile is a first tile and the region is a first region, the method further comprising:
generating a second tile node corresponding to a second tile representing a second region of the geographical area;
generating a tile-to-tile edge connecting the first tile node to the second tile node and defining a relative pose between the first and second regions; and
storing the second tile node and the tile-to-tile edge in the relative atlas graph.

13. The method of claim 11 , wherein storing the tile node, the plurality of element nod

Assignees

• Aurora Operations Inc

Inventors

• Eade Ethan
• Bode Michael
• Bagnell James Andrew

Classifications

• G01C21/26

  specially adapted for navigation in a road network · CPC title

• G06F16/284

  Relational databases · CPC title

• G06T7/73

  using feature-based methods · CPC title

• G06T2207/30244

  Camera pose · CPC title

• G01C21/30

  Map- or contour-matching · CPC title