Teoria da Decisão Métodos de Computação Inteligente Universidade Federal de Pernambuco Centro de Informática – Cin Maria Uilma Rodrigues dos Santos de

Teoria da Decisão

Métodos de Computação InteligenteMétodos de Computação Inteligente

Universidade Federal de PernambucoUniversidade Federal de Pernambuco

Centro de Informática – CinCentro de Informática – Cin

Maria Uilma Rodrigues dos Santos de SousaMaria Uilma Rodrigues dos Santos de Sousa

Sandra Wanderley LubamboSandra Wanderley Lubambo

Roteiro da apresentação

Teoria da Decisão – conceitos básicos Decisões Simples

Princípio da Utilidade Máxima Esperada (UME) Função Utilidade Função Utilidade Multiatributo Redes de Decisão Valor da Informação Sistemas Especialistas

Decisões Complexas Processo Decisão de Markov (MDP) Algoritmo de Iteração de Valor Algoritmo de Iteração de Política MDP em ambiente Parcialmente Observável

Agente de teoria da decisão






Teoria da decisão – conceitos básicos

Teoria daprobabilidade

Teoria dautilidade

Teoria da Decisão

Descreve aquilo que um agente deve

acreditar com base nas evidências

Descreve o que um agente deseja

Descreve o que um agente deve

fazer

A combinação da Teoria da Probabilidade com a Teoria da Utilidade permite ao agente escolher a ação que maximiza seu desempenho esperado.

A teoria da decisão pode ser usada para construir um agente que toma decisões considerando todas as ações possíveis e escolhendo aquela que leva ao melhor resultado esperado. Tal agente é denominado Agente racional.

Teoria da decisão – conceitos básicos

O agente da teoria da decisão pode tomar decisões racionais baseadas em suas crenças e no que ele deseja em contextos nos quais a incerteza e objetivos conflitantes deixam um agente lógico sem meios para decidir;

Um agente lógico faz distinção binária entre estados bons (objetivos) e estados ruins (não-objetivos), enquanto um agente de teoria da decisão tem uma medida contínua da qualidade do estado;

Em resumo: O princípio básico da teoria da decisão é a maximização da utilidade

esperada (UME).






Decisões Simples

“Como um agente deve tomar decisões de modo que, em média, ele

consiga o que quer”

Princípio da (1/2) Utilidade Máxima Esperada (UME)

No texto Port-Royal Logic, escrito em 1662, o filósofo francês Arnauld declarou:

Para julgar o que se deve fazer para obter um bem ou evitar um mal, é necessário considerar não apenas o bem e o mal em si, mas também a probabilidade de ele acontecer ou não acontecer, e ainda visualizar geometricamente a proporção que todos esses itens têm em conjunto. (grifo nosso)

Pág. 566, AIMA- 2ª ed. – (Português).

Princípio da (2/2) Utilidade Máxima Esperada (UME)

afirma que um agente racional deve escolher uma ação que maximize a utilidade esperada do agente;

se relaciona com a idéia de medida de desempenho;

é um modo razoável de tomar decisões.

ou seja:

O agente usa um modelo do mundo junto com a função utilidade (que mede suas preferências entre os estados do mundo), em seguida escolhe a ação que leva à melhor utilidade esperada.

Função utilidade (1/2)

• Capta as preferências de um agente entre estados de mundo e atribui um único número para expressar a desejabilidade de um estado;

Função de Utilidade: associa um valor a um estado; indica o “desejo” por estar nesse estado;

As utilidades são combinadas com probabilidades de resultados de ação para fornecer uma Utilidade Esperada (EU).

Função Utilidade (2/2)

A Utilidade Esperada (EU) da ação A dada a evidência E é calculada usando a fórmula:

onde,E = evidências disponíveis;

Fazer(A) = proposição de execução da ação A;

Resultadoi(A) = estados possíveis de saída da ação A;

P = probabilidade para cada saída possível; U = é a utilidade de cada estado.

EU(A|E) = i P(Resultadoi(A)|Fazer(A),E) * U(Resultadoi(A))

Preferências Racionais (1/4)

As preferências do agente são descritas utilizando as notações a seguir:

