Made available in DSpace on 2018-08-02T00:00:57Z (GMT). No. of bitstreams: 1 tese_4714_PPGEE - Dissertação de Mestrado - Clebson Joel Mendes de Oliveira - 2013.pdf: 34789281 bytes, checksum: 8ec4d56937b45f1e5404523103a99f50 (MD5) Previous issue date: 2013-07-15 / Considerando os atuais desafios da robótica que estão relacionados à área da cognição, percebe-se que algumas dessas atividades que são simples para seres humanos ainda não são tarefas triviais para robôs. Logo, ainda há vários problemas não resolvidos de forma robusta, que estão relacionados à falha de robôs quando defrontados com o caos do mundo real, principalmente em ambientes externos dinâmicos, tais como: mapeamento, planejamento de trajetória, localização, navegação e identificação de objetos segundo suas formas e funções. Como muitos desses problemas apresentam chances de serem resolvidos por Visão Computacional, o objetivo deste trabalho foi desenvolver um método de localização visual autônomo online aplicado a ambientes externos dinâmicos, sem considerar informações a priori através da caracterização visual de cenas. Para isso, desenvolveu-se um modelo para caracterização visual de cenas baseado na estimação de Funções Massa de Probabilidade (Probability Mass Functions - PMFs) de características visuais Speeded Up Robust Features (SURF) para os lugares do mapa de um ambiente externo. Utilizando esse modelo para localizar amostras de lugares do mapa, definiu-se um método de localização, que calcula as probabilidades de uma amostra pertencer a lugares candidatos do mapa, e as compara a valores de referência, definidos por curvas Receiver Operating Characteristic (ROC) dos lugares candidatos. Os testes realizados para avaliar o poder de caracterização do modelo desenvolvido, e a qualidade do método de localização proposto utilizaram um mapa visual gerado por um grupo de imagens de caracterização de 28 lugares da Universidade Federal do Espírito Santo (UFES). Já para avaliar a generalização do modelo de caracterização aplicado ao problema de reconhecimento de objetos, foram utilizados grupos de imagens de caracterização de 4 objetos similares. Pelos resultados obtidos, comprova-se que este trabalho alcançou seus objetivos, pois amostras visuais do ambiente externo dinâmico utilizado foram localizadas corretamente, alcançando desempenho global de classificação pelo menos aceitável (> 0, 7) segundo o índice Area Under Curve (AUC). Para o melhor caso do algoritmo foram gastos 3,361 segundos, e também foi possível reconhecer objetos com desempenho global de classificação pelo menos aceitável, gastando 265 milisegundos no melhor caso.

