Programação em lógica não-monotônica aplicada à redução do espaço de planos em processos de decisão de Markov
Carregando...
Arquivos
Citações na Scopus
Tipo de produção
Tese
Data
2016
Autores
Ferreira, L. A.
Orientador
Santos, Paulo Eduardo
Periódico
Título da Revista
ISSN da Revista
Título de Volume
Citação
FERREIRA, L. A. Programação em lógica não-monotônica aplicada à redução do espaço de planos em processos de decisão de Markov. 2016. 123 p. Tese (Doutorado em Engenharia Elétrica) - Centro Universitário FEI, São Bernardo do Campo, 2016. Disponível em: . Acesso em: 28 set. 2018.
Texto completo (DOI)
Palavras-chave
Programação lógica,Processos Markovianos de decisão,Programação não-monotônica
Resumo
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.
In sequential decision making problems, dealing with unforeseen changes in the environment is still an open problem. While describing only the current domain increases the chances of failing when making a decision in an environment that has already changed, describing every possibility of the domain in order to avoid errors may lead to a description that has a high memory cost and also needs long periods in the search for the optimal solution. In order to solve this problem, this work proposes the ASP(MDP) which uses Answer Set Programming to describe a Markov Decision Process in which Monte Carlo Policy Evaluation and Reinforcement Learning can be used to interact with the environment and find the optimal solution. While Answer Set Programming allows for the revision of the domain’s description, Reinforcement Learning and Monte Carlo Policy Evaluation interact with the environment and discovers the missing information so that optimal solution can be found. For ASP(MDP)’s evaluation, four experiments were proposed and has been shown that using Answer Set Programming to describe the Markov Decision Process can reduce the search space and also allows the search to proceed when the environment changes without the need to restart the searching process. In the first experiment the best sequence for allocating processes in servers is wanted, considering the processing power and failure rate of the servers. For this situation, not only ASP(MDP) provided a reduction in the search space but the optimal solution found is the same as the one present by a method that did not use Answer Set Programming. For the second experiment, the reaction control system of the space shuttle was used and the objective was to perform a manoeuvre in the space. Results show that ASP(MDP) was capable of greatly reduce the search space and time needed to find the optimal solution and also was able to find the description of the Markov decision process that was being used. The third experiment takes place in a nonstationary deterministic grid world in which ASP(MDP) is used with Reinforcement Learning algorithms. In this case, ASP(MDP) was capable of dealing with changes in the sets of states and actions, which is Reinforcement Learning methods are not capable of dealing with. Furthermore, the use of the knowledge gained in the previous map allows the learning process to non-deterministic version of the previous one and shows that ASP(MDP) can be used in nondeterministic non-stationary problems, which may also allows for reduction in the search space and acceleration in the learning process. Thus, this work presents a method that is elaboration tolerant and can be used to search for the optimal solution in non-stationary non-deterministic Markov Decision Processes, such that the optimal solution can be found faster by exploring a reduced search space.
In sequential decision making problems, dealing with unforeseen changes in the environment is still an open problem. While describing only the current domain increases the chances of failing when making a decision in an environment that has already changed, describing every possibility of the domain in order to avoid errors may lead to a description that has a high memory cost and also needs long periods in the search for the optimal solution. In order to solve this problem, this work proposes the ASP(MDP) which uses Answer Set Programming to describe a Markov Decision Process in which Monte Carlo Policy Evaluation and Reinforcement Learning can be used to interact with the environment and find the optimal solution. While Answer Set Programming allows for the revision of the domain’s description, Reinforcement Learning and Monte Carlo Policy Evaluation interact with the environment and discovers the missing information so that optimal solution can be found. For ASP(MDP)’s evaluation, four experiments were proposed and has been shown that using Answer Set Programming to describe the Markov Decision Process can reduce the search space and also allows the search to proceed when the environment changes without the need to restart the searching process. In the first experiment the best sequence for allocating processes in servers is wanted, considering the processing power and failure rate of the servers. For this situation, not only ASP(MDP) provided a reduction in the search space but the optimal solution found is the same as the one present by a method that did not use Answer Set Programming. For the second experiment, the reaction control system of the space shuttle was used and the objective was to perform a manoeuvre in the space. Results show that ASP(MDP) was capable of greatly reduce the search space and time needed to find the optimal solution and also was able to find the description of the Markov decision process that was being used. The third experiment takes place in a nonstationary deterministic grid world in which ASP(MDP) is used with Reinforcement Learning algorithms. In this case, ASP(MDP) was capable of dealing with changes in the sets of states and actions, which is Reinforcement Learning methods are not capable of dealing with. Furthermore, the use of the knowledge gained in the previous map allows the learning process to non-deterministic version of the previous one and shows that ASP(MDP) can be used in nondeterministic non-stationary problems, which may also allows for reduction in the search space and acceleration in the learning process. Thus, this work presents a method that is elaboration tolerant and can be used to search for the optimal solution in non-stationary non-deterministic Markov Decision Processes, such that the optimal solution can be found faster by exploring a reduced search space.