Algoritmos eficientes para o problema do orçamento mínimo em processos de decisão Markovianos sensíveis ao risco (2018)
- Authors:
- Autor USP: MOREIRA, DANIEL AUGUSTO DE MELO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: CIENCIA DA COMPUTACAO
- Keywords: Markov decision process; Planejamento probabilístico; Probabilistic planning; Processos de decisão Markovianos; Risk-sensitive; Sensibilidade ao risco
- Agências de fomento:
- Language: Português
- Abstract: O principal critério de otimização utilizado em Processos de Decisão Markovianos (mdps) é minimizar o custo acumulado esperado. Embora esse critério de otimização seja útil, em algumas aplicações, o custo gerado por algumas execuções pode exceder um limite aceitável. Para lidar com esse problema foram propostos os Processos de Decisão Markovianos Sensíveis ao Risco (rs-mdps) cujo critério de otimização é maximizar a probabilidade do custo acumulado não ser maior que um orçamento limite definido pelo usuário, portanto garantindo que execuções custosas de um mdp ocorram com menos probabilidade. Algoritmos para rs-mdps possuem problemas de escalabilidade quando lidam com intervalos de custo amplos, uma vez que operam no espaço aumentado que enumera todos os possíveis orçamentos restantes. Neste trabalho é proposto um novo problema que é encontrar o orçamento mínimo para o qual a probabilidade de que o custo acumulado não exceda esse orçamento converge para um máximo. Para resolver esse problema são propostas duas abordagens: (i) uma melhoria no algoritmo tvi-dp (uma solução previamente proposta para rsmdps) e (ii) o primeiro algoritmo de programação dinâmica simbólica para rs-mdps que explora as independências condicionais da função de transição no espaço de estados aumentado. Os algoritmos propostos eliminam estados inválidos e adicionam uma nova condição de parada. Resultados empíricos mostram que o algoritmo rs-spudd é capaz de resolver problemas até 103 vezes maior que oalgoritmo tvi-dp e é até 26.2 vezes mais rápido que tvi-dp (nas instâncias que o algoritmo tvi-dp conseguiu resolver). De fato, é mostrado que o algoritmo rs-spudd é o único que consegue resolver instâncias grandes dos domínios analisados. Outro grande desafio em rs-mdps é lidar com custos contínuos. Para resolver esse problema são definidos os rs-mdps híbridos que incluem variáveis contínuas e discretas, além do orçamento limite definido pelo usuário. É mostrado que o algoritmo de programação dinâmica simbólica (sdp), existente na literatura, pode ser usado para resolver esse tipo de mdps. Esse algoritmo foi empiricamente testado de duas maneiras diferentes: (i) comparado com os demais algoritmos propostos em um domínio em que todos são capazes de resolver e (ii) testado em um domínio que somente ele é capaz de resolver. Os resultados mostram que o algoritmo sdp para rs-mdp híbridos é capaz de resolver domínios com custos contínuos sem a necessidade de enumeração de estados, porém em troca do aumento do custo computacional
- Imprenta:
- Data da defesa: 06.11.2018
-
ABNT
MOREIRA, Daniel Augusto de Melo. Algoritmos eficientes para o problema do orçamento mínimo em processos de decisão Markovianos sensíveis ao risco. 2018. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12022019-141016/. Acesso em: 24 jan. 2026. -
APA
Moreira, D. A. de M. (2018). Algoritmos eficientes para o problema do orçamento mínimo em processos de decisão Markovianos sensíveis ao risco (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12022019-141016/ -
NLM
Moreira DA de M. Algoritmos eficientes para o problema do orçamento mínimo em processos de decisão Markovianos sensíveis ao risco [Internet]. 2018 ;[citado 2026 jan. 24 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12022019-141016/ -
Vancouver
Moreira DA de M. Algoritmos eficientes para o problema do orçamento mínimo em processos de decisão Markovianos sensíveis ao risco [Internet]. 2018 ;[citado 2026 jan. 24 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12022019-141016/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
