Methods and systems for map generation and alignment

1. A method comprising:

receiving, from a sensor, first sensor data indicative of positions of a plurality of markers relative to the sensor within an environment;

determining a pose of the sensor within a map of the plurality of markers based on the first sensor data;

receiving, from the sensor, second sensor data indicative of distance from the sensor to a surface within the environment;

determining an occupancy grid map representing the surface within the environment based on the second sensor data and the determined pose of the sensor;

determining a transformation between the map of the plurality of markers and a design model of the environment that relates occupied cells in the occupancy grid map to sampled points from the design model; and

causing a robot to navigate the environment based on the transformation between the map of the plurality of markers and the design model.

2. The method of claim 1 , wherein the plurality of markers comprises a plurality of retroreflective markers arranged along a horizontal plane, and wherein the first sensor data is received from a two-dimensional laser scanner.

3. The method of claim 1 , wherein determining the transformation comprises determining a rotation and a translation of a horizontal plane.

4. The method of claim 1 , wherein determining the transformation comprises sampling a plurality of two-dimensional rotation and translation values.

5. The method of claim 1 , wherein determining the transformation comprises:

determining, for each candidate transformation of a plurality of candidate transformations, a sum of point-to-line normal distances between occupied cells in the occupancy grid map and lines from the design model that contain the sampled points; and

determining the transformation from the plurality of candidate transformations based on the sum of point-to-line normal distances determined for each candidate transformation.

6. The method of claim 1 , wherein determining the transformation comprises:

determining, for each candidate transformation of a plurality of candidate transformations, a measure confidence comprising a percentage of occupied cells in the occupancy grid map that are within a threshold distance of lines from the design model that contain the sampled points; and

determining the transformation from the plurality of candidate transformations based on the measure confidence determined for each candidate transformation.

7. The method of claim 6 , further comprising providing an indication of the measure confidence for the determined transformation.

8. The method of claim 1 , wherein determining the occupancy grid map comprises assigning each cell a state that is one of an obstacle, free space, and an unknown region.

9. The method of claim 1 , further comprising:

refining the pose of the sensor within the map of the plurality of markers based on additional received sensor data; and

adjusting the transformation between the map of the plurality of markers and the design model of the environment based on the refined pose of the sensor within the map of the plurality of markers.

10. The method of claim 9 , wherein adjusting the transformation comprises sampling a range of candidate transformations based on the determined transformation, wherein the sampled range of candidate transformations in narrower than an initial range of candidate transformations used to determine the transformation.

11. The method of claim 1 , further comprising determining the map of the plurality of markers and the transformation by solving a graph-based optimization problem.

12. The method of claim 11 , wherein the graph-based optimization problem comprises a separate edge for each point-to-line normal distance between an occupied cell in the occupancy grid map and a line from the design model that contains a sampled point.

13. The method of claim 1 , wherein the design model of the environment comprises a computer-aided design (CAD) model.

14. The method of claim 13 , further comprising:

identifying an alignment error in the CAD model based on the transformation; and

providing an indication of the identified alignment error in the CAD model.

15. A system, comprising:

a sensor;

a computing system; and

a non-transitory computer readable medium; and

program instructions stored on the non-transitory computer readable medium and executable by the computing system to:

receive, from the sensor, first sensor data indicative of positions of a plurality of markers relative to the sensor within an environment;

determine a pose of the sensor within a map of the plurality of markers based on the first sensor data;

receive, from the sensor, second sensor data indicative of distance from the sensor to a surface within the environment;

determine an occupancy grid map representing the surface within the environment based on the second sensor data and the determined pose of the sensor;

determine a transformation between the map of the plurality of markers and a design model of the environment that relates occupied cells in the occupancy grid map to sampled points from the design model; and

cause a robot to navigate the environment based on the transformation between the map of the plurality of markers and the design model.

16. The system of claim 15 , wherein the plurality of markers comprises retroreflective markers.

17. The system of claim 15 , wherein the computing system is further configured to:

refine the pose of the sensor within the map of the plurality of markers based on additional received sensor data; and

adjust the transformation between the map of the plurality of markers and the design model of the environment based on the refined pose of the sensor within the map of the plurality of markers.

18. A non-transitory computer readable medium having stored therein program instructions executable by a computing system to cause the computing system to perform operations, the operations comprising:

receiving, from a sensor, first sensor data indicative of positions of a plurality of markers relative to the sensor within an environment;

determining a pose of the sensor within a map of the plurality of markers based on the first sensor data;

receiving, from the sensor, second sensor data indicative of distance from the sensor to a surface within the environment;

determining an occupancy grid map representing the surface within the environment based on the second sensor data and the determined pose of the sensor;

determining a transformation between the map of the plurality of markers and a design model of the environment that relates occupied cells in the occupancy grid map to sampled points from the design model; and

causing a robot to navigate the environment based on the transformation between the map of the plurality of markers and the design model.

19. The non-transitory computer readable medium of claim 18 , wherein the sensor is coupled to a vehicle; and

wherein the operations further comprise:

determining a pose of the vehicle using a fixed sensor to vehicle transform.