# US 10,503,760 B2 · Use of relative atlas in an autonomous vehicle

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

- Number: US 10,503,760 B2
- Document ID: US10503760B2
- Status: Granted
- Kind: B2
- Application number: 15/940,525
- Filed: 2018-03-29
- Published: 2019-10-03
- Granted: 2019-12-10
- Earliest claimed: 2018-03-29
- Assignees: Aurora Innovation, Inc.
- Applicants: Aurora Innovation, Inc.
- Inventors: Ethan Eade; Michael Bode; James Andrew Bagnell
- Web page: https://patentgrep.com/patent/US10503760B2

## CPC

- G06F 16/29: Geographical information databases
- B60W 60/001: {Planning or execution of driving tasks}
- G01C 21/26: specially adapted for navigation in a road network
- G01C 21/30: Map- or contour-matching
- G01C 21/3848: {Data obtained from both position sensors and additional sensors}
- G01C 21/3881: {Tile-based structures}
- G05D 1/00: Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots (drive control systems specially adapted for autonomous road vehicles B60W60/00)
- G05D 1/0246: {using a video camera in combination with image processing means}
- G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)}
- G05D 1/0278: {using satellite positioning signals, e.g. GPS}
- G06F 16/284: {Relational databases}
- G06T 7/12: Edge-based segmentation
- G06T 7/168: involving transform domain methods
- G06V 10/426: Graphical representations
- G06V 20/56: exterior to a vehicle by using sensors mounted on the vehicle
- G06V 20/584: {of vehicle lights or traffic lights}
- G06V 20/588: {Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road}
- G08G 1/00: Traffic control systems for road vehicles (arrangement of road signs or traffic signals E01F9/00 {; automatic vehicle control B62D})
- G06T 2207/30252: Vehicle exterior; Vicinity of vehicle
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- B60W: CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT
- 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
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

A relative atlas may be used to lay out elements in a digital map used in the control of an autonomous vehicle. A vehicle pose for the autonomous vehicle within a geographical area may be determined, and the relative atlas may be accessed to identify elements in the geographical area and to determine relative poses between those elements. The elements may then be laid out within the digital map using the determined relative poses, e.g., for use in planning vehicle trajectories, for estimating the states of traffic controls, or for tracking and/or identifying dynamic objects, among other purposes.

## Claims

### Claim 1

A method of generating a digital map for use by an autonomous vehicle, the method comprising:
determining a vehicle pose for the autonomous vehicle within a geographical area;
accessing a relative atlas to identify a plurality of elements in the geographical area, wherein the relative atlas comprises a relative atlas graph, and wherein the relative atlas graph includes a plurality of element nodes for the plurality of elements and a plurality of edges, each of which connecting a pair of element nodes from among the plurality of element nodes and defining a relative pose between the associated elements for the pair of element nodes;
accessing the relative atlas to determine relative poses between the plurality of elements; and
laying out the plurality of elements within the digital map using the determined relative poses, 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 relative map; and
laying out a second element among the plurality of elements at a second position in the relative map, including determining the second position from the first position using a relative pose between the first and second elements and defined in a first edge among the plurality of edges that connects a first element node for the first element with a second element node for the second element.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

The method of claim 2, wherein the database comprises a relational database.

### Claim 4 (depends on 1)

The method of claim 1, wherein each of the plurality of element nodes includes an identifier field including an identifier for the associated element thereof, and wherein each of the plurality of edges includes first and second identifier fields including identifiers for the associated elements for the pair of element nodes connected thereby.

### Claim 5 (depends on 1)

The method of claim 1, wherein each of the plurality of element nodes includes a type field specifying a type that characterizes the respective element node and wherein each of the plurality of edges includes a type field specifying a type that characterizes the respective edge.

### Claim 6 (depends on 5)

The method of claim 5, wherein each of the plurality of element nodes includes a payload field including element-specific data, and wherein each of the plurality of edges includes a payload field including edge-specific data.

### Claim 7 (depends on 6)

The method of claim 6, wherein the element-specific data in the payload field for the first element node is structured based upon the type specified in the type field of the first element node, and wherein the edge-specific data in the payload field for the first edge is structured based upon the type specified in the type field of the first edge.

