Fundação de Apoio a Pesquisa e à Inovação Tecnológica do Estado de Sergipe - FAPITEC/SE / The evolution of mobile robotics has directed research in this area to solve increasingly complex tasks. In these tasks, when optimized behaviors are specified, a deliberative process is required in order to determine the best action before executing it. In navigation architectures, the deliberation process is usually accomplished by a motion planning strategy. One of the motion planning techniques which has received much of the attention from the researches is the Rapidly-exploring Random Tree (RRT), because of its capacity to reduce representation dimension quickly. The vast majority of the research developed in this area, so far, is mainly focused on developing variants of the RRT for specific problems, not providing detailed analyzes regarding the influence of different variables in the classical algorithm. In this master’s work the focus is precisely to fill this gap by investigating the influence of different variables that compose the classic RRT algorithm, in other words, a detailed analysis of the RRT degrees of freedom and its influence on the final result. In addition, unlike most RRT papers, where the objective is to find the best path between two points, this dissertation presents a new approach in RRT searches by combining the search for a compact and complete representation of the configuration space with a low computational cost and knowledge of only the robot’s goal configuration. To validate and analyze the results obtained, tests by simulation are performed. / A evolução na área de robótica móvel tem direcionado as pesquisas nesse campo para a solução de tarefas cada vez mais complexas. Nessas tarefas, quando comportamentos otimizados são especificados, faz-se necessário um processo de deliberação para determinar a melhor ação a ser tomada antes de executá-la. Em arquiteturas de navegação, o processo de deliberação é normalmente realizado por uma estratégia de planejamento de movimento. Uma das técnicas de planejamento de movimento que tem recebido grande parte da atenção dos pesquisadores dessa área nos últimos tempos é a Rapidly-exploring Random Tree (RRT), pela sua capacidade de reduzir a dimensão da representação de forma rápida. A maioria dos trabalhos de pesquisa desenvolvidos utilizando RRT, até o momento, tem como foco principal desenvolver variantes dessa técnica para problemas específicos, sem apresentar análises aprofundadas quanto a influência das diferentes variáveis do algoritmo clássico. Neste trabalho de mestrado o foco é, justamente, suprir essa carência, investigando a influência das diferentes variáveis que compõem o algoritmo clássico da RRT, ou seja, uma análise detalhada dos graus de liberdade da RRT e suas influências no resultado final. Além disso, diferentemente da maioria dos trabalhos em RRT, em que o objetivo é encontrar o melhor caminho entre dois pontos, esta dissertação apresenta uma nova abordagem nas pesquisas em RRT ao combinar a busca por uma representação compacta e completa do espaço de configuração com um baixo custo computacional e com o conhecimento a priori apenas da configuração de destino do robô. Para validar e analisar os resultados obtidos, testes por simulação são realizados.

