Robot localization with co-located markers

• US 10,824,160 B2
• Filed: 10/03/2018
• Issued: 11/03/2020
• Est. Priority Date: 09/28/2018
• Status: Active Grant

• Current Assignee: Intrinsic Innovation LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Holz, Dirk, Murphy, Elizabeth
• Primary Examiner(s): Nguyen, Tan Q
• Application Number:
  US16/150,482
• Publication Number:
  US 20200103914A1
• Time in Patent Office: 762 Days
• Field of Search: 701 23
• CPC Class Codes: G01C 21/3602 Input other than that of destination using image analysis, e.g. detection of road signs, lanes, buildings, real preceding vehicles using a camera
• CPC Class Codes: G01C 21/383 Indoor data
• 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: G01C 21/3881 Tile-based structures
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0234 using optical markers or beacons optical beacons per se G01S1/70
• CPC Class Codes: G05D 1/0244 using reflecting strips
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

One method disclosed includes identifying, in a map of markers fixed in an environment, two co-located markers within a threshold distance of each other, where each of the two co-located markers has a non-overlapping visibility region. The method further includes determining a set of detected markers based on sensor data from a robotic device. The method additionally includes identifying, from the set of detected markers, a detected marker proximate to a first marker of the two co-located markers. The method also includes enforcing a visibility constraint based on the non-overlapping visibility region of each of the two co-located markers to determine an association between the detected marker and a second marker of the two co-located markers. The method further includes determining a location of the robotic device in the environment relative to the map based on the determined association.

Claims

1. A method comprising:

identifying, in a map of markers fixed in an environment, two co-located markers within a threshold distance of each other, wherein each of the two co-located markers has a non-overlapping visibility region;

determining a set of detected markers based on sensor data from a robotic device;

identifying, from the set of detected markers, a detected marker proximate to a first marker of the two co-located markers;

determining visibility of each of the two co-located markers from a current position of the robotic device based on the non-overlapping visibility region of each of the two co-located markers;

determining an association between the detected marker and a second marker of the two co-located markers based on the determined visibility of each of the two co-located markers, wherein the determined association indicates that the detected marker represents the second marker in the map; and

determining a location of the robotic device in the environment relative to the map based on the determined association and one or more other associations between one or more other detected markers in the set and one or more other markers in the map.

2. The method of claim 1, wherein each marker in the map is substantially flat, and wherein each marker has a respective visibility cone.

3. The method of claim 2, wherein determining visibility of a given marker of the co-located markers comprises determining whether an angle between a measurement ray and a marker normal is consistent with the respective visibility cone for the given marker.

4. The method of claim 3, wherein the measurement ray comprises a ray between a mapped position of the given marker and a current sensor position of a sensor on the robotic device.

5. The method of claim 3, wherein determining whether the angle between the measurement ray and the marker normal is consistent with the respective visibility cone for the given marker comprises evaluating a dot product of the measurement ray and the marker normal.

6. The method of claim 1, wherein identifying the detected marker proximate to the first marker comprises conducting a nearest neighbor search of the map for a nearest neighbor marker to the detected marker.

7. The method of claim 6, wherein the nearest neighbor search comprises a grid search, and wherein the grid search returns a grid cell that includes each of the two co-located markers.

8. The method of claim 1, wherein the second marker is one of a plurality of markers co-located with the first marker, and wherein the method further comprises:

determining the association between the detected marker and the second marker by searching the plurality of markers for a closest marker to the detected marker, wherein the closest marker is determined to be visible.

9. The method of claim 1, wherein determining the location of the robotic device comprises using the association for an iterative closest point localization algorithm which yields a transformation that relates detected markers in a sensor scan to the map of markers.

10. The method of claim 9, wherein for the iterative closest point localization algorithm, a visibility constraint is not enforced for mapped markers which do not have any co-located markers within the threshold distance.

11. The method of claim 1, wherein the threshold distance is based on a resolution of a sensor on the robotic device used to generate the sensor data.

12. The method of claim 1, further comprising storing an indication that the first marker and the second marker comprise a pair of co-located markers in a lookup table, wherein the lookup table is referenced when determining the association between the second marker and the detected marker.

13. The method of claim 1, wherein each of the markers in the map is a retro-reflective marker, and wherein the sensor data is generated using a laser-based sensor on the robotic device.

14. The method of claim 1, wherein each of the markers is fixed at substantially a same height within the environment.

15. The method of claim 1, further comprising controlling the robotic device based on the determined location of the robotic device.

16. The method of claim 1, wherein the robotic device is a mobile robotic device, the method further comprising navigating the robotic device in the environment based on the determined location of the robotic device.

17. The method of claim 1, wherein the first marker and the second marker are fixed in the environment such that the first marker and the second marker are oriented substantially opposite each other.

18. The method of claim 1, wherein the first marker and the second marker are fixed in the environment such that the first marker and the second marker are oriented at substantially a right angle to each other.

19. A robotic device comprising a control system configured to:

identify, in a map of markers fixed in an environment, two co-located markers within a threshold distance of each other, wherein each of the two co-located markers has a non-overlapping visibility region;

determine a set of detected markers based on sensor data from a robotic device;

identify, from the set of detected markers, a detected marker proximate to a first marker of the two co-located markers;

determining visibility of each of the two co-located markers from a current position of the robotic device based on the non-overlapping visibility region of each of the two co-located markers;

determining an association between the detected marker and a second marker of the two co-located markers based on the determined visibility of each of the two co-located markers, wherein the determined association indicates that the detected marker represents the second marker in the map; and

determining a location of the robotic device in the environment relative to the map based on the determined association and one or more other associations between one or more other detected markers in the set and one or more other markers in the map.

20. A non-transitory computer readable medium comprising program instructions executable by at least one processor to cause the at least one processor to perform functions comprising:

identifying, in a map of markers fixed in an environment, two co-located markers within a threshold distance of each other, wherein each of the two co-located markers has a non-overlapping visibility region;

determining a set of detected markers based on sensor data from a robotic device;

identifying, from the set of detected markers, a detected marker proximate to a first marker of the two co-located markers;

determining visibility of each of the two co-located markers from a current position of the robotic device based on the non-overlapping visibility region of each of the two co-located markers;

determining an association between the detected marker and a second marker of the two co-located markers based on the determined visibility of each of the two co-located markers, wherein the determined association indicates that the detected marker represents the second marker in the map; and

determining a location of the robotic device in the environment relative to the map based on the determined association and one or more other associations between one or more other detected markers in the set and one or more other markers in the map.