Position recognition methods of autonomous mobile robots

• US 9,304,001 B2
• Filed: 02/24/2014
• Issued: 04/05/2016
• Est. Priority Date: 07/03/2013
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, Soon Yong, Roh, Kyung Shik
• Primary Examiner(s): Tarcza, Thomas
• Assistant Examiner(s): GOLDMAN, RICHARD A
• Application Number:
  US14/187,670
• Publication Number:
  US 20150012209A1
• Time in Patent Office: 771 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/0231 using optical position detecting means position-fixing by using electromagnetic waves other than radio waves, e.g. optical position detecting means G01S5/16
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

In some example embodiments, a position recognition method of an autonomous mobile robot may include: dividing a grid map into a plurality of spaces; extracting, by a processor, learning data of each of the plurality of spaces; generating, by the processor, space models of each of the plurality of spaces using the extracted learning data; and/or recognizing, by the processor, a current position of the autonomous mobile robot based on the extracted learning data, the space models, and actual range scan data input through the autonomous mobile robot.

Claims

1. A position recognition method of an autonomous mobile robot, the method comprising:

obtaining actual range scan data using a range scan sensor of the autonomous mobile robot;

dividing a grid map into a plurality of spaces;

extracting, by a processor, learning data descriptive of each of the plurality of spaces;

generating, by the processor, space models of each of the plurality of spaces using the extracted learning data; and

recognizing, by the processor, a current position of the autonomous mobile robot based on the extracted learning data, the space models, and the actual range scan data.

2. The position recognition method according to claim 1, wherein the dividing of the grid map into the plurality of spaces comprises:

extracting, by the processor, a generalized Voronoi graph (GVG) from the grid map;

extracting, by the processor, reference positions from the extracted GVG;

classifying, by the processor, neighboring reference positions among the extracted reference positions into same groups, and providing identical identification numbers to the extracted reference positions in the same groups, wherein each of the extracted reference positions in a same group can be identified by a unique position on the grid map and by an associated identical identification number; and

propagating, by the processor, the identical identification numbers as identification numbers provided to the extracted reference positions in the same groups to neighboring grid cells to which identification numbers are not provided, to divide the grid map into the plurality of spaces;

wherein the propagating of the identical identification numbers expands coverage of the grid map by a same group of the extracted reference positions with the associated identical identification number to include neighboring grid cells, of the same group of the extracted reference positions with the associated identical identification number, to which the identification numbers are not provided.

3. The position recognition method according to claim 2, wherein the extracting, by the processor, of the GVG is performed using a brushfire algorithm.

4. The position recognition method according to claim 2, wherein the extracted reference positions are points where three or more edges on the GVG intersect.

5. The position recognition method according to claim 2, wherein the classifying, by the processor, of the neighboring reference positions into the same groups is performed using a spectral clustering algorithm.

6. The position recognition method according to claim 1, wherein the extracting, by the processor, of the learning data descriptive of each of the plurality of spaces comprises:

extracting, by the processor, a plurality of sample positions from each of the plurality of spaces;

extracting, by the processor, virtual range scan data at each of the extracted plurality of sample positions; and

extracting, by the processor, virtual local shape context descriptors of the extracted virtual range scan data.

7. The position recognition method according to claim 6, wherein the extracting, by the processor, of the virtual range scan data at each of the extracted plurality of sample positions is performed by modeling a range scan sensor at the extracted plurality of sample positions and then applying a ray casting algorithm to the modeled range scan sensor.

8. The position recognition method according to claim 6, wherein the virtual range scan data comprises a plurality of scan points.

9. The position recognition method according to claim 8, wherein a number of the plurality of scan points is equal to a number of rays radiated from the modeled range scan sensor.

10. The position recognition method according to claim 8, wherein the extracting, by the processor, of the virtual local shape context descriptors comprises:

defining, by the processor, a local coordinate system of each of the plurality of scan points;

defining, by the processor, a circle having a radius of a designated length based on an origin of the defined local coordinate system; and

equally dividing, by the processor, the defined circle by a length in a radial direction and an angle in an angular direction.

11. The position recognition method according to claim 6, wherein the generating of the space models of each of the plurality of spaces comprises:

calculating, by the processor, virtual representative shape context descriptors using the extracted virtual local shape context descriptors;

calculating, by the processor, a virtual histogram of the virtual representative shape context descriptors; and

generating, by the processor, the space models of each of the plurality of spaces using the calculated virtual histogram.

12. The position recognition method according to claim 11, wherein the calculating, by the processor, of the virtual representative shape context descriptors comprises:

clustering, by the processor, the virtual local shape context descriptors into a plurality of clusters; and

calculating, by the processor, a mean of the virtual local shape context descriptors in each of the plurality of clusters.

13. The position recognition method according to claim 12, wherein the clustering, by the processor, of the virtual local shape context descriptors into the plurality of clusters is performed using a K-means clustering algorithm.

14. The position recognition method according to claim 11, wherein the calculating, by the processor, of the virtual histogram is performed by approximating the virtual local shape context descriptors to one of the calculated virtual representative shape context descriptors.

15. The position recognition method according to claim 14, wherein an x-axis of the virtual histogram represents identification numbers of the virtual representative shape context descriptors, and a y-axis of the virtual histogram represents a number of the virtual representative shape context descriptors for which the virtual local shape context descriptors are approximated.

16. The position recognition method according to claim 6, wherein the recognizing, by the processor, of the current position of the autonomous mobile robot comprises:

calculating, by the processor, actual local shape context descriptors of actual range scan data input through the autonomous mobile robot;

calculating, by the processor, an actual histogram of the calculated actual local shape context descriptors;

calculating, by the processor, classification scores of each of the plurality of spaces using the calculated actual histogram and the space models;

determining, by the processor, a space having a highest calculated classification score as a space where the autonomous mobile robot is located;

determining, by the processor, nearest virtual range scan data that is nearest to the actual range scan data among the virtual range scan data of the determined space;

determining, by the processor, matching points between the nearest virtual range scan data and the actual range scan data; and

calculating, by the processor, relative positions of the actual range scan data to the nearest virtual range scan data.

17. The position recognition method according to claim 16, wherein the determining, by the processor, of the matching points between the nearest virtual range scan data and the actual range scan data is performed by comparing the virtual local shape context descriptors of the nearest virtual range scan data and the actual local shape context descriptors of the actual range scan data with each other using a Hungarian method.

18. The position recognition method according to claim 16, wherein the calculating, by the processor, of the relative positions of the actual range scan data to the nearest virtual range scan data is performed using a random sample consensus (RANSAC) algorithm.

19. A position recognition method of an autonomous mobile robot, the method comprising:

inputting actual range scan data to a processor of the autonomous mobile robot;

dividing a grid map into a plurality of spaces;

extracting, by the processor, learning data descriptive of each of the plurality of spaces;

generating, by the processor, space models of each of the plurality of spaces using the extracted learning data; and

recognizing, by the processor, a current position of the autonomous mobile robot based on the extracted learning data, the space models, and the actual range scan data.

20. A position recognition method of an autonomous mobile robot, the method comprising:

dividing a grid map into a plurality of spaces;

extracting, by a processor of the autonomous mobile robot, learning data descriptive of each of the plurality of spaces;

generating, by the processor, space models of each of the plurality of spaces using the extracted learning data;

recognizing, by the processor, a current position of the autonomous mobile robot based on the extracted learning data, the space models, and actual range scan data input through the autonomous mobile robot; and

moving the autonomous mobile robot based on the recognized current position.