Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado. / Markov Decision Process (MDP) model problems of sequential decision making, where the possible actions have probabilistic effects on the successor states (defined by state transition matrices). Real-time dynamic programming (RTDP), is a technique for solving MDPs when there exists information about the initial state. Traditional approaches show better performance in problems with sparse state transition matrices, because they can achieve the convergence to optimal policy efficiently, without visiting all states. But, this advantage can be lose in problems with dense state transition matrices, in which several states can be achieved in a step (for example, control problems with exogenous events). An approach to overcome this limitation is to explore regularities existing in the domain dynamics through a factored representation, i.e., a representation based on state variables. In this master thesis, we propose a new algorithm called FactRTDP (Factored RTDP), and its approximate version aFactRTDP (Approximate and Factored RTDP), that are the first factored efficient versions of the classical RTDP algorithm. We also propose two other extensions, FactLRTDP and aFactLRTDP, that label states for which the value function has converged to the optimal. The experimental results show that when these new algorithms are executed in domains with dense transition matrices, they converge faster. And they have a good online performance in domains with dense transition matrices and few dependencies among state variables.

Processos de Decisão Markovianos (Markov Decision Process - MDP) modelam problemas de tomada de decisão sequencial em que as possíveis ações de um agente possuem efeitos probabilísticos sobre os estados sucessores (que podem ser definidas por matrizes de transição de estados). Programação dinâmica em tempo real (Real-time dynamic programming - RTDP), é uma técnica usada para resolver MDPs quando existe informação sobre o estado inicial. Abordagens tradicionais apresentam melhor desempenho em problemas com matrizes esparsas de transição de estados porque podem alcançar eficientemente a convergência para a política ótima, sem ter que visitar todos os estados. Porém essa vantagem pode ser perdida em problemas com matrizes densas de transição, nos quais muitos estados podem ser alcançados em um passo (por exemplo, problemas de controle com eventos exógenos). Uma abordagem para superar essa limitação é explorar regularidades existentes na dinâmica do domínio através de uma representação fatorada, isto é, uma representação baseada em variáveis de estado. Nesse trabalho de mestrado, propomos um novo algoritmo chamado de FactRTDP (RTDP Fatorado), e sua versão aproximada aFactRTDP (RTDP Fatorado e Aproximado), que é a primeira versão eficiente fatorada do algoritmo clássico RTDP. Também propomos outras 2 extensões desses algoritmos, o FactLRTDP e aFactLRTDP, que rotulam estados cuja função valor convergiu para o ótimo. Os resultados experimentais mostram que estes novos algoritmos convergem mais rapidamente quando executados em domínios com matrizes de transição densa e tem bom comportamento online em domínios com matrizes de transição densa com pouca dependência entre as variáveis de estado. / Markov Decision Process (MDP) model problems of sequential decision making, where the possible actions have probabilistic effects on the successor states (defined by state transition matrices). Real-time dynamic programming (RTDP), is a technique for solving MDPs when there exists information about the initial state. Traditional approaches show better performance in problems with sparse state transition matrices, because they can achieve the convergence to optimal policy efficiently, without visiting all states. But, this advantage can be lose in problems with dense state transition matrices, in which several states can be achieved in a step (for example, control problems with exogenous events). An approach to overcome this limitation is to explore regularities existing in the domain dynamics through a factored representation, i.e., a representation based on state variables. In this master thesis, we propose a new algorithm called FactRTDP (Factored RTDP), and its approximate version aFactRTDP (Approximate and Factored RTDP), that are the first factored efficient versions of the classical RTDP algorithm. We also propose two other extensions, FactLRTDP and aFactLRTDP, that label states for which the value function has converged to the optimal. The experimental results show that when these new algorithms are executed in domains with dense transition matrices, they converge faster. And they have a good online performance in domains with dense transition matrices and few dependencies among state variables.

