Associating semantic location data with automated environment mapping

• US 9,574,883 B2
• Filed: 03/24/2015
• Issued: 02/21/2017
• Est. Priority Date: 03/24/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Watts, Kevin William, Mason, Julian Mac Neille, Anderson-Sprecher, Peter Elving
• Primary Examiner(s): Werner, Brian P
• Application Number:
  US14/667,655
• Publication Number:
  US 20160282126A1
• Time in Patent Office: 700 Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G05B 19/41895 using automatic guided vehicles [AGV] control of position or course of AGV's G05D1/00
• CPC Class Codes: G05B 2219/31007 Floor plan, map stored in on-board computer of vehicle
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0297 by controlling means in a control room
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• 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: G09B 29/004 Map manufacture or repair; Tear or ink or water resistant maps; Long-life maps printing processes for maps B41M3/02; by permanently attaching map sections to sheets B42B7/00
• CPC Class Codes: G09B 29/007 using computer methods
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00
• CPC Class Codes: H03K 19/17768 for security
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/3278 using physically unclonable functions [PUF]
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y02P 90/60 Electric or hybrid propulsion means for production processes

Abstract

Systems and methods are provided for generating maps with semantic labels. A computing device can determine a first map that includes features located at first positions and semantic labels located at semantic positions, and determine a second map that includes at least some of the features located at second positions. The computing device can identify a first region with fixed features located at first positions and corresponding equivalent second positions. The computing device can identify a second region with moved features located at first positions and corresponding non-equivalent second positions. The computing device can determine one or more transformations between first positions and second positions. The computing device can assign the semantic labels to the second map at second semantic positions, where the second semantic positions are the same in the first region, and where the second semantic positions in the second region are based on the transformation(s).

Claims

1. A method, comprising:

determining a first map of an environment using a computing device, wherein the first map comprises a plurality of features located at a corresponding plurality of first positions and a plurality of semantic labels located at a corresponding plurality of semantic positions;

determining a second map of the environment using the computing device, wherein the second map comprises at least some of the plurality of features located at a corresponding plurality of second positions;

identifying a plurality of moved features using the computing device, wherein a moved feature in the plurality of moved features is located at a corresponding first position of the plurality of first positions and a different corresponding second position of the plurality of second positions, and wherein the corresponding first position of the moved feature is not equivalent to the different corresponding second position of the moved feature;

for each semantic label of the plurality of semantic labels, the computing device identifying a nearby subset of the plurality of moved features;

for each semantic label of the plurality of semantic labels, the computing device determining a transformation based on a coordinate mapping between the first positions and the second positions of the nearby subset of moved features identified for the semantic label;

for each semantic label of the plurality of semantic labels, the computing device assigning a semantic position in the second map to the semantic label using the transformation determined for the semantic label; and

generating an output of the computing device based on the second map.

2. The method of claim 1, wherein the computing device is part of a robotic device, wherein determining the first map comprises determining a first map based on first data obtained by one or more sensor devices of the robotic device, wherein determining the second map comprises determining the second map based on second data obtained by the one or more sensor devices of the robotic device, and wherein generating the output comprises navigating the robotic device through the environment based on guidance provided by at least one semantic label of the second map.

3. The method of claim 1, wherein determining the transformation based on the coordinate mapping comprises determining an affine transformation of an initial position to a transformed position.

4. The method of claim 3, wherein the affine transformation comprises at least one of:

a rotation related to the initial position, a translation related to the initial position, a reflection related to the initial position, and a combination of one or more rotations, translations, and reflections.

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

determining a current position of a particular feature of the plurality of features;

determining whether the current position of the particular feature is equivalent to a first position for the particular feature; and

after determining that the current position of the particular feature is not equivalent to a first position for the particular feature, determining the second map of the environment.

6. The method of claim 1, wherein a particular semantic label of the plurality of semantic labels is associated with a particular object and the particular semantic label corresponds to a particular semantic position of the plurality of semantic positions, and wherein determining the second map comprises:

determining a current position of the particular object;

determining whether the current position of the particular object is equivalent to the particular semantic position; and

after determining that the current position of the particular object is not equivalent to the particular semantic position, determining the second map of the environment.

7. The method of claim 1, wherein determining the second map comprises determining the second map at periodic intervals in time.

8. The method of claim 1, wherein the environment comprises at least a third region that differs from the first region, wherein the third region comprises one or more third features, and wherein the method further comprises:

determining one or more moved third features of the one or more third features, wherein each moved third feature of the one or more moved third features is located at a corresponding first position of the plurality of first positions and a different corresponding second position of the plurality of second positions, and where the corresponding first position of the moved feature is not equivalent to the different corresponding second position of the moved feature; and

determining one or more second transformations for the third region between first positions and second positions of the one or more moved third features, wherein semantic positions in the second plurality of semantic positions for semantic labels in the third region are based on the one or more second transformations for the third region.

21. The method of claim 1, wherein identifying the plurality of moved features comprises:

determining whether a feature is in the plurality of moved features based on comparing movement of the feature to a corresponding threshold for at least one map dimension of a plurality of map dimensions.

9. A computing device, comprising:

one or more processors; and

data storage including at least computer-executable instructions stored thereon that, when executed by the one or more processors, cause the computing device to perform functions comprising;

