SYSTEMS AND METHODS FOR ROBOTIC MAPPING

• US 20180120116A1
• Filed: 11/01/2016
• Published: 05/03/2018
• Est. Priority Date: 11/01/2016
• Status: Active Grant

• Current Assignee: Brain Corporation
• Original Assignee: Brain Corporation
• Inventors: Rombouts, Jaldert, Gabardos, Borja Ibarz, Passot, Jean-Baptiste, Smith, Andrew
• Granted Patent: US 10,274,325 B2
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3848 Data obtained from both position sensors and additional sensors
• CPC Class Codes: G01S 15/89 for mapping or imaging
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

Systems and methods for robotic mapping are disclosed. In some exemplary implementations, a robot can travel in an environment. From travelling in the environment, the robot can create a graph comprising a plurality of nodes, wherein each node corresponds to a scan taken by a sensor of the robot at a location in the environment. In some exemplary implementations, the robot can generate a map of the environment from the graph. In some cases, to facilitate map generation, the robot can constrain the graph to start and end at a substantially similar location. The robot can also perform scan matching on extended scan groups, determined from identifying overlap between scans, to further determine the location of features in a map.

Claims

1. A method of generating a map by a robot, comprising:

traveling, by the robot, in an environment;

creating a graph comprising a plurality of nodes, wherein each node corresponds to a scan taken by a sensor of the robot at a location in the environment;

constraining the graph to start and end at a substantially similar location;

performing scan matching on extended scan groups determined at least in part from groups of the plurality of nodes;

associating a range of possible locations with each of the plurality of nodes based at least in part on the scan matching;

determining confidences associated with each range of possible locations;

optimizing the graph to find a likely location of the plurality of nodes based at least in part on the associated confidences; and

generating the map from the optimized graph.

2. The method of claim 1, wherein the generation of the map comprises ray tracing with the scans taken by the sensor, the scans associated with the plurality of nodes.

3. The method of claim 1, wherein optimizing the graph comprises:

generating a cost function based at least in part on;

(1) relative locations of each of the plurality of nodes, and (2) the confidences associated with each of the plurality of nodes; and

solving the cost function for a minimum.

4. The method of claim 1, wherein constraining the graph to start and end at the substantially similar location further comprises constraining the graph to start and end in view of a home locator.

5. The method of claim 1, wherein the traveling, by the robot, in the environment further comprises navigating under user control.

6. The method of claim 1, wherein the associated confidences further comprise using a probability distribution indicative at least in part of a probability that a given node is in a given location.

7. The method of claim 1, wherein the extended scan groups determined at least in part from groups of the plurality of nodes, further comprises:

selecting a root node as a reference location;

finding possible overlaps in measurements of distinct features in scans taken at other nodes; and

grouping the other nodes into extended scan groups based at least in part on overlapping distinct features of the scans at those respective other nodes.

8. A robot, comprising:

a sensor configured to take scans of an environment at a plurality of nodes, wherein each node is associated with a location; and

a mapping and localization unit configured to;

create a graph of the nodes based at least in part on the taken scans;

determine extended scan groups based at least in part on groups of the plurality of nodes; and

perform scan matching on the extended scan groups.

9. The robot of claim 8, wherein the mapping and localization unit is further configured to constrain the graph to start and end at a substantially similar location.

10. The robot of claim 8, wherein the mapping and localization unit is further configured to determine confidences associated with the location of each node.

11. The robot of claim 10, wherein the mapping and localization unit is further configured to generate a cost function based at least in part on the confidences and locations of each node, wherein the mapping and localization unit determines the location of each node in the graph based on solving the cost function for a minimum.

12. The robot of claim 8, further comprising a processor that is further configured to render a map from the graph, the map rendered based at least in part on ray tracings of the scans.

13. The robot of claim 8, further comprising an actuator configured to move the robot between locations.

14. The robot of claim 8, further comprising a user interface configured for user control of the robot.

15. The robot of claim 8, further comprising a navigation unit configured to navigate the robot autonomously.

16. A non-transitory computer-readable storage apparatus having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus to operate a robot, the instructions configured to, when executed by the processing apparatus, cause the processing apparatus to:

cause a sensor to generate scans of an environment at a plurality of nodes, wherein each node of the plurality is associated with a location;

create a graph of the plurality of nodes based on the generated scans;

determine extended scan groups based at least in part from scans associated with groups of the plurality of nodes; and

perform scan matching on the extended scan groups.

17. The non-transitory computer-readable storage apparatus of claim 16, further comprising one or more instructions, when executed by the processing apparatus, that further cause the processing apparatus to constrain the graph to start and end at a substantially similar location.

18. The non-transitory computer-readable storage apparatus of claim 16, wherein each extended scan group comprises three or more scans.

19. The non-transitory computer-readable storage apparatus of claim 16, further comprising one or more instructions, when executed by the processing apparatus, that further cause the processing apparatus to determine a cost function based at least in part on confidences associated with the location of each node.

20. The non-transitory computer-readable storage apparatus of claim 19, further comprising one or more instructions, when executed by the processing apparatus, that further cause the processing apparatus to generate a map based at least in part on minimizing the cost function.