Search

Neste trabalho introduzimos uma maneira original de construir um Sistema Especialista: transformar uma Base de Conhecimento em um programa PROLOG. Enquanto que todos os Sistemas Especialista encontrados na bibliografia são controlados por um \"shell\", obtemos, com essa transformação, um Sistema Especialista cujo controle é feito pelo próprio PROLOG. Apresentamos também, um protótipo de um compilador para automatizar a referida transformação. This work introduces a way of transforming directly a Knowledge Base into a PROLOG program. With the method presented here we obtain an Expert System, the control of which is carried out by PROLOG itself, without requiring the use of a shell. We also present a model of a compiler which automates the mentioned method of transformation.

Stochastic Value Gradient (SVG) methods underlie many recent achievements of model-based Reinforcement Learning (RL) agents in continuous state-action spaces. Such methods use data collected by exploration in the environment to produce a model of its dynamics, which is then used to approximate the gradient of the objective function w.r.t. the agent\'s parameters. Despite the practical significance of these methods, many algorithm design choices still lack rigorous theoretical or empirical justification. Instead, most works rely heavily on benchmark-centric evaluation methods, which confound the contributions of several components of an RL agent\'s design to the final performance. In this work, we propose a fine-grained analysis of core algorithmic components of SVGs, including: the gradient estimator formula, model learning and value function approximation. We implement a configurable benchmark environment based on the Linear Quadratic Gaussian (LQG) regulator, allowing us to compute the ground-truth SVG and compare it with learning approaches. We conduct our analysis on a range of LQG environments, evaluating the impact of each algorithmic component in prediction and control tasks. Our results show that a widely used gradient estimator induces a favorable bias-variance trade-off, using a biased expectation that yields better gradient estimates in smaller sample regimes than the unbiased expression for the gradient. On model learning, we show that overfitting to on-policy data may occur, leading to accurate state predictions but inaccurate gradients, highlighting the importance of exploration even in stochastic environments. We also show that value function approximation can be more unstable than model learning, even in simple linear environments. Finally, we evaluate performance when using the model for direct gradient estimation vs. for value function approximation, concluding that the former is more effective for both prediction and control. Métodos de Gradiente de Valor Estocástico (GVE) estão por trás de muitos avanços recentes de agentes de Aprendizado por Reforço (AR) baseado em modelo em espaços de estado-ação contínuos. Tais métodos usam dados coletados por exploração no ambiente para produzir um modelo de sua dinâmica, que é então usado para aproximar o gradiente, com relação aos parâmetros do agente, da função objetivo. Apesar da significância prática desses métodos, muitas escolhas de design algorítmico ainda carecem de rigorosas justificativas teóricas ou empíricas. Em vez disso, muitos trabalhos colocam muito peso em métodos de avaliação em ambientes-referência, o que mistura as contribuições de vários componentes do design de um agente de AR para o desempenho final. Este trabalho propõe uma análise refinada de componentes algorítmicos centrais a métodos de GVE, incluindo: a fórmula de estimação do gradiente, aprendizado do modelo e aproximação de função-valor. É implementado um ambiente-referência configurável baseado no regulador Linear Quadrático Gaussiano (LQG), permitindo computar o verdadeiro GVE e compará-lo com abordagens via aprendizado. Análises são conduzidas em uma variedade de ambientes LQG, avaliando o impacto de cada componente algorítmico em tarefas de predição e controle. Os resultados mostram que um estimador de gradiente amplamente usado induz um balanço de viés e variância favorável, usando uma esperança enviesada que produz estimativas de gradiente melhores com poucas amostras em comparação à fórmula não-enviesada do gradiente. Quanto ao aprendizado do modelo, demonstra-se que o modelo pode sobreajustar-se à dados \\textit, levando à predições acuradas de estados mas inacuradas de gradientes, salientando a importância da exploração até em ambientes estocásticos. É também mostrado que aproximação de função-valor pode ser mais instável que aprendizado de modelo, mesmo em simples ambientes lineares. Finalmente, avalia-se o desempenho ao usar o modelo para estimar o gradiente diretamente vs. para aproximar a função-valor, concluindo que a primeira abordagem é mais efetiva tanto para predição quanto para controle.

A descoberta de conhecimento em bancos de dados (KDD - Knowledge Discovery in Databases) é um tópico de pesquisa que envolve diversas áreas de interesse como Reconhecimento de Padrões, Aprendizado de Máquina, Bancos de Dados e Inteligência Artificial. KDD é definida como um processo não trivial de identificação de padrões válidos, novos, potencialmente úteis e compreensíveis incluídos nos dados. Na mineração de dados, uma das etapas do proceso de KDD, o uso de hierarquias de conceitos pode permitir a descoberta de conhecimento num nível de abstração mais elevado, compacto e muitas vezes mais interessante. Amineração de dados em múltiplos níveis conceituais é mais complexa do que a mineração num único nível, pois o espaço de busca é geralmente maior. Alguns trabalhos empregam a pré-generalização dos dados como forma de reduzir este espaço, dificultando a descoberta em níveis de abstração arbitrários. No entanto, para descobrir regrasa em diferentes níveis de generalidade de maneira eficiente, sem pré-generalizar os dados, é necessário um acesso rápido às hierarquias bem como métodos de avaliação de consultas velozes. Nesta dissertação, é apresentado o sistema NETUNO-HC que realiza indução de regras de classificação em diferentes níveis de generalidade, através do uso de hierarquias de conceitos sobre os valores dos atributos de um banco de dados, sejam eles numéricos ou categóricos. É mostrado como o nível de generalidade das regras descobertas é afetado pela estratégia de busca empregada e pela variação das medidas de relevância. Além disso, como é demonstrado através de uma série de experimentos, o sistema NETUNO-HC implementa técnicas que resultam num aumento de eficiência significativo, a saber: (i) uso de uma primitiva em SQL para efetuar as consultas ao banco de dados, (ii) codoficação numérica da hierarquia conceitual, (iii) estratégia de Busca em Feixe (Bream Search), (iv) codificação e indexação das regras descobertas numa tabela hash. not available

Com o crescimento e a proliferação dos serviços Web, torna-se cada vez mais difícil encontrar um serviço que execute uma tarefa específica. Isso é ainda mais difícil quando não existe um serviço único, mas sim combinações de serviços que podem executar a tarefa desejada. O objetivo deste trabalho é automatizar esta combinação, conhecida como composição de serviços Web. Para atingir este objetivo, será utilizado o sistema de planejamento hierárquico JSHOP2, em conjunto com descrições semânticas de serviços na linguagem OWL-S. Como planejadores não podem lidar com a expressividade da Web Semântica, serão apresentadas algumas formas de integrar o planejador JSHOP2 com motores de inferência. not available

Golog é uma linguagem de alto nível criada para especificar programas para agentes robóticos. No entanto, como acontece em situações do mundo real, Golog deve permitir a programação de agentes capazes de tratar eventos exógenos e imprevistos. Para isso, uma primeira solução seria construir programas prevendo todas as contingências do mundo. No entanto, isso pode levar ao desenvolvimento de agentes robóticos de alto custo e baixo desempenho. Uma outra possibilidade é o planejamento com execução e monitoramento, que, em caso de falha, permite criar um plano para corriji-la. Isso pode ser feito por um planejador para satisfação de metas. Nesse trabalho, mostramos que o meta-interpretador Golog realiza planejamento de forma semelhante aos planejadores hierárquicos e que, baseado nessa técnica, Golog pode resolver problemas de planejamento para satisfação de metas através da definição de procedimentos meta. Chamamos esse tipo de planejamento de GGPP (Golog Goal Procedures based Planner). Para comparar o desempenho do GGPP com outros planejadores, foram implementados e analisados três outros planejadores para satisfação de meta baseados no Cálculo de Situaçõe not available