### Claim 8 (depends on 1)

The method of claim 1, wherein the first edge includes a transformation function defining the relative pose between the first and second elements, and wherein determining the second position from the first position includes applying the transformation function.

### Claim 9 (depends on 1)

The method of claim 1, wherein accessing the relative atlas to determine the plurality of elements includes:
identifying a third element node for a third element that is positioned close to the vehicle pose; and
walking from the third element node to other element nodes among the plurality of nodes in the relative atlas graph using the plurality of edges.

### Claim 10 (depends on 9)

The method of claim 9, wherein laying out the plurality of elements within the digital map using the determined relative poses includes laying out the element corresponding to each other element node by applying the relative pose defined by each edge interposed between the third element node and the other element node.

### Claim 11 (depends on 1)

The method of claim 1, wherein the relative atlas graph further includes a plurality of tile nodes for the geographical area, each tile node corresponding to a tile representing a region of the geographical area, and a second plurality of edges, each edge in the second plurality of edges connecting an element node from among the plurality of element nodes to a tile node from among the plurality of tile nodes and defining a relative pose of the associated element for the connected element node within a frame of reference for the connected tile node.

### Claim 12 (depends on 11)

The method of claim 11, wherein determining the vehicle pose includes determining the vehicle pose within the frame of reference in a first tile defined by a first tile node among the plurality of tile nodes.

### Claim 13 (depends on 12)

The method of claim 12, wherein the first tile node includes geometry data defining a surface model for at least a portion of the region of the geographical area represented by the first tile node, and wherein determining the vehicle pose further 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.

### Claim 14 (depends on 13)

The method of claim 13, further comprising nudging an element represented by a third element node among the plurality of element nodes based upon the alignment of the point cloud with the surface model, including updating a relative pose for an edge connected to the first element node.

### Claim 15 (depends on 14)

The method of claim 14, further comprising propagating the updated relative pose for the edge connected to the third element node to a remote computer system and/or another autonomous vehicle.

### Claim 16 (depends on 13)

The method of claim 13, wherein the surface model is a first surface model, and wherein determining the vehicle pose further includes:
aligning the point cloud with a second surface model for a second tile defined by geometry data stored in a second tile node for the second tile; and
selecting between the first tile and the second tile from which to determine the vehicle pose based upon the alignments of the point cloud with the first and second surface models.

### Claim 17 (depends on 12)

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

### Claim 18 (depends on 17)

The method of claim 17, wherein the relative atlas graph further includes a fixed reference node defining a fixed reference point and a reference frame therefor and a plurality of fixed reference edges connecting the plurality of tile nodes to the fixed reference node and defining relative poses between respective tiles for the plurality of tile nodes and the fixed reference point, wherein selecting the active tile node includes:
determining the location of the autonomous vehicle in the reference frame for the fixed reference point; and
identifying one or more nearby tiles to the determined location using the relative poses defined by the fixed reference edges.

### Claim 19 (depends on 11)

The method of claim 11, wherein the relative atlas graph further includes tile-and-tile edges connecting pairs of tile nodes and defining relative poses between the tiles represented thereby.

### Claim 20 (depends on 19)

The method of claim 19, wherein the relative atlas graph further includes a fixed reference node defining a fixed reference point and a reference frame therefor and a plurality of fixed reference edges connecting the plurality of tile nodes to the fixed reference node and defining relative poses between respective tiles for the plurality of tile nodes and the fixed reference point, and wherein the plurality of element nodes are not directly connected by edges to the fixed reference node such that no relative poses are defined between the plurality of elements and the fixed reference point.

### Claim 21 (depends on 1)

The method of claim 1, wherein the plurality of element nodes includes a plurality of gate nodes, each gate node defining a gate representing a permissible vehicle pose within a geographical area.

### Claim 22 (depends on 21)

The method of claim 21, wherein the plurality of edges includes a plurality of gate-and-gate edges connecting pairs of gate nodes among the plurality of gate nodes, and wherein laying out the plurality of elements within the digital map using the determined relative poses includes determining a plurality of potential paths within the geographical area using the plurality of gate-and-gate edges.