O relacionamento de dados record linkage, originou-se na área da saúde pública e atualmente é aplicado em várias outras áreas como: epidemiologia, pesquisa médica, criação de ensaios clínicos, na área de marketing, gestão de relacionamento com o cliente, detecção de fraude, aplicação da lei e na administração do governo. A técnica consiste no processo de comparação entre dois ou mais registros em diferentes bases de dados e as principais estratégias de record linkage são: manual, deterministic record linkage (DRL) e probabilistic record linkage (PRL). Este estudoteve como objetivo aplicar o record linkage em bases de dados heterogêneas, utilizadas pela rede de atenção à saúde do município de Ribeirão Preto e identificar entre elas a melhor estratégia a ser adotada para a integração de bases de dados na área da saúde. As bases de dados da secretaria Municipal de Saúde de Ribeirão Preto (SMS-RP) e do Hospital das Clínicas da Faculdade de Medicina de Ribeirão Preto (HCFMRP/USP) foram objeto deste estudo, tendo como critério de inclusão apenas os registros de pacientes em que o município de residência informado correspondia ao município de Ribeirão Preto e o atendimento tivesse ocorrido na Unidade Básica Distrital e de Saúde (UDBS) - Centro Saúde Escola Joel Domingos Machado\" (CSE-Sumarezinho) nos anos de janeiro de 2006 a agosto de 2008 e no HCFMRP/USP. Foi selecionada uma amostra aleatória simples resultando em um conjunto de 1.100 registros de pacientes na base de dados do CSE-Sumarezinho e de 370.375 registros na base de dados do HCFMRP/USP. Foram, então, selecionadas quatro variáveis de relacionamento (nome, nome da mãe, sexo e data de nascimento). As estratégias adotadas foram: DRL exato, DRL com discordância em uma variável de relacionamento, e baseada em funções de similaridades (Dice, Levenshtein, Jaro e Jaro-Winkler) e, por fim, PRL. A estratégia DRL exato resultou em 334 registros pareados e na abordagem com discordância de uma variável foram 335, 343, 383 e 495, sendo as variáveis discordantes sexo, data de nascimento, nome e nome da mãe respectivamente. Quanto ao uso das funções de similaridades, as que mais se destacaram foram Jaro-Winkler e Jaro. Quanto à acurácia dos métodos aplicados, o PRL (sensibilidade = 97,75% (CI 95% 96,298,8) e especificidade = 98,55% (CI 95% 97,0-99,4)) obteve melhor sensibilidade e especificidade, seguido do DRL com as funções de similaridade Jaro-Winkler sensibilidade = 91,3% (CI 95% 88,793,4) e especificidade = 99% (CI 95% 97,6-99,7)) e Jaro (sensibilidade = 73,1% (CI 95% 69,476,6) e especificidade = 99,6% (CI 95% 98,5-99,9)). Quanto à avaliação da área sob a curva ROC do PRL, observou-se que há diferença estatisticamente significativa (p = 0,0001) quando comparada com os métodos DRL com discordância da variável nome da mãe, Jaro-Winkler e Jaro. Os resultados obtidos permitem concluir que o método PRL é mais preciso dentre as técnicas avaliadas. Mas as técnicas com a função de similaridade de Jaro-Winkler e Jaro também são alternativas viáveis interessantes devido à facilidade de utilização apesar de apresentarem o valor de sensibilidade ligeiramente menor que o PRL. / The record linkage originated in the area of public health and is currently applied in several other areas such as epidemiology, medical research, establishment of clinical trials, in the area of marketing, manager customer relationships, fraud detection, law enforcement and government administration. The technique consists on the comparison between two or more records in different databases and their key strategies are: manual comparison, Deterministic Record Linkage (DRL), and Probabilistic Record Linkage (PRL).This study aimed to apply the record linkage in heterogeneous databases, used by the network of health care in Ribeirão Preto and identify the best strategy to be adopted for the integration of databases in health care. The databases that were evaluated in this study were of the Municipal Health Department of Ribeirão Preto (SMS-RP) and of the Clinical Hospital of the School of Medicine of Ribeirao Preto (HCFMRP/USP) having as inclusion criterion only the records of patients in the county of residence reported corresponded to the city of Ribeirão Preto and care had taken place in the Basic District Health Unit (UDBS) - School Health Center \"Joel Domingos Machado\" (CSE-Sumarezinho) included in the years from January 2006 to August 2008 and in the HCFMRP/USP. Held to select a simple random sample resulted in a set of 1,100 patient records in the database of the CSE-Sumarezinho and 370,375 records in the database of HCFMRP/USP. Then there was the selection of four linking variables (name, mother\'s name, gender and birth date). The strategies adopted were: the exact DRL, DRL with one variable where the linking is disagreement, applied with similarity functions (Dice, Levenshtein, Jaro, and Jaro-Winkler), and, finally, PRL. The strategy of the exact DRL resulted in 334 matched records and strategy in dealing with disagreement of one variable were 335, 343, 383 and 495, to the following variables discordant gender, birth date, name and mother\'s name, respectively. Regarding the use of similarity functions which most stood out were Jaro and Jaro-Winkler. Regarding the accuracy of the methods applied, the PRL obtained better sensitivity and specificity (sensitivity = 97,75% (CI 95% 96,298,8) and specificity = 98.55% (95% CI 97.0 to 99.4)), followed by the DRL with the similarity functions Jaro-Winkler (sensitivity = 91.3% (95% CI 88.7 to 93.4) and specificity = 99% (95% CI 97.6 to 99, 7)) and then by Jaro (sensitivity = 73.1% (95% CI 69.4 to 76.6) = 99.6% and specificity (95% CI 98.5 to 99.9)). The evaluation of the area under the ROC curve in the PRL, was observed that there is statistically significant difference (p = 0.0001) if it is compared with the DRL methods when there is disagreement in the variable mother\'s name, as well as for Jaro and for Jaro-Winkler. The results indicate that the PRL method is most accurate among the techniques evaluated. Although the techniques with the similarity function of Jaro-Winkler and Jaro were also interesting viable options due to the ease of use, although having the sensitivity value slightly smaller than the PRL.

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.