Nas últimas décadas, o estudo de redes biológicas (BT - do inglês textitBiological neTworks) cresceu em importância por possibilitar o entendimento de como entidades biológicas interagem entre si para realizar tarefas biológicas e como intervir nessas redes para tratar doenças pela aplicação de terapias. Um dos principais desafios da intervenção em BTs é descobrir quando e quais intervenções aplicar para torná-las mais saudáveis. Um conjunto de perfis de atividade de entidades, denominado bacia de atração (BOA), leva a BT em direção a um determinado fenótipo; desta forma, para uma BT ter um fenótipo saudável é necessário que ela esteja em uma BOA saudável. Entretanto, grande parte das propostas desconsidera a existência de BOAs e obtém estratégias de intervenção que evitam certos perfis de atividade de entidades, o que pode causar doenças. Além disso, sem a completa observação de todas as entidades envolvidas em uma tarefa biológica, é difícil inferir um modelo preciso e identificar se a BOA atual é saudável. Em vez de gerar uma estratégia de intervenção a partir de um modelo impreciso, nós propomos um novo arcabouço que aprende as estratégias diretamente de um conjunto de experiências coletado previamente. O arcabouço proposto, denominado Basin of Attraction Control Framework through Experiences (BOAConFE), integra o conceito de BOA e técnicas de aprendizado de máquina para calcular estratégias de controle capazes de levar BTs rapidamente para BOAs saudáveis, enquanto reduz a quantidade de intervenções. BOAConFE calcula a probabilidade de observações estarem em BOAs saudáveis para lidar com a observabilidade parcial e incorporar o conhecimento sobre BOAs no arcabouço. BOAConFE utiliza o método proposto multiple Steps Basin of Attraction Fitted Q-Iteration (mSBOAFQI) que usa essas probabilidades junto com uma trajetória composta por múltiplos passos para definir estratégias de intervenção a partir das experiências. Nós mostramos empiricamente que BOAConFE consegue levar rapidamente uma BT parcialmente observável para BOAs saudáveis, enquanto reduz o número de intervenções. Os nossos resultados destacam os benefícios de usar múltiplos passos para lidar com observabilidade parcial e a probabilidade de observações estarem em BOAs saudáveis para explorar o conhecimento sobre BOAs. Over the last decades, there has been an increase in interest in the study of biological networks (BT) to understand how the entities interact with each other during the execution of biological tasks and how to intervene in these networks for the treatment of diseases. A major challenge in the intervention of BTs is to discover when and what interventions should be applied in order to shift them to healthy phenotypes. A set of entity activity profiles, called basin of attraction (BOA), takes a BT to a specific phenotype; therefore, a healthy BOA drives the BT to a healthy phenotype. However, most proposals disregard BOAs and derive an intervention strategy avoiding certain entity activity profiles, which may disrupt the execution of biological tasks and cause other diseases. Additionally, without the complete observability of all entities, it is difficult to infer an accurate model and to identify whether the current BOA is healthy. Instead of generating an intervention strategy from an inaccurate model, we proposea novel framework that learns a strategy directly from a batch of experiences provided in advance. Our proposed framework, named Basin of Attraction Control Framework through Experiences (BOAConFE), combines BOA and machine learning techniques to derive intervention strategies that are capable of quickly shifting partially observable BTs to healthy BOAs, while reducing the number of interventions. BOAConFE computes the probability of observations being in healthy BOAs in order to use it to deal with partial observability and incorporate BOA knowledge into our framework. Building on BOAConFE, we propose multiple Steps Basin of Attraction Fitted Q-Iteration (mSBOAFQI) that uses these probabilities together with a trajectory composed of multiple steps to define intervention strategies from experiences. We empirically demonstrate that BOAConFE can quickly shift a partially observable BT to healthy BOAs, while reducing the number of interventions. Our results highlight the benefits of using multiple steps to deal with partial observability and BOA probability to explore BOA information.

Em problemas de tomada de decisão sequencial modelados como Processos de Decisão Markovianos (MDP) pode não ser possível obter uma medida exata para as probabilidades de transição de estados. Visando resolver esta situação os Processos de Decisão Markovianos com Probabilidades Imprecisas (Markov Decision Processes with Imprecise Transition Probabilities, MDP-IPs) foram introduzidos. Porém, enquanto estes MDP-IPs se mostram como um arcabouço robusto para aplicações de planejamento no mundo real, suas soluções consomem muito tempo na prática. Em trabalhos anteriores, buscando melhorar estas soluções foram propostos algoritmos de programação dinâmica síncrona eficientes para resolver MDP-IPs com uma representação fatorada para as funções de transição probabilística e recompensa, chamados de MDP-IP fatorados. Entretanto quando o estado inicial de um problema do Caminho mais Curto Estocástico (Stochastic Shortest Path MDP, SSP MDP) é dado, estas soluções não utilizam esta informação. Neste trabalho será introduzido o problema do Caminho mais Curto Estocástico com Probabilidades Imprecisas (Stochastic Shortest Path MDP-IP, SSP MDP-IP) tanto em sua forma enumerativa, quanto na fatorada. Um algoritmo de programação dinâmica assíncrona para SSP MDP-IP enumerativos com probabilidades dadas por intervalos foi proposto por Buffet e Aberdeen (2005). Entretanto, em geral um problema é dado de forma fatorada, i.e., em termos de variáveis de estado e nesse caso, mesmo se for assumida a imprecisão dada por intervalos sobre as variáveis, ele não poderá ser mais aplicado, pois as probabilidades de transição conjuntas serão multilineares. Assim, será mostrado que os SSP MDP-IPs fatorados são mais expressivos que os enumerativos e que a mudança do SSP MDP-IP enumerativo para o caso geral de um SSP MDP-IPs fatorado leva a uma mudança de resolução da função objetivo do Bellman backup de uma função linear para uma não-linear. Também serão propostos algoritmos enumerativos, chamados de RTDP-IP (Real-time Dynamic Programming with Imprecise Transition Probabilities), LRTDP-IP (Labeled Real-time Dynamic Programming with Imprecise Transition Probabilities), SSiPP-IP (Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) e LSSiPP-IP (Labeled Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) e fatorados chamados factRTDP-IP (factored RTDP-IP) e factLRTDP-IP (factored LRTDP-IP). Eles serão avaliados em relação aos algoritmos de programação dinâmica síncrona em termos de tempo de convergência da solução e de escalabilidade. In sequential decision making problems modelled as Markov Decision Processes (MDP) we may not have the state transition probabilities. To solve this issue, the framework based in Markov Decision Processes with Imprecise Transition Probabilities (MDP-IPs) is introduced. Therefore, while MDP-IPs is a robust framework to use in real world planning problems, its solutions are time-consuming in practice. In previous works, efficient algorithms based in synchronous dynamic programming to solve MDP-IPs with factored representations of the probabilistic transition function and reward function, called factored MDP-IPs. However, given a initial state of a system, modeled as a Stochastic Shortest Path MDP (SSP MDP), solutions does not use this information. In this work we introduce the Stochastic Shortest Path MDP-IPs (SSP MDP-IPs) in enumerative form and in factored form. An efficient asynchronous dynamic programming solution for SSP MDP-IPs with enumerated states has been proposed by Buffet e Aberdeen (2005) before which is restricted to interval-based imprecision. Nevertheless, in general the problem is given in a factored form, i.e., in terms of state variables and in this case even if we assume interval-based imprecision over the variables, the previous solution is no longer applicable since we have multilinear parameterized joint transition probabilities. In this work we show that the innocuous change from the enumerated SSP MDP-IP cases to the general case of factored SSP MDP-IPs leads to a switch from a linear to nonlinear objectives in the Bellman backup. Also we propose assynchronous dynamic programming enumerative algorithms, called RTDP-IP (Real-time Dynamic Programming with Imprecise Transition Probabilities), LRTDP-IP (Labeled Real-time Dynamic Programming with Imprecise Transition Probabilities), SSiPP-IP (Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities) and LSSiPP-IP (Labeled Short-Sighted Probabilistic Planner with Imprecise Transition Probabilities), and factored algorithms called factRTDP-IP (factored RTDP-IP) and factLRTDP-IP (factored LRTDP-IP). There algorithms will be evaluated with the synchronous dynamic programming algorithms previously proposed in terms of convergence time and scalability.

