Method, medium, and system estimating pose of mobile robots

• US 8,543,241 B2
• Filed: 09/10/2007
• Issued: 09/24/2013
• Est. Priority Date: 09/13/2006
• Status: Active Grant

• Current Assignee: Harbin Institute of Technology, Samsung Electronics Co. Ltd.
• Original Assignee: Harbin Institute of Technology, Samsung Electronics Co. Ltd.
• Inventors: Hong, Bing rong, Luo, Rong hua, Li, Mao hai, Bang, Seok-won, Kim, Yeon-ho, Myeong, Hyeon
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Nolan, Peter D
• Application Number:
  US11/898,207
• Publication Number:
  US 20080065267A1
• Time in Patent Office: 2,206 Days
• Field of Search: 700/245, 700/246, 700/258, 700/259, 701/23, 701/28, 701/207, 701/217, 901/1, 318/568.11, 318/568.12
• US Class Current: 700/259
• CPC Class Codes: B25J 13/087 for sensing other physical parameters, e.g. electrical or chemical properties
• CPC Class Codes: B25J 13/089 Determining the position of the robot with reference to its environment
• CPC Class Codes: B25J 9/0003 Home robots, i.e. small robots for domestic use
• 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

A method, medium, and system reducing the computational complexity of a Simultaneous Localization And Mapping (SLAM) algorithm that can be applied to mobile robots. A system estimating the pose of a mobile robot with the aid of a particle filter using a plurality of particles includes a sensor which detects a variation in the pose of a mobile robot, a particle filter unit which determines the poses and weights of current particles by applying the detected pose variation to previous particles, and an evolution unit which updates the poses and weights of the current particles by applying an evolution algorithm to the poses and weights of the current particles.

Claims

1. A movement system, the system comprising:

a particle filter unit to determine poses and weights of current particles by applying a detected pose variation to previously identified particles, with the detected pose variation being detected by a sensor to detect a pose variation in a pose of a mobile element;

an evolution unit to update the determined poses and weights of the current particles by applying an evolution algorithm to the determined poses and weights of the current particles to estimate a current pose of the mobile element;

a camera to capture an image of an outside of the mobile element; and

a feature point processing unit to extract a least one feature point from the captured image and to create a map by processing the extracted feature point and the determined poses, with the processing of the extracted feature point including determining whether one of plural currently calculated gray gradient vectors for a current feature point match a previously calculated gray gradient vector for a previously extracted feature point,

wherein the extracted feature point is scale-invariant and rotation-invariant from the captured image.

2. The system of claim 1, further comprising the sensor to detect the pose variation in the pose of the mobile element.

3. The system of claim 2, wherein the sensor comprises at least one of an encoder and a gyroscope.

4. The system of claim 1, wherein each of the poses of the current particles comprises a pair of coordinates on a two-dimensional (2D) coordinate system and azimuth information.

5. The system of claim 1, wherein the system and the mobile element make up a mobile robot, and the system further comprises a traveling module having a moving mechanism to move the mobile robot based upon the estimated current pose of the mobile robot.

6. The system of claim 1, wherein the particle filter unit comprises:

a pose estimator to perform the determining of the poses of the current particles by the applying of the detected pose variation to the previously identified particles; and

a weight calculator to compare an observed pose obtained using the extracted feature point with the determined poses of the current particles and apply a determined high weight value to a current particle that produces a pose determined to be similar to the observed pose.

7. The system of claim 6, wherein the particle filter unit further comprises a sampler to perform sampling on a plurality of available particles according to an initial pose of the mobile element and perform resampling on the sampled plurality of available particles according to corresponding updated weights.

8. The system of claim 1, wherein the evolution unit comprises a crossover applicator to select two or more parent samples from among a plurality of evolution samples, calculate a weighted sum of the selected parent samples, and select one or more samples from among the selected parent samples and one or more child samples generated based on the weighted sum of the selected parent samples, with the evolution samples being obtained from one of a plurality of available particles through random sampling.

9. The system of claim 8, wherein the evolution unit selects one or more samples having determined high weight values from among the selected parent samples and the child samples.

10. The system of claim 1, wherein the evolution unit comprises a mutation applicator to select a parent sample from among a plurality of evolution samples, generate a child sample by applying random noise to the selected parent sample, and select one of the selected parent sample and the child sample that has a higher weight value, with the evolution samples being obtained from one of a plurality of available particles through random sampling.

11. The system of claim 10, wherein the random noise follows a Gaussian distribution.

12. The system of claim 10, wherein the selected parent sample is an evolution sample whose weight value exceeds a predefined threshold.

