Method used by robot for simultaneous localization and map-building

• US 20060041331A1
• Filed: 07/07/2005
• Published: 02/23/2006
• 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
• Granted Patent: US 7,957,836 B2
• Time in Patent Office: Days
• US Class Current: 700/245
• 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; 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 the sampling of the new pose of the robot is determined by a probability obtained after predicting a motion of the robot at an end position of a path that the robot moves at a previous time according to a specified motion command.

6. The method of claim 2, wherein the chromosomes are constructed by replacing the locations of the landmarks at an initial time and a next-generation chromosome selected in a previous time, if not in the initial time, into chromosomes of a present time.

7. The method of claim 2, wherein the chromosomes are constructed by reflecting an average displacement of locations of the particles into the locations of the landmarks at an initial time and a next-generation chromosome selected in a previous time, if not in the initial time, and replacing the locations of the landmarks or the next-generation chromosomes into chromosomes of a present 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−

{overscore (x)}
dy=y−

{overscore (y)}

wherein (μ

_ix′

,μ

_iy′

) denotes the chromosome of the present time, (μ

_ix,μ

_iy) denotes the next-generation chromosome selected in a previous time, (x,y) denotes the location of each particle, and ({overscore (x)},{overscore (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 i^th 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 determined by a number of landmarks.

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 the determining whether a new landmark is generated 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 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 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.

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

initializing a pose of a robot and a location of a landmark, the orientation 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 according to the evolutionary computation method;

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 a random 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.