Um sistema artificial pode usar raciocínio espacial qualitativo para inferir informações sobre seu ambiente tridimensional a partir de imagens bidimensionais. Inferências realizadas com base em raciocínio espacial qualitativo devem ser capazes de lidar com incertezas. Neste trabalho investigamos a utilização de técnicas probabilísticas para tornar o raciocínio espacial qualitativo mais robusto a incertezas e aplicável a agentes móveis em ambientes reais. Investigamos uma formalização de raciocínio espacial com lógica de descrição probabilística em um subdomínio de tráfego. Desenvolvemos também um método que combina raciocínio espacial qualitativo com um filtro Bayesiano para desenvolver dois sistemas que foram aplicados na auto localização de um robô móvel. Executamos dois experimentos de auto localização; um utilizando a teoria de relações qualitativas percebíveis sobre sombra com filtro Bayesiano; e outro utilizando o cálculo de oclusão de regiões e o cálculo de direção com filtro Bayesiano. Ambos os sistemas obtiveram resultados positivos onde somente o raciocínio espacial qualitativo não foi capaz de inferir a localização do robô. Os experimentos com dados reais mostraram robustez aos ruídos e à informação parcial. An artificial system can use qualitative spatial reasoning to obtain information about its tridimensional environment, from bi-dimensional images. Inferences produced by qualitative spatial reasoning must be able to deal with uncertainty. This work investigates the use of probabilistic techniques to make qualitative spatial reasoning more robust against uncertainty, and better applicable to mobile agents in real environments. The work investigates a formalization of spatial reasoning using probabilistic description logics in a traffic domain. Additionally, a method is presented that combines qualitative spatial reasoning with a Bayesian filter, to develop two systems that are applied to self-localization of mobile robots. Two experiments are described; one using the theory of perceptual qualitative relations about shadows; the other using occlusion calculus and direction calculus. Both systems are combined with a Bayesian filter producing positive results in situations where qualitative spatial reasoning alone cannot infer robot location. Experiments with real data show robustness to noise and partial information.

Planejamento em inteligência artificial é a tarefa de determinar ações que satisfaçam um dado objetivo. Nos problemas de planejamento sob incerteza, as ações podem ter efeitos probabilísticos. Esses problemas são modelados como Processos de Decisão Markovianos (Markov Decision Processes - MDPs), modelos que permitem o cálculo de soluções ótimas considerando o valor esperado de cada ação em cada estado. Contudo, resolver problemas grandes de planejamento probabilístico, i.e., com um grande número de estados e ações, é um enorme desafio. MDPs grandes podem ser reduzidos através da computação de bissimulações estocásticas, i.e., relações de equivalência sobre o conjunto de estados do MDP original. A partir das bissimulações estocásticas, que podem ser exatas ou aproximadas, é possível obter um modelo abstrato reduzido que pode ser mais fácil de resolver do que o MDP original. No entanto, para problemas de alguns domínios, a computação da bissimulação estocástica sobre todo o espaço de estados é inviável. Os algoritmos propostos neste trabalho estendem os algoritmos usados para a computação de bissimulações estocásticas para MDPs de forma que elas sejam computadas sobre o conjunto de estados alcançáveis a partir de um dado estado inicial, que pode ser muito menor do que o conjunto de estados completo. Os resultados experimentais mostram que é possível resolver problemas grandes de planejamento probabilístico com desempenho superior às técnicas conhecidas de bissimulação estocástica. Planning in artificial intelligence is the task of finding actions to reach a given goal. In planning under uncertainty, the actions can have probabilistic effects. This problems are modeled using Markov Decision Processes (MDPs), models that enable the computation of optimal solutions considering the expected value of each action when applied in each state. However, to solve big probabilistic planning problems, i.e., those with a large number of states and actions, is still a challenge. Large MDPs can be reduced by computing stochastic bisimulations, i.e., equivalence relations over the original MDP states. From the stochastic bisimulations, that can be exact or approximated, it is possible to get an abstract reduced model that can be easier to solve than the original MDP. But, for some problems, the stochastic bisimulation computation over the whole state space is unfeasible. The algorithms proposed in this work extend the algorithms that are used to compute stochastic bisimulations for MDPs in a way that they can be computed over the reachable set of states with a given initial state, which can be much smaller than the complete set of states. The empirical results show that it is possible to solve large probabilistic planning problems with better performance than the known techniques of stochastic bisimulation.

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.

Um dos modelos mais usados para descrever problemas de planejamento probabilístico, i.e., planejamento de ações com efeitos probabilísticos, é o processo de decisão markoviano (Markov Decision Process - MDP). Soluções tradicionais são baseadas em programação dinâmica, sendo as mais ecientes aquelas baseadas em programação dinâmica em tempo real (Real-Time Dynamic Programming - RTDP), por explorarem somente os estados alcançáveis a partir de um dado estado inicial. Por outro lado, existem soluções ecientes baseadas em métodos de busca heurística em um grafo AND/OR, sendo que os nós AND representam os efeitos probabilísticos das ações e os nós OR representam as escolhas de ações alternativas. Tais soluções também exploram somente estados alcançáveis a partir de um estado inicial porém, guardam um subgrafo solução parcial e usam programação dinâmica para a atualização do custo dos nós desse subgrafo. No entanto, problemas com grandes espaços de estados limitam o uso prático desses métodos. MDPs fatorados permitem explorar a estrutura do problema, representando MDPs muito grandes de maneira compacta e assim, favorecer a escalabilidade das soluções. Neste trabalho, apresentamos uma análise comparativa das diferentes soluções para MDPs, com ênfase naquelas que fazem busca heurística e as comparamos com soluções baseadas em programação dinâmica assíncrona, consideradas o estado da arte das soluções de MPDs. Além disso, propomos um novo algoritmo de busca heurística para MDPs fatorados baseado no algoritmo ILAO* e o testamos nos problemas da competição de planejamento probabilístico IPPC-2011. One of the most widely used models to describe probabilistic planning problems, i.e., planning of actions with probabilistic eects, is the Markov Decision Process - MDP. The traditional solutions are based on dynamic programming, whereas the most ecient solutions are based on Real-Time Dynamic Programming - RTDP, which explore only the reachable states from a given initial state. Moreover, there are ecient solutions based on search methods in a AND/OR graph, where AND nodes represent the probabilistic eects of an action and OR nodes represent the choices of alternative actions. These solutions also explore only reachable states but maintain the parcial subgraph solution, using dynamic programming for updating the cost of nodes of these subgraph. However, problems with large state spaces limit the practical use of these methods. Factored representation of MDPs allow to explore the structure of the problem, and can represent very large MDPs compactly and thus improve the scalability of the solutions. In this dissertation, we present a comparative analysis of dierent solutions for MDPs, with emphasis on heuristic search methods. We compare the solutions which are based on asynchronous dynamic programming which are also considered the state of the art. We also propose a new factored algorithm based on the search algorithm ILAO*. It is also tested by using the problems of the International Probabilistic Planning Competition IPPC-2011.