### Claim 23 (depends on 22)

The method of claim 22, wherein a first gate-and-gate edge among the plurality of gate-and-gate edges connects first and second gate nodes among the plurality of gate nodes that represent a same lane of a roadway.

### Claim 24 (depends on 22)

The method of claim 22, wherein a first gate-and-gate edge among the plurality of gate-and-gate edges connects first and second gate nodes among the plurality of gate nodes that represent different lanes of one or more roadways.

### Claim 25 (depends on 22)

The method of claim 22, wherein the plurality of element nodes further includes a plurality of boundary nodes, each boundary node defining a physical or virtual boundary that restricts vehicle movement within a geographical area.

### Claim 26 (depends on 25)

The method of claim 25, wherein the plurality of edges further includes a plurality of boundary-and-boundary edges connecting pairs of boundary nodes among the plurality of boundary nodes, each boundary-and-boundary edge defining a relative pose between a pair of boundaries defined by the respective pair of boundary nodes.

### Claim 27 (depends on 25)

The method of claim 25, wherein the plurality of edges further includes a plurality of boundary-and-gate edges, each connecting a gate node from among the plurality of gate nodes with a boundary node from among the plurality of boundary nodes and defining a relative pose between a gate and boundary respectively defined by the gate node and boundary node connected thereby.

### Claim 28 (depends on 22)

The method of claim 22, wherein determining the plurality of potential paths includes:
identifying a first gate node for a first gate that is positioned closest to the vehicle pose; and
walking outwardly from the first gate node to other gate nodes among the plurality of gate nodes in the relative atlas graph using the plurality of gate-and-gate-edges.

### Claim 29 (depends on 22)

The method of claim 22, further comprising planning a vehicle trajectory, including selecting a path among the plurality of potential paths.

### Claim 30 (depends on 29)

The method of claim 29, further comprising upsampling the selected path prior to planning the vehicle trajectory.

### Claim 31 (depends on 29)

The method of claim 29, wherein planning the vehicle trajectory further includes planning the vehicle trajectory based on one or more of a traffic control state, a desired destination, or an object tracked by a perception system of the autonomous vehicle.

### Claim 32 (depends on 29)

The method of claim 29, wherein planning the vehicle trajectory further includes planning the vehicle trajectory based on a boundary defined by a boundary node in the relative atlas graph.

### Claim 33 (depends on 1)

The method of claim 1, wherein the plurality of element nodes includes a plurality of traffic device nodes, each traffic device node associated with a traffic control within a geographical area and defining a traffic device, and wherein laying out the plurality of elements within the digital map using the determined relative poses includes laying out a plurality of traffic devices defined by the plurality of traffic device nodes in the digital map.

### Claim 34 (depends on 33)

The method of claim 33, wherein the relative atlas graph further includes a plurality of tile nodes, each tile node corresponding to a tile, and a second plurality of edges, each edge in the second plurality of edges connecting a traffic device node from among the plurality of traffic device nodes to a tile node from among the plurality of tile nodes and defining a relative pose of the traffic device defined by the connected traffic device node within a frame of reference for the connected tile node, and wherein laying out the plurality of traffic devices includes determining a pose of each of the plurality of traffic devices in a frame of reference for a first tile corresponding to a first tile node among the plurality of tile nodes using the relative poses defined by edges among the second plurality of edges.

### Claim 35 (depends on 34)

The method of claim 34, wherein the relative atlas further defines a predicted location of a first traffic device defined by a first traffic device node among the plurality of traffic device nodes in a field of view of a sensor, the method further comprising:
capturing an image with the sensor; and
processing a portion of the image corresponding to the predicted location of the first traffic device to determine a current state of the traffic device.

### Claim 36 (depends on 35)

The method of claim 35, further comprising extracting the portion of the image, and wherein processing the portion of the image comprises processing the portion of the image with an image classifier.

### Claim 37 (depends on 33)

The method of claim 33, wherein the plurality of element nodes includes a control node defining a traffic control for a regulated geographical area, wherein the relative atlas graph further includes a plurality of traffic-device-and-control edges connecting the control node to respective traffic device nodes among the plurality of traffic device nodes.

