Method, apparatus, and medium for building grid map in mobile robot and method, apparatus, and medium for cell decomposition that uses grid map

• US 8,060,254 B2
• Filed: 01/17/2007
• Issued: 11/15/2011
• Est. Priority Date: 06/20/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Myeong, Hyeon, Bang, Seok-won, Lee, Su-jinn, Kong, Dong-geon
• Primary Examiner(s): Black; Thomas
• Assistant Examiner(s): Nolan; Peter D
• Application Number:
  US11/654,015
• Publication Number:
  US 20070293985A1
• Time in Patent Office: 1,763 Days
• Field of Search: 700/245, 700/250, 700/253, 700/258, 701/23, 701/25, 701/26, 701/207, 901/1
• US Class Current: 700/253
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

Provided are a method, apparatus, and medium for building a grid map in a mobile robot and a method, apparatus, and medium for cell decomposition using the grid map building method and apparatus. A mobile robot for building a grid map includes a grid map building unit obtaining grid points by sensing a distance to an external space or obstacle, and building a grid map, a feature point extraction unit extracting feature points from the grid points, a feature point update unit estimating the pose of the robot after the robot moves, and obtaining updated feature points by SLAM (Simultaneous Localization And Map building) algorithm, a transform formula calculation unit calculating a transform formula that transforms feature points extracted by the feature point extraction unit into feature points updated by the feature point update unit, and a grid map update unit updating the grid map according to the obtained formula.

Claims

1. A method of building a grid map of a mobile robot, comprising:

obtaining grid points by sensing a distance to at least one of boundaries of an external space and an obstacle within the boundaries of the external space, and building the grid map;

extracting feature points from the grid points;

estimating pose of the robot after the robot moves, and updating the feature points using a SLAM (Simultaneous Localization And Map building) algorithm;

determining a transform which transforms the feature points extracted from the grid points into the updated feature points;

updating the grid map according to the transform;

extracting an angle of a sweep-line appearing most frequently in the updated grid map;

scanning the grid map according to the extracted sweep-line angle; and

decomposing the grid map into cells by the sweep-line at a position in which the sweep-line meets a feature point.

2. The method of claim 1, wherein the sensing of the distance is performed using a distance measuring sensor.

3. The method of claim 2, wherein the sensor is one of an ultrasound sensor, infrared ray sensor, or laser sensor.

4. The method of claim 1, wherein the extracting of the feature points is performed using a random sample consensus (RANSAC) algorithm or a split and merge algorithm.

5. The method of claim 1, wherein the SLAM (Simultaneous Localization And Map building) algorithm is based on a Kalman filter.

6. The method of claim 1, wherein the transform is determined using an Affine transform or a linear conformal transform method.

7. The method of claim 1, wherein in the extracting of the angle of the sweep-line, the angle of the sweep-line appearing most frequently in the updated grid map is extracted by using any one of a Hough transform, a Radon transform, and a histogram.

8. The method of claim 1, further comprising determining a direction of travel of the robot based on the extracted angle of the sweep-line appearing most frequently in the decomposed cells.

9. The method of claim 8, further comprising combining adjacent decomposed cells in which the robot has identical directions of travel into one cell.

18. At least one computer readable medium storing computer readable instructions to implement the method of claim 1.

10. A mobile robot for building a grid map, comprising:

a grid map builder to obtain grid points by sensing a distance to at least one of boundaries of an external space and an obstacle within the boundaries of the external space, and to build the grid map;

a feature point extractor to extract feature points from the grid points;

a feature point updater to estimate pose of the robot after the robot moves, and updating the feature points by using a SLAM (Simultaneous Localization And Map building) algorithm;

a transform determiner to determine a transform which transforms the feature points extracted by the feature point extractor into feature points updated by the feature point updater;

a grid map updater to update the grid map according to the transform;

a sweep-line angle extractor to extract an angle of a sweep-line appearing most frequently in the updated grid map; and

a cell decomposer to scan the grid map according to the extracted sweep-line angle and to decompose the grid map into cells by the sweep-line at a position in which the sweep-line meets a feature point.

11. The robot of claim 10, wherein the grid map builder obtains the grid points by sensing the distance using one of an ultrasound sensor, infrared ray sensor, or laser sensor.

12. The robot of claim 10, wherein the feature point extractor extracts feature points using a random sample consensus (RANSAC) algorithm or a split and merge algorithm.

13. The robot of claim 10, wherein the SLAM (Simultaneous Localization And Map building) algorithm is based on a Kalman filter.

14. The robot of claim 10, wherein the transform determiner determines the transform using an Affine transform or a linear conformal transform.

15. The robot of claim 10, wherein the sweep-line angle extractor extracts the angle of the sweep-line appearing most frequently in the updated grid map by using one of a Hough transform, a Radon transform, and a histogram.

16. The robot of claim 10, further comprising a direction of travel determiner to determine direction of travel of the robot based on the extracted angle of the sweep-line appearing most frequently in the decomposed cells.

17. The robot of claim 16, further comprising a cell combiner to combine adjacent cells, in which the robot has identical directions of travel among the decomposed cells, into one cell.

19. A method of building a grid map of a mobile robot, comprising:

building the grid map based on grid points obtained by sensing a distance from the robot to objects;

extracting feature points from the grid points;

estimating pose of the robot after robot movement, and updating the feature points using a SLAM (Simultaneous Localization And Map building) algorithm;

determining a transform which transforms the feature points extracted from the grid points into the updated feature points;

updating the grid map according to the transform;

extracting an angle of a sweep-line appearing most frequently in the updated grid map;

scanning the grid map according to the extracted sweep-line angle; and

decomposing the grid map into cells by the sweep-line at a position in which the sweep-line meets a feature point.

20. At least one computer readable medium storing computer readable instructions to implement the method of claim 19.

21. A mobile robot for building a grid map, comprising:

a grid map builder to build the grid map based on grid points obtained by sensing a distance from the robot to objects;

a feature point extractor to extract feature points from the grid points;

a feature point updater to estimate pose of the robot after the robot moves, and updating the feature points by using a SLAM (Simultaneous Localization And Map building) algorithm;

a transform determiner to determine a transform which transforms the feature points extracted by the feature point extractor into feature points updated by the feature point updater;

a grid map updater to update the grid map according to the transform;

a sweep-line angle extractor to extract an angle of a sweep-line appearing most frequently in the updated grid map; and

a cell decomposer to scan the grid map according to the extracted sweep-line angle and to decompose the grid map into cells by the sweep-line at a position in which the sweep-line meets a feature point.