Systems and methods for generating multilevel occupancy and occlusion grids for controlling navigation of vehicles

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.

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.