Formal methods for control synthesis in partially observed environments : application to autonomous robotic manipulation

Modern robots are increasingly expected to function in uncertain and dynamically challenging environments, often in proximity with humans. In addition, wide scale adoption of robots requires on-the-fly adaptability of software for diverse application. These requirements strongly suggest the need to adopt formal representations of high level goals and safety specifications, especially as temporal logic formulas. This approach allows for the use of formal verification techniques for controller synthesis that can give guarantees for safety and performance. Robots operating in unstructured environments also face limited sensing capability. Correctly inferring a robot's progress toward high level goal can be challenging.

This thesis develops new algorithms for synthesizing discrete controllers in partially known environments under specifications represented as linear temporal logic (LTL) formulas. It is inspired by recent developments in finite abstraction techniques for hybrid systems and motion planning problems. The robot and its environment is assumed to have a finite abstraction as a Partially Observable Markov Decision Process (POMDP), which is a powerful model class capable of representing a wide variety of problems. However, synthesizing controllers that satisfy LTL goals over POMDPs is a challenging problem which has received only limited attention.

This thesis proposes tractable, approximate algorithms for the control synthesis problem using Finite State Controllers (FSCs). The use of FSCs to control finite POMDPs allows for the closed system to be analyzed as finite global Markov chain. The thesis explicitly shows how transient and steady state behavior of the global Markov chains can be related to two different criteria with respect to satisfaction of LTL formulas. First, the maximization of the probability of LTL satisfaction is related to an optimization problem over a parametrization of the FSC. Analytic computation of gradients are derived which allows the use of first order optimization techniques.

The second criterion encourages rapid and frequent visits to a restricted set of states over infinite executions. It is formulated as a constrained optimization problem with a discounted long term reward objective by the novel utilization of a fundamental equation for Markov chains - the Poisson equation. A new constrained policy iteration technique is proposed to solve the resulting dynamic program, which also provides a way to escape local maxima.

The algorithms proposed in the thesis are applied to the task planning and execution challenges faced during the DARPA Autonomous Robotic Manipulation - Software challenge.

Convex Relaxation for Low-Dimensional Representation: Phase Transitions and Limitations

There is a growing interest in taking advantage of possible patterns and structures in data so as to extract the desired information and overcome the curse of dimensionality. In a wide range of applications, including computer vision, machine learning, medical imaging, and social networks, the signal that gives rise to the observations can be modeled to be approximately sparse and exploiting this fact can be very beneficial. This has led to an immense interest in the problem of efficiently reconstructing a sparse signal from limited linear observations. More recently, low-rank approximation techniques have become prominent tools to approach problems arising in machine learning, system identification and quantum tomography.

In sparse and low-rank estimation problems, the challenge is the inherent intractability of the objective function, and one needs efficient methods to capture the low-dimensionality of these models. Convex optimization is often a promising tool to attack such problems. An intractable problem with a combinatorial objective can often be "relaxed" to obtain a tractable but almost as powerful convex optimization problem. This dissertation studies convex optimization techniques that can take advantage of low-dimensional representations of the underlying high-dimensional data. We provide provable guarantees that ensure that the proposed algorithms will succeed under reasonable conditions, and answer questions of the following flavor:

More specifically, i) Focusing on linear inverse problems, we generalize the classical error bounds known for the least-squares technique to the lasso formulation, which incorporates the signal model. ii) We show that intuitive convex approaches do not perform as well as expected when it comes to signals that have multiple low-dimensional structures simultaneously. iii) Finally, we propose convex relaxations for the graph clustering problem and give sharp performance guarantees for a family of graphs arising from the so-called stochastic block model. We pay particular attention to the following aspects. For i) and ii), we aim to provide a general geometric framework, in which the results on sparse and low-rank estimation can be obtained as special cases. For i) and iii), we investigate the precise performance characterization, which yields the right constants in our bounds and the true dependence between the problem parameters.

Identificação de danos estruturais utilizando técnicas de otimização.

