Técnicas de Localização para Robôs em Ambientes Internos Claudia Patricia Ochoa Díaz Mestrado em Sistemas Mecatrônicos UnB-2008 1

Técnicas de Localização para Robôs em Ambientes Internos

Claudia Patricia Ochoa DíazMestrado em Sistemas Mecatrônicos

UnB-2008

1

2


LOCALIZAÇÃO

Determinação da postura do robô relativa ao um mapa do

ambiente

3


LOCALIZAÇÃO

Fornecido um mapa do ambiente, o robô deve determinar sua posição relativa no mapa a partir de percepções sensórias e os movimentos executados.

4


Localização Local/Global

Seguimento de posição (Position Tracking): assume que a postura inicial do robô é conhecida. A incerteza é aproximada a uma distribuição unimodal.

Localização Global: a postura inicial é desconhecida. A incerteza da posição do robô é representada por distribuições multimodais.

5


Localização de Markov

• Aplicação mas direta do filtro de Bayes ao problema de localização.

Algoritmo

Entradas: Conhecimento inicial do estado no tempo :Entrada de controle MedidaMapa

Etapa de Predição:

Atualização da medida:

Saída: Conhecimento do estado no tempo t

)1( tbel1ttu

tzm

dxxbelmxuxpxbel ttttt )(),,()( 11

dxxbelmxzpxbel tttt )(),()(

)( txbel

6



• Seguimento de posição: O conhecimento do estado inicial, , é representado como uma função de massa. Se é a posição inicial, então

• Localização Global: O estado inicial é desconhecido. é representado como uma distribuição uniforme sobre o espaço de todas posições possíveis do robô.

)( 0xbel

0x

00

000

0

1)(

xx

xxxbel

)( 0xbel

Xxbel

1)( 0

7



Tomado de R. Siegwart , I Nourbakhsh. Introduction to autonomous mobile robots

)( 0xbel

)(xbel

)(xbel

)( 1xbel

8


Filtro de Kalman Estendido (EKF)

9



• Representa por meio do primeiro e segundo momento, a média e a covariância .

• Assume que o mapa fornecido e representado por um conjunto de “features”

• Inicia com a suposição que todos os objetos são igualmente identificáveis.

• Probabilidade de transição de estados e probabilidade de medição são transformações não lineares g e h, respectivamente.

)( txbel tt

ttt

tttt

xhz

xugx

)(

),( 1

10



Algoritmo

Entradas: Média: Covariância:Entrada de controle:Mapa (conjunto de features)

Etapa de predição:

Etapa de atualização de medida:

Saída:Média:Covariância:

tt

tum

),( 1 ttt ug t

Ttttt RGG 1

))(( ttttt hzK

tttt HKI )(

tt

11



Fonte: S. Thrun , W Burgard, D. Fox. Probabilistics Robotics

12


Localização por células de ocupação (grid localization)Monte Carlo

13


Localização por células

•Utiliza um filtro de histograma para decompor o espaço de estados em pequenas regiões de dimensiones especificas.

•A probabilidade posterior, então é decomposta em um conjunto de valores de probabilidades

onde cada probabilidade, , é definida sobre uma célula, .. O conjunto de todas as células conforma a divisão do espaço em todas as posições possíveis do robô no ambiente:

tkt pxbel ,)(

tkp , kx

tkttt xxxXdom ,,2,1 ...)(

14



Algoritmo

Entradas: Conjunto de valores de probabilidade discretoEntrada de controle:MedidaMapa

Etapa de predição: calculado a partir do modelo de movimento

Etapa de atualização de medida: calculado a partir do modelo de medida

Saída:

1, tkptu

mtz

tkp ,

tkp ,

tkp ,

15


16



17


Localização de Monte Carlo

• Representação do conhecimento bel(xt) por meio de amostras ponderadas (partículas).

• E utilizado para resolver problemas tanto de localização local quanto global.

FILTRO DE PARTICULAS

• Implementação não paramétrica do Filtro de Bayes.• Representação aproximada de uma distribuição por meio de um conjunto de amostras obtidas a partir desta distribuição.

Cada partícula (com ) é “instanciação” do estado no tempo t.

][]2[]1[ ,...,, Mtttt xxx

mtx Mm 1

18


Localização de Monte Carlo

1. Algoritmo MCL( Xt-1, ut zt):

2.

3. Para

4. Amostrar de

5.

6.

7. Cálculo de

8. fim

9. Para

10.

11. Normalizar

12. fim

13. Saida: Cálculo de

tt

mt

mttt wx ,

itw

/it

it ww

Mm 1 ),|( 1

mttt

mt xuxpx

)|( mtt

mt xzpw

Mm 1

t

t )( txbel

)( txbel

19

20

21

22

23

24

25

26

27

28


Variações ao algoritmo MCL

• MCL aumentado: cria partículas aleatórias (além das inicialmente geradas) que servem como um respaldo no casso do robô errar no processo de localização. Estas partículas Podem ser geradas a partir da probabilidade de medida do sensor.

• KLD-Sampling MCL: adapta o numero de partículas conforme o tempo. Em cada iteração do algoritmo o numero de partículas é determinado, de maneira que o erro entre a probabilidade posterior verdadeira e a aproximada seja menor que .

29



EKF Grid L. (Rep. Topológica)

Grid L. (Rep. Métrica) MCL

Medidas Landmarks Landmarks Brutas Brutas

Dist. Posterior Gaussiana Histograma Histograma PartículasEficiência(memória) ++ + - +

Eficiência(tempo) ++ + - +

Implementação + + - ++Resolução ++ - + +Localização Local Global Global Global

30


Simulação : MCL

31


Simulação : MCL

32


Simulação : MCL

33


Definição do problema

Parede 1 Parede 2 Parede 3

Porta 1 Porta 2

34


Estados Possíveis:

• Parede 1: Pa1• Porta 1: Po1• Parede 2: Pa2• Porta 2: Po2• Parede 3: Pa3

Probabilidade Cond. de medidas:

Probabilidade de transição de estado:

)3...,1,1|/( papopaxpopazp tt portaparedezt /

)3...,1,1|3...,1,1( 1 papopaxpapopaxp tt

Definição do problema

35

0 50 100 150 200 250 300 350 4000

2

4x 10

-3

0 50 100 150 200 250 300 350 4000

0.5

1

0 50 100 150 200 250 300 350 4000

0.0020.0040.0060.0080.01

0 50 100 150 200 250 300 350 40000.20.40.60.81

0 50 100 150 200 250 300 350 4000

0.0020.0040.0060.0080.01

0 50 100 150 200 250 300 350 40000.20.40.60.81

0 50 100 150 200 250 300 350 4000

0.0020.0040.0060.0080.01

0 50 100 150 200 250 300 350 40000.20.40.60.81

0 50 100 150 200 250 300 350 4000

0.0020.0040.0060.0080.01

0 50 100 150 200 250 300 350 40000.20.40.60.81

0 50 100 150 200 250 300 350 4000

0.01

0.02

0 50 100 150 200 250 300 350 4000

0.5

1

Dist. Inicial

Parede 1 Porta 1 Parede 2

Medida 2

Medida 3

Medida 1

Medida 4

Medida 5

Parede 3Porta 2

36


Conclusões

• As técnicas baseadas em filtro de Bayes (Localização de Monte Carlo) diferenciam se na representação da função de distribuição do conhecimento inicial do robô.

• O desempenho de localização por método de Monte Carlo está fortementerelacionado com o numero de partículas utilizadas para representar os estados possíveis na trajetória do robô.

• As variações do algoritmo MCL, como o KDL-sampling incrementa a eficiência do filtro de partículas, adaptando o tamanho do conjunto delas na medida que em o conhecimento do estado (bel(x)) mude conforme no tempo.

37


Referências

[1] Fox D., W. Burgard, e S. Thrun. 2005. Probabilistic Robotics. MIT Press

[2] Fox D., W. Burgard, e S. Thrun. 1999. Monte Carlo Localization : Efficient Position Estimation for Mobile Robots.

[3] R. Siegwart., I. Nourbakhsh. 2004. Introduction to Autonomous Mobile Robots. MIT Press.

38

“In theory, there is no difference between theory and practice.In practice, there is.”

Yogi Berra and Jang L.A van de Snepscheut

Documents

Técnicas de Localização para Robôs em Ambientes Internos Claudia Patricia Ochoa Díaz Mestrado em Sistemas Mecatrônicos UnB-2008 1