Este trabalho é dedicado ao desenvolvimento teórico e algorítmico de processos de decisão markovianos com probabilidades imprecisas e representações relacionais. Na literatura, essa configuração tem sido importante dentro da área de planejamento em inteligência artificial, onde o uso de representações relacionais permite obter descrições compactas, e o emprego de probabilidades imprecisas resulta em formas mais gerais de incerteza. São três as principais contribuições deste trabalho. Primeiro, efetua-se uma discussão sobre os fundamentos de tomada de decisão sequencial com probabilidades imprecisas, em que evidencia-se alguns problemas ainda em aberto. Esses resultados afetam diretamente o (porém não restrito ao) modelo de interesse deste trabalho, os processos de decisão markovianos com probabilidades imprecisas. Segundo, propõe-se três algoritmos para processos de decisão markovianos com probabilidades imprecisas baseadas em programação (otimização) matemática. E terceiro, desenvolvem-se ideias propostas por Trevizan, Cozman e de Barros (2008) no uso de variantes do algoritmo Real-Time Dynamic Programming para resolução de problemas de planejamento probabilístico descritos através de versões estendidas da linguagem de descrição de domínios de planejamento (PPDDL). This work is devoted to the theoretical and algorithmic development of Markov Decision Processes with Imprecise Probabilities and relational representations. In the literature, this configuration is important within artificial intelligence planning, where the use of relational representations allow compact representations and imprecise probabilities result in a more general form of uncertainty. There are three main contributions. First, we present a brief discussion of the foundations of decision making with imprecise probabilities, pointing towards key questions that remain unanswered. These results have direct influence upon the model discussed within this text, that is, Markov Decision Processes with Imprecise Probabilities. Second, we propose three algorithms for Markov Decision Processes with Imprecise Probabilities based on mathematical programming. And third, we develop ideas proposed by Trevizan, Cozman e de Barros (2008) on the use of variants of Real-Time Dynamic Programming to solve problems of probabilistic planning described by an extension of the Probabilistic Planning Domain Definition Language (PPDDL).

Um Jogo Markoviano Alternado (Alternating Markov Game - AMG) é uma extensão de um Processo de Decisão Markoviano (Markov Decision Process - MDP) para ambientes multiagentes. O modelo AMG é utilizado na tomada de decisão sequencial de n agentes quando são conhecidas as probabilidades de transição das ações a serem tomadas por cada agente. Nesse trabalho estamos interessados em AMGs com probabilidades de transição de estados imprecisas, por exemplo, quando elas são dadas na forma de intervalos de probabilidades. Apresentamos um novo modelo de AMG, que chamamos de Jogo Markoviano Alternado com Probabilidades Imprecisas (Alternate Markov Game with Imprecise Probabilities - AMGIP) que permite que as imprecisões nas probabilidades de transições de estados sejam dadas na forma de parâmetros sujeitos a restrições lineares que estende trabalhos anteriores em que a imprecisão é dada por intervalos de probabilidades (AMG-INTERVAL). Dizemos que a imprecisão representa escolhas da Natureza. A imprecisão desses modelos implica no valor do jogo ser dado por uma função intervalar. Existem diversas formas de calcular a solução do jogo, que depende do comportamento da Natureza e dos critérios de preferência dos jogadores diante das escolhas da Natureza. Assim, neste trabalho discutimos diversas soluções para o AMG-IP e AMG-INTERVAL. Também como resultado do estudo das relações existentes entre os MDPs e os AMGs, propomos um novo modelo chamado de AMG-ST (Alternating Markov Game with Set-valued Transition), capaz de modelar a incerteza do modelo MDP-ST (Markovian Decision Process with Set-valued Transition) como um jogo entre o agente e a Natureza, isto é, um jogo em que a Natureza faz o papel de um dos jogadores. An Alternating Markov Game (AMG) is an extension of a Markov Decision Process (MDP) for multiagent environments. This model is used on sequencial decision making for n agents when we know the state transition probabilities of actions being taken by each agent. In this work we are interested in AMGs with imprecise probabilities on state transition function, for example, when they are given by probabilities intervals. We present a new AMG model, which we call Alternating Markov Game with Imprecise Probabilities (AMG-IP) that allows imprecision on state transition probabilities given by parameters subject to linear constraints that extend previous works which the imprecision is given by probabilities intervals (AMG-INTERVAL). We say that the imprecision represents the Nature choices. The imprecision of these models implies the game value is given by interval function. There are several ways to calculate the solution of the game, that depend on the behavior of the Nature and the preference criteria of the players on the choices of Nature. Therefore, in this work we discuss various solutions to AMG-IP and AMG-INTERVAL. Also from our study on the relationship among the MDPs and AMGs, we propose a new model called Alternating Markov Game with Set-valued Transition (AMG-ST), that can be used to model the uncertainty of an MDP-ST (Markovian Decision Process with Set-valued Transition) as a result of the match between the agent and the Nature, i.e., a game where the Nature is seen as one of the players.

A maioria das propostas de planejamento de rotas para robôs móveis não leva em conta a existência de soluções para problemas similares ao aprender a política para resolver um novo problema; e devido a isto, o problema de navegação corrente deve ser resolvido a partir do zero, o que pode ser excessivamente custoso em relação ao tempo. Neste trabalho é realizado o acoplamento do conhecimento prévio obtido de soluções similares, representado por uma política abstrata, a um processo de aprendizado por reforço. Além disto, este trabalho apresenta uma arquitetura para o aprendizado por reforço simultâneo, de nome ASAR, onde a política abstrata auxilia na inicialização da política para o problema concreto, e ambas as políticas são refinadas através da exploração. A fim de reduzir a perda de informação na construção da política abstrata é proposto um algoritmo, nomeado X-TILDE, que constrói uma política abstrata estocástica. A arquitetura proposta é comparada com um algoritmo de aprendizado padrão e os resultados demonstram que ela é eficaz em acelerar a construção da política para problemas práticos. Most work in path-planning approaches for mobile robots does not take into account existing solutions to similar problems when learning a policy to solve a new problem, and consequently solves the current navigation problem from scratch, what can be very time consuming. In this work we couple a prior knowledge obtained from a similar solution to a reinforcement learning process. The prior knowledge is represented by an abstract policy. In addition, this work presents a framework for simultaneous reinforcement learning called ASAR, where the abstract policy helps start up the policy for the concrete problem, and both policies are refined through exploration. For the construction of the abstract policy we propose an algorithm called X-TILDE, that builds a stochastic abstract policy, in order to reduce the loss of information. The proposed framework is compared with a default learning algorithm and the results show that it is effective in speeding up policy construction for practical problems.

