lnteligência Artificial

Transcrição

lnteligência Artificial
Introdução ao Processo
Decisório de Markov
Aprendendo em Ambientes Estocásticos
O resultado (próximo estado) não depende apenas
do estado atual e da ação do agente (estocástico)
Outros fatores influenciam de modo não plenamente
conhecido e por isso não diretamente modeláveis
o estado atual e a ação tomada definem um
conjunto de possíveis estados sucessores com as
respectivas probabilidades
Inteligência Artificial
CTC-17
Problema de Decisão Sequencial
1.
2.
3.
4.
O problema de decisão sequencial ocorre quando a cada passo o
agente deve:
Observar o estado do sistema;
Escolher e realizar uma ação;
(Sistema evolui para um novo estado)
Observa um reforço imediato
Repetir os passos 1 – 3
Assume-se tempo discreto
CTC-17
Exemplo
CTC-17
Exemplo - 2
CTC-17
Processo Decisório de Markov
Método de decisão para problema de decisão sequencial
com modelo de transição Markoviano e reforços aditivos
O qualificador Markov significa que as transições
dependem de um subconjunto dos últimos estados e da
ação selecionada.
CTC-17
Definição formal de um PDM
CTC-17
Definição formal de um PDM - 2
CTC-17
Definição formal de um PDM - 3
CTC-17
Exemplo 1: Controle de Inventário
Problema: comprar uma quantidade de um certo
produto a intervalos regulares (em um total de N
intervalos) de modo a satisfazer uma certa demanda
Estado: sk = estoque no começo do período k
Ação: ak = compra feita no começo do período k
Uma perturbação aleatória wk = demanda no período k,
respeitando uma certa distribuição de probabilidade
Reforço rk = r(sk) + cak, onde r(sk) é o custo de estocar sk
unidades do produto no período k e c é o custo unitário
do produto comprado.
10
CTC-17
Exemplo 1: Controle de Inventário
Evolução do estado: sk+1 = sk + ak - wk
Função de custo a ser minimizada:
11
CTC-17
Exemplo 2: Pêndulo Invertido
+F
-F
Problema: controlar um pêndulo invertido
exercendo forças +F ou -F sobre a base do
carrinho (controle bang-bang). “Controlar”
significa não permitir que a barra caia ou que o
carrinho choque-se com as paredes.
12
CTC-17
Exemplo 2: Pêndulo Invertido
(
)
Estado: quádrupla
xt , x&t ,θ t ,θ&t
Ação: +F ou -F
Reforço: -1 em caso de falha, senão 0.
Evolução do estado: sk+1 = f(sk , ak) (?)
Possível função de custo a ser minimizada:

k 
V (so ) = E ∑ γ rt 
 t =0