Sistemas estruturais em suas variadas aplicações incluindo-se veículos espaciais, automóveis e estruturas de engenharia civil tais como prédios, pontes e plataformas off-shore, acumulam dano durante suas vidas úteis. Em muitas situações, tal dano pode não ser visualmente observado. Do ponto de vista da segurança e da performance da estrutura, é desejável monitorar esta possível ocorrência, localizá-la e quantificá-la. Métodos de identificação de sistemas, que em geral, são classificados numa categoria de Técnicas de Avaliação Não-Destrutivas, podem ser utilizados para esta finalidade. Usando dados experimentais tais como frequências naturais, modos de vibração e deslocamentos estáticos, e um modelo analítico estrutural, parâmetros da estrutura podem ser identificados. As propriedades estruturais do modelo analítico são modificadas de modo a minimizar a diferença entre os dados obtidos por aquele modelo e a resposta medida. Isto pode ser definido como um problema inverso onde os parâmetros da estrutura são identificados. O problema inverso, descrito acima, foi resolvido usando métodos globais de otimização devido à provável presença de inúmeros mínimos locais e a não convexidade do espaço de projeto. Neste trabalho o método da Evolução Diferencial (Differential Evolution, DE) foi utilizado como ferramenta principal de otimização. Trata-se de uma meta-heurística inspirada numa população de soluções sucessivamente atualizada por operações aritméticas como mutações, recombinações e critérios de seleção dos melhores indivíduos até que um critério de convergência seja alcançado. O método da Evolução Diferencial foi desenvolvido como uma heurística para minimizar funções não diferenciáveis e foi aplicado a estruturas planas de treliças com diferentes níveis de danos.

Desenvolvimento de técnicas de otimização da programação das limpezas de redes de trocadores de calor

Trocadores de calor são equipamentos muito utilizados na indústria de processos com o objetivo de modificar a temperatura e/ou o estado físico de correntes materiais. Uma rede de trocadores de calor pode ser definida como um grupo de trocadores de calor interligados, a fim de reduzir as necessidades de energia de um sistema. No entanto, durante a operação de uma rede, a eficiência térmica dos trocadores de calor diminui devido à deposição. Esse efeito promove o aumento dos custos de combustível e das emissões de carbono. Uma alternativa para mitigar este problema baseia-se no estabelecimento de uma programação das limpezas dos trocadores de calor durante a operação de rede. Este tipo de abordagem ocasiona uma situação na qual ocorre um conflito de escolha: a limpeza de um trocador de calor pode recuperar a sua eficiência térmica, mas implica custos adicionais, tais como, mão-de-obra, produtos químicos, etc. Além disso, durante a limpeza, o trocador de calor tem de ser contornado por uma corrente de by-pass, o que aumenta temporariamente o consumo de energia. Neste contexto, o presente trabalho tem como objetivo explorar diferentes técnicas de otimização envolvendo métodos estocásticos e heurísticos. Com este objetivo foi desenvolvido um conjunto de códigos computacionais integrados que envolvem a simulação pseudo-estacionária do comportamento da rede relacionado com incrustações e a otimização da programação das limpezas deste tipo de sistema. A solução do problema indica os períodos de tempo para a limpeza de cada trocador de calor. Na abordagem estocástica empregada, os parâmetros do algoritmo genético, como probabilidade de crossover e probabilidade de mutação, foram calibrados para o presente problema. A abordagem heurística desenvolvida se deu através da sequência do conjunto de movimentos zero, um e dois. De forma alternativa, desenvolveu-se a metodologia heurística recursiva na qual os conjuntos de movimentos um e dois foram empregados recursivamente. Também foi desenvolvida a abordagem híbrida que consistiu em diferentes combinações da metodologia estocástica e heurística. A análise comparativa entre as metodologias empregadas teve como objetivo avaliar a abordagem mais adequada para o presente problema da programação das limpezas em termos de função objetivo e esforço computacional. O desempenho da abordagem proposta foi explorado através de uma série de exemplos, incluindo uma refinaria real brasileira. Os resultados foram promissores, indicando que as técnicas de otimização analisadas neste trabalho podem ser abordagens interessantes para operações que envolvam redes de trocadores de calor. Dentre as abordagens de otimização analisadas, a metodologia heurística desenvolvida no presente trabalho apresentou os melhores resultados se mostrando competitiva frente às abordagens comparadas da literatura

Previsão do comportamento hidráulico de um rio com base na estimativa de coeficientes que controlam seu escoamento. Estudo de caso: Rio Bengalas, Nova Friburgo-RJ

