Determining the orientation of flat reflectors during robot mapping

• US 10,852,740 B2
• Filed: 09/28/2018
• Issued: 12/01/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: Murphy, Elizabeth, Holz, Dirk
• Primary Examiner(s): Elchanti, Hussein
• Application Number:
  US16/147,082
• Publication Number:
  US 20200103917A1
• Time in Patent Office: 795 Days
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G05D 1/0236 in combination with a laser lasers per se H01S
• 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 determining a map of markers fixed in an environment, where the map of markers includes a location and an orientation of each marker. The method further includes determining locations of a set of detected markers relative to the map based on a location of a robotic device relative to the map and based on sensor data from the robotic device. The method also includes associating a detected marker from the set of detected markers with a mapped marker based on the determined location of the detected marker relative to the map and based on a visibility constraint related to the orientation of the mapped marker. The method additionally includes adjusting, in the map, the orientation of the mapped marker based on the determined location of the detected marker relative to the map.

Claims

1. A method comprising:

determining a map of markers fixed in an environment, wherein the map of markers includes a location and an orientation of each marker;

determining locations of a set of detected markers relative to the map based on a location of a robotic device relative to the map and based on sensor data from the robotic device;

associating a detected marker from the set of detected markers with a mapped marker based on the determined location of the detected marker relative to the map and based on a visibility constraint related to the orientation of the mapped marker;

adjusting, in the map, the orientation of the mapped marker based on the determined location of the detected marker relative to the map; and

controlling the robotic device based on the adjusted orientation of the mapped marker in the map of markers.

2. The method of claim 1, further comprising initially determining the orientation of the mapped marker based on a plurality of previously determined locations of detected markers associated with the mapped marker.

3. The method of claim 2, wherein determining the orientation of the mapped marker comprises fitting a confidence ellipse to the plurality of previously determined locations of detected markers associated with the mapped marker.

4. The method of claim 2, wherein determining the orientation of the mapped marker comprises:

determining a covariance matrix based on the plurality of previously determined locations of detected markers associated with the mapped marker; and

determining the orientation of the mapped marker based on an eigenvector of the covariance matrix.

5. The method of claim 4, further comprising determining a first and second eigenvalue of the covariance matrix, wherein determining the orientation of the mapped marker is based on the eigenvector associated with a smaller of the first and second eigenvalue.

6. The method of claim 4, wherein adjusting the orientation of the mapped marker based on the determined location of the detected marker relative to the map comprises adjusting the covariance matrix.

7. The method of claim 1, further comprising incrementally adjusting the orientation of the mapped marker after each scan of a sequence of scans by the robotic device.

8. The method of claim 1, further comprising adjusting, in the map, the location of the mapped marker based on the determined location of the detected marker relative to the map.

9. The method of claim 8, wherein adjusting the location of the mapped marker comprises determining a running mean of determined locations of detected markers associated with the mapped marker.

10. The method of claim 1, wherein associating the detected marker from the set of detected markers with the mapped marker comprises determining that the detected marker and the mapped marker are within a threshold distance of each other.

11. The method of claim 1, wherein each marker in the map is substantially flat, and wherein the orientation of each marker corresponds to a marker normal.

12. The method of claim 11, further comprising evaluating the visibility constraint for the mapped marker by determining whether an angle between a measurement ray and the marker normal of the mapped marker is less than a threshold angle.

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

14. The method of claim 12, wherein determining whether the angle between the measurement ray and the marker normal of the mapped marker is less than the threshold angle comprises evaluating a dot product of the measurement ray and the marker normal.

15. The method of claim 1, further comprising adjusting the location of the robotic device relative to the map based on associating the detected marker from the set of detected markers with the mapped marker.

16. 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.

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

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

determine a map of markers fixed in an environment, wherein the map of markers includes a location and an orientation of each marker;

determine locations of a set of detected markers relative to the map based on a location of a robotic device relative to the map and based on sensor data from the robotic device;

associate a detected marker from the set of detected markers with a mapped marker based on the determined location of the detected marker relative to the map and based on a visibility constraint related to the orientation of the mapped marker;

adjust, in the map, the orientation of the mapped marker based on the determined location of the detected marker relative to the map; and

control the robotic device based on the adjusted orientation of the mapped marker in the map of markers.

19. 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:

determining a map of markers fixed in an environment, wherein the map of markers includes a location and an orientation of each marker;

determining locations of a set of detected markers relative to the map based on a location of a robotic device relative to the map and based on sensor data from the robotic device;

associating a detected marker from the set of detected markers with a mapped marker based on the determined location of the detected marker relative to the map and based on a visibility constraint related to the orientation of the mapped marker;

adjusting, in the map, the orientation of the mapped marker based on the determined location of the detected marker relative to the map; and

controlling the robotic device based on the adjusted orientation of the mapped marker in the map of markers.