Métodos de programação dinâmica para solução de problemas de
planejamento probabilístico
• M2 - Um estado inicial s0 ∈ S 1
Renato Schattan Pereira Coelho e
Leliane Nunes de Barros (Orientadora)
• M3 - Um conjunto não vazio de estados meta,
SG ⊆ S
Universidade de São Paulo (USP), Brasil
[email protected], [email protected]
• M4 - Os estados em SG são absorventes, ou seja,
as ações tomadas nestes estados não têm custo
e não levam para estados fora deste conjunto
1. Introdução
• M5 - Um conjunto de ações A e subconjuntos
de ações A(s) denidos para todos os estados
s∈S
Quando estudamos a tomada automática de decisão
um problema comum é o de ir de uma conguração inicial do mundo para uma conguração desejada com o menor custo esperado. Se queremos
resolver um problema deste tipo costumamos usar
um modelo chamado de caminho estocástico mínimo (Shortest Stochastic Path - SSP). Este modelo é baseado nos Processos markovianos de decisão
(Markov Decision Processes - MDP), com algumas
diferenças que o tornam mais interessante computacionalmente e mais natural para modelar este tipo
de problema.
Neste artigo revisaremos os algoritmos que representam o estado da arte na resolução deste tipo de
problema e apontaremos o caminho que está sendo
seguido nesta pesquisa. A base para os algoritmos é o Real-Time Dynamic Programming (RTDP),
que apresenta uma tática eciente para atualização
assíncrona do valor dos estados. A partir desta
tática, surgem dois algoritmos: o Labeled RealTime Dynamic Programming (LRTDP), que apresenta uma maneira interessante de marcar os estados
para aumentar a velocidade de convergência do algoritmo e o Bounded Real-Time Dynamic Programming (BRTDP), que utiliza duas heurísticas para
ajudar na escolha dos estados que devem ser atualizados e para saber quando a política convergiu.
• M6 - Distribuições de probabilidades P (·|s, a)
sobre os estados pertencentes a S dado que uma
ação a ∈ A(s) foi tomada no estado s ∈ S .
• M7 - Um custo, c(a, s), não negativo associado
a se executar a ação a no estado s
• M8 - Os estados são totalmente observáveis
Neste modelo, o tempo é discreto e o agente deve
escolher uma ação em cada instante do tempo. Também é importante, para garantir propriedades dos
algoritmos, que todos os estados tenham uma probabilidade não nula de alcançar algum estado meta.
Dado este modelo, o objetivo do agente é escolher, para cada estado alcançável a partir dos estados
iniciais, a ação que minimiza o valor esperado dos
caminhos até algum estado meta. Isto equivale a
criar uma política, ou seja, uma função π : S → A
que associa a cada estado a melhor ação.
Dado um problema modelado desta maneira podemos calcular recursivamente o custo esperado da execução de uma política a partir de um estado até a
meta (V π (s))2 como:
V π (s) = c(π(s), s) +
2. Caminho estocástico mínimo
X
P (s0 |s, π(s)) ∗ V π (s0 )
s0 ∈S
O valor ótimo de um estado (V ∗ (s)) é o único ponto
xo da equação de Bellman [9]:
Baseado em um modelo muito conhecido, o dos
MDPs (uma boa descrição deste modelo pode ser
encontrada em [7]), foi criado um modelo chamado
SSP, que nos dá uma base formal para os problemas
em que estamos interessados (ir de um conjunto de
estados a outro com o menor custo esperado). Este
modelo tem as seguintes características [2]:
V (s) = min (c(a, s) +
a∈A(s)
X
P (s0 |s, a) ∗ V (s0 ))
s∈S 0
1 Podemos estender a denição para um conjunto não vazio
de estados S0 ⊆ S , sem grandes mudanças nos algoritmos.
2 Neste texto, para simplicar, chamaremos o custo esperado de um caminho a partir de um estado até a meta de valor
de um estado.
• M1 - Um conjunto de estados (S ) nito ou con-
tável
95
Assim, a política ótima (π ∗ (s)) é dada por:
π ∗ (s) = argmin(c(a, s) +
X
a∈A(s)
s∈S 0
• Se os valores dos estados forem inicializados
de maneira correta, um número sucientemente
grande de simulações nos deixará com V π (s) =
V ∗ (s).
P (s0 |s, a) ∗ V ∗ (s0 ))
No artigo original [1] não se deniu uma condição
de parada para esta técnica, entretanto, para que
pudessem ser realizadas comparações com outros algoritmos, considera-se que o algoritmo pára quando
o estado inicial já convergiu. A convergência de um
estado será discutida adiante.
Pela denição, V π (s) = V ∗ (s) = 0, para todo estado pertencente a SG . Este valor pode ser usado
como base da recursão no cálculo dos valores dos outros estados. Abaixo veremos os algoritmos que são
considerados como estado da arte para a resolução
de problemas neste modelo. Todos eles
4. Programação dinâmica em tempo
real com marcações
3. Programação dinâmica em tempo
real
O que torna o RTDP tão poderoso é também sua
grande falha. Escolher o estado que terá seu valor atualizado de acordo com P (·|s, a) faz com que o valor
de V π (s) se aproxime rapidamente de V ∗ (s). Entretanto, a convergência do algoritmo é muito lenta,
dado que os estados que têm pouca probabilidade de
serem alcançados demoram para ter seu valor atualizado e, consequentemente, demoram para convergir.
A maneira encontrada pelo Labeled Real-Time Dynamic Programming (LRTDP) [2] para aumentar a
velocidade de convergência do RTDP é marcar como
resolvidos os estados que já tenham um valor sucientemente próximo ao valor ótimo. Para isto utilizamos o erro de Bellman, denido como:
A base para os algoritmos que representam o estado
da arte na resolução de SSPs é o Real-Time Dynamic
Programming (RTDP) [1], que é uma maneira eciente de atualizar os valores dos estados de maneira
assíncrona. Como utilizaremos os valores dos estados muitas vezes, todos os algoritmos utilizam a técnica de programação dinâmica, armazenando o último valor calculado para um estado em V π (s).
A idéia básica do RTDP é fazer várias simulações
da execução da política e atualizar o valor dos estados ao mesmo tempo em que a política é atualizada.
A política escolhida pelos algoritmos é a política gulosa (πV ), dada por:
πV := argmin(c(a, s) +
a∈A(s)
X
P (s0 |s, a) ∗ V π (s0 ))
E(s) := |V π (s)− min (c(a, s)+
a∈A(s)
s∈S 0
X
P (s0 |s, a)∗V π (s0 ))|
s0 ∈S
que representa a diferença entre o valor armazenado
para um estado e o novo valor que será obtido através
da escolha gulosa de ação.
Embora para SSPs não haja uma maneira fácil
de calcular a distância entre o valor ótimo de um
estado e o valor atual a partir do erro de Bellman, ele
nos indica quando a função não está variando muito.
Assim, o LRTDP marca os estados como resolvidos
quando o erro de Bellman é menor do que algum >
0 para o estado e para todos os estados alcançáveis a
partir dele através da política gulosa. Se, ao nal da
execução do algoritmo, o valor encontrado para os
estados estiver muito longe do valor ótimo, podemos
rodar novamente o algoritmo com um menor que o
inicial.
A existência de loops impossibilita uma tática
mais intuitiva, que marque os estados como resolvidos quando os seus sucessores já tiverem sido marcados, uma vez que este esquema deixaria de marcar
alguns estados que já tivessem convergido.
Para tentar marcar um estado como resolvido o
LRTDP usa o método checkSolved 1. Esse método
Cada simulação começa no estado inicial e pára
quando chega a algum estado meta. Dado um estado, o próximo estado a ser visitado é dado diretamente por P (·|s, πV (s)). O valor de V π (s) é atualizado de acordo com a nova política antes de se passar para o próximo estado.
Esta maneira de escolher quais estados terão seu
valor atualizado é muito poderosa porque os estados que inuenciam mais no valor da esperança são
atualizados mais vezes.
Este algoritmo tem algumas propriedades interessantes [1]:
• Cada uma das simulações termina em um
número nito de passos.
• Se os valores de V π (s) forem monotônicos e admissíveis (menores que V ∗ (s)) quando inicial-
izados, essas propriedades se mantêm ao longo
das atualizações dos valores de V π (s).
• As atualizações de um estado não diminuem o
valor de V π (s).
96
faz uma busca em profundidade nos estados que podem ser alcançados, através da política gulosa, a partir do estado que se está testando. Quando visitamos
um estado temos três situações possíveis: o estado
pode ser um estado meta, o erro de Bellman do estado pode ser menor ou igual a ou o erro de Bellman
pode ser maior do que . Quando a busca encontra
um estado meta ela termina a busca naquele ramo
e muda de ramo. Quando a busca encontra estados
que tenham o erro de Bellman menor ou igual a ela põe seus sucessores em uma pilha e continua a
busca naquele ramo. E quando a busca encontra um
estado que tenha o erro de Bellman maior do que o
algoritmo sabe que o estado estudado não convergiu,
mas por questões de eciência ele continua a busca
em outro ramo.
Assim, após uma chamada à checkSolved temos
duas possibilidades: ou nenhum dos estados visitados tinha o erro de Bellman maior do que e então,
por denição, o estado e todos os seus sucessores
convergiram e podem ser marcados ou existia pelo
menos um estado com erro de Bellman maior do que
e, quando os valores dos estados forem atualizados na ordem reversa em que foram visitados, pelo
menos um estado (o que tinha erro de Bellman maior
do que ) terá seu valor modicado em mais do que
.
Dessa maneira, podemos resolver um SSP simplesmente chamando a função checkSolved para o
estado inicial até que ele tenha P
convergido. Este
método não fará mais do que −1 s∈S V ∗ (s) − h(s)
chamadas à função checkSolved, em que h(s) é a
heurística utilizada para inicializar os valores de
V π (s).
Entretanto, como o estado inicial está muito longe
da meta, ele demora para convergir e não podemos
marcar os outros estados como resolvidos até que
ele tenha convergido. Assim, não aproveitamos o
esquema de rotulação dos estados.
Por esta razão o LRTDP implementa um outro
método (LRTDPTrial 2) que é muito similar às simulações realizadas pelo RTDP. Existem duas diferenças: os estados visitados são guardados em uma
pilha e, quando a simulação atinge um estado meta
ou um estado que já tenha convergido,a simulação
pára e chama-se o método checkSolved para os estados, enquanto eles são desempilhados. Quando algum estado retorna falso outra simulação é iniciada.
Utilizando estes dois métodos temos uma maneira
eciente de vericar se os estados já convergiram e
conseguimos aumentar a velocidade de convergência
do algoritmo, já que os estados com pouca probabilidade de serem alcançados serão visitados nas
chamadas à checkSolved.
Algoritmo 1: checkSolved
Entrada: Um SSP, ,s
Saída: Verdadeiro se s tiver convergido, falso
c.c.
1 resposta = verdadeiro
2 aberto = P ilhaV azia
3 f echado = P ilhaV azia
4 se ¬s.M arcado então aberto.push(s)
5 enquanto aberto 6= P ilhaV azia faça
6
s = aberto.pop()
7
f echado.push(s)
8
//verica o erro de Bellman
9
se s.erro(a) > então
10
resposta = f also
11
continue
12
m se
13
//expande o estado
14
a = s.acaoGulosa()
15
para todo s0 tal que P (s0 |s, a) > 0 faça
16
se ¬s0 .M arcado e ¬Em(s0 , aberto ∪
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
97
f echado) então
aberto.push(s0 )
m se
m para todo
se resposta = verdadeiro então
//marca os estados alcançáveis a partir
da política gulosa
para todo s ∈ f echado faça
s.M arcado = verdadeiro
m para todo
m se
senão
enquanto f echado 6= P ilhaV azia faça
s = f echado.pop()
s.update()
m enqto
m se
m enqto
Resultado: resposta
Algoritmo 2: RTDPTrial
Entrada: Um SSP, ,s
1 visitados = P ilhaV azia
2 enquanto ¬s.M eta() faça
3
//põe o estado na pilha
4
visitados.push(s)
5
//simula a execução da política
6
7
8
9
10
11
12
13
atualiza o estado
V U (s) = min (c(a, s) +
a∈A(s)
V L (s) = min (c(a, s) +
a∈A(s)
gulosa e
m enqto
enquanto visitados 6= P ilhaV azia faça
m enqto
P (s0 |s, a) ∗ V U (s0 ))
s0 ∈S
X
P (s0 |s, a) ∗ V L (s0 ))
s0 ∈S
Assim como no RTDP e no LRTDP as atualizações dos estados preservam a monotonicidade e a admissibilidade das heurísticas, o que nos mostra que
o algoritmo pára após um número nito de simulações e que ele não precisa visitar todos os estados
em S e, muitas vezes, também não precisa visitar todos os estados alcançáveis a partir de s0 seguindo a
política gulosa (principalmente quando há uma probabilidade muito baixa de transição para estes estados) [8].
O ponto fraco deste algoritmo é o cálculo da
heurística superior. É muito fácil calcular uma
heurística inferior para V ∗ (s), por exemplo, tomando
h(s) = 0 ou h(s) = mina∈A(s) c(a, s). Entretanto, o
cálculo de uma heurística superior pode fazer com
que o algoritmo tenha que visitar todo o espaço de
estados [8]. Assim, muitas vezes o custo de se calcular uma heurística superior é maior do que os ganhos
de se utilizar o BRTDP.
a = s.acaoGulosa()
s.update()
s = s.escolhaP roximoEstado(a)
s = visitados.pop()
se ¬checkSolved(s, )
X
então break
5. Programação dinâmica em tempo
real com limitantes
A principal característica do Bounded Real-Time
Dynamic Programming (BRTDP) [8] é manter duas
heurísticas do valor do estado, uma inferior (V L (s),
similar à V π (s)) e uma superior (V U (s)). Utilizando
estas duas heurísticas e analisando a diferença entre
elas o algoritmo consegue: melhorar a maneira de
selecionar os estados que terão seus valores atualizados, facilitar a vericação da distância entre o valor
da heurística e o valor ótimo do estado e diminuir o
número de estados que precisam ser visitados.
Neste algoritmo o conceito de convergência de um
estado é diferente do utilizado no LRTDP. Neste
caso, consideramos que um estado convergiu quando
a diferença entre a heurística superior e a inferior é
menor do que algum > 0. Neste caso sabemos que
quando um estado convergiu a nossa estimativa do
valor do estado não tem um erro maior do que em
relação ao valor ótimo.
O BRTDP utiliza um algoritmo muito parecido
com o do RTDP. A sua principal função é uma simulação da execução da política gulosa (em relação à
heurística inferior). Entretanto, a escolha do próximo estado a ser atualizado é feita através do valor
normalizado de P (s0 |s, a)∗(V U (s0 )−V L (s0 )) e a simulação pára quando se atinge um estado meta ou
quando se atinge um estado que já tenha convergido.
O algoritmo pára de fazer simulações quando o estado inicial já convergiu, ou seja, V U (s0 )−V L (s0 ) <
.
As atualizações de V U (s) e V L (s) são feitas da
mesma maneira que as atualizações de V π (s), isto é:
6. Considerações nais
Neste artigo mostramos um modelo muito interessante, o SSP, que modela de maneira eciente os
problemas nos quais queremos ir de uma conguração inicial a uma conguração nal do mundo com
o menor custo esperado. Modelar o problema desta
maneira possibilita que, muitas vezes, nem todos
os estados do mundo sejam visitados, gerando uma
grande economia de tempo em relação aos resolvedores de MDPs. Entretanto, frequentemente temos
diculdades em modelar um problema com probabilidades precisas de transição. Por isso, nesta iniciação
cientíca o aluno está estudando um modelo recentemente criado [5] que estende o SSP ao possibilitar que sejam fornecidos intervalos de probabilidade
para as transições entre estados. Durante a iniciação cientíca pretendemos adaptar o LRTDP para
que ele resolva problemas deste novo modelo SSPST
(Shortest Stochastic Path with Set Transitions ).
O RTDP apresenta uma técnica muito importante
e atualmente bastante difundida para escolher quais
estados devem ter seu valor atualizado. Entretanto,
esta mesma tática faz com que ele tenha uma convergência demorada. Assim, se quisermos impor um
limite curto de tempo para processamento, o RTDP
pode nos dar uma resposta melhor que os outros algoritmos, mas se quisermos uma resposta ótima (ou
98
sub-ótima) o RTDP levará mais tempo do que os
outros algoritmos.
O LRTDP se aproveita da técnica do RTDP e implementa uma função que marca os estados como
resolvidos para que eles não precisem ser visitados
novamente. Essa função gera um pequeno overhead
e, por isso, o LRTDP costuma devolver políticas um
pouco piores do que o RTDP, quando o tempo de
execução é curto. Entretanto, a velocidade de convergência é extremamente maior do que a do RTDP.
O BRTDP tem três propriedades interessantes: a
facilidade de vericar se um estado convergiu ou não;
o número reduzido de estados que precisam ser visitados (mesmo quando comparado com o RTDP e o
LRTDP que também não precisam visitar todo o espaço de estados); e a técnica aprimorada de seleção
de estados que devem ser atualizados, que favorece
os estados sobre os quais se tem pouca informação,
além dos que têm grande probabilidade de serem alcançados.
Apesar destas propriedades, o custo de se calcular
uma heurística superior pode facilmente fazer com
que o algoritmo deixe de ser interessante quando
comparado com os outros.
[9] Richard E. Bellman, Dynamic Programming, Princeton
University Press, 1957.
[10] Stuart Russel and Peter Norvig, Articial Intelligence: A
Modern Approach, Prentice Hall, Englewood Clis, New
Jersey, 1995.
Esta pesquisa conta com o apoio da FAPESP através do
processo 2008/04728-0.
Referências
[1] Andrew G. Barto, Steven J. Bradtke, and Satinder P.
Singh, Learning to Act Using Real-Time Dynamic Programming, Articial Intelligence 72 (1995), 81138.
[2] Blai Bonet and Héctor Gener, Labeled RTDP: Improv-
ing the Convergence of Real-Time Dynamic Programming, International Conference on Automated Planning
and Scheduling, 2003, pp. 1221.
[3] Craig Boutilier, Thomas Dean, and Steve Hanks,
Decision-Theoretic Planning: Structural Assumptions
and Computational Leverage, Journal of Articial Intelligence Research 11 (1999), 194.
[4] Dana S. Nau, Malik Ghallab, and Paolo Traverso, Automated Planning: Theory and Practice, Morgan Kaufmann Publishers, 2004.
[5] Felipe W. Trevizan, Fabio G. Cozman, and Leliane N.
Barros, Planning under Risk and Knightian Uncertainty,
International Joint Conference on Articial Intelligence,
2007, pp. 20232028.
[6] Felipe W. Trevizan, Um modelo unicado para planejamento sob incerteza, Instituto de Matemática e Estatística, São Paulo, 2006.
[7] Martin L. Puterman, Markov Decision Processes - Discrete Stochastic Dynamic Programming, John, Wyley
and Sons, Inc., 1994.
[8] H. Brendan McMahan, Maxim Likhachev, and Georey
J. Gordon, Bounded Real-Time Dynamic Programming:
RTDP with monotone upper bounds and performance
guarantees, International Conference on Machine Learning, 2005, pp. 569576.
99