Resumo: Processos de decisão de Markov (MDPs) são usados para modelar situações onde é necessário executar ações em sequência em ambientes com incerteza. Este trabalho define uma nova formulação dos processos de decisão de Markov, adicionando a estes a possibilidade de restringir as ações e observações a serem consideradas a cada época de decisão. Estas restrições são descritas na forma de um autômato finito ? assim, a sequência de possíveis ações e observações consideradas na busca pela política ótima passa a ser uma linguagem regular. Chamamos estes processos de Markov limitados por linguagem (LLMDPs e LL-POMDPs). O uso de autômatos para a especificação de restrições facilita o processo de modelagem de problemas. Apresentamos diferentes abordagens para a solução destes problemas, e comparamos seus desempenhos, mostrando que a solução é viável, e mostramos também que em algumas situações o uso de restrições pode ser usado para acelerar a busca por uma solução. Além disso, apresentamos uma modificação nos LLPOMDPs de forma que seja possível especificar duração probabilística discreta para as ações e observações Ver menos

Abstract: Markov decision processes (MDPs) are used to model situations where one needs to execute sequences of actions under uncertainty. This work defines a new formulation of Markov decision processes, with the possibility of restricting the actions and observations to be considered at each decision epoch. These restrictions are described as a finite automation, so the sequence of possible actions (and observations) considered during the search for an optimal policy is a regular language. We call these ?language limited Markov decision processes (LL-MDPs and LL-POMDPs). The use of automata for specifying restrictions helps make the modeling process easier. We present different approaches to solve these problems, and compare their performance, showing that the solution is feasible, and we also show that in some situations some restrictions can be used to speed up the search for a solution. Besides that, we also present one modification on LL-POMDPs to make it possible to specify probabilistic discrete duration for actions and observations Ver menos