1
SA-1
1
Mapeamento
SCE5880
Algoritmos de Estimação para Robótica Móvel
SSC-5880 Denis F. Wolf2
Mapeamento na robótica móvel
� Representações do ambiente (mapas) são fundamentais para diversas tarefas executadas por robôs móveis como: localização e planejamento de trajetória.
� O mapeamento depende da capacidade de interpretação das informações obtidas por sensores. A maioria dos sensores fornece dados extremamente limitados sobre o ambiente, o que torna difícil o mapeamento do mesmo.
SSC-5880 Denis F. Wolf3
Mapeamento: problema de estimação
SSC-5880 Denis F. Wolf4
Tipos de mapas
� Mapas métricos: representam propriedades geométricas do ambiente de forma quantitativa, normalmente, discretizando o espaço representado. A ocupação é uma das propriedades mais representadas nesse tipo de mapa
� Mapas topológicos: representam a conectividade entre determinados locais do ambiente. Normalmente são utilizados grafos na representação, onde as regiões de importância são os nós e a conexão entre elas, os arcos.
SSC-5880 Denis F. Wolf5
Problemas no mapeamento
� Imprecisão na informação obtida por sensores e atuadores.
� Alta dimensionalidade dos modelos utilizados nas representações do ambiente.
� Complexidade do ambiente.
� Correspondência entre regiões do ambiente. (Como determinar se informações obtidas por sensores em
diferentes momentos representam o mesmo local?)
SSC-5880 Denis F. Wolf6
Mapeamento topológico: landmarks
2
SSC-5880 Denis F. Wolf7
Mapeamento topológico: landmarks
SSC-5880 Denis F. Wolf8
Mapeamento topológico: diagramas de Voronoi
SSC-5880 Denis F. Wolf9
Mapeamento topológico: diagramas de Voronoi
SSC-5880 Denis F. Wolf10
Mapeamento topológico: landmarks (câmera + laser)
SSC-5880 Denis F. Wolf11
Mapeamento métrico: occupancy grids
� Dividir o espaço em células e estimar a probabilidade de ocupação de cada célula individualmente baseado na informação obtida pelos sensores.
� Ao final, cada célula é classificada como ocupada, livre ou indefinido.
SSC-5880 Denis F. Wolf12
Cálculo das probabilidades
][1
][11
][1
][][][ )(),|()|()( xyt
xytt
xyt
xyt
xytt
xyt dmmBelummpmzpmBel −−−−∫= η
� Idea: Utilizar um filtro de Bayes para estimar a ocupação das células:
� Importante: o mapa é estático.
)()|()( ][1
][][ xyt
xytt
xyt mBelmzpmBel −= η
3
SSC-5880 Denis F. Wolf13
Cálculo das probabilidades
),misses(),hits(
),hits()( ][
yxyx
yxmBel xy
+=
equivalente a:
ou alternativa simples:
][ )( xytmBel =η
SSC-5880 Denis F. Wolf14
Mapas
Dados do laser Occupancy grid
SSC-5880 Denis F. Wolf15
Mapas
CAD map occupancy grid map
SSC-5880 Denis F. Wolf16
Mapas
USC Ronald Tutor Hall
SSC-5880 Denis F. Wolf17
Mapeamento em ambientes urbanos
� Complexidade
� Escala
� Irregularidade do terreno
� Difícil representação
Problemas:
SSC-5880 Denis F. Wolf18
Mapeamento 3D
� Com base na localização estimada, as informações do laser são projetadas no espaço 3D.
� Os mapas são visualizados em VRML
Plataforma experimental:� Robô Segway RMP
� Laser SICK� GPS� IMU
4
SSC-5880 Denis F. Wolf19
Mapas 3D
Livraria da USC
SSC-5880 Denis F. Wolf20
Mapas 3DMapas 3D
SSC-5880 Denis F. Wolf22
Mapas 3D
SSC-5880 Denis F. Wolf23
Mapas 3D
SSC-5880 Denis F. Wolf24
Mapas 3D
5
Mapas planares
Transformada de Hough 3D
Mapas planares Mapas planares
SSC-5880 Denis F. Wolf28
Mapping dynamic environments
� Two different occupancy grids.� Map S ⇒⇒ Static parts of the environment.
(obstacles that have never been seen to move)
� Map D ⇒⇒ Dynamic parts of the environment.
(obstacles that have been seen to move at least once)
� S U D ⇒⇒ Complete description of the environment.
SSC-5880 Denis F. Wolf29
� o t- Observation at present time (t ).
� S t-1 , D t-1 - Occupancy estimation at previous time (t-1 )
Map update equations
Modified update equations:
SSC-5880 Denis F. Wolf30
High:
Increase occupancy probability
Low:Decrease occupancy probability
Map update
6
Map update example
S t-1 O t
P( D | S t-1 , O t )P( S | S t-1 , O t )
S U D
Static
Dynamic
Occupied
Unknown
Free
SSC-5880 Denis F. Wolf32
Region occupied by
dynamic entities
Robot
S and D maps
SSC-5880 Denis F. Wolf34
� Corners used as landmarks. (Tomasi & Kanade, 1991) used to detect
corners from laser scans.
� Calculate for each point.
� Calculate covariance matrix and eigenvalues .
� If , then the point is a corner.
� Landmarks are differentiated and only static landmarks are used for localization.
� Data Association:� Differentiate concave and convex corners.
� Nearest neighbor gating.
Landmarks detection and data association
y
Nearest neighbor of x:
argmin d(x, yi) for i = 0, 1, 2, … n
for d(x, y) < threshold
SSC-5880 Denis F. Wolf35
Landmarks map
Robot
Landmarks
Occupancy grid map
Landmarks map
7
SSC-5880 Denis F. Wolf37
Experimental Results
California Science Center