Desde o final da década de 1990 existe um interesse crescente na aplicação de técnicas de planejamento automático em IA para resolver problemas reais de engenharia. Além das características dos problemas acadêmicos, tais como a necessidade de raciocinar sobre as ações, problemas reais requerem elicitação, engenharia e gerenciamento detalhado do conhecimento do domínio. Para tais aplicações reais, um processo de design sistemático é necessário onde as ferramentas de Engenharia do Conhecimento e de Requisitons têm um papel fundamental. Esforços acadêmicos recentes na área da Engenharia do Conhecimento em planejamento automático vêm desenvolvido ferramentas e técnicas de apoio ao processo de design de modelos do conhecimento. Porém, dada a natural incompletude do conhecimento, experiência prática em aplicações reais, como por exemplo exploração do espaço, tem mostrado que, mesmo com um processo disciplinado de design, requisitos de pontos de vista diferente (por exemplo, especialistas, usuários e patrocinadores) ainda surgem após a análise, geração e execução de planos. A tese central deste texto é que uma fase de análise de pós-design para o desenvolvimento de aplicações de planejamento em IA resulta em modelos do conhecimento mais ricos e, conseqüentemente, aumenta a qualidade dos planos gerados e a performance dos planejadores automáticos. Neste texto, nós investigamos como os conhecimentos e requisitos ocultos podem ser adquiridos e reutilizados durante a fase de análise de plans (posterior ao design do modelo) e como estes conhecimentos afetam o desempenho do processo de planejamento automático. O texto descreve um framework de post-design chamado postDAM que combina (1) uma ferramenta de engenharia de conhecimento para a aquisição de requisitos e avaliação do plano, (2) um ambiente de prototipagem virtual para a análise e simulação de planos, (3) um sistema de banco de dados para armazenamento de avaliações de planos, e (4) um sistema de raciocínio ontológico para o re-uso e descoberta de conhecimento sobre o domínio. Com o framework postDAM demonstramos que a análise de pós-design auxilia a descoberta de requisitos ocultos e orienta o ciclo de refinamento do modelo. Este trabalho apresenta três estudos de caso com domínios conhecidos na literatura e oito planejadores do estado da arte. Nossos resultados demonstram que melhorias significativas na qualidade do plano e um aumento na velocidade dos planejadores de até três ordens de grandeza pode ser alcançada através de um processo disciplinado e cuidados de pós-design. Nós demonstramos também que rationales provenientes dos usuários capturados durante as avaliações de planos podem ser úteis e reutilizáveis em novas avaliações de plano e em novos projetos. Nós argumentamos que esse processo de pós-design é fundamental para a implantação da tecnologia de planejamento automático em aplicações do mundo real. Até onde sabemos, este é o primeiro trabalho que investiga a análise de pós-design em aplicações de planejamento automático da IA. Since the end of the 1990s there has been an increasing interest in the application of AI planning techniques to solve real-life problems. In addition to characteristics of academic problems, such as the need to reason about actions, real-life problems require detailed knowledge elicitation, engineering, and management. A systematic design process in which Knowledge and Requirements Engineering techniques and tools play a fundamental role is necessary in such applications. Research on Knowledge Engineering for planning and scheduling has created tools and techniques to support the design process of planning domain models. However, given the natural incompleteness of the knowledge, practical experience in real applications such as space exploration has shown that, even with a disciplined process of design, requirements from different viewpoints (e.g. stakeholders, experts, users) still emerge after plan generation, analysis and execution. The central thesis of this dissertation is that an post-design analysis phase in the development of AI planning applications leads to richer knowledge models and, consequently, to high-performance and high-quality plans. In this dissertation, we investigate how hidden knowledge and requirements can be acquired and re-used during a plan analysis phase that follows model design and how they affect planning performance. We describe a post-design framework called postDAM that combines (1) a knowledge engineering tool for requirements acquisition and plan evaluation, (2) a virtual prototyping environment for the analysis and simulation of plans, (3) a database system for storing plan evaluations, and (4) an ontological reasoning system for knowledge re-use and discovery. Our framework demonstrates that post-design analysis supports the discovery of missing requirements and guides the model refinement cycle. We present three case studies using benchmark domains and eight state-of-the-art planners. Our results demonstrate that significant improvements in plan quality and an increase in planning speed of up to three orders of magnitude can be achieved through a careful post-design process. We also demonstrate that rationales captured during plan evaluations from users can be useful and reusable in further plan evaluations and in new application designs. We argue that such a post-design process is critical for deployment of planning technology in real-world applications. To our knowledge, this is the first work that investigate post-design analysis for AI planning applications.

Em geral, quando modelamos problemas de planejamento probabilístico do mundo real, usando o arcabouço de Processos de Decisão Markovianos (MDPs), é difícil obter uma estimativa exata das probabilidades de transição. A incerteza surge naturalmente na especificação de um domínio, por exemplo, durante a aquisição das probabilidades de transição a partir de um especialista ou de dados observados através de técnicas de amostragem, ou ainda de distribuições de transição não estacionárias decorrentes do conhecimento insuficiente do domínio. Com o objetivo de se determinar uma política robusta, dada a incerteza nas transições de estado, Processos de Decisão Markovianos com Probabilidades Imprecisas (MDP-IPs) têm sido usados para modelar esses cenários. Infelizmente, apesar de existirem diversos algoritmos de solução para MDP-IPs, muitas vezes eles exigem chamadas externas de rotinas de otimização que podem ser extremamente custosas. Para resolver esta deficiência, nesta tese, introduzimos o MDP-IP fatorado e propomos métodos eficientes de programação matemática e programação dinâmica que permitem explorar a estrutura de um domínio de aplicação. O método baseado em programação matemática propõe soluções aproximadas eficientes para MDP-IPs fatorados, estendendo abordagens anteriores de programação linear para MDPs fatorados. Essa proposta, baseada numa formulação multilinear para aproximações robustas da função valor de estados, explora a representação fatorada de um MDP-IP, reduzindo em ordens de magnitude o tempo consumido em relação às abordagens não-fatoradas previamente propostas. O segundo método proposto, baseado em programação dinâmica, resolve o gargalo computacional existente nas soluções de programação dinâmica para MDP-IPs propostas na literatura: a necessidade de resolver múltiplos problemas de otimização não-linear. Assim, mostramos como representar a função valor de maneira compacta usando uma nova estrutura de dados chamada de Diagramas de Decisão Algébrica Parametrizados, e como aplicar técnicas de aproximação para reduzir drasticamente a sobrecarga computacional das chamadas a um otimizador não-linear, produzindo soluções ótimas aproximadas com erro limitado. Nossos resultados mostram uma melhoria de tempo e até duas ordens de magnitude em comparação às abordagens tradicionais enumerativas baseadas em programação dinâmica e uma melhoria de tempo de até uma ordem de magnitude sobre a extensão de técnicas de iteração de valor aproximadas para MDPs fatorados. Além disso, produzimos o menor erro de todos os algoritmos de aproximação avaliados. When modeling real-world decision-theoretic planning problems with the framework of Markov Decision Processes(MDPs), it is often impossible to obtain a completely accurate estimate of transition probabilities. For example, uncertainty arises in the specification of transitions due to elicitation of MDP transition models from an expert or data, or non-stationary transition distributions arising from insuficient state knowledge. In the interest of obtaining the most robust policy under transition uncertainty, Markov Decision Processes with Imprecise Transition Probabilities (MDP-IPs) have been introduced. Unfortunately, while various solutions exist for MDP-IPs, they often require external calls to optimization routines and thus can be extremely time-consuming in practice. To address this deficiency, we introduce the factored MDP-IP and propose eficient mathematical programming and dynamic programming methods to exploit its structure. First, we derive eficient approximate solutions for Factored MDP-IPs based on mathematical programming resulting in a multilinear formulation for robust maximin linear-value approximations in Factored MDP-IPs. By exploiting factored structure in MDP-IPs we are able to demonstrate orders of magnitude reduction in solution time over standard exact non-factored approaches. Second, noting that the key computational bottleneck in the dynamic programming solution of factored MDP-IPs is the need to repeatedly solve nonlinear constrained optimization problems, we show how to target approximation techniques to drastically reduce the computational overhead of the nonlinear solver while producing bounded, approximately optimal solutions. Our results show up to two orders of magnitude speedup in comparison to traditional at dynamic programming approaches and up to an order of magnitude speedup over the extension of factored MDP approximate value iteration techniques to MDP-IPs while producing the lowest error among all approximation algorithm evaluated.