Nesta tese é realizada a modelagem do comportamento hidráulico dos principais rios que compõem a bacia hidrográfica do Rio Bengalas, localizada no município de Nova Friburgo-RJ, a qual abrange a área mais urbanizada da referida cidade. Para a realização das simulações foi utilizado o Sistema de Modelagem de Águas MOHID, ferramenta MOHID Land. Já para a calibração do modelo foram adotados alguns métodos de otimização, mais precisamente, os algoritmos de Luus- Jaakola (LJ) e Colisão de Partículas (PCA), acoplados ao referido sistema, com o intuito de determinar os principais parâmetros necessários à modelagem de corpos hídricos, bem como suas bacias hidrográficas. Foram utilizados dados topográficos do IBGE disponibilizados pela prefeitura após a elaboração do Plano de Águas Pluviais da região de interesse. Com o modelo devidamente calibrado por meio de dados experimentais, foi realizada a validação do mesmo através da simulação de inundações nesta região. Apesar de técnicas de otimização acopladas à plataforma MOHID terem sido utilizadas pela primeira vez em um rio de montanha, os resultados apresentaram-se importantes e qualitativamente satisfatórios do ponto de vista de auxílio à tomada de decisões, tendo como base a prevenção de danos causados pelas elevações da lâmina dágua que ocorrem frequentemente em Nova Friburgo, como por exemplo, a recente tragédia de janeiro de 2011 ocorrida na Região Serrana do Estado do Rio de Janeiro.

Aplicação de Inteligência Computacional para a Solução de Problemas Inversos de Transferência Radiativa em Meios Participantes Unidimensionais

Esta pesquisa consiste na solução do problema inverso de transferência radiativa para um meio participante (emissor, absorvedor e/ou espalhador) homogêneo unidimensional em uma camada, usando-se a combinação de rede neural artificial (RNA) com técnicas de otimização. A saída da RNA, devidamente treinada, apresenta os valores das propriedades radiativas [ω, τ0, ρ1 e ρ2] que são otimizadas através das seguintes técnicas: Particle Collision Algorithm (PCA), Algoritmos Genéticos (AG), Greedy Randomized Adaptive Search Procedure (GRASP) e Busca Tabu (BT). Os dados usados no treinamento da RNA são sintéticos, gerados através do problema direto sem a introdução de ruído. Os resultados obtidos unicamente pela RNA, apresentam um erro médio percentual menor que 1,64%, seria satisfatório, todavia para o tratamento usando-se as quatro técnicas de otimização citadas anteriormente, os resultados tornaram-se ainda melhores com erros percentuais menores que 0,04%, especialmente quando a otimização é feita por AG.

Estudo do comportamento e otimização do projeto estrutural de edifícios de concreto armado.

Com base no crescimento exponencial das populações urbanas, a demanda por espaço para habitação tem crescido vertiginosamente. Para atender a estas necessidades, edificações cada vez mais altas e mais esbeltas são projetadas e vãos cada vez maiores são utilizados. Novos materiais são criados e aprimorados para que seja extraído o máximo de desempenho com o menor custo. Deste modo, esta dissertação tem como objetivo o estudo do comportamento e otimização do projeto estrutural de edifícios. Para tal, considera-se ao longo do estudo o projeto de uma edificação de concreto armado com 47 metros de altura e 15 pavimentos, submetida às ações das cargas usuais de projeto atuantes sobre edifícios residenciais, além das cargas de vento. No que tange ao desenvolvimento do modelo computacional são empregadas técnicas usuais de discretização, via método dos elementos finitos, por meio do programa ANSYS. Inicialmente, a resposta estática e dinâmica do modelo estrutural é obtida e comparada com base nos valores limites propostos por normas de projeto. A partir de análises qualitativas e quantitativas desenvolvidas sobre a resposta estrutural do modelo em estudo são utilizadas técnicas de otimização com o objetivo de modificar e aprimorar o desempenho estrutural do edifício analisado.

Aplicação de técnicas de otimização no gerenciamento da deposição em redes de trocadores de calor