Notação:– A B: A é preferível a B– A ~ B: agente indiferente entre A e B– A B: agente prefere A à B ou é indiferente

Em ambientes deterministas: A e B são estados resultantes concretos e totalmente especificados;

Em ambientes não deterministas: A e B são loterias, i.e., distribuições probabilísticas sobre um conjunto de estados de saída (os “prêmios” da loteria).

Preferências Racionais (2/4)

Uma loteria L com resultados possíveis C1,...,Cn que pode ocorrer com as probabilidades p1,...pn é descrita como:

A principal questão para a teoria da utilidade é compreender como as preferências entre loterias complexas estão relacionadas a preferências entre estados subjacentes nessas loterias;

Para fazer isso, impomos restrições razoáveis sobre a relação de preferências.

L = (p1.C1; p2. C2; ...; pn.Cn)

Restrições sobre Preferências Racionais (3/4)

Axiomas da Teoria da Utilidade:– Ordenabilidade:

(A > B) ( B > A) (A ~ B)

– Transitividade:(A > B) (B > C) (A > C)

– Continuidade:A > B > C p [p,A; 1 – p,C] ~ B

– Substitutibilidade:A ~ B [p,A; 1 – p,C] ~ [p,B; 1 – p,C]

– Monoticidade:A > B ( p q [p,A; 1 – p,B] [q,A; 1 – q,B] )

– Decomponibilidade:[p,A; 1 – p, [q,B; 1 – q,C] ] ~ [p,A; (1 – p)q,B; (1 – p)(1 – q), C]

Preferências que satisfaçam os axiomas garantem a existência de uma função valores reais U, tal que:

– U(A) > U(B) A > B– U(A) = U(B) A ~ B– U (p1.S1; ... ; pn.Sn) = i pi U(Si)

Restrições sobre Preferências Racionais (4/4)

Exemplo:

Supondo um agente com preferências não transitivas (A > B > C >A) , onde A, B e C são bens que podem ser livremente trocados. O agente possui o bem A e recebe uma proposta para trocar C por A oferecendo, quantia em dinheiro pela troca.

Se C > A, então um agente que possui A pagaria 1 centavo para obter CSe B > C, então um agente que possui C pagaria 1 centavo para obter BSe A > B, então um agente que possui B pagaria 1 centavo para obter A

Conclusão: Violação das restrições levam a comportamentos irracionais.

Exemplo: A Utilidade do Dinheiro (1/2)

Um jogador ganhou um prêmio de R$ 1.000.000 em um programa de TV;

Apresentador oferece uma proposta:– Se ele jogar a moeda e aparecer cara jogador perde tudo;– Se aparecer coroa jogador ganha R$ 3.000.000;

Supondo que a moeda é justa o Valor Monetário Esperado (VME) de aceitar proposta é: VME = 0.5 (R$ 0) + 0.5 (R$ 3.000.000) = R$ 1.500.000;

O Valor Monetário Esperado de recusar a proposta é de R$ 1.000.000 (menor);

Isso indica que seria melhor aceitar a aposta ?

Exemplo: A Utilidade do Dinheiro (1/2)

A Utilidade Esperada (EU) para cada uma das duas ações, Sk = riqueza atual do jogador é:

– EU (Aceitar) = 0.5 U(Sk) + 0.5 U(Sk+3.000.000)

– EU (Rejeitar) = U(Sk+1.000.000)

Ação racional: rejeitar !

Calculando a Utilidade Esperada (EU) para cada uma das duas ações temos que a decisão depende do estado de riqueza atual do jogador, uma vez que a utilidade (mudança no estilo de vida) para o primeiro R$ 1.000.000 é muito alta.

Conclusão: a utilidade não é diretamente proporcional ao valor monetário;

Funções de Utilidade Multiatributo

Existem problemas em que resultados são caracterizados por dois ou mais atributos.

Como tratar funções de utilidades com várias variáveis X1, ..., Xn ?Ex.: Construir aeroporto - U(Morte, Barulho, Custo)

Existem basicamente dois casos:

– Decisões podem ser tomadas sem combinar os valores dos atributos em um único valor da utilidade (Dominância);