Como a complexidade das tarefas realizadas por robôs móveis vêm aumentando a cada dia, a percepção do robô deve ser capaz de capturar informações mais ricas do ambiente, que permitam a tomada de decisões complexas. Entre os possíveis tipos de informação que podem ser obtidos do ambiente, as informações geométricas e semânticas têm papéis importantes na maioria das tarefas designadas a robôs. Enquanto as informações geométricas revelam como os objetos e obstáculos estão distribuídos no espaço, as informações semânticas capturam a presença de estruturas complexas e eventos em andamento no ambiente, e os condensam em descrições abstratas. Esta tese propõe uma nova técnica probabilística para construir uma representação do ambiente baseada em objetos a partir de imagens capturadas por um robô navegando com uma câmera de vídeo solidária a ele. Esta representação, que fornece descrições geométricas e semânticas de objetos, é chamada O-Map, e é a primeira do gênero no contexto de navegação de robôs. A técnica de mapeamento proposta é também nova, e resolve concomitantemente os problemas de localização, mapeamento e classificação de objetos, que surgem quando da construção de O-Maps usando imagens processadas por detectores imperfeitos de objetos e sem um sensor de localização global. Por este motivo, a técnica proposta é chamada O-SLAM, e é o primeiro algoritmo que soluciona simultaneamente os problemas de localização e mapeamento usando somente odometria e o resultado de algoritmos de reconhecimento de objetos. Os resultados obtidos através da aplicação de O-SLAM em imagens processadas por uma técnica simples de detecção de objetos mostra que o algoritmo proposto é capaz de construir mapas que descrevem consistentemente os objetos do ambiente, dado que o sistema de visão computacional seja capaz de detectá-los regularmente. Em particular, O-SLAM é eficaz em fechar voltas grandes na trajetória do robô, e obtém sucesso mesmo se o sistema de detecção de objetos posuir falhas, relatando falsos positivos e errando a classe do objeto algumas vezes, consertando estes erros. Dessa forma, O-SLAM é um passo em direção à solução integrada do problema de localização, mapeamento e reconhecimento de objetos, a qual deve prescindir de um sistema pronto de reconhecimento de objetos e gerar O-Maps somente pela fusão de informações geométricas e visuais obtidas pelo robô. As tasks performed by mobile robots are increasing in complexity, robot perception must be able to capture richer information from the environment in order to allow complex decision making. Among the possible types of information that can be retrieved from the environment, geometric and semantic information play important roles in most of the tasks assigned to robots. While geometric information reveals how objects and obstacles are distributed in space, semantic information captures the presence of complex structures and ongoing events from the environment and summarize them in abstract descriptions. This thesis proposes a new probabilistic technique to build an object-based representation of the robot surrounding environment using images captured by an attached video camera. This representation, which provides geometric and semantic descriptions of the objects, is called O-Map, and is the first of its kind in the robot navigation context. The proposed mapping technique is also new, and concurrently solves the localization, mapping and object classification problems arisen from building O-Maps using images processed by imperfect object detectors and no global localization sensor. Thus, the proposed technique is called O-SLAM, and is the first algorithm to solve the simultaneous localization and mapping problem using solely odometers and the output from object recognition algorithms. The results obtained by applying O-SLAM to images processed by simple a object detection technique show that the proposed algorithm is able to build consistent maps describing the objects in the environment, provided that the computer vision system is able to detect them on a regular basis. In particular, O-SLAM is effective in closing large loops in the trajectory, and is able to perform well even if the object detection system makes spurious detections and reports wrong object classes, fixing these errors. Thus, O-SLAM is a step towards the solution of the simultaneous localization, mapping and object recognition problem, which must drop the need for an off-the-shelf object recognition system and generate O-Maps only by fusing geometric and appearance information gathered by the robot.

Esta dissertação tem como objetivo estudar a combinação de duas técnicas de planejamento em inteligência artificial: planejamento hierárquico e planejamento sob incerteza Knightiana. Cada uma delas possui vantagens distintas, mas que podem ser combinadas, permitindo um ganho de eficiência para o planejamento sob incerteza e maior robustez a planos gerados por planejadores hierárquicos. Primeiramente, estudamos um meio de efetuar uma transformação, de modo sistemático, que permite habilitar algoritmos de planejamento determinístico com busca progressiva no espaço de estados a tratar problemas com ações não-determinísticas, sem considerar a distribuição de probabilidades de efeitos das ações (incerteza Knightiana). Em seguida, esta transformação é aplicada a um algoritmo de planejamento hierárquico que efetua decomposição a partir das tarefas sem predecessoras, de modo progressivo. O planejador obtido é competitivo com planejadores que representam o estado-da-arte em planejamento sob incerteza, devido à informação adicional que pode ser fornecida ao planejador, na forma de métodos de decomposição de tarefas. This dissertation\'s objective is to study the combination of two artificial intelligence planning techniques, namely: hierarchical planning and planning under Knightian uncertainty. Each one of these has distinct advantages, but they can be combined, allowing the planning under uncertainty a performance gain and giving the hierarchical planning the ability to produce more robust plans. First, we study a way of performing a transformation, in a sistematic way, that enables forward-chaining deterministic planning algorithms to deal with non-deterministic actions, that doesn\'t take into account the probability distribution of actions\' effects (Knightian uncertainty). Afterwards, this transformation is applied to a hierarchical planning algorithm that progressively performs decomposition starting from tasks without predecessors. The obtained planner is competitive with state-of-the-art non-deterministic planners, thanks to the additional information that can be given to the planner, in the form of task decomposition methods.

