Building elevation maps from laser data

A device for generating an elevation map of a roadway, the device comprising:

• memory storing sensor data, the sensor data including a plurality of data points, each data point of the plurality of data points representing a position and elevation of a particular location along the roadway;
• and
• a processor, coupled to the memory and operable to:
• access the stored sensor data;
• generate a 2D grid of the roadway, the 2D grid including a plurality of cells, each cell representing an area of the roadway;
• generate a first set of data points for each cell of the plurality of cells based on the positions of the plurality of data points;
• filter the first set of data points for each cell of the plurality of cells in order to generate a second set of data points for each cell of the plurality of cells;
• for each cell of the plurality of cells, identify a data point of the second set of data points associated with a lowest relative elevation;
• and
• generate the elevation map of the roadway based on the identified data points of the second sets of data points associated with the lowest relative elevations.

A non-transitory, tangible computer-readable storage medium on which computer readable instructions of a program are stored, the instructions, when executed by a processor, cause the processor to perform a method of generating an elevation map of a roadway, the method comprising:

• receiving sensor data, the sensor data including a plurality of data points, each of the plurality of data points representing a position and elevation of a particular location along the roadway;
• generating a 2D grid of the roadway, the 2D grid including a plurality of cells, each cell representing an area of the roadway;
• generating a first set of data points for each cell of the plurality of cells based on the positions of the plurality of data points;
• filtering the first set of data points for each cell of the plurality of cells in order to generate a second set of data points for each cell of the plurality of cells;
• for each cell of the plurality of cells, identifying a data point of the second set of data points associated with a lowest relative elevation;
• and
• generating the elevation map of the roadway based on the identified data points of the second sets of data points associated with the lowest relative elevations.

A vehicle comprising:

• a braking system configured to decelerate the vehicle;
• an acceleration system configured to accelerate the vehicle;
• a steering system configured to change a direction of motion of the vehicle;
• a processor configured to control the breaking, acceleration, and steering systems;
• and
• memory coupled to the processor, the memory storing an elevation map, the elevation map being generated by:
• receiving sensor data, the sensor data including a plurality of data points, each of the plurality of data points representing a position and elevation of a particular location along a roadway;
• generating a 2D grid of the roadway, the 2D grid including a plurality of cells, each cell representing an area of the roadway;
• generating a first set of data points for each cell of the plurality of cells based on the positions of the plurality of data points;
• filtering the first set of data points for each cell of the plurality of cells in order to generate a second set of data points for each cell of the plurality of cells;
• for each cell of the plurality of cells, identifying a data point of the second set of data points associated with a lowest relative elevation;
• and
• generating the elevation map based on the identified data points of the second sets of data points associated with the lowest relative elevations;
• and
• wherein the processor is operable to access the elevation map from the memory and use the elevation map to navigate the vehicle along a route by controlling one or more of the braking, acceleration, and steering systems.