– A utilidade resultante da combinação dos valores dos atributos pode ser especificada concisamente (Estrutura de Preferência e Utilidade Multi-atributo);

Dominância Total

Se um estado S1 possui valores melhores em todos seus atributos do que S2, então existe uma dominância total de S1 sobre S2;

Exemplo: Local S1 para Aeroporto custa menos, gera menos poluição sonora e é mais seguro que S2;

Dominância total raramente acontece na prática;

Dominância Estocástica

Exemplo: Custo de construir aeroporto , vamos supor :

– Em S1 valor uniformemente distribuído entre $2,8 e $4,8 bilhões;

– Em S2 valor uniformemente distribuído entre $3 e $5,2 bilhões;

Dada a informação que utilidade decresce com custo:– S1 domina estocasticamente S2 Isso não decorre da comparação entre custos

esperados

$

- 2,8-5.2

P

S1

S2

Dominância Estocástica

Na prática, dominância estocástica pode geralmente ser definida usando apenas um raciocínio qualitativo;

Existem algoritmos envolvendo “redes probabilísticas qualitativas” permitindo sistemas de tomada de decisão baseado em dominância estocástica sem usar valor;

Ex.: custo de construção aumenta com a distância para a cidade:– S1 é mais próximo da cidade do que S2 S1 domina S2 estocasticamente

sobre o custo

Estrutura de Preferência e Utilidade Multiatributo

Supondo que existem n atributos com d possíveis valores:– No pior caso, serão necessários dn valores para especificar a função de utilidade

completa;

A Teoria da Utilidade Multiatributo assume que preferências de agentes possuem certa regularidade (estrutura); - A abordagem básica é identificar regularidades no comportamento de preferências; - Tenta mostrar que um agente com certo tipo de estrutura de preferências possui uma função de utilidade do tipo:

U(x1 ... Xn) = f[ f1(x1) ..... fn (xn) ] Onde f seja uma função o mais simples possível

Estrutura de Preferência: Determinista

A regularidade básica que surge em estruturas de preferências determinísticas é chamada Independência de Preferências;

X1 e X2 são preferencialmente independente de X3 :– Se a Preferência entre resultados {x1, x2, x3} e {x1’, x2’, x3} não depende

do valor específico x3 para o atributo X3

– Ex.: {barulho, custo, morte}

{20.000 sofrem; $4,6 bilhões; 0,06 mortes/mhm} vs. {70.000 sofrem; $4,2 bilhões; 0,06 mortes/mhm}

Estrutura de Preferência: Determinista

Independência preferencial mútua (MPI): todos os pares de atributos são preferencialmente independente com relação aos demais;– Ex.: {custo e morte} são preferencialmente independente de barulho

{barulho e morte} são preferencialmente independente de custo

(Debreu, 1960) Com MPI, o comportamento preferencial do agente pode ser descrito como uma maximização da função:

V (x1 ... xn) = i Vi(xi) – Ex.: V(barulho,custo,morte ) = - barulho x 10 - custo - morte x 10¹²⁴

Estrutura de Preferência: Estocástica

Deve-se levar em consideração preferências sobre loterias; ( distribuição de probabilidades sobre um conjunto de resultados reais )

Conjunto de atributo X é independente de utilidade com relação ao conjunto de atributo Y :– Se a preferência sobre loterias em X não dependem dos valores dos atributos em Y

Independência de utilidade mútua (MUI)

Um conjuto de atributos é mutuamente indepentente da utilidade : - Se cada um dos seus subconjuntos de atributos é independente de utilidade dos atributos restantes;

(Keeney, 1974 ) Existe MUI então, comportamento do agente pode ser descrito usando a função:

U = k1U1 + k2U2 + k3U3 + k1 k2U1U2 + k2 k3U2U3 + k3 k1U3U1 + k1k2k3U1U2U3

Estrutura de Preferência: Estocástica

(Keeney, 1974 ) Existe MUI então, comportamento do agente pode ser descrito usando a função:

U = k1U1 + k2U2 + k3U3 + k1 k2U1U2 + k2 k3U2U3 + k3 k1U3U1 + k1k2k3U1U2U3

Em geral, um problema de “n” atributos que exibe MUI pode ser modelado com a utilização de “n” utilidades de um único atributo e “n” constantes