Deposição é um fenômeno indesejável que ocorre na superfície dos trocadores de calor ao longo de sua operação, ocasionando redução na efetividade térmica e aumento da resistência ao escoamento nestes equipamentos. Estes efeitos trazem grandes consequências econômicas e ambientais, devido ao aumento dos custos operacionais (energia adicional é requerida), aumento dos custos de projeto (demanda por equipamentos de maior área de troca térmica), limitações hidráulicas (que pode levar a uma diminuição da carga processada) e aumento das emissões (aumento da queima de combustíveis fósseis para suprir a energia adicional requerida). Neste contexto, o presente trabalho tem por objetivo fornecer ferramentas computacionais robustas que apliquem técnicas de otimização para o gerenciamento da deposição em redes de trocadores de calor, visando minimizar os seus efeitos negativos. Estas ferramentas foram desenvolvidas utilizando programação matemática no ambiente computacional GAMS, e três abordagens distintas para a resolução do problema da deposição foram pesquisadas. Uma delas consiste na identificação do conjunto ótimo de trocadores de calor a serem limpos durante uma parada para manutenção da planta, visando restaurar a carga térmica nesses equipamentos através da remoção dos depósitos existentes. Já as duas outras abordagens consistem em otimizar a distribuição das vazões das correntes ao longo de ramais paralelos, uma de forma estacionária e a outra de forma dinâmica, visando maximizar a recuperação de energia ao longo da rede. O desempenho destas três abordagens é ilustrado através de um conjunto de exemplos de redes de trocadores de calor, onde os ganhos reais obtidos com estas ferramentas de otimização desenvolvidas são demonstrados

Muitiobjective pressurized water reactor reload core design by nondominated genetic algorithm search

The design of pressurized water reactor reload cores is not only a formidable optimization problem but also, in many instances, a multiobjective problem. A genetic algorithm (GA) designed to perform true multiobjective optimization on such problems is described. Genetic algorithms simulate natural evolution. They differ from most optimization techniques by searching from one group of solutions to another, rather than from one solution to another. New solutions are generated by breeding from existing solutions. By selecting better (in a multiobjective sense) solutions as parents more often, the population can be evolved to reveal the trade-off surface between the competing objectives. An example illustrating the effectiveness of this novel method is presented and analyzed. It is found that in solving a reload design problem the algorithm evaluates a similar number of loading patterns to other state-of-the-art methods, but in the process reveals much more information about the nature of the problem being solved. The actual computational cost incurred depends: on the core simulator used; the GA itself is code independent.

Natural actor and belief critic: Reinforcement algorithm for learning parameters of dialogue systems modelled as POMDPs

This article presents a novel algorithm for learning parameters in statistical dialogue systems which are modeled as Partially Observable Markov Decision Processes (POMDPs). The three main components of a POMDP dialogue manager are a dialogue model representing dialogue state information; a policy that selects the system's responses based on the inferred state; and a reward function that specifies the desired behavior of the system. Ideally both the model parameters and the policy would be designed to maximize the cumulative reward. However, while there are many techniques available for learning the optimal policy, no good ways of learning the optimal model parameters that scale to real-world dialogue systems have been found yet. The presented algorithm, called the Natural Actor and Belief Critic (NABC), is a policy gradient method that offers a solution to this problem. Based on observed rewards, the algorithm estimates the natural gradient of the expected cumulative reward. The resulting gradient is then used to adapt both the prior distribution of the dialogue model parameters and the policy parameters. In addition, the article presents a variant of the NABC algorithm, called the Natural Belief Critic (NBC), which assumes that the policy is fixed and only the model parameters need to be estimated. The algorithms are evaluated on a spoken dialogue system in the tourist information domain. The experiments show that model parameters estimated to maximize the expected cumulative reward result in significantly improved performance compared to the baseline hand-crafted model parameters. The algorithms are also compared to optimization techniques using plain gradients and state-of-the-art random search algorithms. In all cases, the algorithms based on the natural gradient work significantly better. © 2011 ACM.

Partially Observable Markov Decision Processes with continuous observations for dialogue management

This work shows how a dialogue model can be represented as a Partially Observable Markov Decision Process (POMDP) with observations composed of a discrete and continuous component. The continuous component enables the model to directly incorporate a confidence score for automated planning. Using a testbed simulated dialogue management problem, we show how recent optimization techniques are able to find a policy for this continuous POMDP which outperforms a traditional MDP approach. Further, we present a method for automatically improving handcrafted dialogue managers by incorporating POMDP belief state monitoring, including confidence score information. Experiments on the testbed system show significant improvements for several example handcrafted dialogue managers across a range of operating conditions.

非结构化P2P系统Overlay优化技术综述

