Processo de Decisão de Markov

Processo de Decisão de Markov

(Parte 6 de 10)

• Uma ação a ser executada;

• Uma lista de planos condicionais que podem ser executados em seguida. A escolha do próximo plano depende da observação obtida.

Um plano condicional pode ser representado como uma árvore ou como uma função recursiva (como na Figura 4). Nas duas representações, o plano (ρ) começa recomendando a

Processos de Decisão de Markov: um tutorial ação a1 e indicando o próximo plano (ρ1 nas funções recursivas). O novo plano, dependendo da observação (o3 ou o2), pode recomendar a1 ou a2, e assim por diante.

o o o o o

Figura 4. Política para POMDP representada como árvore (esquerda) e como plano recursivo (direita).

3.4.4 Representação por controladores finitos Uma forma de representar políticas de horizonte infinito é usando controladores finitos [3]. Estes controladores são similares aos planos condicionais representados como árvores, exceto que formam ciclos fechados. Cada estado representa uma ação, e as arestas representam observações. Ao executar uma ação em um estado e obter uma observação, o próximo estado já é determinado. Um exemplo de controlador é mostrado na Figura 5.

o o

Figura 5. Política para POMDP representada como controlador de estados finitos.

O controlador pode também ser estocástico: para cada estado do controlador, há uma distribuição de probabilidade sobre as ações [34]. A ação tomada naquele estado é escolhida pelo controlador de acordo com esta distribuição. A distribuição das probabilidades de geração de cada ação é escolhida de forma a maximizar a recompensa esperada em um horizonte

Processos de Decisão de Markov: um tutorial infinito.

3.4.5 Representação por históricos limitados Uma outra abordagem é manter apenas parte do histórico (por exemplo, as últimas k ações e observações) como estado de informação, e usar uma política que faça o mapeamento destas seqüências em ações [35], usando uma janela deslizante no tempo. Por exemplo, se k = 3, apenas as três últimas ações e observações são usadas na política, que consistirá em um mapeamento de todas as possíveis seqüências de três ações e observações em ações. Se o histórico completo é

A equação de otimalidade, quando escrita em termos de estados de informação, é:

onde It é o estado de informação no momento t. Com históricos limitados, It é substituído por Ikt (uma lista das últimas k ações e observações):

A representação de política por histórico limitado permite que algoritmos mais rápidos sejam usados, mas as políticas encontradas podem ter desempenho arbitrariamente ruim (se ações e observações muito importantes acontecem no início do histórico, elas não estarão mais disponíveis em épocas de decisão mais adiante no tempo).

3.4.6 Representação por redes neurais Redes neurais podem ser treinadas para aproximar a função valor ótima, usando várias arquiteturas diferentes [36, 37]. Algumas das possibilidades são:

• Uma rede tem como entrada as k ações e observações mais recentes, e a saída é uma aproximação da função valor para todos os estados;

• Uma rede tem como entrada a ação e a observação executadas, além de algumas variáveis usadas para representar o estado de informação (um estado de crença, por exemplo). A saída é, como no caso anterior, uma aproximação da função valor para todos os estados.

• Usa-se uma rede neural para cada ação, e cada rede é treinada para aproximar o valor esperado da ação de acordo com um estado de informação. Para escolher uma ação, o estado de informação é usado como entrada uma vez em cada rede, e a ação com melhor valor é escolhida.

Processos de Decisão de Markov: um tutorial

Representação Horizonte Solução exata

Hiperplanos F/I S Discretização F/I N

Planos F S

Controladores I S

Controladores estocásticos I S

Históricos limitados F/I N Redes neurais I∗ N

Tabela 3. Métodos para a representação de políticas para POMDPs

3.4.7 Comparação entre representações de políticas A tabela 3 resume os métodos usados para representar políticas para POMDPs e suas características. A representação por redes neurais poderia em tese ser adaptada para horizonte finito, embora até onde saibamos isto nunca tenha sido feito. Há outras formas de representar políticas para POMDPs que este tutorial não descreve, inclusive formas mistas (por exemplo, o algoritmo HSVI representa limites inferior e superior da função valor, usando hiperplanos para o limite inferior [38]).