Cada uma das funções utilidades de único atributo pode ser desenvolvida independente e a combinação oferecerá a garantia de gerar preferências globais corretas.

Redes de DecisõesMecanismo geral para tomada de decisões racionaisRepresentam : Estado atual do agente,

suas ações possíveis, estado resultante, e a utilidade desse estado;Extende Redes Bayesianas com ações e utilidades;

– Nós de acaso (ovais): representam variáveis aleatórias;

– Nós de Decisão (retângulo): pontos onde agente deve escolher uma ação;

– Nós de Utilidade (diamantes): representam as funções de utilidade do agente;

As ações são selecionadas pela avaliação da rede

Redes de Decisões

Área A

Nível de TráfegoAéreo

Potencial paraLitígio

Custo daConstrução

U

F(u)=X

Área B

Nível de TráfegoAéreo

Potencial paraLitígio


U

F(u)=Y

EU(A|E) = i P(Resultado(A)|Fazer(A),E) * U(Resultado(A))

V (x1 ... xn) = i Vi(xi)

(Tabela de ação-utilidade)(versão simplificada )

Descrição daUtilidade doAgente

ou

U= k1U1 + k2U2 + k3U3 + k1 k2U1U2 + k2 k3U2U3 + k3 k1U3U1 + k1k2k3U1U2U3

Redes de Decisões

Aplicação do Algoritmo de avaliação:

1. Atribuir os valores das variáveis para o estado corrente;

2. Calcular o valor esperado do nó de

utilidade dado a ação e os valores das variáveis para cada valor possível do nó de decisão;

3. Retornar a ação com maior Utilidade Máxima Esperada

Área A

Morte(3)

Barulho(2)


(200)

U

F(u)=X

Área B

Morte(3)

Barulho(4000)


(150)

U

F(u)=Y

Onde: X > YRetorna : AREA A

f.utilidade = - barulho x 10f.utilidade = - barulho x 10⁴ - custo - morte x 10¹² morte barulho custo f. utilidade

area A 3 2 200 -3.000.000.020.200area B 3 4000 150 -3.000.040.000.150

Teoria do Valor da InformaçãoAté agora, informações fornecidas ao agente antes da tomada de decisão;

A Teoria do Valor da Informação permite que o agente escolha quais informações adquirir;

Exemplo: comprar os direitos de exploração de reservas de petróleo:– Dois blocos A e B, apenas um possui óleo com valor C;– Probabilidade de comprar o bloco certo = 0,5– O preço de cada bloco é C/2;– Consultor oferece uma pesquisa para detectar qual bloco possui petróleo. Qual o valor dessa

informação?Solução:

– Calcular o valor esperado da informação = valor esperado da melhor ação dada a informação – valor esperado da melhor ação sem a informação;

– Pesquisador irá informar: “há óleo em A” ou “não há óleo em A” (p = 0,5)– Então:

0,5 x valor de “comprar A” dado que “há óleo em A” + 0,5 x valor de “comprar B” dado que “não há óleo em A” – 0 == (0,5 x C/2) + (0,5 x C/2) – 0 = C/2

A informação é tão valiosa quanto o próprio bloco

Valor da Informação: Exemplo

A1 e A2 duas rotas distintas através de uma montanha;– A1 e A2 são as únicas ações possíveis, com EU U1 e U2;– A1 = caminho mais baixo, sem muito vento;– A2 = caminho mais alto, com muito vento;– U (A1) > U (A2) !!!

Nova evidência NE produzirá novas utilidades esperadas U1’ e U2’;– Vale a pena adquirir NE?

E se mudássemos o cenário?– II) A1 e A2 são duas estradas onde venta muito, de mesmo tamanho e levamos um ferido

grave;– III) Mesmas estradas A1 e A2 mas agora no verão;

Conclusão: uma informação só terá valor caso ela gere uma mudança de plano, e se esse novo plano for significante melhor do que o antigo !

Sistemas Especialistas

No campo da Análise de Decisões temos a aplicação da Teoria da Decisão a problemas reais (principalmente envolvendo altos riscos);

