Apparatus and method for building map

• US 8,306,738 B2
• Filed: 03/10/2009
• Issued: 11/06/2012
• Est. Priority Date: 09/16/2008
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kong, Dong-Geon, Lee, Hyoung-Ki
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): MOYER, DALE S
• Application Number:
  US12/382,187
• Publication Number:
  US 20100070078A1
• Time in Patent Office: 1,337 Days
• Field of Search: 700245-264, 701300-541, 901/1, 901/47
• US Class Current: 701/411
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/027 comprising intertial navigation means, e.g. azimuth detector inertial navigation G01C21/16; inertial navigation combined with non-inertial navigation instruments G01C21/165
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06V 10/62 relating to a temporal dimension, e.g. time-based feature extraction; Pattern tracking
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

An apparatus and method for building a map are provided. According to the apparatus and method, a path is generated on the basis of the degrees of uncertainty of features extracted from an image obtained while a mobile robot explores unknown surroundings, and the mobile robot travels along the generated path. The path based on the degrees of uncertainty of the features is generated and this may increase the accuracy of a feature map of the mobile robot or accuracy in self localization.

Claims

1. An apparatus for building a map, the apparatus comprising:

an obstacle map builder to build an obstacle map on the basis of obtained obstacle detection information;

a controller to build a feature map including a plurality of features, position information of the features, and information regarding degrees of uncertainty of the features on the basis of an amount of change in posture and an image obtained while a mobile robot moves, and localizing the mobile robot itself;

a path generator to generate a moving path on the basis of the degrees of uncertainty of the features obtained by the mobile robot, wherein the path generator selectively generates the moving path from among a plurality of moving paths including an exploration path for reducing the degrees of uncertainty of the features and a self-localization enhancement path for reducing a degree of uncertainty of a position of the mobile robot, wherein the exploration path and the self-localization enhancement path are generated on the basis of the degrees of uncertainty of the features; and

a drive controller to control the mobile robot to travel along the generated moving path,

wherein the feature map and the obstacle map are updated on the basis of the amount of change in posture, the image, and the obstacle detection information obtained while the mobile robot travels along the generated moving path.

2. The apparatus of claim 1, wherein a destination is a point between an unknown region and an empty region having no obstacles in the obstacle map being built.

3. The apparatus of claim 1, wherein when there are a plurality of features having a degree of uncertainty of a first threshold value or more among the features, the path generator divides a space in which the features having a degree of uncertainty of the first threshold value or more exist into two or more spaces and generates the exploration path including average positions of the features existing in the respective divided spaces as intermediate path points and extending from a current position to the destination.

4. The apparatus of claim 1, wherein when a Kalman filter is used to estimate positions of the features, the controller calculates the degrees of uncertainty of the features using an error covariance matrix.

5. The apparatus of claim 1, wherein the controller extracts features from an image obtained while the mobile robot travels along the exploration path, searches the feature map for features matching the extracted features, and updates position information of the searched features.

6. The apparatus of claim 1, wherein when a degree of uncertainty of a position of the mobile robot is a second threshold value or more while the mobile robot travels along the exploration path, the path generator stops the exploration path travel, generates the self-localization enhancement path for reducing a degree of uncertainty of a position of the mobile robot, controls the drive controller such that the mobile robot travels along the self-localization enhancement path, and controls the drive controller such that the mobile robot resumes the stopped exploration path travel when the mobile robot travels along the self-localization enhancement path and a degree of uncertainty of a position of the mobile robot decreases.

7. The apparatus of claim 1, wherein when it is determined that a degree of uncertainty of a current position of the mobile robot is a second threshold value or more, the path generator searches for features having a smaller degree of uncertainty than a third threshold value and generates a closed path, as the self-localization enhancement path, including positions of the searched features as intermediate path points and having the current position as a destination.

8. The apparatus of claim 7, wherein when a Kalman filter is used to estimate the current position of the mobile robot, the controller calculates the degree of uncertainty of the current position using a covariance of the estimated current position.

9. The apparatus of claim 7, wherein when a particle filter is used to estimate the current position of the mobile robot, the controller calculates variances of particles, which are samples indicating virtual positions of the mobile robot, with respect to an average position of the particles and calculates the degree of uncertainty of the current position of the mobile robot on the basis of the calculated variances.

10. The apparatus of claim 7, wherein the controller updates the current position using position information obtained while the mobile robot travels along the closed path.