Um agente de planejamento em Inteligência Artificial deve estar preparado para lidar com aspectos dinâmicos do domínio, ou seja, com os efeitos de suas ações, bem como com mudanças provocadas por outros agentes (eventos exógenos). Neste caso, é possível identificar duas situações distintas: todas as informações necessárias sobre a dinâmica do ambiente são, de alguma forma, modeladas pelo agente e consideradas durante o planejamento; ou o agente não possui conhecimento completo do ambiente, sendo que as ações exógenas só são percebidas durante a execução do plano. Neste último caso, podem ocorrer falhas na execução das ações do agente, por exemplo, as pré-condições nas quais o plano se baseia deixam de ser verdadeiras e a meta do agente pode não ser mais alcançável. Para garantir que o agente saia da situação de plano inválido e alcance seu conjunto de metas originais, é preciso fazer um \"reparo de plano\" ou \"replanejamento\". Enquanto no replanejamento o agente abandona o plano original e constrói um novo plano para o estado atual, o reparo de plano tenta fazer um compromisso com o plano original, gerando o menor número de mudanças possível para que o novo plano atinja as metas do problema original. O processo de reparo de plano envolve duas operações básicas: (a) remover do plano as ações que estejam impedindo a execução do mesmo e (b) adicionar novas ações a fim de atingir as metas. A proposta deste trabalho é aplicar e implementar o método de reparo de plano chamado de \"refinamento reverso\". O sistema de reparo implementado será capaz de realizar duas operações: adicionar ações por meio dos procedimentos clássicos de refinamento de planos e remover ações por refinamento reverso com a adição de heurísticas para melhorar o desempenho da tarefa de reparo. An Artificial Intelligence planning agent must be prepared to deal with dynamic aspects of the domain, in other words, with its actions effects as well as the changes caused by other agents (exogenous events). In this case it is possible to identify two situations: all the necessary information about the environment dynamics are modeled by the agent and considered during the planning; or the agent has an incomplete knowledge about the environment and the exogenous events are only noted during the plan execution. In the latter case, some actions can fail, e.g. because some preconditions are no longer satisfied implying that the goals may not be achieved anymore. To make sure that the agent leaves the invalid plan situation and reach its original goals, it is necessary to make a \"plan repair\" or \"replanning\". While in the replanning the agent discards the original plan and makes a new one for the present condition, the plan repair tries to make a commitment with the original plan, making the least changes necessary to achieve the goals of the original problem. The plan repair process involves two basic operations: (a) remove the actions that are blocking the plan to be executed and (b) add new actions to achieve the goals. The proposal of this work is to apply and implement the repair method called \"unrefinement\". This repair system will be able to perform two operations: add actions through plan refinement classical procedures, and remove actions by this new method called unrefinement with addition of heuristics to improve the repair task performance.

Nesta tese, exploramos tomada de decisão com preferências parcialmente ordenadas: dadas duas ações, o indivíduo pode preferir uma ação a outra, julgá-las equivalentes, ou julgá-las incomparáveis. Tais preferências são originárias da incerteza sobre determinados estados do modelo de decisão e são reveladas pela imprecisão nos valores de probabilidade. Investigamos seis critérios de escolha de estratégias em problemas de decisão seqüenciais, representados por árvores de decisão e diagramas de influência, com probabilidades imprecisas: T-maximin, T-maximax, T-maximix, Dominação por Intervalos, Maximalidade e E-admissibilidade. Apresentamos novos algoritmos que geram estratégias para todos estes critérios. As principais contribuições deste trabalho estão na implementação dos algoritmos e na análise, sob o ponto de vista computacional, dos diversos critérios considerados como racionais em situações de incerteza representada por conjuntos de probabilidades. In this thesis we explore situations where preferences are partially ordered: given two acts, the agent may prefer one to another, or nd them to be equivalent, or nd them to be incomparable. Such preferences stem from the uncertainty associated to some states of the decisions model and are revealed by imprecision in probability values. We investigate six criteria for strategy selection in decision trees and inuence diagrams with imprecise probabilities: -maximin, -maximax, -maximix, Interval Dominance, Maximality and E-admissibility. We present new algorithms that generate strategies for all these criteria. The main contributions of this work are twofold: the implementation of these algorithms and the analysis, under the computational point of view, of the criteria considered ratio- nal in uncertain situations represented by set of probabilities.

A adoção em larga escala de redes de computadores e gerenciadores de banco de dados contribuiu para o surgimento de sistemas de informação complexos. Atualmente, estes sistemas tornaram-se elementos essenciais na vida das pessoas, dando suporte a processos de negócio e serviços corporativos indispensáveis à sociedade, como automação bancária e telefonia. A utilização de componentes na estruturação destes sistemas promove maior qualidade e flexibilidade ao produto e agiliza o processo de desenvolvimento. Entretanto, para que estes benefícios sejam totalmente observados, é fundamental que os provedores de componentes de prateleira projetem especificações precisas, completas e consistentes. Geralmente, as especificações omitem ou negligenciam o comportamento dos componentes nas situações de falha. Desta forma, a utilização de componentes não confiáveis, cujos comportamentos não podem ser inteiramente previstos, compromete seriamente o projeto de sistemas tolerantes a falhas. Uma estratégia para a especificação de componentes tolerantes a falhas é informar a ocorrência de erros através de exceções e realizar a recuperação dos mesmos por rotinas de tratamento correspondentes. A especificação deve separar claramente o comportamento normal do excepcional, destinado à recuperação do erro. Entretanto, em sistemas concorrentes e distribuídos, a especificação apenas deste tratamento local não é suficiente. Uma exceção pode ser lançada em decorrência de erros sistêmicos (i.e. problemas de rede) que afetam todo o sistema. Assim, determinadas exceções devem ser tratadas em nível arquitetural, envolvendo os demais componentes no tratamento. O modelo conceitual de ações Atômicas Coordenadas (ações CA - Coordinated Atomic actions), bastante aplicado na estruturação de sistemas tolerantes a falhas, define um mecanismo geral para a coordenação do tratamento excepcional dos componentes, que cooperam na execução das atividades e competem por recursos compartilhados. Portanto, o modelo de ações CA oferece uma solução potencialmente viável para a especificação do tratamento de exceções em nível arquitetural. Este trabalho propõe um framework para a especificação do tratamento de exceções em nível arquitetural, baseando-se no modelo de aninhamento de ações CA e utilizando a linguagem orientada a eventos CSP (Communicating Sequential Processes). Sua principal característica é prover um protocolo padronizado para a coordenação do tratamento de exceções, que envolve a cooperação dos componentes do sistema. Além disso, é apresentada uma estratégia para a verificação formal dos sistemas na ferramenta FDR (Failure Divergence Refinement), com base no modelo de refinamento por rastros. The widespread scale adoption of computer networks and database management systems has contributed to the arising of complex information systems. Nowadays, these systems have become essential aspects in the everyday life, supporting business processes and indispensable enterprise services to society such as banking automation and telephony. The usage of components in structuring of these systems promotes higher quality and flexibility to the product and accelerates the software development process. However, in order to fully observe the benefits it is essential that the suppliers of these COTS (commercial off-the-shelf) design precise, complete and consistent specifications. Generally, the specifications omit or neglect the behavior of these components in exceptional situations. Therefore, the usage of untrustworthy components whose behavior cannot be entirely foreseen seriously compromise the design of fault-tolerant systems. One of the strategies used for the specification of fault-tolerant components is to inform the occurrence of errors through exceptions and make its recovering by the correspondent exception handling routines. The specification should separate clearly the normal behavior from the exceptional one, specially designed for error recovery. However, in concurrent and distributed systems, specification of local exception handling is not enough. An exception could be raised as a result of systemic errors (i.e. network errors) which affect the entire system, thus specific types of exceptions should be treated at an architectural level involving all the other components in this handling activity. The conceptual model of Coordinated Atomic (CA) actions, often applied in the structuring of fault-tolerant systems, defines a general mechanism for coordination of exception handling with components that cooperate while executing activities and compete for shared resources. Therefore, the model of CA actions offers a perfectly viable solution for the specification of exception handling at an architectural level. This work proposes a framework for the specification of exception handling at an architectural level, based on the nesting model of CA actions and using the event-oriented language CSP (Communicating Sequential Processes). Its main characteristic is to provide a standardized protocol for coordination of exception handling that involves the cooperation of system components. Moreover, it is presented a formal strategy for system verification using the FDR (Failure Divergence Refinement) tool, based on the traces refinement model.

