Processo de Decisão de Markov

Processo de Decisão de Markov

(Parte 4 de 10)

s ← s0;4 enquanto o critério de final da rodada não for satisfeito faça5

Avalie o valor de cada ação no estado atual:6 para cada a ∈ A faça7

fim9

Algoritmo 4: Algoritmo RTDP para MDPs.

RTDP, como o LRTDP [16], o BRTDP [17] e o FRTDP [18].

2.2.5 Outros métodos Uma exposição extensa sobre MDPs é dada por Puterman [8] e por Bertsekas [6], que dão detalhes de outros algoritmos. Hauskrecht [7] também mostra diversos algoritmos para MDPs. Os métodos descritos neste capítulo são os métodos clássicos; há uma grande quantidade de métodos e algoritmos melhores [19–2] para a solução de MDPs que não abordaremos.

Processos de Decisão de Markov: um tutorial

3 Processos de Decisão de Markov Parcialmente Observáveis

Um processo de decisão de Markov parcialmente observável (POMDP) é uma generalização de MDPs onde o estado atual do sistema não necessariamente é conhecido. Ao invés disso, o tomador de decisões se lembra das ações que executou e das observações que percebeu ao longo do tempo, e tenta usar estas informações para tomar a próxima decisão. É possível, por exemplo, que ao invés de um “estado atual do sistema”, uma distribuição de probabilidades sobre os estados seja mantida enquanto as decisões são tomadas. POMDPs são mais difíceis de resolver que os MDPs, mas são mais expressivos.

POMDPs podem ser usados para modelar problemas em muitas áreas diferentes. Cassandra [23] mostra possibilidades em manutenção de máquinas, navegação de robôs, controle de elevadores, visão computacional, modelagem de comportamento em ecossistemas, aplicações militares, diagnóstico médico, educação e várias outras áreas. Alguns casos notáveis de aplicação são o trabalho de Hauskrecht com a modelagem de doenças isquêmicas do coração [1, 7]; o trabalho de Pineau, que usou POMDPs para modelar o comportamento de um robô para ajudar idosos a se lembrarem de seus compromissos, acompanhá-los e guiar (de maneira limitada) diálogos [24]; e o trabalho de Poupart, que implementou um sistema que acompanha o comportamento de pacientes com demência, monitorando-os com uma câmera e ajudando com os passos para lavar as mãos, entre outras coisas [25].

Como um exemplo, podemos considerar o seguinte problema:

Uma pessoa está em uma sala onde há duas portas. Atrás de uma das portas há um tigre, que a pessoa deve evitar, e a outra porta é uma saída segura do local onde ela está. Por um certo número de vezes a pessoa pode escolher entre três ações possíveis:

• Ouvir (para tentar determinar atrás de qual porta está o tigre); • Abrir a porta à esquerda;

• Abrir a porta à direita.

Depois de algum tempo o tomador de decisões decidirá por abrir uma das portas, quando deverá finalmente encontrar-se com o tigre ou sair em segurança. Ao ouvir, no entanto, ele pode mudar seu grau de certeza sobre qual porta esconde o tigre. Cada vez que ouve, ele obtém uma de duas observações:

• O tigre parece estar atrás da porta da esquerda; • O tigre parece estar atrás da porta da direita.

Processos de Decisão de Markov: um tutorial

Estas observações podem não corresponder à realidade, porque ele pode ter se confundido ao tentar determinar de que porta vem o ruído produzido pelo tigre. Ele pode, no entanto, ouvir mais vezes, a fim de aumentar seu grau de certeza.

Há, como podemos ver, incerteza quanto ao estado atual do sistema (o tomador de decisões não sabe atrás de qual porta o tigre está); após cada ação, uma observação é recebida (que não necessariamente informa com total certeza o estado atual); e cada ação pode resultar em uma recompensa (positiva ou negativa). Veremos mais adiante como modelar este problema formalmente como um POMDP.

Definição 3.1 (POMDP) Um processo de decisão de Markov parcialmente observável (POMDP) é uma tupla (S, A, T, R, Ω, O), onde:

• S é um conjunto de estados em que o processo pode estar; • A é um conjunto de ações que podem ser executadas em diferentes épocas de decisão;

• T : S ×A×S 7→ [0,1] é uma função que dá a probabilidade de o sistema passar para um estado s′, dado que estava no estado s e a ação executada foi a;

• R : S ×A 7→ R é uma função que dá o custo (ou recompensa) por tomar uma decisão a quando o processo está em um estado s;

• Ω é um conjunto de observações que são obtidas em cada época de decisão;

• O : S × A × Ω 7→ [0,1] é uma função que dá a probabilidade de uma observação o ser verificada, dados um estado s e a última ação a executada.

Este tutorial trata apenas do caso em que S,A e Ω são finitos.

Em um POMDP não há a possibilidade de se observar diretamente o estado em que o sistema está em um dado momento, ou seja, o tomador de decisões não sabe o estado atual s (ao contrário do que acontece em um problema modelado como MDP). No entanto, cada ação tem como resultado alguma observação que é probabilisticamente relacionada ao estado do sistema.