No início os Sistemas Especialistas concentravam-se em responder perguntas e não em tomadas de decisão;

Hoje temos que os Sistemas Especialistas envolvem um Processo de Engenharia do Conhecimento com etapas definidas e que fornecem as seguintes capacidades:– tomar decisões; – usar valor da informação para decidir se deve adquirir;– calcular a sensibilidade de suas decisões.

Sistemas Especialistas

Um exemplo: ( Selecionar

tratamento médico para doença do coração em

crianças )

Etapas do processo de Engenharia do ConhecimentoCrie um Modelo Causal

1) Determinar ( sintomas, doenças, tratamentos e resultados ); 2) Desenhar arcos ( que doenças causam cada sintoma ); 3) Desenhar arcos ( que tratamentos aliviam os sintomas de cada doença)

Simplifique até chegar a um modelo de decisão qualitativa

Remover variáveis não estão envolvidas em decisões de tratamento

Atribua Probabilidades 1) Pode vir de Banco de Dados de Pacientes; 2) Estudos de Literatura; 3) Avaliação de Especialistas

Atribua Utilidade Criar escala do melhor ao pior resultado: Recuperação Completa = 0 e Morte = -1000

Verifique e Refine o modelo

Necessita conjunto de pares (entrada , saída) --> ( sintomas, solicitar tratamento )

Execute a análise de sensibilidade

Verifica se a melhor decisão é sensível a pequenas mudanças nas probabilidades e utilidades atribuídas

Decisões Complexas

“Métodos para decidir o que fazer hoje, dado que nós poderemos ter que decidir

de novo amanhã”

Problemas de Decisões Seqüenciais

Onde a utilidade do agente depende de uma seqüência de decisões;

Exemplo: (que explica como os problemas de decisão seqüenciais são definidos)

– Interação termina quando agente alcança um dos estados finais (+1 ou -1);– Ações disponíveis: Acima, Abaixo, Esquerda e Direita;– Ambiente totalmente observável;– Ações não confiáveis (locomoção estocástica);

1 2 43

3

2

1 INÍCIO

-1

+1 0.8

0.1 0.1

Processo de Decisão Markoviana (MDP)

É a especificação de um problema de decisão seqüencial para ambiente TO com um modelo de transição de Markov e Recompensas Aditivas

Definido pelos seguintes componentes:– Estado Inicial: S0– Modelo de Transição: T(s,a,s’)– Função de Recompensa: R(s)

Modelo de Transição T(s, a, s’): probabilidade de chegar a s’ como resultado da execução da ação a em s;

Hipótese de transições Markovianas: próximo estado depende apenas da ação atual e estado atual, não passados;

Em cada estado s agente recebe uma Recompensa R(s):– R(s) = -0.04 para todos estados não terminais;– Dois estados finais R(s) = +1 ou R(s) = -1;– Utilidade é a soma das recompensas recebidas;– Exemplo: Se Agente alcançar +1 em “10” passos Teremos ( 1 - ( 0,04 x 10 ) ) Então a U = 0,6

Processo de Decisão Markoviana (MDP)

EXEMPLO

A manutenção de um equilíbrio cuidadoso entre Risco e Recompensa é uma das características dos MDP’s

Problema Estados Ações RecompensasAgente jogador de damas

Configurações do tabuleiro

Mover uma determinada peça

Capturas - Perdas

Agente em jogo de luta

Posições / energia dos lutadores, tempo, se está sendo atacado ou não etc...

Mover-se em uma determinada direção, lançar, magia, bater etc..

(sangue tirado - sangue perdido)

Agente patrulhador

Posição no mapa (atual e passada)

Ir para algum lugar vizinho do mapa

Ociosidade (tempo sem visitas) do lugar visitado atualmente

Como são as soluções para esse problema?

Seqüência fixa de ações não resolvem o problema;

Uma solução deve especificar o que o agente deve fazer em qualquer um dos estados que ele possa chegar: – Política: (s) = ação recomendada para estado s

Política Ótima: – Política que produz a mais alta utilidade esperada;– Notação: *

1 2 43

3

2

1

-1

+1

Funções de Utilidade para Problemas Seqüenciais

Soma das recompensas é uma escolha para medida de desempenho do agente;

