Programação em lógica não-monotônica aplicada à redução do espaço de planos em processos de decisão de Markov

• Ano de defesa: 2016
• Autor(a) principal: Ferreira, L. A.
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Centro Universitário FEI, São Bernardo do Campo
• Palavras-chave em Português: Programação lógica; Processos Markovianos de decisão; Programação não-monotônica
• Link de acesso: https://repositorio.fei.edu.br/handle/FEI/272

Um desafio presente em problemas de tomada de decisão sequencial é o fato de que, ao longo do tempo, um domínio pode sofrer alterações não previstas. Enquanto que descrever apenas o domínio atual faz com que a chance de falhas na tomada de decisão aumente conforme o domínio sofre mudanças, descrever todas as possibilidades deste domínio com a finalidade de garantir que não haverá falhas quando o domínio sofrer alterações pode ser uma solução com alto custo de armazenamento e longo tempo de busca pela solução ótima. Para resolver este problema, este trabalho propõe o ASP(MDP) que utiliza Answer Set Programming para a descrição de um processo Markoviano de decisão em que avaliação de política de Monte Carlo ou Aprendizado por Reforço podem ser utilizados para realizar a interação com o ambiente e encontrar a solução ótima do problema. Enquanto a utilização de Answer Set Programming permite que a descrição do domínio seja revista conforme as alterações ocorrem, Aprendizado por Reforço ou avaliação de política de Monte Carlo permitem que as interações com o ambiente forneçam as informações restantes necessárias para que a solução ótima seja encontrada. Para avaliar o ASP(MDP) foram propostos quatro experimentos que demonstraram que a utilização de Answer Set Programming para descrever o processo Markoviano de decisão é capaz de reduzir o espaço de busca pela solução ótima, além de permitir que esta solução do problema seja encontrada sem a necessidade de reiniciar o processo de busca pela solução quando o domínio sofre alterações. No primeiro experimento deseja-se obter a melhor alocação de aplicações em servidores, sendo considerados o tempo necessário para o processamento de cada aplicação e a probabilidade de falha dos servidores. A utilização do ASP(MDP) permitiu verificar que o espaço de busca foi reduzido e a solução ótima obtida é a mesma com ou sem a utilização do Answer Set Programming para descrever o problema. Para o segundo experimento foi utilizado o sistema de controle por reações de um ônibus espacial, em que se deseja realizar uma manobra no espaço. Os resultados mostram que a utilização do Answer Set Programming permitiu não somente a redução no espaço de busca, mas também uma redução no tempo necessário para a obtenção da solução ótima e a própria descrição do processo Markoviano de decisão. O terceiro experimento se passa em um mundo de grade determinístico em que são comparados algoritmos de Aprendizado por Reforço com ASP(MDP). Neste experimento nota-se que é possível utilizar o ASP(MDP) em problemas que os conjuntos de estados e ações sofrem alterações ao longo do tempo, ao contrário do RL, e que a utilização de conhecimento adquirido antes das mudanças no ambiente fazem com que o aprendizado no novo mapa seja mais rápida do que quando é utilizado somente RL. O último experimento se passa na versão não-determinística do experimento anterior e mostra que ASP(MDP) pode ser utilizado em domínios não-determinísticos e não-estacionários, permitindo a redução do espaço de busca e do tempo necessário para encontrar a solução ótima. Portanto, este trabalho apresenta um método tolerante à elaboração que permite a busca por soluções ótimas em processos Markovianos de decisão não-estacionários e não-determinísticos de forma que a solução seja encontrada mais rapidamente pela exploração de um espaço de busca menor.