Como o atual do sistema não é acessível ao tomador de decisões, é possível usar o histórico anterior de ações e observações para escolher a melhor ação.

Definição 3.2 (Estado de informação)

O estado de informação Ik representa o conhecimento que se tem sobre o sistema na época de decisão k, e consiste de:

Processos de Decisão de Markov: um tutorial

• Uma distribuição de probabilidades sobre os estados na primeira época de decisão, denotado por b0;

• O histórico completo de ações e observações, desde a primeira época de decisão.

O espaço de todos os estados de informação para um POMDP P será denotado por I(P). Quando não houver ambiguidade, I será usado no lugar de I(P).

Uma política para um POMDP deve mapear estados de informação em ações. Agora podemos formular o problema do tigre como um POMDP:

• S: há dois estados, tigre_esq e tigre_dir; • A: há três ações, ouvir, abrir_esq e abrir_dir;

• T: nenhuma ação altera o estado do sistema (por mais que o tomador de decisões goste da idéia, abrir portas ou ouvir não farão o tigre mudar de lugar!);

• R: há uma recompensa positiva igual a 30 para abrir a porta onde o tigre não está, e uma recompensa negativa (um custo igual a 100) para abrir a porta onde o tigre está;

• Ω: há duas observações, tigre_esq e tigre_dir;

• O: a ação ouvir dá a observação equivalente ao estado atual (ou seja, a observação “correta”) com probabilidade 0.9, e a observação oposta com probabilidade 0.1. As ações de abrir portas dão sempre a observação correta.

O problema modelado desta forma pode ser resolvido por algoritmos que determinam uma política otimal para POMDPs. Esta política receberá como entrada o estado de informação atual, e a saída será a recomendação de uma ação que maximiza a recompensa esperada do tomador de decisões.

3.1 Dinâmica de sistemas modelados como POMDPs

A dinâmica de um sistema modelado como POMDP é mostrada na Figura 2: a cada época de decisão, o tomador de decisões verifica o estado de informação atual (I na figura), a última ação executada e a última observação obtida do ambiente. A partir desses dados, um estimador de estados de informação (τ na figura) determina um novo estado de informação, que é usado como entrada para uma política pi, que determina a próxima ação a ser tomada. Esta ação tem um efeito sobre o ambiente, que retorna uma observação o. Na próxima época de decisão, esta observação e a última ação executada serão usadas para determinar o próximo

Processos de Decisão de Markov: um tutorial pi (polıtica) ambiente τ (estimador de estados de informacao) I (novo estado de informacao) o (nova observacao) a (acao executada) a (acao executada) tomador de decisoes Figura 2. Funcionamento de um sistema modelado como POMDP.

estado de informação. Nesta figura há uma aresta levando o novo estado de informação de τ a τ para enfatizar o fato de que o estado de informação da época de decisão anterior é usado para determinar o da próxima época de decisão.

A maneira mais direta de representar estados de informação é como uma lista de ações e observações executadas desde a primeira época de decisão (além da distribuição inicial de probabilidades sobre os possíveis estados): o estado de informação na época de decisão

desta forma é trivial: basta adicionar o par (a,o) com a última ação e a observação resultante.

No entanto, uma política para POMDP teria que mapear o espaço I de todos os estados de informação em ações, e a enumeração de todos os possíveis históricos de um processo é inviável. Usa-se então uma estatística suficiente para representar o estado de informação atual. Uma estatística muito usada para representar estados de informação é o estado de crença, uma distribuição de probabilidades sobre os possíveis estados do sistema. Há uma distribuição inicial de probabilidades sobre os estados, que refletem a crença do tomador de decisões a respeito do estado inicial. Ao tomar uma decisão e executar uma ação a, o agente perceberá uma observação o. Sabendo a distribuição de probabilidades anterior, a ação executada e a observação resultante, o agente pode calcular uma nova distribuição de probabilidades sobre os estados (ou seja, um novo “estado de crença”). No problema do tigre o estado de crença inicial é (0.5,0.5), porque o tomador de decisões nada sabe sobre a localização do tigre. Após executar a ação “ouvir” e receber a observação “tigre à direita” ele poderá melhorar seu estado de crença, que pode mudar para (0.20,0.70) resultando em um

Processos de Decisão de Markov: um tutorial maior grau de certeza a respeito do que há atrás de cada porta. No estado de crença inicial, (0.5,0.5), as recompensas esperadas para as ações são:

Este exemplo mostra como a escolha da ação depende do estado de crença: quando o tomador de decisões não tem certeza suficiente sobre o estado atual (por exemplo no estado de crença (0.5,0.5), a melhor decisão (ou seja, a que tem maior recompensa esperada) é “ouvir”, porque evita o risco do encontro com o tigre (que aparece no exemplo na forma da recompensa igual a -100) e ajuda a melhorar o estado de crença. Já com o estado de crença (0.05,0.95) a melhora ação é abrir a porta da esquerda. O tomador de decisões repete a ação “ouvir” até que o estado de crença mude o suficiente para que a recompensa esperada das ações de abrir portas seja maior do que a de ouvir.

(Parte 4 de 10)

Comentários