13. The system of claim 1, wherein the detected pose variation is a pose estimation, as a probability distribution, of the mobile element based on measured movement, by the sensor, of the mobile robot.

14. The system of claim 13, wherein the probability distribution is based at least on a conditional probability p(xt|xt−

1, ut−

1), where xt−

1 indicates a pose at a time (t−

1), ut−

1 indicates data measured by the sensor, and xt indicates a pose at a current time t.

15. The system of claim 14, wherein the determined pose of each current particle is represented by a respective xt pose and the determined weight of each current particle is represented by a respective wt weight, with the respective wt indicating a probability of an actual pose of the mobile element coinciding with the respective xt pose.

16. The system of claim 15, further comprising a feature point matcher to match the extracted feature points with stored feature points,

wherein the determining of the poses and weights by the particle filter includes updating the determined weights after feature point matching by the feature point matcher.

17. A movement system, the system comprising:

a particle filter unit to determine poses and weights of current particles by applying a detected pose variation to previously identified particles, with the detected pose variation being detected by a sensor to detect a pose variation in a pose of a mobile element;

an evolution unit to update the determined poses and weights of the current particles by applying an evolution algorithm to the determined poses and weights of the current particles to estimate a current pose of the mobile element;

a camera to capture an image of an outside of the mobile element; and

a feature point processing unit to extract a least one feature point from the captured image and to create a map by processing the extracted feature point and the determined poses,

wherein the extracted feature point is scale-invariant and rotation-invariant from the captured image,

wherein the evolution unit comprises a mutation applicator to select a parent sample from among a plurality of evolution samples, generate a child sample by applying random noise to the selected parent sample, and select one of the selected parent sample and the child sample that has a higher weight value, with the evolution samples being obtained from one of a plurality of available particles through random sampling, and

wherein the selected parent sample is an evolution sample whose weight value exceeds a predefined threshold.

18. A mobile movement controlling method, the method comprising:

determining poses and weights of current particles by applying a detected pose variation to previously identified particles, with the detected pose variation being a pose variation in a pose of a mobile element;

updating and outputting the determined poses and weights of the current particles by applying an evolution algorithm to the determined poses and weights of the current particles to estimate a current pose of the mobile element;

capturing an outside image of the mobile element; and

extracting at least one feature point from the captured image for obtaining an observed pose and creating a map by processing the extracted feature point and the determined poses, with the processing of the extracted feature point including determining whether one of plural currently calculated gray gradient vectors for a current feature point match a previously calculated gray gradient vector for a previously extracted feature point,

wherein the extracted feature point is scale-invariant and rotation-invariant from the captured image.

19. The method of claim 18, further comprising detecting the pose variation in the pose of the mobile element.

20. The method of claim 19, wherein the detecting of the pose variation comprises using at least one of an encoder and a gyroscope.

21. The method of claim 18, wherein each of the poses of the current particles comprises a pair of coordinates on a two-dimensional (2D) coordinate system and azimuth information.

22. The method of claim 18, wherein the determining of the poses and weights further comprises:

performing the determining of the poses of the current particles by applying the detected pose variation to the previously identified particles; and

comparing an observed pose obtained using the extracted feature point with the determined poses of the current particles and applying a determined high weight value to a current particle that produces a pose determined to be similar to the observed pose.

23. The method of claim 22, wherein the determining further comprises:

performing sampling on a plurality of available particles according to an initial pose of the mobile element; and

performing resampling on the sampled plurality of available particles according to corresponding updated weights.

24. The method of claim 18, wherein the updating comprises:

selecting two or more parent samples from among a plurality of evolution samples that are obtained from one of a plurality of available particles through random sampling;

calculating a weighted sum of the selected parent samples; and

selecting one or more samples from among the selected parent samples and one or more child samples that are generated based on the weighted sum of the selected parent samples.

25. The method of claim 24, wherein the selecting of the one or more samples from among the selected parent samples and the one or more child samples comprises selecting one or more samples having determined high weight values from among the selected parent samples and the child samples.

26. The method of claim 18, wherein the updating comprises:

selecting a parent sample from among a plurality of evolution samples that are obtained from one of a plurality of available particles through random sampling;

generating a child sample by applying random noise to the selected parent sample; and

selecting one of the selected parent sample and the child sample that has a higher weight value.

27. The method of claim 26, wherein the random noise follows a Gaussian distribution.

28. The method of claim 26, wherein the selected parent sample is an evolution sample whose weight value exceeds a predefined threshold.