非结构化P2P Overlay网络的结构松散,网络中资源的分布没有明确的限制,这使得非结构化P2P Overlay网络中的资源搜索在很大程度上依赖于通信开销巨大的泛洪法,因而非结构化P2P系统在伸缩性,可用性等方面,存在明显的不足.非结构化P2P Overlay网络的上述特点决定了非结构化P2P Overlay优化技术的重要性.本文分四大类别,对非结构化P2P Overlay优化技术进行了介绍,分析比较了各类方法的优劣以及它们的适用场合,并在此基础上对未来工作进行了展望.

地震波阻抗反演的迭代正则化算法

Post-stack seismic impedance inversion is the key technology of reservoir prediction and identification. Geophysicists have done a lot of research for the problem, but the developed methods still cannot satisfy practical requirements completely. The results of different inversion methods are different and the results of one method used by different people are different too. The reasons are due to the quality of seismic data, inaccurate wavelet extraction, errors between normal incidence assumption and real situation, and so on. In addition, there are two main influence factors: one is the band-limited property of seismic data; the other is the ill-posed property of impedance inversion. Thus far, the most effective way to solve the band-limited problem is the constrained inversion. And the most effective way to solve ill-posed problems is the regularization method assisted with proper optimization techniques. This thesis systematically introduces the iterative regularization methods and numerical optimization methods for impedance inversion. A regularized restarted conjugate gradient method for solving ill-posed problems in impedance inversion is proposed. Theoretic simulations are made and field data applications are performed. It reveals that the proposed algorithm possesses the superiority to conventional conjugate gradient method. Finally, non-smooth optimization is proposed as the further research direction in seismic impedance inversion according to practical situation.

RABBIT: A Compiler for SCHEME

We have developed a compiler for the lexically-scoped dialect of LISP known as SCHEME. The compiler knows relatively little about specific data manipulation primitives such as arithmetic operators, but concentrates on general issues of environment and control. Rather than having specialized knowledge about a large variety of control and environment constructs, the compiler handles only a small basis set which reflects the semantics of lambda-calculus. All of the traditional imperative constructs, such as sequencing, assignment, looping, GOTO, as well as many standard LISP constructs such as AND, OR, and COND, are expressed in macros in terms of the applicative basis set. A small number of optimization techniques, coupled with the treatment of function calls as GOTO statements, serve to produce code as good as that produced by more traditional compilers. The macro approach enables speedy implementation of new constructs as desired without sacrificing efficiency in the generated code. A fair amount of analysis is devoted to determining whether environments may be stack-allocated or must be heap-allocated. Heap-allocated environments are necessary in general because SCHEME (unlike Algol 60 and Algol 68, for example) allows procedures with free lexically scoped variables to be returned as the values of other procedures; the Algol stack-allocation environment strategy does not suffice. The methods used here indicate that a heap-allocating generalization of the "display" technique leads to an efficient implementation of such "upward funargs". Moreover, compile-time optimization and analysis can eliminate many "funargs" entirely, and so far fewer environment structures need be allocated at run time than might be expected. A subset of SCHEME (rather than triples, for example) serves as the representation intermediate between the optimized SCHEME code and the final output code; code is expressed in this subset in the so-called continuation-passing style. As a subset of SCHEME, it enjoys the same theoretical properties; one could even apply the same optimizer used on the input code to the intermediate code. However, the subset is so chosen that all temporary quantities are made manifest as variables, and no control stack is needed to evaluate it. As a result, this apparently applicative representation admits an imperative interpretation which permits easy transcription to final imperative machine code. These qualities suggest that an applicative language like SCHEME is a better candidate for an UNCOL than the more imperative candidates proposed to date.

Multilevel mesh partitioning for optimizing domain shape

Multilevel algorithms are a successful class of optimization techniques that address the mesh partitioning problem for mapping meshes onto parallel computers. They usually combine a graph contraction algorithm together with a local optimization method that refines the partition at each graph level. To date, these algorithms have been used almost exclusively to minimize the cut-edge weight in the graph with the aim of minimizing the parallel communication overhead. However, it has been shown that for certain classes of problems, the convergence of the underlying solution algorithm is strongly influenced by the shape or aspect ratio of the subdomains. Therefore, in this paper, the authors modify the multilevel algorithms to optimize a cost function based on the aspect ratio. Several variants of the algorithms are tested and shown to provide excellent results.