# US 12,181,887 B2 · Occupancy grid movie system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,181,887 B2 - Document ID: US12181887B2 - Status: Granted - Kind: B2 - Application number: 18/328,354 - Filed: 2023-06-02 - Published: 2023-10-05 - Granted: 2024-12-31 - Earliest claimed: 2018-07-30 - Assignees: GM Cruise Holdings LLC - Applicants: GM Global Technology Operations LLC - Inventors: Gabriel Warshauer-Baker; Kevin Chu - Web page: https://patentgrep.com/patent/US12181887B2 ## CPC - G05D 1/0221: {involving a learning process} - G05D 1/0238: {using obstacle or wall sensors (G05D1/0246 and G05D1/0289 take precedence; lidar systems designed for anti-collision purposes G01S17/93)} - B60W 60/001: {Planning or execution of driving tasks} - G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes} - G05D 1/0231: {using optical position detecting means (position-fixing by using electromagnetic waves other than radio waves, e.g. optical position detecting means G01S5/16)} - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - B60W 10/06: including control of combustion engines - B60W 10/18: including control of braking systems - B60W 10/20: including control of steering systems - B60W 2554/00: Input parameters relating to objects - B60W 2710/06: Combustion engines, Gas turbines - B60W 2710/18: Braking system - B60W 2710/20: Steering systems - G01C 21/00: Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 (measuring distance traversed on the ground by a vehicle G01C22/00; control of position, course, altitude or attitude of vehicles G05D1/00; traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968) - 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/0212: {with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287)} - G05D 2101/10: using artificial intelligence [AI] techniques - G06F 16/29: Geographical information databases - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - 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) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Various technologies described herein pertain to generating an occupancy grid movie for utilization in motion planning for the autonomous vehicle. The occupancy grid movie can be generated for a given time and can include time-stepped occupancy grids for future times that are at predefined time intervals from the given time. The time-stepped occupancy grids include cells corresponding to regions in an environment surrounding the autonomous vehicle. Probabilities can be assigned to the cells specifying likelihoods that the regions corresponding to the cells are occupied at the future times. Moreover, cached query objects that respectively specify indices of cells of a grid occupied by a representation of an autonomous vehicle at corresponding orientations are described herein. An occupancy grid for the environment surrounding the autonomous vehicle can be queried to determine whether cells of the occupancy grid are occupied utilizing a cached query object from the cache query objects. ## Claims ### Claim 1 An autonomous vehicle, comprising: a computing system, comprising: a processor; and memory storing: cached query objects that respectively specify indices of cells of a grid occupied by a representation of the autonomous vehicle; and computer-executable instructions that, when executed by the processor, cause the processor to perform acts comprising: selecting a first shaped cached query object from the cached query objects that provides a first representation of the autonomous vehicle; querying whether first cells of an occupancy grid for an environment surrounding the autonomous vehicle are occupied utilizing the first shaped cached query object; determining a first portion of a motion plan for the autonomous vehicle based on whether the first cells of the occupancy grid are occupied; selecting a second shaped cached query object from the cached query objects that provides a differing second representation of the autonomous vehicle, wherein the first shaped cached query object and the second shaped cached query object have differing shapes; querying whether second cells of the occupancy grid for the environment surrounding the autonomous vehicle are occupied utilizing the second shaped cached query object; determining a second portion of the motion plan for the autonomous vehicle based on whether the second cells of the occupancy grid are occupied; and controlling the autonomous vehicle based on the motion plan. ### Claim 2 (depends on 1) The autonomous vehicle of claim 1, wherein the first shaped cached query object is selected for a first step of a motion planning process, and the second shaped cached query object is selected for a second step of a motion planning process. ### Claim 3 (depends on 1) The autonomous vehicle of claim 1, wherein the first portion of the motion plan comprises a path for motion of the autonomous vehicle, and the second portion of the motion plan comprises a speed of the autonomous vehicle when traveling along the path. ### Claim 4 (depends on 1) The autonomous vehicle of claim 1, wherein the first shaped cached query object has a rectangular shape, and the second shaped cached query object as a trapezoidal shape. ### Claim 5 (depends on 1) The autonomous vehicle of claim 1, wherein the first shaped cached query object is a rectangle, and the second shaped cached query object is a non-rectangular polygon. ### Claim 6 (depends on 1) The autonomous vehicle of claim 1, the memory further stores computer-executable instructions that, when executed by the processor, cause the processor to perform acts comprising: translating the first shaped cached query object based on a proposed location of the autonomous vehicle, wherein the first cells of the occupancy grid are queried utilizing the first shaped cached query object as translated; and translating the second shaped cached query object based on the proposed location of the autonomous vehicle, wherein the second cells of the occupancy grid are queried utilizing the second shaped cached query object as translated. ### Claim 7 (depends on 1) The autonomous vehicle of claim 1, wherein the first shaped cached query object and the second shaped cached query object are selected based on a proposed orientation of the autonomous vehicle. ### Claim 8 (depends on 7) The autonomous vehicle of claim 7, wherein orientations of the representations of the autonomous vehicle in the grid for the cached query objects are at a predefined rotation interval. ### Claim 9 (depends on 8) The autonomous vehicle of claim 8, wherein the predefined rotation interval is 1 degree. ### Claim 10 (depends on 8) The autonomous vehicle of claim 8, wherein the predefined rotation interval is 10 degrees. ### Claim 11 (depends on 1) The autonomous vehicle of claim 1, further comprising: an engine; a braking system; and a steering system; wherein the computing system is in communication with the engine, the braking system, and the steering system, and wherein controlling the autonomous vehicle based on the motion plan further comprises controlling at least one of the engine, the braking system, or the steering system based on the motion plan. ### Claim 12 A method performed by a processor of a computing system of an autonomous vehicle, comprising: selecting a first shaped cached query object from cached query objects that provides a first representation of the autonomous vehicle, the cached query objects respectively specify indices of cells of a grid occupied by a representation of the autonomous vehicle; querying whether first cells of an occupancy grid for an environment surrounding the autonomous vehicle are occupied utilizing the first shaped cached query object; determining a first portion of a motion plan for the autonomous vehicle based on whether the first cells of the occupancy grid are occupied; selecting a second shaped cached query object from the cached query objects that provides a differing second representation of the autonomous vehicle, wherein the first shaped cached query object and the second shaped cached query object have differing shapes; querying whether second cells of the occupancy grid for the environment surrounding the autonomous vehicle are occupied utilizing the second shaped cached query object; determining a second portion of the motion plan for the autonomous vehicle based on whether the second cells of the occupancy grid are occupied; and controlling the autonomous vehicle based on the motion plan. ### Claim 13 (depends on 12) The method of claim 12, wherein the first shaped cached query object is selected for a first step of a motion planning process, and the second shaped cached query object is selected for a second step of a motion planning process. ### Claim 14 (depends on 12) The method of claim 12, wherein the first portion of the motion plan comprises a path for motion of the autonomous vehicle, and the second portion of the motion plan comprises a speed of the autonomous vehicle when traveling along the path. ### Claim 15 (depends on 12) The method of claim 12, wherein the first shaped cached query object has a rectangular shape, and the second shaped cached query object as a trapezoidal shape. ### Claim 16 (depends on 12) The method of claim 12, wherein the first shaped cached query object is a rectangle, and the second shaped cached query object is a non-rectangular polygon. ### Claim 17 (depends on 12) The method of claim 12, further comprising: translating the first shaped cached query object based on a proposed location of the autonomous vehicle, wherein the first cells of the occupancy grid are queried utilizing the first shaped cached query object as translated; and translating the second shaped cached query object based on the proposed location of the autonomous vehicle, wherein the second cells of the occupancy grid are queried utilizing the second shaped cached query object as translated. ### Claim 18 (depends on 12) The method of claim 12, wherein the first shaped cached query object and the second shaped cached query object are selected based on a proposed orientation of the autonomous vehicle. ### Claim 19 A computing system, comprising: a processor; and memory storing: cached query objects that respectively specify indices of cells of a grid occupied by a representation of an autonomous vehicle; and computer-executable instructions that, when executed by the processor, cause the processor to perform acts comprising: selecting a first shaped cached query object from the cached query objects that provides a first representation of the autonomous vehicle; querying whether first cells of an occupancy grid for an environment surrounding the autonomous vehicle are occupied utilizing the first shaped cached query object; determining a first portion of a motion plan for the autonomous vehicle based on whether the first cells of the occupancy grid are occupied; selecting a second shaped cached query object from the cached query objects that provides a differing second representation of the autonomous vehicle, wherein the first shaped cached query object and the second shaped cached query object have differing shapes; querying whether second cells of the occupancy grid for the environment surrounding the autonomous vehicle are occupied utilizing the second shaped cached query object; determining a second portion of the motion plan for the autonomous vehicle based on whether the second cells of the occupancy grid are occupied; and controlling the autonomous vehicle based on the motion plan. ### Claim 20 (depends on 19) The computing system of claim 19, wherein the first shaped cached query object is selected for a first step of a motion planning process, and the second shaped cached query object is selected for a second step of a motion planning process.