A falta de materiais instrucionais digitais disponíveis em larga escala e com baixo custo levou à criação da tecnologia de Objetos de Aprendizagem (OAs) [Wiley 2000]. Nessa tecnologia, materiais para ensino e aprendizagem são construídos na forma de pequenos componentes (objetos) para que possam ser combinados de várias maneiras diferentes, ou seja, possam ser reutilizados na composição de seqüências didáticas que cubram um determinado domínio de aprendizagem, por exemplo, Geometria Euclidiana ou Eletrostática. Nessa visão, cabe ao professor (ou ao próprio aluno) decidir qual é a seqüência de OAs mais adequada para um determinado contexto instrucional (ou de acordo com as preferências do aluno). OAs podem estar disponíveis em grandes repositórios na Internet, de maneira que qualquer usuário - professor ou estudante - possa buscá-los e recuperá-los de acordo com suas necessidades. Para tornar a busca e recuperação mais ecientes, cada objeto precisa ser descrito num formato padrão o que permite a sua utilização em diversas plataformas. Atualmente, cada uma das tarefas associadas à descoberta e utilização de OAs é realizada de forma não automatizada, ou seja, um professor ao elaborar um curso, deve fazer uma busca nos repositórios de OAs disponíveis, ou na própria Web, e selecionar os objetos de interesse. Nessa etapa, é preciso que o professor analise cada OA recuperado a m de decidir: (a) se ele satisfaz ou não os objetivos didáticos em questão; (b) em que ponto do curso o OA pode ser inserido, dadas as suposições sobre o conhecimento prévio feitas no projeto de construção do OA; (c) qual é o nível de diculdade, o contexto instrucional e o tipo de recurso de aprendizagem do OA desejados (por exemplo, exercício, simulação, notas de aula, testes etc.). Além disso, quando o professor faz a busca por OAs, ele utiliza somente palavras-chave, sem nenhuma referência sobre a estrutura do domínio de conhecimento. Essa é a principal limitação dessa tecnologia: não existem padrões para a representação do conteúdo de um OA, que possibilite automatizar a recuperação e análise de OAs em termos do seu conteúdo relacionado ao domínio no qual ele se insere. Esse trabalho propõe uma ferramenta, chamada SEQUOA (Seqüenciamento de OAs), que dê suporte ao professor para a tarefa de seleção e composição de OAs, com base na tecnologia da Web Semântica. Com esse objetivo, foi feito um estudo de caso para o domínio da Eletrostática. Foram construídas ontologias para: formalizar as descrições de OAs, baseando-se em padrões largamente adotados, e descrever o domínio de aprendizagem de uma maneira didática (segundo educadores experientes no domínio em questão). O uso dessas ontologias permite que a ferramenta SEQUOA seja capaz de realizar inferências sobre as diferentes características dos OAs e gerar um conjunto de seqüências alternativas de OAs, para um determinado domínio de aprendizagem, promovendo assim o reuso de OAs. The lack of large amounts of digital instructional material available at a low cost lead to the creation of Learning Objects (LOs) [Wiley 2000]. With this technology, instructional material is built in the form of small components (objects) that can be combined in dierent arrangements allowing for their re-utilization in the composition of didactic sequences that cover a domain, for example, Euclidian Geometry or Electrostatic. Hence it is the teacher (or even the student) who decides which is the more appropriate LO sequence for a determined instructional context (or in accordance with the students\' preference). LOs maybe available in Internet repositories, so that any user a teacher or a student can search and retrieve them as needed. To make this search and retrieval more eective, every object must be described in a standard format what is also useful to allow its use in any platform. Currently, the tasks associated with LOs discovery and utilization are accomplished manually. The teacher who needs to elaborate an instructional module must do a search in the available repositories and select useful and relevant objects inspecting one by one, eventually spending large amounts of time searching for keywords. In this stage its necessary that the teacher analyzes each retrieved LO in order to decide: a) if it satises or not the course didactic objectives; b) in each part of the course the LO may be inserted, considering its assumptions about the previous knowledge made in its design; c) which are the diculty level, instructional context and type of earning resource (example, exercise, simulation, notes, tests, etc). Moreover, when a teacher searches for LOs, she only has keywords, there are no references to the knowledge domain structure. This is this technology main shortcoming: there are no standards to represent a LO content which makes it possible to automate LOs retrieval and analysis considering its content related to the knowledge domain it pertains to. Automating this search has been the aim of many research projects, with the goal of time saving and optimality, in terms of selecting the LOs that will best satisfy the teacher\'s needs. Based on Articial Intelligence techniques, this work proposes a new way of structuring a learning domain and a framework that allows a teacher to select LOs automatically in accordance with her preferences or needs. This work also proposes a set of ontologies to formalize LOs descriptions, based on domain knowledge structure and on standard descriptions that are widely adopted, allowing the utilization of theorem provers based on description logics to make inferences

Neste trabalho, apresentamos o desenvolvimento de ferramentas no programa iGeom - Geometria Interativa na Internet, para ensino-aprendizagem de Geometria, dando destaque aos recursos que facilitam a integração e uso deste programa, principalmente em ambientes de educação a distância via Internet. Atualmente, este tipo de programa é bastante conhecido e a Geometria que ele possibilita é usualmente denominada Geometria Dinâmica. Em poucas palavras, um programa de Geometria Dinâmica é a implementação computacional da régua e do compasso, permitindo que os objetos construídos sejam movidos mantendo-se às propriedades da construção. Dentre os principais recursos desenvolvidos, destacamos a autoria e a validação automática de exercícios e a comunicação com servidores, que podem ser utilizados para integrarem o iGeom em sistemas gerenciadores de cursos pela Web. Deste modo, se integrado a um sistema gerenciador, estes recursos podem ser utilizados para facilitar a tarefa do professor, que poderá criar exercícios diretamente pela Web e não precisará avaliar pessoalmente as respostas de cada aluno, e também para que o aluno saiba de imediato se sua solução está dentro do esperado pelo professor.¶ In this work, we present the development of tools on the software iGeom - Interactive Geometry on Internet, which can be used for teaching and learning Geometry. We highlight the features that simplify the integration and the use of the iGeom in distance education through Internet mainly. Presently, this kind of program is well known and the Geometry it allows is usually named Dynamic Geometry. Concisely, a Dynamic Geometry software is the computational implementation of the ruler and compass. It allows the user to drag objects and to automatically redraw the whole construction while preserving their mathematical properties. We focus three features among the main developed ones: the communication, the authoring and the automatic checking of exercises. These resources simplify the teacher’s task, when integrated into a learning management system. With them, the teacher can create exercises directly on the Web leaving to the software the task of checking each student’s answer. Moreover, the student can have, in real time, an evaluation of his own performance.