3.5 Algoritmos

Esta seção apresenta algoritmos para determinar políticas otimais para POMDPs. Esta

Não é uma lista exaustiva nem completamente detalhada, porque há uma quantidade muito grande de algoritmos que são muito diferentes entre si.

O problema de se encontrar uma função valor ótima para um POMDP é P-ESPAÇO difícil [39] para horizonte finito e indecidível para horizonte infinito (mas decidível e P-ESPAÇO difícil para -aproximações [7, 40]). A dificuldade em resolver POMDPs está principalmente em dois fatores:

• A maldição da dimensionalidade: para um problema com |S| estados, uma política otimal deve ser definida sobre um espaço contínuo de dimensão |S| − 1;

• A maldição do histórico: a busca por uma política otimal assemelha-se a uma busca em largura por todos os possíveis históricos de ação e observação, simulando o POMDP. O número de seqüências de ação e observação cresce exponencialmente com o horizonte de planejamento.

Há, no entanto, uma série de algoritmos aproximados e heurísticas que apresentam bom desempenho na prática [7, 24, 25, 41]. Todos os algoritmos que abordaremos foram de-

Processos de Decisão de Markov: um tutorial senvolvidos para POMDPs de crença. Há uma distinção importante a ser feita entre dois problemas que estes algoritmos resolvem:

• Horizonte finito: para horizonte finito e política não-estacionária, conhecemos apenas os algoritmos de iteração de valores (que também convergem para a função valor ótima no caso de horizonte infinito) e alguns dos algoritmos baseados em pontos de crença;

• Horizonte infinito: todos os outros são algoritmos para horizonte infinito, e para muitos há garantia de convergência para uma -aproximação da função valor ótima.

3.5.1 Iteração de Valores A iteração de valores é a forma clássica de resolução de POMDPs. Estes são algoritmos de programação dinâmica que resolvem o problema para horizonte finito de forma exata (e por isso são muito ineficientes), e conseguem -aproximações para problemas de horizonte infinito.

O valor de um estado de crença na época de decisão k pode ser dado por

onde Γk é um conjunto de hiperplanos de dimensão |S| representando a função valor para a política. Se a política for estacionária, Γk será o mesmo para todo valor de k.

Assim, V é para POMDPs o conjunto de todas as funções f : B 7→ R. Da mesma forma que para MDPs, um mapeamento h : B ×A×V 7→ R dá o valor de uma ação em um estado de crença, somado ao valor de se prosseguir com uma política otimal:

O operador H : V 7→ V de melhoria de política para POMDPs é:

e a equação de otimalidade para POMDPs é

Os diferentes algoritmos de iteração de valores baseiam-se nesta equação de otimalidade, e funcionam basicamente da mesma forma, mostrada no Algoritmo 5. A função

Processos de Decisão de Markov: um tutorial valor nestes algoritmos é representada por conjuntos de hiperplanos denotados Γi, onde i é o número da iteração do algoritmo. Dado um horizonte z, o algoritmo calcula inicialmente a função valor para horizonte 1, em seguida para horizonte 2, até z, ou seja, da última época de decisão para a primeira (por isso dizemos que o conjunto Γi representa a época de decisão z − i).

A diferença entre os algoritmos de iteração de valores está apenas na forma como cal- culam Γi a partir de Γi−1, que no Algoritmo 5 consiste na chamada da subrotina passo_dp na linha 1.

Hiperplanos evitam a representação de pontos de crença diretamente, uma vez que o espaço de crença é infinito (e apenas uma parte dos pontos poderia ser representada). Usando o fato de que

o mapeamento h e o operador H são redefinidos, e a equação de otimalidade pode ser escrita como

Após fixar a e o, Ma,o é uma matriz |S| × |S|, que para cada par de estados si e sj, dá a probabilidade de se chegar a sj observando o (ou seja, p(sj,o|si,a)). Além disso, ra é um vetor coluna com as recompensas imediatas (ra(s) = R(s,a)).

(Parte 6 de 10)

Comentários