Quando um robô autônomo tenta resolver as tarefas de navegação dentro de um ambiente real interno usando relações qualitativas, vários problemas aparecem tais como observação parcial do ambiente e percepção incerta. Isso ocorre porque os sensores do robô não proporcionam informação suficiente para perceber completamente as situações do ambiente, além de incorporarem ruído no processo. A web semântica dota o robô autônomo com a habilidade de obter conhecimento de senso comum extraído da web, conhecimento este que os sensores do robô não podem proporcionar. Porém, nem sempre é fácil levar efetivamente estes recursos semânticos da web ao uso prático. Neste trabalho, foi examinado o uso de recursos semânticos da web na navegação robótica; mais especificamente, em uma navegação qualitativa onde o raciocínio incerto desempenha um papel significativo. Nós avaliamos o uso de uma representação relacional; particularmente, na combinação da informação semântica web e dos dados de baixo nível proporcionados pelos sensores, permitindo uma descrição de objetos e das relações entre os mesmos. Esta representação também permite o uso de abstração e generalização das situações do ambiente. Este trabalho propõe a arquitetura Web-based Relational Robotic Architecture (WRRA )para navegação robótica que combina os dados de baixo nível dos sensores do robô e os recursos web semânticos existentes baseados em lógica descritiva probabilística, como aprendizagem e planejamento relacional probabilístico. Neste trabalho, mostramos os benefícios desta arquitetura em um robô simulado, apresentando um estudo de caso sobre como os recursos semânticos podem ser usados para lidar com a incerteza da localização e o mapeamento em um problema prático. / When an autonomous robot attempts to solve navigation tasks in a qualitative relational way within a real indoor environments, several problems appear such as partial observation of the environment, and uncertain perception, since the robots sensors do not provide enough information to perceive completely the environment situations, besides the sensors incorporate noise in the process. The semantic web information endows the autonomous robot with the ability to obtain common sense knowledge from the web that the robot\'s sensors cannot provide. However, it is not always easy to effectively bring these semantic web resources into practical use. In this work, we examine the use of semantic web resources in robot navigation; more specifically, in qualitative navigation where uncertain reasoning plays a significant role. We evaluate the use of a relational representation; particularly, in the combination of the semantic web and the low-level data sensor information, which allows a description of relationships among objects. This representation also allows the use of abstraction and generalization of the environment situations. This work proposes the framework Web-based Relational Robotic Architecture WRRA for robot navigation that connects the low-level data from robot\'s sensors and existing semantic web resources based on probabilistic description logics, with probabilistic relational learning and planning. We show the benefits of this framework in a simulated robot, presenting a case study on how semantic web resources can be used to face location and mapping uncertain in a practical problem.

A transmissão de energia em corrente contínua, a partir de conversores fonte de tensão, é oportuna ao progresso do sistema elétrico de potência e tem permitido vantajosas aplicações. Muito se dá, devido ao emprego na conexão de sistemas com frequências distintas, além da redução de perdas na transmissão, provida pelas características operacionais destes. VSCs também promovem o controle do fluxo de potência, possibilitando uma efetiva contextualização no âmbito das redes inteligentes. Diante deste cenário, este estudo pretende construir um perfil de corrente através do Cálculo de Curto-Circuito Probabilístico, que emprega a Simulação de Monte Carlo, para prover as informações ao desenvolvimento de projetos de equipamentos, ajustes da proteção e controle de sistemas de transmissão em corrente contínua. A Simulação de Monte Carlo requer muitas iterações, tendo um custo computacional elevado. Se forem executadas em programas comerciais, exige um tempo elevado para leitura dos sinais em arquivos. Devido a isso, um programa de código livre usando linguagem C++, foi desenvolvido para possibilitar acesso aos sinais de interesse ainda em memória, reduzindo desta forma o tempo computacional. Além disso, para melhorar a performance, foram usadas técnicas de processamento paralelo e de computação em nuvem. Desta forma, este estudo contribui com informações indispensáveis ao projeto de equipamentos de proteção dos sistemas de transmissão em corrente contínua de forma a cooperar com o desenvolvimento consistente desta tecnologia. / Transmitting electrical power in direct current using a VSC is suitable for the progress of these systems and has remarkable and advantageous applications. This happens in order to connect two systems with distinct frequencies. This type of line is also used in the reduction of losses in transmission over long distances, provided by their operating characteristics. These converters also promote the control of power flow between distinct generation units, making them effective in the context of Smart Grids. Based on this, the purpose of this research is to construct a profile of a current using a Probabilistic Short-Circuit Analysis by Monte Carlo Simulation to provide basic data to the optimum development of design equipment in protection and control. The Monte Carlo Simulation requires many iterations to find an optimal result. An open source program using C++ language was developed to describe all the system models variables in order to decrease the computation time, as it is time consuming to read signals stored on a disk using commercial software. Moreover, in order to lower computation costs, parallel process techniques and cloud computing were used. Therefore, this study contributes to the literature by providing essential information for designing equipment for Direct Current transmission protection systems.

