Planejamento probabilístico com becos sem saída (2017)
- Authors:
- Autor USP: SIMÃO, THIAGO DIAS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: INTELIGÊNCIA ARTIFICIAL; PROCESSOS ESTOCÁSTICOS; PROCESSOS DE MARKOV
- Keywords: Becos-sem-saída; Dead-ends; MDP; Planejamento probabilístico; Probabilistic planning; SSP MDP
- Agências de fomento:
- Language: Português
- Abstract: Planejamento probabilístico lida com a tomada de decisão sequencial em ambientes estocásticos e geralmente é modelado por um Processo de Decisão Markoviano (Markovian Decision Process - MDP). Um MDP modela a interação entre um agente e o seu ambiente: em cada estágio, o agente decide executar uma ação, com efeitos probabilísticos e um certo custo, que irá produzir um estado futuro. O objetivo do agente MDP é minimizar o custo esperado ao longo de uma sequência de escolhas de ação. O número de estágios que o agente atua no ambiente é chamado de horizonte, o qual pode ser finito, infinito ou indefinido. Um exemplo de MDP com horizonte indefinido é o Stochastic Shortest Path MDP (SSP MDP), que estende a definição de MDP adicionando um conjunto de estados meta (o agente para de agir ao alcançar um estado meta). Num SSP MDP é feita a suposição de que é sempre possível alcançar um estado meta a partir de qualquer estado do mundo. No entanto, essa é uma suposição muito forte e que não pode ser garantida em aplicações práticas. Estados a partir dos quais é impossível atingir a meta são chamados de becos-sem-saída. Um beco-sem-saída pode ser evitável ou inevitável (se nenhuma política leva do estado inicial para a meta com probabilidade um). Em trabalhos recentes foram propostas extensões para SSP MDP que permitem a existência de diferentes tipos de beco-sem-saída, bem como algoritmos para resolvê-los. No entanto, a detecção de becos-sem-saída é feita utilizando: (i) heurísticas quepodem falhar para becos-sem-saída implícitos ou (ii) métodos mais confiáveis, mas que demandam alto custo computacional. Neste projeto fazemos uma caracterização formal de modelos de planejamento probabilístico com becos-sem-saída. Além disso, propomos uma nova técnica para detecção de becos-sem-saída baseada nessa caracterização e adaptamos algoritmos de planejamento probabilístico para utilizarem esse novo método de detecção. Os resultados empíricos mostram que o método proposto é capaz de detectar todos os becos-sem-saída de um dado conjunto de estados e, quando usado com planejadores probabilísticos, pode tornar esses planejadores mais eficientes em domínios com becos-sem-saída difíceis de serem detectados
- Imprenta:
- Data da defesa: 06.03.2017
-
ABNT
SIMÃO, Thiago Dias. Planejamento probabilístico com becos sem saída. 2017. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2017. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/. Acesso em: 16 abr. 2024. -
APA
Simão, T. D. (2017). Planejamento probabilístico com becos sem saída (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/ -
NLM
Simão TD. Planejamento probabilístico com becos sem saída [Internet]. 2017 ;[citado 2024 abr. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/ -
Vancouver
Simão TD. Planejamento probabilístico com becos sem saída [Internet]. 2017 ;[citado 2024 abr. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04072017-095306/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
