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

• US 20070293985A1
• Filed: 01/17/2007
• Published: 12/20/2007
• 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
• Granted Patent: US 8,060,254 B2
• Time in Patent Office: Days
• US Class Current: 700/245
• 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 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; and

updating the grid map according to the transform.

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

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

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

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

6. The method of claim 1, further comprising:

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.

7. The method of claim 6, 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 6, 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.

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

20. 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 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 feature points extracted by the feature point extractor into feature points updated by the feature point updater; and

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

11. The robot of claim 10, wherein the grid map builder obtains the grid points by sensing a 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, further comprising:

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.

16. The robot of claim 15, 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.

17. The robot of claim 15, 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.

18. The robot of claim 17, 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.

21. 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; and

updating the grid map according to the transform.

22. At least one computer readable medium storing computer readable instructions to implement the method of claim 21.

23. 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 feature points extracted by the feature point extractor into feature points updated by the feature point updater; and

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