Planning is the sub-area of artificial intelligence that studies the process of selecting actions to lead an agent, e.g. a robot or a softbot, to a goal state. In many realistic scenarios, any choice of actions can lead the robot into a dead-end state, that is, a state from which the goal cannot be reached. In such cases, the robot can, pro-actively, resort to human help in order to reach the goal, an approach called symbiotic autonomy. In this work, we propose two different approaches to tackle this problem: (I) contingent planning, where the initial state is partially observable, configuring a belief state, and the outcomes of the robot actions are non-deterministic; and (II) probabilistic planning, where the initial state may be partially or totally observable and the actions have probabilistic outcomes. In both approaches, the human help is considered a scarce resource that should be used only when necessary. In contingent planning, the problem is to find a policy (a function mapping belief states into actions) that: (i) guarantees the agent will always reach the goal (strong policy); (ii) guarantees that the agent will eventually reach the goal (strong cyclic policy), or (iii) does not guarantee achieving the goal (weak policy). In this scenario, we propose a contingent planning system that considers human help to transform weak policies into strong (cyclic) policies. To do so, two types of human help are included: (i) human actions that modify states and/or belief states; and (ii) human observations that modify belief states. In probabilistic planning, the problem is to find a policy (a function mapping between world states and actions) that can be one of these two types: a proper policy, where the agent has probability 1 of reaching the goal; or an improper policy, in the case of unavoidable dead-ends. In general, the goal of the agent is to find a policy that minimizes the expected accumulated cost of the actions while maximizes the probability of reaching the goal. In this scenario, this work proposes probabilistic planners that consider human help to transform improper policies into proper policies however, considering two new (alternative) criteria: either to minimize the probability of using human actions or to minimize the expected number of human actions. Furthermore, we show that optimal policies under these criteria can be efficiently computed either by increasing human action costs or given a penalty when a human help is used. Solutions proposed in both scenarios, contingent planning and probabilistic planning with human help, were evaluated over a collection of planning problems with dead-ends. The results show that: (i) all generated policies (strong (cyclic) or proper) include human help only when necessary; and (ii) we were able to find policies for contingent planning problems with up to 10^15000 belief states and for probabilistic planning problems with more than 3*10^18 physical states. / Planejamento é a subárea de Inteligência Artificial que estuda o processo de selecionar ações que levam um agente, por exemplo um robô, de um estado inicial a um estado meta. Em muitos cenários realistas, qualquer escolha de ações pode levar o robô para um estado que é um beco-sem-saída, isto é, um estado a partir do qual a meta não pode ser alcançada. Nestes casos, o robô pode, pró-ativamente, pedir ajuda humana para alcançar a meta, uma abordagem chamada autonomia simbiótica. Neste trabalho, propomos duas abordagens diferentes para tratar este problema: (I) planejamento contingente, em que o estado inicial é parcialmente observável, configurando um estado de crença, e existe não-determinismo nos resultados das ações; e (II) planejamento probabilístico, em que o estado inicial é totalmente observável e as ações tem efeitos probabilísticos. Em ambas abordagens a ajuda humana é considerada um recurso escasso e deve ser usada somente quando estritamente necessária. No planejamento contingente, o problema é encontrar uma política (mapeamento entre estados de crença e ações) com: (i) garantia de alcançar a meta (política forte); (ii) garantia de eventualmente alcançar a meta (política forte-cíclica), ou (iii) sem garantia de alcançar a meta (política fraca). Neste cenário, uma das contribuições deste trabalho é propor sistemas de planejamento contingente que considerem ajuda humana para transformar políticas fracas em políticas fortes (cíclicas). Para isso, incluímos ajuda humana de dois tipos: (i) ações que modificam estados do mundo e/ou estados de crença; e (ii) observações que modificam estados de crenças. Em planejamento probabilístico, o problema é encontrar uma política (mapeamento entre estados do mundo e ações) que pode ser de dois tipos: política própria, na qual o agente tem probabilidade 1 de alcançar a meta; ou política imprópria, caso exista um beco-sem-saída inevitável. O objetivo do agente é, em geral, encontrar uma política que minimize o custo esperado acumulado das ações enquanto maximize a probabilidade de alcançar a meta. Neste cenário, este trabalho propõe sistemas de planejamento probabilístico que considerem ajuda humana para transformar políticas impróprias em políticas próprias, porém considerando dois novos critérios: minimizar a probabilidade de usar ações do humano e minimizar o número esperado de ações do humano. Mostramos ainda que políticas ótimas sob esses novos critérios podem ser computadas de maneira eficiente considerando que ações humanas possuem um custo alto ou penalizando o agente ao pedir ajuda humana. Soluções propostas em ambos cenários, planejamento contingente e planejamento probabilístico com ajuda humana, foram empiricamente avaliadas sobre um conjunto de problemas de planejamento com becos-sem-saida. Os resultados mostram que: (i) todas as políticas geradas (fortes (cíclicas) ou próprias) incluem ajuda humana somente quando necessária; e (ii) foram encontradas políticas para problemas de planejamento contingente com até 10^15000 estados de crença e para problemas de planejamento probabilístico com até 3*10^18 estados do mundo.