Outras escolhas possíveis podem ser escritas por: Uh ([s0, s1, ... , sn])

Como definir funções de utilidades para problemas seqüenciais?Deve-se responder as seguintes perguntas:

• O Horizonte Temporal para a tomada de decisão é Finito ou Infinito ?• Como calcular a utilidade de uma seqüência de estados ?


O Horizonte Temporal para a tomada de decisão é Finito ou Infinito ?

Exemplo.: – Supondo que o agente inicia em (3,1)– N = 3 para atingir +1 agente deve executar ação Acima– N = 100 tempo suficiente para executar ação Esquerda (rota mais segura)


Como calcular a utilidade de uma seqüência de estados ?Pode ser visualizado como uma questão de Teoria da

Utilidade Multiatributo onde: Cada “si“ é visualizado como um atributo da

seqüência de estados [so,s 1,...,s n]

Baseado no princípio estacionariedade, existem apenas duas maneiras de atribuir utilidades a seqüência de utilidades:– Recompensas aditivas;– Recompensas descontadas;

Recompensas

Recompensas Aditivas:– Uh ([s0, s1, ... , sn]) = R(s0) + R(s1) + R(s2) + ...

Recompensas Descontadas:– Uh ([s0, s1, ... , sn]) = R(s0) + R(s1) + 2 R(s2) + ...– Onde é chamado fator de desconto com valor entre 0 e 1;

Fator de desconto:– Descreve a preferência de um agente com relação a recompensas atuais

sobre recompensas futuras; próximo a 0 recompensas no futuro distante são irrelevantes; = 1 recompensa aditiva;

Algoritmo de Iteração de Valor (1/3)

A idéia básica do algorítmo é: calcular a utilidade de cada estado e depois empregar as utilidades de estados para selecionar uma ação ótima;

Proposto para calcular uma política ótima;

A Utilidade de cada estado é definida em termos da utilidade das seqüências de ações que podem se seguir a partir dele;

Equações de Bellman (1957) são a base do algoritmo de Iteração de valor para resolver MDPs;

Se houver n estados possíveis, então haverá n equações de Bellman, uma para cada estado.


Utilidade de um estado, dada pela equação de Bellman,é a recompensa imediata correspondente a este estado R(s), somada à utilidade descontada esperada do próximo estado, supondo que o agente escolha a ação ótima.

U(s) = R(s),+ maxa s’ T(s,a,s’) U(s’)

Algoritmo:

1. Inicializar utilidades com valores iniciais arbitrários (tipicamente 0);

2. Calcular o lado direito da equação para cada estado;3. Atualizar valor da utilidade de cada estado;4. Continuar até convergir para um único conjunto de

soluções


Exemplo: U(1,1) = -0.04 + max

(Acima) { 0.8 U(1,2) + 0.1 U(2,1) + 0.1 U(1,1),

(Esquerda) 0.9 U(1,1) + 0,1 U(1,2),

(Abaixo) 0.9 U(1,1) + 0.1 U(2,1),(Direita) 0.8 U(2,1) + 0.1 U(1,2) + 0.1 U(1,1) }

1 2 43

3

2

1

0.812

0.762

0.705

0.812 0.918

0.660 -1

+1

0.655 0.611 0.388

•Utilidades dos estados no mundo 4 x 3, calculadas com y = 1 e R(s)= -0,04 para estados não terminais.

•Note que: as utilidades são mais altas para estados mais próximos à saída, porque são necessários menos passos para alcançar a saída.

Algoritmo de Iteração de política (1/2)

A idéia básica do algorítmo é: se uma ação é claramente melhor que todas as outras, então a magnitude exata das utilidades nos estados envolvidos não precisa ser exata;

Essa idéia sugere um caminho alternativo para encontrar políticas ótimas;

O algoritmo alterna entre as duas etapas a seguir, iniciando a partir de uma política inicial 0:

1. Avaliação da Política: dada política i , calcular Ui = U i , se i tivesse de ser executada;

2. Aperfeiçoamento da Política: calcular nova política UMEi+1, utilizando a observação

antecipada de um passo baseada em Ui.

Algoritmo encerra quando o passo Melhora da Política não produz nenhuma mudança nas utilidades;

