Efficient mapping of robot environment

• US 10,078,333 B1
• Filed: 04/17/2016
• Issued: 09/18/2018
• Est. Priority Date: 04/17/2016
• Status: Active Grant

• Current Assignee: X Development LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Bajracharya, Max
• Primary Examiner(s): Wiltey, Nicholas K
• Application Number:
  US15/131,014
• Time in Patent Office: 884 Days
• Field of Search: None
• CPC Class Codes: B25J 9/1697 Vision controlled systems
• CPC Class Codes: G05D 1/0251 extracting 3D information from a plurality of images taken from different locations, e.g. stereo vision stereoscopic image analysis H04N13/00; depth recovery from images G06T7/593
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: Y10S 901/01 Mobile robot

Abstract

Methods, apparatus, systems, and computer-readable media are provided for efficient mapping of a robot environment. In various implementations, a group of data points may be sensed by a three-dimensional sensor. One or more voxels of a three-dimensional voxel model that are occupied by the group of data points may be identified. For each occupied voxel, a column of the three-dimensional voxel model that contains the occupied voxel may be identified. Occupied voxels contained in each column may be indexed by elevation. In various implementations, one or more sparse linked data structures may be used to represent the columns.

Claims

1. A method, comprising:

receiving, by one or more processors, from a three-dimensional vision sensor of a robot, a group of data points sensed by the three-dimensional vision sensor;

identifying, by the one or more processors, one or more voxels of a three-dimensional voxel model that are occupied by the group of data points;

determining, by the one or more processors, for each occupied voxel, data representing the occupied voxel, wherein the data includes statistics about how a plurality of data points of the group of data points are spatially distributed within the occupied voxel;

identifying, by the one or more processors, for each occupied voxel, a column of the three-dimensional voxel model that contains the occupied voxel; and

indexing in memory, by the one or more processors the data representing voxels of the three-dimensional voxel model, the indexing comprising indexing, in the memory, the data representing occupied voxels contained in each column by elevation without indexing one or more unoccupied voxels by elevation.

2. The method of claim 1, wherein the indexing comprises generating, for each column of the three-dimensional voxel model that contains one or more occupied voxels, a linked data structure with one or more nodes representing the one or more occupied voxels contained in the column.

3. The method of claim 2, wherein the linked data structure comprises a linked list.

4. The method of claim 2, wherein the linked data structure is a binary tree.

5. The method of claim 4, wherein the binary tree is searchable by voxel elevation.

6. The method of claim 2, wherein the nodes are linked in order of elevation.

7. The method of claim 2, further comprising:

searching, by the one or more processors, linked data structures associated with each column to identify voxels within a target elevation range; and

operating, by the one or more processors, one or more portions of the robot to move along one or more paths that avoid voxels identified from the searching.

8. The method of claim 1, further comprising analyzing the statistics to identify a surface formed by the one or more data points contained in the voxel.

9. The method of claim 1, further comprising:

identifying, by the one or more processors, one or more of the occupied voxels that satisfy a criterion;

projecting, by the one or more processors, the one or more occupied voxels that satisfy the criterion onto a two-dimensional plane representing a surface navigable by the robot; and

calculating, by the one or more processors, a path across the surface for the robot to navigate, wherein the path avoids obstacles represented by the projected one or more occupied voxels.

10. The method of claim 9, wherein the criterion comprises an elevation range that corresponds to at least a height of the robot.

11. The method of claim 1, further comprising allocating, by the one or more processors, a greater amount of memory to store data representing each occupied voxel than is allocated to store data indicative of any unoccupied voxel of the three-dimensional voxel model.

12. The method of claim 1, further comprising allocating, by the one or more processors, memory from a heap to each occupied voxel, wherein unoccupied voxels are not allocated from the heap.

13. The method of claim 1, further comprising:

classifying, by the one or more processors, as manipulable object voxels, one or more occupied voxels containing data points deemed to be associated with a manipulable object;

obtaining, by the one or more processors, from the three-dimensional vision sensor, one or more up-to-date depth values associated with data points within the one or more manipulable object voxels; and

determining, by the one or more processors, that the manipulable object has moved based at least in part on the one or more up-to-date depth values.

14. A robot comprising:

a three-dimensional vision sensor;

one or more processors operably coupled with the three-dimensional vision sensor; and

memory operably coupled with the one or more processors, the memory storing instructions that, when executed by the one or more processors, cause the one or more processors to;

receive, from the three-dimensional vision sensor, a group of data points sensed by the three-dimensional vision sensor;

identify one or more voxels of a three-dimensional voxel model that are occupied by the group of data points;

determine, for each occupied voxel, data representing the occupied voxel, wherein the data includes statistics about how a plurality of data points of the group of data points are spatially distributed within the occupied voxel;

identify, for each occupied voxel, a column of the three-dimensional voxel model that contains the occupied voxel; and

index, in the memory, the data representing voxels of the three-dimensional voxel model, wherein in indexing the voxels the one or more processors are to index, in the memory, the data representing occupied voxels contained in each column by elevation without indexing one or more unoccupied voxels by elevation.

15. The robot of claim 14, wherein the memory further comprises instructions that, when executed by the one or more processors, cause the one or more processors to generate, for each column of the three-dimensional voxel model that contains one or more occupied voxels, a linked data structure with one or more nodes representing the one or more occupied voxels contained in the column.

16. The robot of claim 15, wherein the linked data structure comprises a linked list.

17. The robot of claim 15, wherein the linked data structure is a binary tree that is searchable by voxel elevation.

18. The robot of claim 15, wherein the nodes are linked in order of elevation.

19. The robot of claim 14, wherein the memory further comprises instructions that, when executed by the one or more processors, cause the one or more processors to:

identify one or more of the occupied voxels that satisfy a criterion;

project the one or more occupied voxels that satisfy the criterion onto a two-dimensional plane representing a surface navigable by the robot; and

calculate a path across the surface for the robot to navigate, wherein the path avoids obstacles represented by the projected one or more occupied voxels.

20. The robot of claim 14, wherein the memory further comprises instructions that, when executed by the one or more processors, cause the one or more processors to:

classify, as manipulable object voxels, one or more occupied voxels containing data points deemed to be associated with a manipulable object;

obtain, from the three-dimensional vision sensor, one or more up-to-date depth values associated with data points within the one or more manipulable object voxels; and

determine that the manipulable object has moved based at least in part on the one or more up-to-date depth values.

21. The robot of claim 14 wherein the memory further comprises instructions that, when executed by the one or more processors, cause the one or more processors to allocate memory from a heap portion of the memory to each occupied voxel, wherein unoccupied voxels are not allocated from the heap portion of the memory.

22. At least one non-transitory computer-readable medium comprising instructions that, in response to execution of the instructions by a robot, cause the robot to perform the following operations:

receiving, from a three-dimensional vision sensor of the robot, a group of data points sensed by the three-dimensional vision sensor;

identifying one or more voxels of a three-dimensional voxel model that are occupied by the group of data points;

determining, for each occupied voxel, data representing the occupied voxel, wherein the data includes statistics about how a plurality of data points of the group of data points are spatially distributed within the occupied voxel;

identifying, for each occupied voxel, a column of the three-dimensional voxel model that contains the occupied voxel; and

indexing, in memory, the data representing the occupied voxels contained in each column by elevation without indexing one or more unoccupied voxels by elevation.