29. The method of claim 18, wherein the detected pose variation is a pose estimation, as a probability distribution, of the mobile element based on measured movement, by a sensor, of the mobile robot.

30. The method of claim 29, wherein the probability distribution is based at least on a conditional probability p(xt|xt−

1, ut−

1), where xt−

1 indicates a pose at a time (t−

1), ut−

1 indicates data measured by sensor, and xt indicates a pose at a current time t.

31. The method of claim 30, wherein the determined pose of each current particle is represented by a respective xt pose and the determined weight of each current particle is represented by a respective wt weight, with the respective wt indicating a probability of an actual pose of the mobile element coinciding with the respective xt pose.

32. The method of claim 31, further comprising matching the extracted feature points with stored feature points, wherein the determining of the poses and weights further comprises updating the determined weights after the matching.

34. At least one non-transitory medium comprising computer readable code to control at least one processing element to implement the method of claim 18.

33. A mobile movement controlling method, the method comprising:

determining poses and weights of current particles by applying a detected pose variation to previously identified particles, with the detected pose variation being a pose variation in a pose of a mobile element;

updating and outputting the determined poses and weights of the current particles by applying an evolution algorithm to the determined poses and weights of the current particles to estimate a current pose of the mobile element;

capturing an outside image of the mobile element; and

extracting at least one feature point from the captured image for obtaining an observed pose and creating a map by processing the extracted feature point and the determined poses,

wherein the extracted feature point is scale-invariant and rotation-invariant from the captured image,

wherein the updating comprises;

selecting a parent sample from among a plurality of evolution samples that are obtained from one of a plurality of available particles through random sampling;

generating a child sample by applying random noise to the selected parent sample; and

selecting one of the selected parent sample and the child sample that has a higher weight value, and

wherein the selected parent sample is an evolution sample whose weight value exceeds a predefined threshold.

35. A movement system, the system comprising:

a particle filter unit to determine poses and weights of current particles by applying a detected pose variation to previously identified particles, with the detected pose variation being detected by a sensor to detect a pose variation in a pose of a mobile element;

an evolution unit to update the determined poses and weights of the current particles by applying an evolution algorithm to the determined poses and weights of the current particles to estimate a current pose of the mobile element;

a camera to capture an image of an outside of the mobile element; and

a feature point processing unit to extract a least one feature point from the captured image and to create a map by processing the extracted feature point and the determined poses,

wherein the extracted feature point is scale-invariant and rotation-invariant from the captured image,

wherein the detected pose variation is a pose estimation, as a probability distribution, of the mobile element based on measured movement, by the sensor, of the mobile robot, and

wherein the probability distribution is based at least on a conditional probability p(xt|xt−

1, ut−

1), where xt−

1 indicates a pose at a time (t−

1), ut−

1 indicates data measured by the sensor, and xt indicates a pose at a current time t.

36. The system of claim 35, wherein the determined pose of each current particle is represented by a respective xt pose and the determined weight of each current particle is represented by a respective wt weight, with the respective wt indicating a probability of an actual pose of the mobile element coinciding with the respective xt pose.

37. The system of claim 36, further comprising a feature point matcher to match the extracted feature points with stored feature points,

wherein the determining of the poses and weights by the particle filter includes updating the determined weights after feature point matching by the feature point matcher.

38. A mobile movement controlling method, the method comprising:

determining poses and weights of current particles by applying a detected pose variation to previously identified particles, with the detected pose variation being a pose variation in a pose of a mobile element;

updating and outputting the determined poses and weights of the current particles by applying an evolution algorithm to the determined poses and weights of the current particles to estimate a current pose of the mobile element;

capturing an outside image of the mobile element; and

extracting at least one feature point from the captured image for obtaining an observed pose and creating a map by processing the extracted feature point and the determined poses,

wherein the extracted feature point is scale-invariant and rotation-invariant from the captured image,

wherein the detected pose variation is a pose estimation, as a probability distribution, of the mobile element based on measured movement, by a sensor, of the mobile robot, and

wherein the probability distribution is based at least on a conditional probability p(xt|xt−

1, ut−

1), where xt−

1 indicates a pose at a time (t−

1), ut−

1 indicates data measured by sensor, and xt indicates a pose at a current time t.

39. The method of claim 38, wherein the determined pose of each current particle is represented by a respective xt pose and the determined weight of each current particle is represented by a respective wt weight, with the respective wt indicating a probability of an actual pose of the mobile element coinciding with the respective xt pose.

40. The method of claim 39, further comprising matching the extracted feature points with stored feature points,

wherein the determining of the poses and weights further comprises updating the determined weights after the matching.