Xavier: Navegação Baseado em
POMDP
Sven Koenig, Reid G. Simmons
Apresentador: Pedro Mitsuo Shiroma
Definição do Problema
• Navegação robusta de um robô móvel, por
longos períodos de tempo, em um ambiente
interno não-estruturado.
• Caminhar por corredores, por longos
períodos de tempo, sem perder-se.
Dificuldades
X
X
Imprecisão nos sensores.
atuadores
Abordagens Existentes
• Mapas métricos
• + Fácil atualização dos dados de odometria para
o mapa,
• - Problema de dead-reckoning
• Mapas topológicos
• + Compactação dos dados
• - Incerteza nos sensores
Abordagens Existentes
• Navegação métrica
relatório de movimento
X
relatório do sensor
•Navegação baseado em landmark
Abordagens Existentes
• Incapazes de lidar:
• Com múltiplas possibilidades para a postura do robô,
• E lidar, de forma unificada, com as incertezas nos:
•
•
•
•
•
atuadores,
sensores,
interpretação dos dados,
posição inicial,
caráter estático da cena
Trabalhos Relacionados
• Como trabalhar de maneira segura em um
ambiente impreciso?
• Filtro de Kalman – Unimodal
• Redes Bayesianas – Espaço discreto
• POMDP
Trabalhos Relacionados: Dervish
• Dervish:
• Mapa topológico
• Planejamento externo
• “Intuição”
• Xavier:
• Misto de mapa topológico e métrico
• Planejamento inerente à arquitetura
• Formalismo matématico (POMDP)
Navegação POMDP
•Partially Observable Markov Decision Process
Processo de Markov
• AFN:
• Alfabeto = ações,
• Transição = probabilidades,
Cair no chão/0.1
Cair no
chão/0.9
cara
Jogar/0.5
coroa
Jogar/0.5
Jogar/0.5
Jogar/0.5
• Propriedade de Markov: O próximo estado é
determinado exclusivamente pelo estado atual e a
ação tomada.
Processo de Decisão de Markov
•
Ações Determinísticas =S x
4-upla: (S, A, T,Estocásticas
R):
= p(s’/s,a)
• S = Conjunto de estados,
• A = Conjunto de ações,
• T:S£A ! ? = função de transição de estado,
• R:S£A !< = função de recompensa
• A melhor ação nem sempre é aquela que
traz a maior recompensa imediata:
Planejamento a longo prazo.
Prog. Dinâmica (Bellman):
V(s) = maxa2 A [R (s)+ b s’ 2 Sp(s’/s,a)V(s’)]
Processo de Decisão de Markov
• Solução para um MDP: Política
• Política: p: S ! A
• Programação linear
• Value Iteration Algorithm: Horizonte de tempo:
1, 2,..., 1
Exemplo
?
a(s) = arg maxa2 A [R (s,a) + b s’ 2 Sp(s’/s,a)V(s’)]
Processo de Decisão de Markov
1.
2.
3.
•
Determine o estado corrente s,
Execute a ação p(s),
Volte para o primeiro passo,
Assume observação total: O novo estado é
conhecido pelo sistema
Processo de Decisão de Markov
Parcialmente Observável
• Observações O,
• Uma distribuição para as observações,
• e para o estado inicial.
Processo de Decisão de Markov
Parcialmente Observável
• M = (S, O, p, A, s, p, q, r), onde :
•
•
•
•
•
•
•
•
S = conjunto de estados,
O = conjunto de observações,
p = distribuição do estado inicial,
A(s) = ações possíveis para o estado s,
s = estado atual,
p(s’/s,a) = função de transição,
q(o/s,a) = função de observação,
r(s/a) = função de recompensa.
Processo de Decisão de Markov
Parcialmente Observável
Processo de Decisão de Markov
Parcialmente Observável
• O estado atual é observado,
• Decisão requer manter um histórico do
ponto de partida, ações tomadas,
observações realizadas: Não-Markoviano,
• É necessário manter o histórico?
• Não! Estado de crença: “Onde eu acho que
estou”
Processo de Decisão de Markov
Parcialmente Observável
• Solução exata: NP –difícil
• Heurísticas:
• MLS (Most Likely State),
• Votação,
• Witness
• Grid-based
• Fatorar dependências.
Processo de Decisão de Markov
Parcialmente Observável
•
•
•
•
q,p: Estimativa inicial, aprendizado,
Mapa métrico = estados,
Modelo atuador = p,
Modelo sensores = q.
Arquitetura Xavier
Arquitetura Xavier
Subsumption Architecture
Comportamento Objetos
Mudanças no mundo
Planejador Tarefas
Planejador Trajetórias
Navegador
Desvio de Obstáculos
Parada Emergencial
Identificação objetos
Monitoramento Mudanças
Construção mapas
Exploração
Vagar
Desvio de Obstáculos
Processo Off-line
Arquitetura Xavier
Mapa topológico
Modelo atuadores
Modelo sensores
Modelo portas
Compilador
POMDP
POMDPEstimação da(s)
Detector de portas,
espaços livres.
Geração
da política
Movimentos
desejados
postura(s)
Localização
Relatório sensores
Alvos
Mudanças na
direção
Seleção
diretivas
e distância percorrida
Relatório atuadores Desvio de
obstáculos
Grade de ocupação
Xavier
Sonar
Geração movimentos
Odometria
Motores
Relatórios
• Movimento: Discretizado com 1 metro
• Sensores:
• Esquerda: Incerto, parede, abertura pequena,
abertura média, abertura grande;
• Direita: Incerto, parede, abertura pequena,
abertura média, abertura grande;
• Frente: Incerto, parede.
Modelo Orientação
• Robô possui 6 d.o.f.: Como representar
rotações?
• Cada postura é representada por quatro
estados:
Modelo Corredor
• Conhecimento métrico preciso
Modelo Corredor
• Conhecimento métrico impreciso
Modelo Junção
Exemplo
Exemplo
Exemplo
Exemplo
• Animação
Como Alinhar-se?
• Detector de retas na grade de ocupação:
• Escorregamento rotacional não é tratado pelo
modelo proposto.
Múltipla detecção de
características
Conclusões
• Caminhar por corredores, que formam ângulos
retos, por longos períodos de tempo, sem perderse completamente.
• Vantagens:
• Representação multimodal;
• Acoplado com o planejamento;
• Desvantagens:
• Requer discretização do ambiente;
• Milhares de estados: Custo computacional;
Conclusões
• Exemplo prático pobre,
• Modelar especificamente as junções,
• Localização de Monte-Carlo:
• Utiliza Filtro de Partículas;
• Espaço contínuo;
• Computacionalmente tratável.