∞
desconto temporal γ < 1: POR QUÊ?
13
CTC-17
O que é uma solução para um Problema
de Markov?
Uma
sequencia de ações (plano)
pode resolver um ambiente
Estocástico?
Políticas (ou Estratégia) versus
Planos…Formalização
CTC-17
Exemplo MDP
Descrição: Controle de Movimentação de robô
modelado como um PDM
No início, robô está em l1
Objetivo é levar o robô até l4
Robô pode “deslizar” ao tentar se mover de uma posição
para outra
CTC-17
Exemplo MDP
CTC-17
Exemplo MDP - 2
CTC-17
Exemplo MDP - 3
CTC-17
Exemplo MDP - 4
CTC-17
O que é uma solução para o problema?
Uma sequencia fixa de ações ou plano NÃO é
capaz de resolver o problema de modo
confiável…
É necessário uma função que mapeie estados
para ações. Esta função geralmente é chamada
de estratégia ou politica
CTC-17
Exemplos de Políticas – Problema 1
CTC-17
Exemplos de Políticas – Problema 2
CTC-17
Estado inicial
Para cada estado s, há um
probabidade P(s) do
sistema iniciar no estado s
Por simplicidade, vamos
considerar que existe um
estado inicial s onde:
CTC-17
Histórico de Estados
CTC-17
Exemplo – Histórico de Estados
CTC-17
Exemplo – Histórico de Estados - 2
CTC-17
Exemplo – Histórico de Estados - 3
CTC-17
Qualidade de Políticas
Em um PDM com transicões não deterministicas, Uma
política pode garantir alcançar sempre o estado objetivo
em um determinado número de passos ou custo ?
Como definir quando uma política é melhor que outra?
Chegar ao estado objetivo é o bastante?
É necessário uma forma de medir a qualidade de uma
dada política. Como ?
CTC-17
Qualidade de Políticas - 2
Qual o valor de uma política? Valores são na
verdade associados a históricos…
Mas como vimos, políticas induzem uma distribuição
de probabilidades sobre históricos. Assim…
Essa qualidade (ou utilidade) pode ser medida
através do valor esperado da adoção de uma
política.
CTC-17
Política Ótima
CTC-17
Funções de Utilidade pode incluir retornos negativos
(Custo) e positivos (Recompensa)
CTC-17
Exemplo
CTC-17
Recompensa descontada
O tempo deveria influenciar o valor de recompensa?.....
Uma recompensa de 100 dolares hoje é tão boa, quanto uma recompensa de 100
dólares daqui a seis meses?
Para problemas com tempo infinito, é fundamental ter recompensas descontadas….
Porquê?
CTC-17
Fator de Desconto
CTC-17
Otimalidade de Políticas
A maximização do valor esperado é o critério mais
utilizado para determinar otimização de políticas.
Entretanto, isso é dependente do número de passos
(decisões) que o agente dispõe para agir. Isto é
comumente chamado de horizonte de tomada de
decisão.
O horizonte pode ser finito ou infinito
CTC-17
MDP de Horizonte Finito e Políticas
Estacionárias
CTC-17
Políticas Estacionárias e Horizonte
Infinito
CTC-17
Como comparar políticas em Horizontes
Infinitos
Há tres possibilidades:
CTC-17
Política Ótima
Então já sabemos o que é uma política ótima...
Como encontrar uma politica ótima dado um MDP ?
CTC-17
Algoritmo para cálculo de política ótima
CTC-17
Algoritmo: Iteração de valor
(Value Iteration)
CTC-17
Algoritmo: Iteração de valor
(Value Iteration) - 2
CTC-17
Exemplo Deterministico – Função de Valor
CTC-17
Exemplo - 2
CTC-17
Calculando V(s)
Início com valores nulos
CTC-17
Discussão da Iteração de Valor
Algoritmo de Iteração de valor computa um novo valor a cada
iteração e escolhe a política baseado nesses valores
Este algoritmo converge em número de iterações em tempo
polinomial do número de estados
O número de estados geralmente é muito grande em problemas
reais
É necessário examinar o espaço inteiro em cada iteração
Por tal razão, o algoritmo demanda grande quantidade de tempo
e espaço
Além disso, a função de transição propabilística p e os retornos
devem ser conhecidos, mas muitas vezes não é este o caso!
CTC-17
A equação de Bellman e o algoritmo de
Iteração de Valor
Vimos que uma política ótima é aquela que
maximiza o valor esperado de seguir de tal política a
partir de um estado inicial. Formalmente:
CTC-17
Equações de Otimalidade de Bellman
Uma política ótima é uma política, logo:
Para reforços determinísticos, fica:
Considere os seguintes operadores de Programação Dinâmica
CTC-17
Teoremas de Programação Dinâmica
É possível demonstrar que a função V* é o ponto fixo do operador T
(Equação de otimalidade de Bellman), ou
Também é possível demonstrar que para uma dada política µ, a
função Vµ é a única função limitada que satisfaz
CTC-17
Algoritmos para MDP
O algoritmo de Iteração de valor, nada mais é do
que a aplicação recursiva do operador T, a uma
aproximação inicial arbitrária V0
CTC-17
Outro algoritmo para MDP: Iteração de
Política
CTC-17
Outro Exemplo Gridworld
CTC-17

lnteligência Artificial

Transcrição

Documentos relacionados

Não há um movimento terrorista gerido por computadores

Inteligência Artificial

Resolução RDC nº 56 2009

BRAIN. Broad Research in Artificial Intelligence and

Mídias móveis, vida artificial

Apresentação do PowerPoint

Dome File - Portal Geo Brasil

File - Unidade de Cuidados Paliativos do Hospital de Seia

Agentes ou Jogadores? Os monstros estranhamente reais dos

No 2 - Março / 2000 - Clube Excursionista Carioca

Neve Artificial