### Claim 38 (depends on 37)

The method of claim 37, wherein the plurality of element nodes further includes a plurality of passage nodes defining passages through the regulated geographical area, and wherein the relative atlas graph includes a plurality of control-and-passage edges connecting the plurality of passage nodes to the control node.

### Claim 39 (depends on 38)

The method of claim 38, wherein the relative atlas graph further includes passage-and-gate edges connecting passage nodes from among the plurality of passage nodes to one or more gate nodes from among the plurality of element nodes to define gates that are controlled by the traffic control.

### Claim 40 (depends on 1)

The method of claim 1, further comprising detecting a dynamic object proximate the autonomous vehicle by comparing sensor data collected by the autonomous vehicle against the digital map.

### Claim 41 (depends on 1)

The method of claim 1, further comprising tracking movement of a dynamic object using the digital map.

### Claim 42

An apparatus, comprising:
a memory storing a relative atlas, wherein the relative atlas comprises a relative atlas graph, and wherein the relative atlas graph includes a plurality of element nodes for the plurality of elements and a plurality of edges, each of which connecting a pair of element nodes from among the plurality of element nodes and defining a relative pose between the associated elements for the pair of element nodes;
one or more processors coupled to the memory; and
computer instructions executable by the one or more processors to generate a digital map for use by an autonomous vehicle by determining a vehicle pose for the autonomous vehicle within a geographical area, accessing the relative atlas to identify a plurality of elements in the geographical area, accessing the relative atlas to determine relative poses between the plurality of elements, and laying out the plurality of elements within the digital map using the determined relative poses, wherein the computer instructions are configured to lay out the plurality of elements within the digital map using the determined relative poses by:
laying out a first element among the plurality of elements at a first position in the relative map; and
laying out a second element among the plurality of elements at a second position in the relative map, including determining the second position from the first position using a relative pose between the first and second elements and defined in a first edge among the plurality of edges that connects a first element node for the first element with a second element node for the second element.

### Claim 43 (depends on 42)

The apparatus of claim 42, wherein the apparatus is an autonomous vehicle control system of the autonomous vehicle.

### Claim 44

An autonomous vehicle, comprising:
a memory storing a relative atlas, wherein the relative atlas comprises a relative atlas graph, and wherein the relative atlas graph includes a plurality of element nodes for the plurality of elements and a plurality of edges, each of which connecting a pair of element nodes from among the plurality of element nodes and defining a relative pose between the associated elements for the pair of element nodes; and
an autonomous vehicle control system coupled to the memory and configured to generate a digital map by determining a vehicle pose within a geographical area, accessing the relative atlas to identify a plurality of elements in the geographical area, accessing the relative atlas to determine relative poses between the plurality of elements, and laying out the plurality of elements within the digital map using the determined relative poses, wherein autonomous vehicle control system is configured to lay out the plurality of elements within the digital map using the determined relative poses by:
laying out a first element among the plurality of elements at a first position in the relative map; and
laying out a second element among the plurality of elements at a second position in the relative map, including determining the second position from the first position using a relative pose between the first and second elements and defined in a first edge among the plurality of edges that connects a first element node for the first element with a second element node for the second element.

### Claim 45

A non-transitory computer readable storage medium storing computer instructions executable by one or more processors to perform a method of generating a digital map for use by an autonomous vehicle, the method comprising:
determining a vehicle pose for the autonomous vehicle within a geographical area;
accessing a relative atlas to identify a plurality of elements in the geographical area, wherein the relative atlas comprises a relative atlas graph, and wherein the relative atlas graph includes a plurality of element nodes for the plurality of elements and a plurality of edges, each of which connecting a pair of element nodes from among the plurality of element nodes and defining a relative pose between the associated elements for the pair of element nodes;
accessing the relative atlas to determine relative poses between the plurality of elements; and
laying out the plurality of elements within the digital map using the determined relative poses, 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 relative map; and
laying out a second element among the plurality of elements at a second position in the relative map, including determining the second position from the first position using a relative pose between the first and second elements and defined in a first edge among the plurality of edges that connects a first element node for the first element with a second element node for the second element.