determining a first map of an environment, wherein the first map comprises a plurality of features located at a corresponding plurality of first positions and a plurality of semantic labels located at a corresponding plurality of semantic positions;

determining a second map of the environment, wherein the second map comprises at least some of the plurality of features located at a corresponding plurality of second positions;

identifying a plurality of moved features, wherein a moved feature in the plurality of moved features is located at a corresponding first position of the plurality of first positions and a different corresponding second position of the plurality of second positions, and wherein the corresponding first position of the moved feature is not equivalent to the different corresponding second position of the moved feature;

for each semantic label of the plurality of semantic labels, identifying a nearby subset of the plurality of moved features;

for each semantic label of the plurality of semantic labels, determining a transformation based on a coordinate mapping between the first positions and the second positions of the nearby subset of moved features identified for the semantic label;

for each semantic label of the plurality of semantic labels, assigning a semantic position in the second map to the semantic label using the transformation determined for the semantic label; and

generating an output based on the second map.

10. The computing device of claim 9, wherein the computing device is part of a robotic device, wherein determining the first map comprises determining a first map based on first data obtained by one or more sensor devices of the robotic device, wherein determining the second map comprises determining the second map based on second data obtained by the one or more sensor devices of the robotic device, and wherein generating the output comprises navigating the robotic device through the environment based on guidance provided by at least one semantic label of the second map.

11. The computing device of claim 9, wherein determining the transformation based on the coordinate mapping comprises determining an affine transformation of an initial position to a transformed position.

12. The computing device of claim 11, wherein the affine transformation comprises at least one of:

a rotation related to the initial position, a translation related to the initial position, a reflection related to the initial position, and a combination of one or more rotations, translations, and reflections.

13. The computing device of claim 9, wherein determining the second map comprises:

determining a current position of a particular feature of the plurality of features;

determining whether the current position of the particular feature is equivalent to a first position for the particular feature; and

after determining that the current position of the particular feature is not equivalent to a first position for the particular feature, determining the second map of the environment.

14. The computing device of claim 9, wherein a particular semantic label of the plurality of semantic labels is associated with a particular object and the particular semantic label corresponds to a particular semantic position of the plurality of semantic positions, and wherein determining the second map comprises:

determining a current position of the particular object;

determining whether the current position of the particular object is equivalent to the particular semantic position; and

after determining that the current position of the particular object is not equivalent to the particular semantic position, determining the second map of the environment.

15. The computing device of claim 9, wherein determining the second map comprises determining the second map at periodic intervals in time.

16. The computing device of claim 9, wherein the environment comprises at least a third region that differs from the first region, wherein the third region comprises one or more third features, and wherein the functions further comprise:

determining one or more moved third features of the one or more third features, wherein each moved third feature of the one or more moved third features is located at a corresponding first position of the plurality of first positions and a different corresponding second position of the plurality of second positions; and

determining one or more second transformations for the third region between first positions and second positions of the one or more moved third features, wherein semantic positions in the second plurality of semantic positions for semantic labels in the third region are based on the one or more second transformations for the third region.

17. A non-transitory computer readable medium having stored thereon instructions, that when executed by one or more processors of a computing device, cause the computing device to perform functions comprising:

determining a first map of an environment, wherein the first map comprises a plurality of features located at a corresponding plurality of first positions and a plurality of semantic labels located at a corresponding plurality of semantic positions;

determining a second map of the environment, wherein the second map comprises at least some of the plurality of features located at a corresponding plurality of second positions;

identifying a plurality of moved features, wherein a moved feature in the plurality of moved features is located at a corresponding first position of the plurality of first positions and a different corresponding second position of the plurality of second positions, and wherein the corresponding first position of the moved feature is not equivalent to the different corresponding second position of the moved feature;

for each semantic label of the plurality of semantic labels, identifying a nearby subset of the plurality of moved features;

for each semantic label of the plurality of semantic labels, determining a transformation based on a coordinate mapping between the first positions and the second positions of the nearby subset of moved features identified for the semantic label;

for each semantic label of the plurality of semantic labels, assigning a semantic position in the second map to the semantic label using the transformation determined for the semantic label; and

generating an output based on the second map.

18. The non-transitory computer readable medium of claim 17, wherein the non-transitory computer readable medium is part of a robotic device, wherein determining the first map comprises determining a first map based on first data obtained by one or more sensor devices of the robotic device, wherein determining the second map comprises determining the second map based on second data obtained by the one or more sensor devices of the robotic device, and wherein generating the output comprises navigating the robotic device through the environment based on guidance provided by at least one semantic label of the second map.

19. The non-transitory computer readable medium of claim 17, wherein determining the transformation based on the coordinate mapping comprises determining an affine transformation of an initial position to a transformed position, and wherein the affine transformation comprises at least one of:

a rotation related to the initial position, a translation related to the initial position, a reflection related to the initial position, and a combination of one or more rotations, translations, and reflections.

20. The non-transitory computer readable medium of claim 17, wherein determining the second map comprises:

determining a current position of a particular feature of the plurality of features;

determining whether the current position of the particular feature is equivalent to a first position for the particular feature; and

after determining that the current position of the particular feature is not equivalent to a first position for the particular feature, determining the second map of the environment.