INTRODUÇÃO À ROBÓTICA
MÓVEL
Aula 27
Edson Prestes
Departamento de Informática Teórica
http://www.inf.ufrgs.br/~prestes
[email protected]
Localização
l
l
l
l
É um componente essencial para um robô ser
completamente autônomo.
Se o robô não sabe sua posição no ambiente ele não
pode realizar nenhuma tarefa de navegação
A odometria por si só não é suficiente para ser usada
como estimativa da posição do robô, pois o erro de
estimativa cresce de forma ilimitada.
Os principais algoritmos são baseados em processo de
Filtragem de Kalman e de Bayes.
Localização
l
l
l
O processo de auto-localização usando Filtro de
Kalman considera que a postura do robô pode ser
representada por uma distribuição gaussiana.
Esta forma de estimação assume que a crença sobre a
localização robô não possui ambiguidades. Portanto, a
distribuição é sempre unimodal.
Distribuições unimodais são particularmente importante
em problemas de position tracking.
Localização
l
l
l
Em position tracking, a postura inicial do robô é
conhecida.
As observações feitas pelo robô podem ser associadas
de forma única com as características armazenadas no
mapa do ambiente.
Exemplo: se um robô sabe aproximadamente sua
localização e detecta uma porta, ele pode determinar
sua postura usando a informação sobre sua posição e a
da porta, armazenada no mapa do ambiente.
Figura extraída de [1]
Localização
l
l
l
l
Se a incerteza sobre a postura do robô é alta então
múltiplas portas armazenadas no mapa podem
corresponder à porta observada pelo robô.
Temos situações ambíguas.
Logo, o método deve modela a postura do robô através
de uma distribuição multi-modal.
Problemas com esta característica são chamados de
problemas de auto-localização global.
Localização
Figura extraída de [1]
Localização Probabilística- Filtragem
Bayesiana
l
l
Seja X o espaço de estados do robô. Queremos estimar
o estado x 2 X, que é sua postura corrente.
Para isto é necessário estimar a seguinte probabilidade
condicional (posterior probability)
P(x(k) | u(0:k–1), y(1:k))
que consiste na probabilidade de x(k) ser a postura real
do robô dados u(0:k–1) e y(1:k), onde u(0:k-1) são as
ações nos instantes de 0 a k-1; e y(1:k) são as
observações feitas nos instantes de 1 a k.
l
Observe que u e y são considerados de forma
sincronizada, u(0), y(1), u(1), y(2), … u(k-1),y(k)
Localização Probabilística- Filtragem
Bayesiana
l
A probabilidade posterior (detalhes em [1])
(1)
Onde
P(y(k)|x(k)) é o modelo de observação, i.e., a
probabilidade de observar y(k) na postura x(k).
P(x(k)| u(k-1), x(k-1)) é o modelo de movimento que
pode ser visto como a probabilidade de transição de
x(k-1) para x(k) após a aplicação da ação u(k-1).
n(k) é a constante de normalização.
Localização Probabilística- Filtragem
Bayesiana
l
A equação (1) é um caso particular, que considera os
estados discretos da seguinte equação
(2)
Onde
P(y(k)|x(k)) é o modelo de observação, i.e., a
probabilidade de observar y(k) na postura x(k).
P(x(k)| u(k-1), x(k-1)) é o modelo de movimento que
pode ser visto como a probabilidade de transição de
x(k-1) para x(k) após a aplicação da ação u(k-1).
n(k) é a constante de normalização.
Localização Probabilística- Filtragem
Bayesiana
l
l
Tanto a equação (1) quanto a equação (2), incorporam de
forma conjunta os passos de predição e atualização,
diferentemente da filtragem de Kalman.
O passo de predição atualiza a probabilidade corrente da
postura do robô, P(x(k-1)|u(0:k-2),y(1:k-1)), usando a
medida de odometria u(k-1).
Estimado no instante k-1
Localização Probabilística- Filtragem
Bayesiana
l
O passo de atualização é executado quando o robô
percebe uma medida y(k) com as informações sobre o
ambiente no estado x(k). Isto é feito através do termo
p(y(k)|x(k)).
Calculado no passo anterior
onde
Localização Probabilística- Representação
Resolução espacial : 10 ~30
cm
Resolução angular : 2 ~10
graus
Figura extraída de [1]
Localização Probabilística- Representação
Algoritmo extraído de [1]
Localização Probabilística- Filtragem
Bayesiana
Muitas operações devem ser realizadas.
Para aumentar a eficiência das linhas de 2-5, Fox et al [2]
propuseram o seguinte algoritmo:
l
desloca os dados de acordo com o movimento do robô
l
O grid é convoluído com um kernel gaussiano. No caso
bidimensional temos
l
l
O eixo x, temos
P'(x,y, µ)=0.5P((x,y, µ))+(0.25)(P((x-1,y,µ)) + P((x+1,y, µ)))
l
Localização Probabilística- Filtragem
Bayesiana
l
O processo é repetido para os eixos y e µ
l
Em seguida, a observação y(i) é integrada no grid.
l
Isto é feito multiplicando cada célula do grid pela
probabilidade de observação, dado que o robô tem a
postura correspondente àquela célula.
Localização Probabilística- Filtragem
Bayesiana
Figuras extraídas de [1]
Localização Probabilística- Filtragem
Bayesiana
Figuras extraídas de [1]
Localização Probabilística- Filtragem
Bayesiana – Filtro de Partículas
l
l
Uma alternativa eficiente para representar e manter a
PDF.
É chamado de Localização Monte Carlo, Condensation,
entre outros
A idéia chave é representar a probabilidade posterior,
P(x(k) | u(0:k–1), y(1:k))
através de um conjunto de amostras.
l
l
Cada amostra é um par (x,w) que contém uma hipótese
candidata x sobre a postura do robô e um fator w que
indica a adequação da hipótese em representar a postura
real do robô.
Localização Probabilística- Filtragem
Bayesiana – Filtro de Partículas
Localização Probabilística- Filtragem
Bayesiana – Filtro de Partículas
Motion Model
Figura extraída de [1]
Localização Probabilística- Filtragem
Bayesiana – Filtro de Partículas
Sensor Model
Figura extraída de [1]
Localização Probabilística- Filtragem
Bayesiana – Filtro de Partículas
Figura extraída de [1]
Localização Probabilística- Filtragem
Bayesiana – Filtro de Partículas
Figura extraída de [1]
Localização Probabilística- Filtragem
Bayesiana – Filtro de Partículas
Figura extraída de [1]
Localização Probabilística- Filtragem
Bayesiana – Filtro de Partículas
Como incorporar o Filtro de Partículas no
Processo de Mapeamento de forma a
desenvolver um método SLAM ?
Particle Selection based on
Potential Fields
¢
Particle filter method draws samples randomly in
the free-space environment.
¢
This strategy has at least two disadvantages:
All regions will have the same importance.
— The regions near the obstacles are improperly covered.
—
Particle Selection based on
Potential Fields
How to produce a good environment covering?
How to minimize the number of particles keeping
the filter convergence to the correct solution?
Particle Selection based on
Potential Fields
¢
An initial tentative has been proposed by Kwon
et al.
¢
They consider that the robot will always follow
the topological edges of the environment freespace.
¢
The method samples particles around topological
edges.
¢
The number of particles significantly diminishes.
Particle Selection based on
Potential Fields
This strategy is very efficient to dense
environments.
¢ When the robot is in a sparse environment, the
method fails.
¢
robot
Sparse Regions
The regions near the obstacles
are improperly covered
Topological Edges
Particle Selection based on
Potential Fields
How to solve this problem ?
By sampling particles near the walls.
a)
b)
Depending on the
sensor range, we can
focus on different
regions to draw
particles
Particle Selection based on
Potential Fields
¢
¢
To determine the best navigational edges, we need
—
The grid cells size (wcell);
—
The maximum robot distance from the walls (drobot). We can
consider only a small fraction of the sensor range as useful
information, e.g., only 30% of the sonar returns.
By using this information, we know the cells that will comprise
navigational edges should be far from the nearest obstacles
η = drobot /wcell
Particle Selection based on
Potential Fields
By shrinking the free-space cells through a thinning
algorithm, we can determine the navigational edges.
η=1
Particle Selection based on
Potential Fields
By shrinking the free-space cells through a thinning
algorithm, we can determine the navigational edges.
η=2
Particle Selection based on
Potential Fields
By shrinking the free-space cells through a thinning
algorithm, we can determine the navigational edges.
η=4
Particle Selection based on
Potential Fields
By shrinking the free-space cells through a thinning
algorithm, we can determine the navigational edges.
η = 10
Particle Selection based on
Potential Fields
By shrinking the free-space cells through a thinning
algorithm, we can determine the navigational edges.
η = 17
Particle Selection based on
Potential Fields
By shrinking the free-space cells through a thinning
algorithm, we can determine the navigational edges.
Final Skeleton
(The result produced by Kwon’s methods)
Particle Selection based on
Potential Fields
By considering the maximum robot’s distance from the
walls (drobot) as half of the sensors range
Low potential (0.0)
High potential (1)
Intermediary potential (0.5)
Particle Selection based on
Potential Fields
The probability that a cell r is selected to generate one
particle
Where c is a constant and p( r ) is the potential stored in
the cell r
Results
Uniform distribution samples
particles in regions that will not
help the robot in the localization.
Kwon’s method samples most of
the particles in the sparse
regions.
The method proposed produces
the best covering.
Green cells – Uniform distribution
Red cells
– Method proposed
Lilac cells – Kwon methods
Sparse
Regions
Results
Connected dense environment
The environment has 10m x 10m.
The robot can sense any obstacle at maximum distance
of 2m.
Environment 10m x 10m
Sensor Range 2m
Connected sparse environment
30m
24m
(c)
(b)
(a)
Sensor Range 2m
(b)
(a)
(c)
Non-Connected Sparse
Environment
The environment has 10m x 10m.
The robot can sense any obstacle at maximum distance
of 2m.
30m
24m
Sensor Range 2m
Adding information using the
robot motion
Robot motion and sensor readings are used to provide an initial
particle orientation.
The initial orientation is determined from the vector field computed
from the intermediary skeleton.
Final Results
Método
publicado em
[3] e [4].
Percentage of successful localizations. For each initial particle
distribution and number of particles the convergence rate
without and with orientation of the particles is given.
BIBLIOGRAFIA
l
l
l
l
[1] Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Burgard, W.,
Kavraki, L., Thrun, S. Principles of Robot Motion : Theory, Algorithms,
and Implementations. MIT Press. 2005.
[2] D. Fox, W. Burgard and S. Thrun. Markov Localization for mobile
robots in dynamic environments. Journal of Artificial Intelligence
Research (JAIR), 11: 391-427, 1999
[3] SILVA JÚNIOR, E. P., Ritt, M., Fuhr, GImproved Particle Filter for
Sparse Environments Accepted for publication in the Special Issue
“Intelligent Robotic Systems” of the Journal of the Brazilian Computer
Society, 2009.
[4] SILVA JÚNIOR, E. P., RITT, M., FUHR, G. Improving Monte Carlo
Localization in Sparse Environments using Structural Environment
Information. In: IEEE/RSJ International Conference on Intelligent Robots
and Systems, Nice, France, 2008.