Algoritmo de Iteração de política (2/2)

Equação de Bellman para avaliar a utilidade de um estado:

Ui(s) = R(s) + s’ T(s, i(s), s’) Ui(s’)

Exemplo: Supondo que i seja a política mostrada na figura ao lado. Então, para os estados (1,1) e (1,2), temos i(1,1) = Acima, i(1,2) = Acima, conforme demonstrado e, assim por diante:

Ui (1,1) = 0.8 Ui(1,2) + 0.1 Ui(1,1) + 0.1 Ui(2,1)

Ui (1,2) = 0.8 Ui(1,3) + 0.2 Ui(1,2) ,

.

.

.1 2 43

3

2

1

-1

+1

MDPs Parcialmente Observáveis (POMDPs) (1/3)

Os MDPs assumem que o ambiente é totalmente observável e a política ótima depende apenas estado atual;

Em ambientes parcialmente observáveis o agente não sabe necessariamente onde ele está, portanto:

• Não pode executar a ação (s) recomendada para esse estado;• A utilidade de um estado s e a ação ótima no s depende não só de s, mas

também do quanto o agente sabe quando está em s;

Por esta razão: • MDPs em ambientes parcialmente observáveis (POMDPs) em geral são

muito mais difíceis;• Não podemos evitá-los o mundo real é um deles.


Os POMDPs possuem os mesmo elementos de um MDPs acrescentando apenas:

• O Modelo de Observação: O(s, o), o qual especifica a probabilidade de perceber a observação o no estado s;

Estado de crença = conjunto de estados reais em que o agente pode estar.

Em POMDPs um estado de crença b, é uma distribuição probabilística sobre todos os estados possíveis:• Exemplo:

Para o mundo 4 x 3 o estado de crença inicial poderia ser descrito como:

{1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 0, 0}

b(s) denota a probabilidade atribuída ao estado s pelo estado de crença b;


Em POMDPs:

Uma ação altera tanto o estado físico quanto o estado de crença;

O valor da informação é incluído como componente do processo de decisão;

A ação ótima depende apenas do estado de crença atual do agente, ou seja, não depende do estado real em que ele se encontra;






Agente de teoria da decisão (1/2)

Agente da Teoria da decisão:• Pode tomar decisões racionais baseado no que acredita e deseja;• É capaz de tomar decisões em ambientes onde incertezas e objetivos conflitantes

deixariam um agente lógico sem poder decidir;• Possui uma escala contínua de medida de qualidade sobre os estados;

Pode ser construído para um ambiente POMDP usando Redes de Decisões Dinâmicas para:• Representar os modelos de Transição e Observação;• Atualizar o Estado de crença;• Projetar possíveis seqüências de ações;

Decisões são tomadas projetando para frente possíveis seqüências de ações e escolhendo a melhor;

Agente da teoria da decisão (2/2)

Escolhedor de ação

Am

bie

nte

Sensores

Atuadores

Modelo dosambientes(passados)

e atual

Interpretador de percepçõesRegras: percepção(t) modelo(t-1) modelo(t)

Atualizador do modelo do ambienteRegras: modelo(t) modelo(t)

Atualizador dos objetivosRegras: modelo(t) objetivos(t-1) objetivos(t)

Objetivos

t))objetivos(|])o([U(resultad

ação

faz( açãoaçãoargmax i

ni

i

1i

1

Utilidadesu:modelos x objetivos R

Iteração de Valor (diagrama de classe)

AçãoTransição

Probabilidade () : probabilidade

Iteração Valor

Utilidade ( estado: estado, maxerror: Int ) : utilidadeGama : descontoDelta : int

MDPEstados

FuncaoUtilidade : utilidadeFuncaoRecompensa : recompensa

Iteração de Política (diagrama de classe)

AçãoTransição

Probabilidade () : probabilidade

Iteração Valor

Política ( estado: estado ) : políticaPi : política

MDPEstados

FuncaoUtilidade : utilidade

Documents

Teoria da Decisão Métodos de Computação Inteligente Universidade Federal de Pernambuco Centro de Informática – Cin Maria Uilma Rodrigues dos Santos de