Os processos de decisão de Markov (Markov Decision Process - MDP) têm sido usados para resolução de problemas de tomada de decisão sequencial. Existem problemas em que lidar com os riscos do ambiente para obter um resultado confiável é mais importante do que maximizar o retorno médio esperado. MDPs que lidam com esse tipo de problemas são chamados de processos de decisão de Markov sensíveis a risco (Risk-Sensitive Markov Decision Process - RSMDP). Dentre as diversas variações de RSMDP, estão os trabalhos baseados em utilidade exponencial que utilizam um fator de risco, o qual modela a atitude a risco do agente e que pode ser propensa ou aversa. Os algoritmos existentes na literatura para resolver esse tipo de RSMDPs são ineficientes se comparados a outros algoritmos de MDP. Neste projeto, é apresentada uma solução que pode ser usada em problemas maiores, tanto por executar cálculos apenas em estados relevantes para atingir um conjunto de estados meta partindo de um estado inicial, quanto por permitir processamento de números com expoentes muito elevados para os ambientes computacionais atuais. Os experimentos realizados evidenciam que (i) o algoritmo proposto é mais eficiente, se comparado aos algoritmos estado-da-arte para RSMDPs; e (ii) o uso da técnica LogSumExp permite resolver o problema de trabalhar com expoentes muito elevados em RSMDPs. / Markov Decision Process (MDP) has been used very efficiently to solve sequential decision-making problems. There are problems where dealing with environmental risks to get a reliable result is more important than maximizing the expected average return. MDPs that deal with this type of problem are called risk-sensitive Markov decision processes (RSMDP). Among the several variations of RSMDP are the works based on exponential utility that use a risk factor, which models the agent\'s risk attitude that can be prone or averse. The algorithms in the literature to solve this type of RSMDPs are inefficient when compared to other MDP algorithms. In this project, a solution is presented that can be used in larger problems, either by performing calculations only in relevant states to reach a set of meta states starting from an initial state, or by allowing the processing of numbers with very high exponents for the current computational environments. The experiments show that (i) the proposed algorithm is more efficient when compared to state-of-the-art algorithms for RSMDPs; and (ii) the LogSumExp technique solves the problem of working with very large exponents in RSMDPs

