# US 8,543,241 B2 · Method, medium, and system estimating pose of mobile robots

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,543,241 B2
- Document ID: US8543241B2
- Status: Granted
- Kind: B2
- Application number: 11/898,207
- Filed: 2007-09-10
- Published: 2008-03-13
- Granted: 2013-09-24
- Earliest claimed: 2006-09-13
- Assignees: Samsung Electronics Co., Ltd.; Harbin Institute of Technology
- Applicants: Bing rong Hong; Rong hua Luo; Mao hai Li; Seok-won Bang; Yeon-ho Kim; Hyeon Myeong
- Inventors: Bing rong Hong; Rong hua Luo; Mao hai Li; Seok-won Bang; Yeon-ho Kim; Hyeon Myeong
- Web page: https://patentgrep.com/patent/US8543241B2

## CPC

- G05D 1/0246: {using a video camera in combination with image processing means}
- B25J 9/0003: {Home robots, i.e. small robots for domestic use}
- B25J 13/087: {for sensing other physical parameters, e.g. electrical or chemical properties}
- B25J 13/089: {Determining the position of the robot with reference to its environment}
- G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)}
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50})

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 10)

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

### Claim 12 (depends on 10)

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

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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.

### Claim 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.

### Claim 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.

### Claim 19 (depends on 18)

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

### Claim 20 (depends on 19)

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

### Claim 21 (depends on 18)

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.

### Claim 22 (depends on 18)

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.

### Claim 23 (depends on 22)

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.

### Claim 24 (depends on 18)

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.

### Claim 25 (depends on 24)

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.

### Claim 26 (depends on 18)

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.

### Claim 27 (depends on 26)

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

### Claim 28 (depends on 26)

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

### Claim 29 (depends on 18)

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.

### Claim 30 (depends on 29)

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.

### Claim 31 (depends on 30)

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.

### Claim 32 (depends on 31)

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.

### Claim 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.

### Claim 34 (depends on 18)

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

### Claim 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.

### Claim 36 (depends on 35)

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.

### Claim 37 (depends on 36)

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.

### Claim 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.

### Claim 39 (depends on 38)

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.

### Claim 40 (depends on 39)

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.