Técnicas de Localização para Robôs em Ambientes Internos Claudia Patricia Ochoa Díaz Mestrado...

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

Claudia Patricia Ochoa DíazMestrado em Sistemas Mecatrônicos

UnB-2008

1

2

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

LOCALIZAÇÃO

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

ambiente

3

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

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

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

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

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

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

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

Localização de Markov

• 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

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

Localização de Markov

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

)( 0xbel

)(xbel

)(xbel

)( 1xbel

8

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

Filtro de Kalman Estendido (EKF)

9

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

Filtro de Kalman Estendido (EKF)

• 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

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

Filtro de Kalman Estendido (EKF)

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

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

Filtro de Kalman Estendido (EKF)

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

12

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

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

13

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

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

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

Localização por células

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

Localização por células

16

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

Localização por células

17

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

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

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

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

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

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

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

Localização de Markov

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

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

Simulação : MCL

31

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

Simulação : MCL

32

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

Simulação : MCL

33

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

Definição do problema

Parede 1 Parede 2 Parede 3

Porta 1 Porta 2

34

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

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

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

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

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

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