Utilizou-se neste trabalho um sistema de filas contendo três servidores exponenciais, heterogêneos, operando em paralelo. Trocas entre filas são permitidas após o usuário analisar dois aspectos: a diferença entre o tamanho das filas envolvidas na troca e o grau de vizinhança entre elas. O jockeying não é obrigatório, podendo os usuários optar por ele com uma probabilidade de ocorrência de acordo com os aspectos citados. Como resultado deste estudo foi obtida uma equação geral que representa o sistema. O sistema M/(M/1)3 com jockeying probabilístico tem uma ociosidade bem menor que o tradiconal M/Mi/3, alimentado por fila única. Outras características foram analisadas. / We consider a parallel queueing system with three exponential heterogeneous servers where is allowed jockey among queues with no obligation and the customers may choose for it with an occurrence probability after they have been analyzed two aspects: the difference between involved lines lenght in jockeying and the neighborhood degree among them. The effect of this study is a general equation which represents the system. The M/(M/1)3 system with probabilistc jockeying has a smaller idleness than the traditional M/Mi/3 fed from a single queue. We also analysed other characteristics.

Planejamento Probabilístico estuda os problemas de tomada de decisão sequencial de um agente, em que as ações possuem efeitos probabilísticos, modelados como um processo de decisão markoviano (Markov Decision Process - MDP). Dadas a função de transição de estados probabilística e os valores de recompensa das ações, é possível determinar uma política de ações (i.e., um mapeamento entre estado do ambiente e ações do agente) que maximiza a recompensa esperada acumulada (ou minimiza o custo esperado acumulado) pela execução de uma sequência de ações. Nos casos em que o modelo MDP não é completamente conhecido, a melhor política deve ser aprendida através da interação do agente com o ambiente real. Este processo é chamado de aprendizado por reforço. Porém, nas aplicações em que não é permitido realizar experiências no ambiente real, por exemplo, operações de venda, é possível realizar o aprendizado por reforço sobre uma amostra de experiências passadas, processo chamado de aprendizado por reforço em lote (Batch Reinforcement Learning). Neste trabalho, estudamos técnicas de aprendizado por reforço em lote usando um histórico de interações passadas, armazenadas em um banco de dados de processos, e propomos algumas formas de melhorar os algoritmos existentes. Como um estudo de caso, aplicamos esta técnica no aprendizado de políticas para o processo de venda de impressoras de grande formato, cujo objetivo é a construção de um sistema de recomendação de ações para vendedores iniciantes. / Probabilistic planning studies the problems of sequential decision-making of an agent, in which actions have probabilistic effects, and can be modeled as a Markov decision process (MDP). Given the probabilities and reward values of each action, it is possible to determine an action policy (in other words, a mapping between the state of the environment and the agent\'s actions) that maximizes the expected reward accumulated by executing a sequence of actions. In cases where the MDP model is not completely known, the best policy needs to be learned through the interaction of the agent in the real environment. This process is called reinforcement learning. However, in applications where it is not allowed to perform experiments in the real environment, for example, sales process, it is possible to perform the reinforcement learning using a sample of past experiences. This process is called Batch Reinforcement Learning. In this work, we study techniques of batch reinforcement learning (BRL), in which learning is done using a history of past interactions, stored in a processes database. As a case study, we apply this technique for learning policies in the sales process for large format printers, whose goal is to build a action recommendation system for beginners sellers.

As proteínas são moléculas que desempenham funções essenciais para a vida. Para entender a função de uma proteína é preciso conhecer sua estrutura tridimensional. No entanto, encontrar a estrutura da proteína pode ser um processo caro e demorado, exigindo profissionais altamente qualificados. Neste sentido, métodos computacionais têm sido investigados buscando predizer a estrutura de uma proteína a partir de uma sequência de aminoácidos. Em geral, tais métodos computacionais utilizam conhecimentos de estruturas de proteínas já determinadas por métodos experimentais, para tentar predizer proteínas com estrutura desconhecida. Embora métodos computacionais como, por exemplo, o Rosetta, I-Tasser e Quark tenham apresentado sucesso em suas predições, são apenas capazes de produzir estruturas significativamente semelhantes às já determinadas experimentalmente. Com isso, por utilizarem conhecimento a priori de outras estruturas pode haver certa tendência em suas predições. Buscando elaborar um algoritmo eficiente para Predição de Estruturas de Proteínas livre de tendência foi desenvolvido um Algoritmo de Estimação de Distribuição (EDA) específico para esse problema, com modelagens full-atom e algoritmos ab initio. O fato do algoritmo proposto ser ab initio é mais interessante para aplicação envolvendo proteínas com baixa similaridade, com relação às estruturas já conhecidas. Três tipos de modelos probabilísticos foram desenvolvidos: univariado, bivariado e hierárquico. O univariado trata o aspecto de multi-modalidade de uma variável, o bivariado trata os ângulos diedrais (Φ Ψ) de um mesmo aminoácido como variáveis correlacionadas. O hierárquico divide o problema em subproblemas e tenta tratá-los separadamente. Os resultados desta pesquisa mostraram que é possível obter melhores resultados quando considerado a relação bivariada (Φ Ψ). O hierárquico também mostrou melhorias nos resultados obtidos, principalmente para proteínas com mais de 50 resíduos. Além disso, foi realiza uma comparação com algumas heurísticas da literatura, como: Busca Aleatória, Monte Carlo, Algoritmo Genético e Evolução Diferencial. Os resultados mostraram que mesmo uma metaheurística pouco eficiente, como a Busca Aleatória, pode encontrar a solução correta, porém utilizando muito conhecimento a priori (predição que pode ser tendenciosa). Por outro lado, o algoritmo proposto neste trabalho foi capaz de obter a estrutura da proteína esperada sem utilizar conhecimento a priori, caracterizando uma predição puramente ab initio (livre de tendência). / Proteins are molecules that perform critical roles in the living organism and they are essential for their lifes. To understand the function of a protein, its 3D structure should be known. However, to find the protein structure is an expensive and a time-consuming task, requiring highly skilled professionals. Aiming to overcome such a limitation, computational methods for Protein Structure Prediction (PSP) have been investigated, in order to predict the protein structure from its amino acid sequence. Most of computational methods require knowledge from already determined structures from experimental methods in order to predict an unknown protein. Although computational methods such as Rosetta, I-Tasser and Quark have showed success in their predictions, they are only capable to predict quite similar structures to already known proteins obtained experimentally. The use of such a prior knowledge in the predictions of Rosetta, I-Tasser and Quark may lead to biased predictions. In order to develop a computational algorithm for PSP free of bias, we developed an Estimation of Distribution Algorithm applied to PSP with full-atom and ab initio model. A computational algorithm with ab initio model is mainly interesting when dealing with proteins with low similarity with the known proteins. In this work, we developed an Estimation of Distribution Algorithm with three probabilistic models: univariate, bivariate and hierarchical. The univariate deals with multi-modality of the distribution of the data of a single variable. The bivariate treats the dihedral angles (Proteins are molecules that perform critical roles in the living organism and they are essential for their lifes. To understand the function of a protein, its 3D structure should be known. However, to find the protein structure is an expensive and a time-consuming task, requiring highly skilled professionals. Aiming to overcome such a limitation, computational methods for Protein Structure Prediction (PSP) have been investigated, in order to predict the protein structure from its amino acid sequence. Most of computational methods require knowledge from already determined structures from experimental methods in order to predict an unknown protein. Although computational methods such as Rosetta, I-Tasser and Quark have showed success in their predictions, they are only capable to predict quite similar structures to already known proteins obtained experimentally. The use of such a prior knowledge in the predictions of Rosetta, I-Tasser and Quark may lead to biased predictions. In order to develop a computational algorithm for PSP free of bias, we developed an Estimation of Distribution Algorithm applied to PSP with full-atom and ab initio model. A computational algorithm with ab initio model is mainly interesting when dealing with proteins with low similarity with the known proteins. In this work, we developed an Estimation of Distribution Algorithm with three probabilistic models: univariate, bivariate and hierarchical. The univariate deals with multi-modality of the distribution of the data of a single variable. The bivariate treats the dihedral angles (Φ Ψ) within an amino acid as correlated variables. The hierarchical approach splits the original problem into subproblems and attempts to treat these problems in a separated manner. The experiments show that, indeed, it is possible to achieve better results when modeling the correlation (Φ Ψ). The hierarchical model also showed that is possible to improve the quality of results, mainly for proteins above 50 residues. Besides, we compared our proposed techniques among other metaheuristics from literatures such as: Random Walk, Monte Carlo, Genetic Algorithm and Differential Evolution. The results show that even a less efficient metaheuristic such as Random Walk managed to find the correct structure, however using many prior knowledge (prediction that may be biased). On the other hand, our proposed EDA for PSP was able to find the correct structure with no prior knowledge at all, so we can call this prediction as pure ab initio (biased-free).