Made available in DSpace on 2016-06-02T19:03:58Z (GMT). No. of bitstreams: 1 5694.pdf: 2329501 bytes, checksum: 90a80d78f180e25fc719ec410704ff8f (MD5) Previous issue date: 2013-12-13 / Financiadora de Estudos e Projetos / In Computer Science, ontologies are used for knowledge representation in a number of applications, aiming to structure and handle domain semantics through models shared by humans and computational systems. Although traditional ontologies model semantic information and support reasoning tasks, they are based on a formalism which is less suitable to express the vagueness inherent in real-world phenomena and human language. To address this issue, many proposals investigate how traditional ontologies can be extended by incorporating concepts from fuzzy sets and fuzzy logic, resulting in fuzzy ontologies. In special, combining the formalism from fuzzy ontologies with fuzzy rule-based reasoning, which has been successfully applied in the context of fuzzy inference systems, can lead to more expressive inferences involving imprecision. In this sense, this doctoral thesis aims at exploring the integration of fuzzy ontology reasoning with fuzzy inference systems, resulting in the definition and the development of two approaches: HyFOM (Hybrid integration of Fuzzy Ontology and Mamdani reasoning) and FT-FIS (Fuzzy Tableau and Fuzzy Inference System). HyFOM is based on a hybrid architecture combining reasoners for ontologies, fuzzy ontologies and fuzzy inference systems, focusing on the interaction among its independent components. FT-FIS defines an interface between a fuzzy tableau-based algorithm and a fuzzy inference system, including the fuzzyRuleReasoning predicate that allows fuzzy rule-based reasoning to be invoked whenever necessary for fuzzy ontology reasoning tasks. The main contribution of HyFOM and FT-FIS comes from their reasoning architectures, which combine flexibility in terms of fuzzy rule semantics with the collaboration between inferences from both types of reasoning. Experiments regarding the recommendation of touristic attractions, based on synthetic data, revealed that HyFOM and FT-FIS provide integrated inferences, in addition to a more expressive approximation of the relation defined by fuzzy rules than the results from the fuzzyDL reasoner. In experiments involving the evaluation of chemical risk in food samples, based on real data, results obtained by HyFOM and FT-FIS are also more precise than fuzzyDL results, in comparison with reference values available in this domain. / No contexto da Ciência da Computação, ontologias são utilizadas para representação de conhecimento em diversas aplicações, com o intuito de estruturar e tratar a semântica de domínios específicos. Embora representem e permitam inferir conhecimento implícito, as ontologias convencionais baseiam-se em um formalismo que não é capaz de expressar a imprecisão presente em fenômenos do mundo real e na linguagem humana. Para abordar esta limitação, há diversas pesquisas que investigam a incorporação de conceitos da teoria de conjuntos fuzzy e da lógica fuzzy em ontologias, resultando em ontologias fuzzy. Em especial, combinar o formalismo das ontologias fuzzy com o raciocínio baseado em regras fuzzy, utilizado com sucesso no contexto de sistemas de inferência fuzzy, pode proporcionar uma maior expressividade com relação às inferências envolvendo imprecisão. Neste sentido, o objetivo deste projeto de doutorado é explorar a integração do raciocínio de ontologias fuzzy e de sistemas de inferência fuzzy, resultando na definição e no desenvolvimento das abordagens HyFOM (Hybrid integration of Fuzzy Ontology and Mamdani reasoning) e FT-FIS (Fuzzy Tableau and Fuzzy Inference System). HyFOM baseia-se em uma arquitetura híbrida que combina motores de inferência existentes na literatura para ontologias, ontologias fuzzy e sistemas de inferência fuzzy, com foco na interação entre seus componentes independentes. FT-FIS define uma interface entre um algoritmo baseado em tableau fuzzy e um sistema de inferência fuzzy, incluindo o predicado fuzzyRuleReasoning que permite invocar o raciocínio baseado em regras fuzzy quando for necessário para as tarefas de raciocínio da ontologia fuzzy. A principal contribuição das arquiteturas de raciocínio de HyFOM e FT-FIS está na combinação de flexibilidade, em termos da semântica das regras fuzzy, com a colaboração entre as inferências de ambos tipos de raciocínio. Experimentos considerando a recomendação de atrações turísticas, baseados em dados sintéticos, revelaram que HyFOM e FT-FIS são capazes de proporcionar inferências integradas, além de uma aproximação mais expressiva da relação estabelecida pelas regras fuzzy que os resultados providos pelo raciocinador fuzzyDL. Em experimentos envolvendo o domínio de risco químico em alimentos, baseado em dados reais, os resultados de HyFOM e FT-FIS também são mais precisos que os resultados de fuzzyDL, em comparação com valores de referência disponíveis nesse domínio.