11. An apparatus for building a map, the apparatus comprising:

an obstacle map builder to build an obstacle map on the basis of obtained obstacle detection information;

a controller to build a feature map including a plurality of features, position information of the features, and information regarding degrees of uncertainty of the features on the basis of an amount of change in posture of a mobile robot and an image obtained while the mobile robot moves, and localizing the mobile robot itself;

a path generator to generate a moving path on the basis of the degrees of uncertainty of the features obtained by the mobile robot for reducing the degree of uncertainty of the features by searching for features having a degree of uncertainty that meets or exceeds a first threshold value among the features, and to generate the moving path to include positions of the searched features as intermediate path points, the generated moving path extending from a current position to a destination; and

a drive controller to control the mobile robot to travel along the generated moving path,

wherein the feature map and the obstacle map are updated on the basis of the amount of change in posture, the image and the obstacle detection information obtained while the mobile robot travels along the generated moving path.

12. A method of building a map, the method comprising:

building an obstacle map of a mobile robot on the basis of obtained obstacle detection information;

building a feature map including a plurality of features, position information of the features, and information regarding degrees of uncertainty of the features on the basis of an amount of change in posture and an image obtained while the mobile robot moves;

generating a moving path on the basis of the degrees of uncertainty of the features obtained by the mobile robot, wherein the generating of the moving path comprises selectively generating the moving path from among a plurality of moving paths including an exploration path for reducing the degrees of uncertainty of the features and a self-localization enhancement path for reducing a degree of uncertainty of a position of the mobile robot, wherein the exploration path and the self-localization enhancement path are generated on the basis of the degrees of uncertainty of the features; and

traveling along the generated moving path,

wherein the feature map and the obstacle map are updated on the basis of the amount of change in posture, the image, and the obstacle detection information obtained while the mobile robot travels along the generated moving path.

13. The method of claim 12, wherein the generating of the exploration path includes:

searching for features having a degree of uncertainty of a first threshold value or more among the features; and

generating the exploration path including positions of the searched features as intermediate path points and extending from a current position to a destination.

14. The method of claim 13, wherein the destination is a point between an unknown region and an empty region having no obstacles in the obstacle map being built.

15. The method of claim 12, wherein when a Kalman filter is used to estimate positions of the features, the degrees of uncertainty of the features are calculated using an error covariance matrix.

16. The method of claim 12, wherein the generating of the self-localization enhancement path includes:

determining whether or not a degree of uncertainty of a current position of the mobile robot is a second threshold value or more;

when it is determined that the degree of uncertainty of the current position is the second threshold value or more, searching for features having a smaller degree of uncertainty than a third threshold value; and

generating a closed path, as the self-localization enhancement path, including positions of the searched features as intermediate path points and having the current position as a destination.

17. The method of claim 16, further comprising:

traveling along the closed path,

wherein the current position is updated using position information obtained while the mobile robot travels along the closed path.

18. The method of claim 12, further comprising:

when a degree of uncertainty of a position of the mobile robot is a second threshold value or more while the mobile robot travels along the exploration path, stopping the exploration path travel;

traveling along the self-localization enhancement path and reducing a degree of uncertainty of a position of the mobile robot; and

resuming the stopped exploration path travel.

19. An apparatus for building a map, the apparatus comprising:

an obstacle map builder to build an obstacle map on the basis of obtained obstacle detection information;

a controller to build a feature map including a plurality of features, position information of the features, and information regarding degrees of uncertainty of the features on the basis of an amount of change in posture of a mobile robot and an image obtained while the mobile robot moves, and localizing the mobile robot itself;

a path generator to generate a self-localization enhancement path for reducing a degree of uncertainty of a position of the mobile robot, wherein when the degree of uncertainty of the position of the mobile robot meets or exceeds a first threshold value while the mobile robot travels along a path, the path generator stops the travel along the path, generates the self-localization enhancement path for reducing the degree of uncertainty of a position of the mobile robot, controls the drive controller such that the mobile robot travels along the self-localization enhancement path, and controls the drive controller such that the mobile robot resumes the stopped path travel when the mobile robot travels along the self-localization enhancement path and the degree of uncertainty of the position of the mobile robot has decreased; and

a drive controller to control the mobile robot to travel along the generated moving path,

wherein the feature map and the obstacle map are updated on the basis of the amount of change in posture, the image, and the obstacle detection information obtained while the mobile robot travels.