Made available in DSpace on 2014-06-12T17:41:02Z (GMT). No. of bitstreams: 2 arquivo7116_1.pdf: 5607923 bytes, checksum: 7f7c3e789878d66c39e90745a6ae7caa (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / O planejamento da operação do Sistema Interligado Nacional (SIN) sempre utilizou os limites operativos calculados de forma determinística, e a análise de expansão tem sido conduzida considerando o critério determinístico. Todavia, com a crescente complexidade operacional do SIN, aliada às novas necessidades gerenciais envolvendo a busca de maior confiabilidade, constata-se uma tendência de se calcular níveis de risco em diferentes níveis de agregação utilizando técnicas probabilísticas. Atualmente, o Operador Nacional do Sistema Elétrico (ONS) e a Empresa de Pesquisa Energética (EPE) já consideram, na elaboração de seus estudos, análises de natureza probabilística que estimam o nível de risco ao qual o SIN está sujeito. Esta dissertação registra diversos resultados de avaliações dos níveis de risco probabilísticos do sistema elétrico que atende à região Nordeste do Brasil, excetuando-se o Estado do Maranhão. São consideradas diferentes investigações como: geração, transmissão pura e transmissão composta, onde considera-se a combinação de geração e transmissão, através de análises de confiabilidade no cenário de carga pesada, para os anos de 2008, 2009 e 2010. Constatou-se a robustez do parque gerador, que mesmo a análise de enumeração simples apresenta uma representatividade necessária para o espaço probabilístico de estados representado apenas pela transmissão. Foi evidenciada uma substancial melhoria de todos os indicadores de confiabilidade no presente trabalho, caracterizando a melhoria no sistema de transmissão que compõe o Sistema Nordeste, quando observada a evolução temporal deste sistema

Dois modelos principais de planejamento em inteligência artificial são os usados, respectivamente, em planejamento probabilístico (MDPs e suas generalizações) e em planejamento não-determinístico (baseado em model checking). Nessa dissertação será: (1) exibido que planejamento probabilístico e não-determinístico são extremos de um rico contínuo de problemas capaz de lidar simultaneamente com risco e incerteza (Knightiana); (2) obtido um modelo para unificar esses dois tipos de problemas usando MDPs imprecisos; (3) derivado uma versão simplificada do princípio ótimo de Bellman para esse novo modelo; (4) exibido como adaptar e analisar algoritmos do estado-da-arte, como (L)RTDP e LDFS, nesse modelo unificado. Também será discutido exemplos e relações entre modelos já propostos para planejamento sob incerteza e o modelo proposto. / Two noteworthy models of planning in AI are probabilistic planning (based on MDPs and its generalizations) and nondeterministic planning (mainly based on model checking). In this dissertation we: (1) show that probabilistic and nondeterministic planning are extremes of a rich continuum of problems that deal simultaneously with risk and (Knightian) uncertainty; (2) obtain a unifying model for these problems using imprecise MDPs; (3) derive a simplified Bellman\'s principle of optimality for our model; and (4) show how to adapt and analyze state-of-art algorithms such as (L)RTDP and LDFS in this unifying setup. We discuss examples and connections to various proposals for planning under (general) uncertainty.

Dissertação apresentada para obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores, na Faculdade de Engenharia da Universidade do Porto, sob a orientação do Professor Doutor Manuel António Cerqueira da Costa Matos

La presente monografía tiene como objetivo minimizar los costos totales de pedidos, proponer un sistema de inventario que permita saber cuánto y cuando pedir, esto será relevante para la nueva política de inventarios. Para ello se han aplicado modelos de inventarios que se ajuste a las condiciones de la empresa Aspersud, la misma que tiene un departamento de Operaciones y Mantenimiento al cual llamamos también departamento de O y M, que se encarga de conservar los institutos IRU y ILN funcionales y seguros, optimizando la vida útil de cada uno de sus componentes. En la actualidad O y M presenta una nueva política de reducción de costos. Adicionalmente, la presente Monografía tiene la finalidad de demostrar la importancia de que toda organización lucrativa o no, debe aplicar un sistema de inventarios que le permita tener un buen control, y tener la certeza de tomar buenas decisiones. No solo se enuncia el modelo matemático de inventario, además de hacer un análisis de la procedencia de dicha fórmula que permite minimizar mis costos de pedido y saber en qué momento se debe reabastecer.

Dois modelos principais de planejamento em inteligência artificial são os usados, respectivamente, em planejamento probabilístico (MDPs e suas generalizações) e em planejamento não-determinístico (baseado em model checking). Nessa dissertação será: (1) exibido que planejamento probabilístico e não-determinístico são extremos de um rico contínuo de problemas capaz de lidar simultaneamente com risco e incerteza (Knightiana); (2) obtido um modelo para unificar esses dois tipos de problemas usando MDPs imprecisos; (3) derivado uma versão simplificada do princípio ótimo de Bellman para esse novo modelo; (4) exibido como adaptar e analisar algoritmos do estado-da-arte, como (L)RTDP e LDFS, nesse modelo unificado. Também será discutido exemplos e relações entre modelos já propostos para planejamento sob incerteza e o modelo proposto. / Two noteworthy models of planning in AI are probabilistic planning (based on MDPs and its generalizations) and nondeterministic planning (mainly based on model checking). In this dissertation we: (1) show that probabilistic and nondeterministic planning are extremes of a rich continuum of problems that deal simultaneously with risk and (Knightian) uncertainty; (2) obtain a unifying model for these problems using imprecise MDPs; (3) derive a simplified Bellman\'s principle of optimality for our model; and (4) show how to adapt and analyze state-of-art algorithms such as (L)RTDP and LDFS in this unifying setup. We discuss examples and connections to various proposals for planning under (general) uncertainty.

O principal critério de otimização utilizado em Processos de Decisão Markovianos (mdps) é minimizar o custo acumulado esperado. Embora esse critério de otimização seja útil, em algumas aplicações, o custo gerado por algumas execuções pode exceder um limite aceitável. Para lidar com esse problema foram propostos os Processos de Decisão Markovianos Sensíveis ao Risco (rs-mdps) cujo critério de otimização é maximizar a probabilidade do custo acumulado não ser maior que um orçamento limite definido pelo usuário, portanto garantindo que execuções custosas de um mdp ocorram com menos probabilidade. Algoritmos para rs-mdps possuem problemas de escalabilidade quando lidam com intervalos de custo amplos, uma vez que operam no espaço aumentado que enumera todos os possíveis orçamentos restantes. Neste trabalho é proposto um novo problema que é encontrar o orçamento mínimo para o qual a probabilidade de que o custo acumulado não exceda esse orçamento converge para um máximo. Para resolver esse problema são propostas duas abordagens: (i) uma melhoria no algoritmo tvi-dp (uma solução previamente proposta para rsmdps) e (ii) o primeiro algoritmo de programação dinâmica simbólica para rs-mdps que explora as independências condicionais da função de transição no espaço de estados aumentado. Os algoritmos propostos eliminam estados inválidos e adicionam uma nova condição de parada. Resultados empíricos mostram que o algoritmo rs-spudd é capaz de resolver problemas até 103 vezes maior que o algoritmo tvi-dp e é até 26.2 vezes mais rápido que tvi-dp (nas instâncias que o algoritmo tvi-dp conseguiu resolver). De fato, é mostrado que o algoritmo rs-spudd é o único que consegue resolver instâncias grandes dos domínios analisados. Outro grande desafio em rs-mdps é lidar com custos contínuos. Para resolver esse problema são definidos os rs-mdps híbridos que incluem variáveis contínuas e discretas, além do orçamento limite definido pelo usuário. É mostrado que o algoritmo de programação dinâmica simbólica (sdp), existente na literatura, pode ser usado para resolver esse tipo de mdps. Esse algoritmo foi empiricamente testado de duas maneiras diferentes: (i) comparado com os demais algoritmos propostos em um domínio em que todos são capazes de resolver e (ii) testado em um domínio que somente ele é capaz de resolver. Os resultados mostram que o algoritmo sdp para rs-mdp híbridos é capaz de resolver domínios com custos contínuos sem a necessidade de enumeração de estados, porém em troca do aumento do custo computacional. / The main optimization criterion used in Markovian Decision Processes (mdps) is to minimize the expected cumulative cost. Although this optimization criterion is useful, in some applications the cost generated by some executions may exceed an acceptable threshold. In order to deal with this problem, the Risk-Sensitive Markov Decision Processes (rs-mdps) were proposed whose optimization criterion is to maximize the probability of the cumulative cost not to be greater than an user-defined budget, thus guaranteeing that costly executions of an mdp occur with least probability. Algorithms for rs-mdps face scalability issues when handling large cost intervals, since they operate in an augmented state space which enumerates the possible remaining budgets. In this work, we propose a new challenging problem of finding the minimum budget for which the probability that the cumulative cost does not exceed this budget converges to a maximum. To solve this problem, we propose: (i) an improved version of tvi-dp (a previous solution for rs-mdps) and (ii) the first symbolic dynamic programming algorithm for rs-mdps that explores conditional independence of the transition function in the augmented state space. The proposed algorithms prune invalid states and perform early termination. Empirical results show that rs-spudd is able to solve problems up to 103 times larger than tvi-dp and is up to 26.2 times faster than tvi-dp (in the instances tvi-dp was able to solve). In fact, we show that rs-spudd is the only one that can solve large instances of the analyzed domains. Another challenging problem for rs-mdps is handle continous costs. To solve this problem, we define Hybrid rs-mdps which include continous and discrete variables, and the user-defined budget. In this work, we show that Symbolic Dynamic Programming (sdp) algorithm can be used to solve this kind of mdps. We empirically evaluated the sdp algorithm: (i) in a domain that can be solved with the previously proposed algorithms and (ii) in a domain that only sdp can solve. Results shown that sdp algorithm for Hybrid rs-mdps is capable of solving domains with continous costs, but with a higher computational cost.

O presente trabalho é um esforço de apresentar, organizado em forma de survey, um conjunto de resultados que ilustram a aplicação de um certo método probabilístico. Embora não apresentemos resultados novos na área, acreditamos que a apresentação sistemática destes resultados pode servir para a compreensão de uma ferramenta útil para quem usa dos métodos probabilísticos na sua pesquisa em combinatória. Os resultados de que falaremos tem aparecido na última década na literatura especializada e foram usados na investigação de problemas que resitiram a outras aproximações mais clássicas. Em vez de teorizar sobre o método a apresentar, nós adotaremos a estratégia de apresentar três problemas, usando-os como exemplos práticos da aplicação do método em questão. Surpeendentemente, apesar da dificuldade que apresentaram para ser resolvidos, estes problemas compartilham a caraterística de poder ser formulados muito intuitivamente, como veremos no Capítulo 1. Devemos advertir que embora os problemas que conduzem nossa exposição pertençam a áreas tão diferentes quanto teoria de números, geometria e combinatória, nosso intuito é fazer énfase no que de comum tem as suas soluções e não das posteriores implicações que estes problemas tenham nas suas respectivas áreas. Ocasionalmente comentaremos sim, outras possíveis aplicações das ferramentas usadas para solucionar estes problemas de motivação. Os problemas de que trataremos tem-se caracterizado por aguardar várias décadas em espera de solução: O primeiro, da teoria de números, surgiu na pesquisa de séries de Fourier que Sidon realizava a princípios de século e foi proposto por ele a Erdös em 1932. Embora tenham havido, desde 1950, diversos avanços na pesquisa deste problema, o resultado de que falaremos data de 1981. Já o segundo problema, da geometria, é uma conjectura formulada em 1951 por Heilbronn e refutada finalmente em 1982. O último problema, de combinatória, é uma conjectura de Erdös e Hanani de 1963, que foi tratada em diversos casos particulares até ser finalmente resolvida em toda sua generalidade em 1985. / The following work is an effort to present, in survey form, a collection of results that illustrate the application of a certain probabilistic method in combinatorics. We do not present new results in the area; however, we do believe that the systematic presentation of these results can help those who use probabilistic methods comprenhend this useful technique. The results we refer to have appeared over the last decade in the research literature and were used in the investigation of problems which have resisted other, more classical, approaches. Instead of theorizing about the method, we adopted the strategy of presenting three problems, using them as practical examples of the application of the method in question. Surpisingly, despite the difficulty of solutions to these problems, they share the characteristic of being able to be formulated very intuitively, as we will see in Chapter One. We should warn the reader that despite the fact that the problems which drive our discussion belong to such different fields as number theory, geometry and combinatorics, our goal is to place emphasis on what their solutions have in common and not on the subsequent implications that these problems have in their respective fields. Occasionally, we will comment on other potential applications of the tools utilized to solve these problems. The problems which we are discussing can be characterized by the decades-long wait for their solution: the first, from number theory, arose from the research in Fourier series conducted by Sidon at the beginning of the century and was proposed by him to Erdös in 1932. Since 1950, there have been diverse advances in the understanding of this problem, but the result we talk of comes from 1981. The second problem, from geometry, is a conjecture formulated in 1951 by Heilbronn and finally refuted in 1982. The last problem, from combinatorics, is a conjecture formulated by Erdös and Hanani in 1963 that was treated in several particular cases but was only solved in its entirety in 1985.

O presente trabalho é um esforço de apresentar, organizado em forma de survey, um conjunto de resultados que ilustram a aplicação de um certo método probabilístico. Embora não apresentemos resultados novos na área, acreditamos que a apresentação sistemática destes resultados pode servir para a compreensão de uma ferramenta útil para quem usa dos métodos probabilísticos na sua pesquisa em combinatória. Os resultados de que falaremos tem aparecido na última década na literatura especializada e foram usados na investigação de problemas que resitiram a outras aproximações mais clássicas. Em vez de teorizar sobre o método a apresentar, nós adotaremos a estratégia de apresentar três problemas, usando-os como exemplos práticos da aplicação do método em questão. Surpeendentemente, apesar da dificuldade que apresentaram para ser resolvidos, estes problemas compartilham a caraterística de poder ser formulados muito intuitivamente, como veremos no Capítulo 1. Devemos advertir que embora os problemas que conduzem nossa exposição pertençam a áreas tão diferentes quanto teoria de números, geometria e combinatória, nosso intuito é fazer énfase no que de comum tem as suas soluções e não das posteriores implicações que estes problemas tenham nas suas respectivas áreas. Ocasionalmente comentaremos sim, outras possíveis aplicações das ferramentas usadas para solucionar estes problemas de motivação. Os problemas de que trataremos tem-se caracterizado por aguardar várias décadas em espera de solução: O primeiro, da teoria de números, surgiu na pesquisa de séries de Fourier que Sidon realizava a princípios de século e foi proposto por ele a Erdös em 1932. Embora tenham havido, desde 1950, diversos avanços na pesquisa deste problema, o resultado de que falaremos data de 1981. Já o segundo problema, da geometria, é uma conjectura formulada em 1951 por Heilbronn e refutada finalmente em 1982. O último problema, de combinatória, é uma conjectura de Erdös e Hanani de 1963, que foi tratada em diversos casos particulares até ser finalmente resolvida em toda sua generalidade em 1985. / The following work is an effort to present, in survey form, a collection of results that illustrate the application of a certain probabilistic method in combinatorics. We do not present new results in the area; however, we do believe that the systematic presentation of these results can help those who use probabilistic methods comprenhend this useful technique. The results we refer to have appeared over the last decade in the research literature and were used in the investigation of problems which have resisted other, more classical, approaches. Instead of theorizing about the method, we adopted the strategy of presenting three problems, using them as practical examples of the application of the method in question. Surpisingly, despite the difficulty of solutions to these problems, they share the characteristic of being able to be formulated very intuitively, as we will see in Chapter One. We should warn the reader that despite the fact that the problems which drive our discussion belong to such different fields as number theory, geometry and combinatorics, our goal is to place emphasis on what their solutions have in common and not on the subsequent implications that these problems have in their respective fields. Occasionally, we will comment on other potential applications of the tools utilized to solve these problems. The problems which we are discussing can be characterized by the decades-long wait for their solution: the first, from number theory, arose from the research in Fourier series conducted by Sidon at the beginning of the century and was proposed by him to Erdös in 1932. Since 1950, there have been diverse advances in the understanding of this problem, but the result we talk of comes from 1981. The second problem, from geometry, is a conjecture formulated in 1951 by Heilbronn and finally refuted in 1982. The last problem, from combinatorics, is a conjecture formulated by Erdös and Hanani in 1963 that was treated in several particular cases but was only solved in its entirety in 1985.

In terms of standard probabilistic reasoning, in order to perform inference from a knowledge base, it is normally necessary to guarantee the consistency of such base. When we come across an inconsistent set of probabilistic assessments, it interests us to know where the inconsistency is, how severe it is, and how to correct it. Inconsistency measures have recently been put forward as a tool to address these issues in the Artificial Intelligence community. This work investigates the problem of measuring inconsistency in probabilistic knowledge bases. Basic rationality postulates have driven the formulation of inconsistency measures within classical propositional logic. In the probabilistic case, the quantitative character of probabilities yielded an extra desirable property: that inconsistency measures should be continuous. To attend this requirement, inconsistency in probabilistic knowledge bases have been measured via distance minimisation. In this thesis, we prove that the continuity postulate is incompatible with basic desirable properties inherited from classical logic. Since minimal inconsistent sets are the basis for some desiderata, we look for more suitable ways of localising the inconsistency in probabilistic logic, while we analyse the underlying consolidation processes. The AGM theory of belief revision is extended to encompass consolidation via probabilities adjustment. The new forms of characterising the inconsistency we propose are employed to weaken some postulates, restoring the compatibility of the whole set of desirable properties. Investigations in Bayesian statistics and formal epistemology have been interested in measuring an agent\'s degree of incoherence. In these fields, probabilities are usually construed as an agent\'s degrees of belief, determining her gambling behaviour. Incoherent agents hold inconsistent degrees of beliefs, which expose them to disadvantageous bet transactions - also known as Dutch books. Statisticians and philosophers suggest measuring an agent\'s incoherence through the guaranteed loss she is vulnerable to. We prove that these incoherence measures via Dutch book are equivalent to inconsistency measures via distance minimisation from the AI community. / Em termos de raciocínio probabilístico clássico, para se realizar inferências de uma base de conhecimento, normalmente é necessário garantir a consistência de tal base. Quando nos deparamos com um conjunto de probabilidades que são inconsistentes entre si, interessa-nos saber onde está a inconsistência, quão grave esta é, e como corrigi-la. Medidas de inconsistência têm sido recentemente propostas como uma ferramenta para endereçar essas questões na comunidade de Inteligência Artificial. Este trabalho investiga o problema da medição de inconsistência em bases de conhecimento probabilístico. Postulados básicos de racionalidade têm guiado a formulação de medidas de inconsistência na lógica clássica proposicional. No caso probabilístico, o carácter quantitativo da probabilidade levou a uma propriedade desejável adicional: medidas de inconsistência devem ser contínuas. Para atender a essa exigência, a inconsistência em bases de conhecimento probabilístico tem sido medida através da minimização de distâncias. Nesta tese, demonstramos que o postulado da continuidade é incompatível com propriedades desejáveis herdadas da lógica clássica. Como algumas dessas propriedades são baseadas em conjuntos inconsistentes minimais, nós procuramos por maneiras mais adequadas de localizar a inconsistência em lógica probabilística, analisando os processos de consolidação subjacentes. A teoria AGM de revisão de crenças é estendida para englobar a consolidação pelo ajuste de probabilidades. As novas formas de caracterizar a inconsistência que propomos são empregadas para enfraquecer alguns postulados, restaurando a compatibilidade de todo o conjunto de propriedades desejáveis. Investigações em estatística Bayesiana e em epistemologia formal têm se interessado pela medição do grau de incoerência de um agente. Nesses campos, probabilidades são geralmente interpretadas como graus de crença de um agente, determinando seu comportamento em apostas. Agentes incoerentes possuem graus de crença inconsistentes, que o expõem a transações de apostas desvantajosas - conhecidas como Dutch books. Estatísticos e filósofos sugerem medir a incoerência de um agente através do prejuízo garantido a qual ele está vulnerável. Nós provamos que estas medidas de incoerência via Dutch books são equivalentes a medidas de inconsistência via minimização de distâncias da comunidade de IA.