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.