# US 2023/0056589 A1 · Systems and methods for generating multilevel occupancy and occlusion grids for controlling navigation of vehicles > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2023/0056589 A1 - Document ID: US20230056589A1 - Status: Published application - Kind: A1 - Application number: 17/821,550 - Filed: 2022-08-23 - Published: 2023-02-23 - Earliest claimed: 2021-08-23 - Assignees: Argo AI, LLC - Applicants: Argo AI, LLC - Inventors: Kai Trojahner - Web page: https://patentgrep.com/patent/US20230056589A1 ## CPC - B60W 60/0016: {of the vehicle or its occupants} - B60W 40/09: Driving style or behaviour - B60W 2040/0881: {Seat occupation; Driver or passenger presence} - B60W 2540/01: Occupants other than the driver - B60W 2556/40: High definition maps - 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 ## Abstract This document discloses methods of acquiring a 3D map of an area with multiple heights. The 3D map may include tiles, each of which provides ground height information for one or more of the plurality of levels. A grid corresponding to the 3D map is generated. The grid may divide each of the plurality of tiles into a plurality of cells, The grid may include: (a) a unique index assigned to each of the plurality of cells, in which the unique index is convertible to an index of a tile of the 3D map in which that cell is included, and (b) a plurality of gridlets associated with each of the plurality of cells, wherein a number of the plurality of gridlets associated with a cell is equal to a number of height levels represented by a tile of the 3D map in which that cell is included. ## Claims ### Claim 1 A method of generating an occupancy and occlusion grid of a geographic area, the method comprising, by a processor: acquiring a 3D map of a geographic area comprising a plurality of height levels, wherein the 3D map comprises a plurality of tiles, each tile providing ground height information for one or more of the plurality of height levels; generating a grid corresponding to the 3D map that divides each of the plurality of tiles into a plurality of cells, the grid comprising: a unique index assigned to each of the plurality of cells, the unique index convertible to an index of a tile of the 3D map in which that cell is included, and a plurality of gridlets associated with each of the plurality of cells, wherein a number of the plurality of gridlets associated with a cell is equal to a number of height levels represented by a tile of the 3D map in which that cell is included; and saving the grid to a map data set. ### Claim 2 (depends on 1) The method of claim 1, further comprising generating, using the grid, an occupancy and occlusion grid by: receiving, from one or more sensors of a vehicle, a point cloud comprising a plurality of impact points corresponding to a portion of the grid, wherein each of the plurality of impact points comprises a location having z-coordinate with respect to the geographic area; identifying at least one cell of the portion of the grid that includes an impact point; and assigning an occupied state to the at least one cell, the occupied state being indicative of an object being present in the at least one cell. ### Claim 3 (depends on 2) The method of claim 2, further comprising identifying, using a z-coordinate of the impact point and a unique index of the at least one cell, a height above ground (HAG) for the at least one cell, wherein the HAG is indicative of a height below which the at least one cell is occupied. ### Claim 4 (depends on 3) The method of claim 3, further comprising resolving conflicts between two or more HAGs identified for the at least one cell by using a maximum value of the two or more HAGs. ### Claim 5 (depends on 3) The method of claim 3, further comprising: identifying a ray between the impact point and an origin point; and assigning, to one or more cells traversed by the ray, an occluded state, the occluded state being indicative of the one or more sensors not receiving information about occupancy of the one or more cells. ### Claim 6 (depends on 5) The method of claim 5, further comprising: identifying, using a location of the origin point and a location of the impact point, a height of the ray in each of the one or more cells; and identifying, for each of the one or more cells, using a height of the ray in that cell and a unique index of that cell, a height above ground (HAG) for that cell, wherein the HAG is indicative of a height below which that cell is occluded. ### Claim 7 (depends on 6) The method of claim 6, further comprising resolving conflicts between two or more HAGs identified for that cell by using a minimum value of the two or more HAGs. ### Claim 8 (depends on 6) The method of claim 6, further comprising: caching the HAG for all levels of a given cell index; and using the cached HAD for updating the occupancy and occlusion grid for another portion of the grid. ### Claim 9 (depends on 5) The method of claim 5, wherein the origin point is a location of the vehicle in the geographical area. ### Claim 10 (depends on 1) The method of claim 1, further comprising identifying, using the occupancy and occlusion grid, a trajectory for a vehicle as the vehicle moves in the geographic area. ### Claim 11 A system for generating an occupancy and occlusion grid of a geographic area, the system comprising: a processor; and a memory containing programming instructions that are configured to, when executed, cause the processor to: acquire a 3D map of a geographic area comprising a plurality of height levels, wherein the 3D map comprises a plurality of tiles, each tile providing ground height information for one or more of the plurality of height levels, and generate a grid corresponding to the 3D map that divides each of the plurality of tiles into a plurality of cells, the grid comprising: a unique index assigned to each of the plurality of cells, the unique index convertible to an index of a tile of the 3D map in which that cell is included, and a plurality of gridlets associated with each of the plurality of cells, wherein a number of the plurality of gridlets associated with a cell is equal to a number of height levels represented by a tile of the 3D map in which that cell is included, and save the grid to a map data set. ### Claim 12 (depends on 11) The system of claim 11, further comprising programming instructions to generate, using the grid, an occupancy and occlusion grid by: receiving, from one or more sensors of a vehicle, a point cloud comprising a plurality of impact points corresponding to a portion of the grid, wherein each of the plurality of impact points comprises a location having z-coordinate with respect to the geographic area; identifying at least one cell of the portion of the grid that includes an impact point; and assigning an occupied state to the at least one cell, the occupied state being indicative of an object being present in the at least one cell. ### Claim 13 (depends on 12) The system of claim 12, further comprising programming instructions to identify, using a z-coordinate of the impact point and a unique index of the at least one cell, a height above ground (HAG) for the at least one cell, wherein the HAG is indicative of a height below which the at least one cell is occupied. ### Claim 14 (depends on 13) The system of claim 13, further comprising programming instructions to resolve conflicts between two or more HAGs identified for the at least one cell by using a maximum value of the two or more HAGs. ### Claim 15 (depends on 14) The system of claim 14, further comprising programming instructions to: identify a ray between the impact point and an origin point; and assign, to one or more cells traversed by the ray, an occluded state, the occluded state being indicative of the one or more sensors not receiving information about occupancy of the one or more cells. ### Claim 16 (depends on 15) The system of claim 15, further comprising programming instructions to: identify, using a location of the origin point and a location of the impact point, a height of the ray in each of the one or more cells; and identify, for each of the one or more cells, using a height of the ray in that cell and a unique index of that cell, a height above ground (HAG) for that cell, wherein the HAG is indicative of a height below which that cell is occluded. ### Claim 17 (depends on 15) The system of claim 15, wherein the origin point is a location of the vehicle in the geographical area. ### Claim 18 (depends on 11) The system of claim 11, further comprising programming instructions to identify, using the occupancy and occlusion grid, a trajectory for a vehicle as the vehicle moves in the geographic area. ### Claim 19 (depends on 18) The system of claim 18, wherein the processor and memory are components of the vehicle. ### Claim 20 A computer program product comprising a memory a memory containing programming instructions that are configured to, when executed, cause a processor to: acquire a 3D map of a geographic area comprising a plurality of height levels, wherein the 3D map comprises a plurality of tiles, each tile providing ground height information for one or more of the plurality of levels, and generate a grid corresponding to the 3D map that divides each of the plurality of tiles into a plurality of cells, the grid comprising: a unique index assigned to each of the plurality of cells, the unique index convertible to an index of a tile of the 3D map in which that cell is included, and a plurality of gridlets associated with each of the plurality of cells, wherein a number of the plurality of gridlets associated with a cell is equal to a number of height levels represented by a tile of the 3D map in which that cell is included; and save the grid to a map data set.