Method used by robot for simultaneous localization and map-building

• US 7,957,836 B2
• Filed: 07/07/2005
• Issued: 06/07/2011
• Est. Priority Date: 08/05/2004
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Myeong, Hyeon, Hong, Sungi
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): PATTON, SPENCER D
• Application Number:
  US11/175,396
• Publication Number:
  US 20060041331A1
• Time in Patent Office: 2,161 Days
• Field of Search: 700/245, 700/253, 700/254, 701/23, 701/25, 701/26, 701/27, 701/200, 701/205, 701/207, 701/208, 701/210, 701/216, 701/217, 701/223, 701/224, 701/300
• US Class Current: 700/253
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• 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

A method used by a robot for simultaneous localization and map-building, including: initializing a pose of the robot and locations of landmarks; sampling a new pose of the robot during motion of the robot, and constructing chromosomes using the locations of the landmarks; observing the landmarks from a present location of the robot; generating offspring from the chromosomes; and selecting next-generation chromosomes from the chromosomes and the offspring using observation values of the landmarks.

Claims

1. A method used by a robot for simultaneous localization and map-building, comprising:

initializing a pose of the robot and locations of landmarks;

sampling a new pose of the robot during motion of the robot, and constructing chromosomes using the locations of the landmarks;

observing the landmarks from a present location of the robot;

generating offspring from the chromosomes using a random value of one of the landmarks according to a Gaussian distribution and a variance of the one of the landmarks; and

selecting next-generation chromosomes from the chromosomes and the offspring using observation values of the landmarks.

2. The method of claim 1, wherein the initializing of the pose of the robot is implemented by generating a plurality of particles based on the pose of the robot.

3. The method of claim 2, wherein the locations of the landmarks are determined from values obtained after observing distances and directions from the locations of each of the particles to the landmarks.

4. The method of claim 3, wherein the initial locations of the landmarks (μ

_x,0,μ

_y,0) are determined by an inverse function of an observation function in which a distance is expressed as r, a direction is expressed as φ

, and the initial pose of the robot is expressed as (S_0,x,S_0,y,S_0,θ

), the observation function being

5. The method of claim 2, wherein sampling the new pose of the robot is determined by a motion model obtained after predicting a motion of the robot at an end position of a path that the robot moved at a previous time according to a specified motion command.

6. The method of claim 2, wherein the constructing chromosomes obtains chromosomes of a present time from the locations of the landmarks if the present time is an initial time, or from a chromosome selected in a previous time if the present time is not the initial time,

wherein the chromosome selected in the previous time is a next-generation chromosome of the previous time.

7. The method of claim 2, wherein the constructing chromosomes obtains chromosomes of a present time from the location of the landmarks if the present time is an initial time, or from reflecting an average displacement of locations of the particles in a chromosome selected in a previous time if the present time is not the initial time,

wherein the chromosome selected in the previous time is a next-generation chromosome of the previous time.

8. The method of claim 7, wherein the chromosome of the present time is determined by the following equations

μ

′

_ix=μ

_ix−

dx

μ

′

_iy=μ

_iy−

dy, (i=1, . . . , N)

dx=x−

x

dy=y−

y

wherein (μ

′

_ix,μ

′

_iy) denotes the chromosome of the present time, (μ

_ix,μ

_iy) denotes the chromosome selected in the previous time, (x,y) denotes the location of each particle, and ( x, y) denotes the average location of particles.

9. The method of claim 1, wherein the generation of the offspring is generated by a Gaussian mutation method according to the following equation, an i^th chromosome being expressed as μ

_i,t-1, and offspring of the ith chromosome being expressed as μ

_i,t,

μ

_i,t=μ

_i,t-1+σ

_i,t−

N_i(0,1),

wherein N_i(0,

     1) is a random value obtained by a Gaussian distribution of mean 0 and variance 1 of an i^th landmark, and ν

_i is a variance of an i^th landmark.

10. The method of claim 9, wherein σ

_i is determined by

σ

_i,t=σ

_i,t-1−

exp(τ

′

−

N(0,1)+τ

−

N_i(0,1)),

wherein N(0,

     1) has the same value for every landmark according to the Gaussian distribution, and τ

′ and

τ

are constants.

11. The method of claim 1, wherein the selecting of the next-generation chromosomes includes:

evaluating a conformance of the offspring and the chromosomes; and

selecting the next-generation chromosome by a specified method based on the conformance.

12. The method of claim 11, wherein the conformance is calculated in a case where an observation value of a landmark n_t at time t is z, and a prediction value is {circumflex over (z)}_nt,t, by an objective function w_t according to a difference between the two values by the following equation:

w_t=(z_t−

{circumflex over (z)}_nt,t)^TR<sup>−

1</sup>(z_t−

{circumflex over (z)}_nt,t),

wherein T is a transpose, and R is a constant covariance matrix.

13. The method of claim 12, wherein {circumflex over (z)}_nt,t is predicted by the following equation, in a case where θ

_nt is a chromosome, and s_t is a prediction value of a pose of the robot;

14. The method of claim 1, wherein the observing includes:

determining whether a new landmark is generated; and

initializing a location of a generated landmark, if a new landmark is generated.

15. The method of claim 14, wherein determining whether a new landmark is generated is determined by a data association method.

16. The method of claim 14, wherein the selecting of the next-generation chromosomes includes:

evaluating fitness of the offspring chromosomes; and

selecting the next-generation chromosomes by a specified method based on the fitness or an objective function.

17. A non-transitory computer-readable storage medium encoded with processing instructions for causing a processor to perform a method used by a robot for simultaneous localization and map-building, the method comprising:

initializing a pose of a robot and locations of landmarks;

sampling a new pose of the robot during motion of the robot, and constructing chromosomes using the locations of the landmarks;

observing the landmarks from a present location of the robot;

generating offspring from the chromosomes using a random value of one of the landmarks according to a Gaussian distribution and a variance of the one of the landmarks; and

selecting next-generation chromosomes from the chromosomes and the offspring using observation values of the landmarks.

18. A method of simultaneous localization and map-building, comprising:

initializing a pose of a robot and a location of a landmark, the pose including a direction in which a front of the robot faces and x,y coordinates indicating a location of the robot;

sampling a new position of the robot as the robot moves;

constructing a chromosome for an evolutionary computation, the chromosome indicating the location of the landmark and being an object in the evolutionary computation;

observing the landmark from the new position;

determining whether a new landmark is present and, if so, initializing a location of the new landmark using an observed distance and angle from the robot to the landmark;

generating, when a new landmark is determined not to be present, offspring from a present parent chromosome using a random value of one of the landmarks according to a Gaussian distribution and a variance of the one of the landmarks;

evaluating fitness of the parent and the offspring, fitness being defined as an objective function according to a difference between an observation value and a prediction value of each landmark; and

selecting a next generation chromosome from the parents and the offspring based on fitness values.

19. The method of claim 18, wherein the observing is performed using a sensor.

20. The method of claim 18, wherein the new landmark is determined by a data association method.

21. The method of claim 20, wherein the offspring are generated according to a mutation method using the Gaussian distribution.

22. The method of claim 20, wherein selecting is performed using a random roulette wheel method, a random competition method, or a tournament method.