Incremental Control Synthesis for Robotics in the Presence of Temporal Logic Specifications

This thesis presents methods for incrementally constructing controllers in the presence of uncertainty and nonlinear dynamics. The basic setting is motion planning subject to temporal logic specifications. Broadly, two categories of problems are treated. The first is reactive formal synthesis when so-called discrete abstractions are available. The fragment of linear-time temporal logic (LTL) known as GR(1) is used to express assumptions about an adversarial environment and requirements of the controller. Two problems of changes to a specification are posed that concern the two major aspects of GR(1): safety and liveness. Algorithms providing incremental updates to strategies are presented as solutions. In support of these, an annotation of strategies is developed that facilitates repeated modifications. A variety of properties are proven about it, including necessity of existence and sufficiency for a strategy to be winning. The second category of problems considered is non-reactive (open-loop) synthesis in the absence of a discrete abstraction. Instead, the presented stochastic optimization methods directly construct a control input sequence that achieves low cost and satisfies a LTL formula. Several relaxations are considered as heuristics to address the rarity of sampling trajectories that satisfy an LTL formula and demonstrated to improve convergence rates for Dubins car and single-integrators subject to a recurrence task.

Problemas inversos aplicados à identificação de parâmetros hidrodinâmicos de um modelo do estuário do rio Macaé

Esta tese tem por objetivo propor uma estratégia de obtenção automática de parâmetros hidrodinâmicos e de transporte através da solução de problemas inversos. A obtenção dos parâmetros de um modelo físico representa um dos principais problemas em sua calibração, e isso se deve em grande parte à dificuldade na medição em campo desses parâmetros. Em particular na modelagem de rios e estuários, a altura da rugosidade e o coeficiente de difusão turbulenta representam dois dos parâmetros com maior dificuldade de medição. Nesta tese é apresentada uma técnica automatizada de estimação desses parâmetros através deum problema inverso aplicado a um modelo do estuário do rio Macaé, localizado no norte do Rio de Janeiro. Para este estudo foi utilizada a plataforma MOHID, desenvolvida na Universidade Técnica de Lisboa, e que tem tido ampla aplicação na simulação de corpos hídricos. Foi realizada uma análise de sensibilidade das respostas do modelo com relação aos parâmetros de interesse. Verificou-se que a salinidade é uma variável sensível a ambos parâmetros. O problema inverso foi então resolvido utilizando vários métodos de otimização através do acoplamento da plataforma MOHID a códigos de otimização implementados em Fortran. O acoplamento foi realizado de forma a não alterar o código fonte do MOHID, possibilitando a utilização da ferramenta computacional aqui desenvolvida em qualquer versão dessa plataforma, bem como a sua alteração para o uso com outros simuladores. Os testes realizados confirmam a eficiência da técnica e apontam as melhores abordagens para uma rápida e precisa estimação dos parâmetros.

Problemas direto e inverso de processos de separação em leito móvel simulado mediante mecanismos cinéticos de adsorção

Diversas aplicações industriais relevantes envolvem os processos de adsorção, citando como exemplos a purificação de produtos, separação de substâncias, controle de poluição e umidade entre outros. O interesse crescente pelos processos de purificação de biomoléculas deve-se principalmente ao desenvolvimento da biotecnologia e à demanda das indústrias farmacêutica e química por produtos com alto grau de pureza. O leito móvel simulado (LMS) é um processo cromatográfico contínuo que tem sido aplicado para simular o movimento do leito de adsorvente, de forma contracorrente ao movimento do líquido, através da troca periódica das posições das correntes de entrada e saída, sendo operado de forma contínua, sem prejuízo da pureza das correntes de saída. Esta consiste no extrato, rico no componente mais fortemente adsorvido, e no rafinado, rico no componente mais fracamente adsorvido, sendo o processo particularmente adequado a separações binárias. O objetivo desta tese é estudar e avaliar diferentes abordagens utilizando métodos estocásticos de otimização para o problema inverso dos fenômenos envolvidos no processo de separação em LMS. Foram utilizados modelos discretos com diferentes abordagens de transferência de massa, com a vantagem da utilização de um grande número de pratos teóricos em uma coluna de comprimento moderado, neste processo a separação cresce à medida que os solutos fluem através do leito, isto é, ao maior número de vezes que as moléculas interagem entre a fase móvel e a fase estacionária alcançando assim o equilíbrio. A modelagem e a simulação verificadas nestas abordagens permitiram a avaliação e a identificação das principais características de uma unidade de separação do LMS. A aplicação em estudo refere-se à simulação de processos de separação do Baclofen e da Cetamina. Estes compostos foram escolhidos por estarem bem caracterizados na literatura, estando disponíveis em estudos de cinética e de equilíbrio de adsorção nos resultados experimentais. De posse de resultados experimentais avaliou-se o comportamento do problema direto e inverso de uma unidade de separação LMS visando comparar os resultados obtidos com os experimentais, sempre se baseando em critérios de eficiência de separação entre as fases móvel e estacionária. Os métodos estudados foram o GA (Genetic Algorithm) e o PCA (Particle Collision Algorithm) e também foi feita uma hibridização entre o GA e o PCA. Como resultado desta tese analisouse e comparou-se os métodos de otimização em diferentes aspectos relacionados com o mecanismo cinético de transferência de massa por adsorção e dessorção entre as fases sólidas do adsorvente.

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.

Formulação teórica dos fundamentos da otimização global topográfica com análise de desempenho e aplicações à estabilidade de fases de misturas termodinâmicas

Métodos de otimização que utilizam condições de otimalidade de primeira e/ou segunda ordem são conhecidos por serem eficientes. Comumente, esses métodos iterativos são desenvolvidos e analisados à luz da análise matemática do espaço euclidiano n-dimensional, cuja natureza é de caráter local. Consequentemente, esses métodos levam a algoritmos iterativos que executam apenas as buscas locais. Assim, a aplicação de tais algoritmos para o cálculo de minimizadores globais de uma função não linear,especialmente não-convexas e multimodais, depende fortemente da localização dos pontos de partida. O método de Otimização Global Topográfico é um algoritmo de agrupamento, que utiliza uma abordagem baseada em conceitos elementares da teoria dos grafos, a fim de gerar bons pontos de partida para os métodos de busca local, a partir de pontos distribuídos de modo uniforme no interior da região viável. Este trabalho tem dois objetivos. O primeiro é realizar uma nova abordagem sobre método de Otimização Global Topográfica, onde, pela primeira vez, seus fundamentos são formalmente descritos e suas propriedades básicas são matematicamente comprovadas. Neste contexto, propõe-se uma fórmula semi-empírica para calcular o parâmetro chave deste algoritmo de agrupamento, e, usando um método robusto e eficiente de direções viáveis por pontos-interiores, estendemos o uso do método de Otimização Global Topográfica a problemas com restrições de desigualdade. O segundo objetivo é a aplicação deste método para a análise de estabilidade de fase em misturas termodinâmicas,o qual consiste em determinar se uma dada mistura se apresenta em uma ou mais fases. A solução deste problema de otimização global é necessária para o cálculo do equilíbrio de fases, que é um problema de grande importância em processos da engenharia, como, por exemplo, na separação por destilação, em processos de extração e simulação da recuperação terciária de petróleo, entre outros. Além disso, afim de ter uma avaliação inicial do potencial dessa técnica, primeiro vamos resolver 70 problemas testes, e então comparar o desempenho do método proposto aqui com o solver MIDACO, um poderoso software recentemente introduzido no campo da otimização global.

Otimização global topográfica aplicada a problemas de otimização com restrições de igualdade e desigualdade

Os métodos de otimização que adotam condições de otimalidade de primeira e/ou segunda ordem são eficientes e normalmente esses métodos iterativos são desenvolvidos e analisados através da análise matemática do espaço euclidiano n-dimensional, o qual tem caráter local. Esses métodos levam a algoritmos iterativos que são usados para o cálculo de minimizadores globais de uma função não linear, principalmente não-convexas e multimodais, dependendo da posição dos pontos de partida. Método de Otimização Global Topográfico é um algoritmo de agrupamento, o qual é fundamentado nos conceitos elementares da teoria dos grafos, com a finalidade de gerar bons pontos de partida para os métodos de busca local, com base nos pontos distribuídos de modo uniforme no interior da região viável. Este trabalho tem como objetivo a aplicação do método de Otimização Global Topográfica junto com um método robusto e eficaz de direções viáveis por pontos-interiores a problemas de otimização que tem restrições de igualdade e/ou desigualdade lineares e/ou não lineares, que constituem conjuntos viáveis com interiores não vazios. Para cada um destes problemas, é representado também um hiper-retângulo compreendendo cada conjunto viável, onde os pontos amostrais são gerados.

Materials selection in mechanical design

A novel materials-selection procedure has been developed and implemented in software. The procedure makes use of Materials Selection Charts: a new way of displaying material property data; and performance indices: combinations of material properties which govern performance. Optimization methods are employed for simultaneous selection of both material and shape.

Structured precision modelling with Cholesky basis superposition for speech recognition

Structured precision modelling is an important approach to improve the intra-frame correlation modelling of the standard HMM, where Gaussian mixture model with diagonal covariance are used. Previous work has all been focused on direct structured representation of the precision matrices. In this paper, a new framework is proposed, where the structure of the Cholesky square root of the precision matrix is investigated, referred to as Cholesky Basis Superposition (CBS). Each Cholesky matrix associated with a particular Gaussian distribution is represented as a linear combination of a set of Gaussian independent basis upper-triangular matrices. Efficient optimization methods are derived for both combination weights and basis matrices. Experiments on a Chinese dictation task showed that the proposed approach can significantly outperformed the direct structured precision modelling with similar number of parameters as well as full covariance modelling. © 2011 IEEE.

CFD modeling of single-phase flow in a packed bed with MRI validation

Computational fluid dynamics (CFD) simulations are becoming increasingly widespread with the advent of more powerful computers and more sophisticated software. The aim of these developments is to facilitate more accurate reactor design and optimization methods compared to traditional lumped-parameter models. However, in order for CFD to be a trusted method, it must be validated using experimental data acquired at sufficiently high spatial resolution. This article validates an in-house CFD code by comparison with flow-field data obtained using magnetic resonance imaging (MRI) for a packed bed with a particle-to-column diameter ratio of 2. Flows characterized by inlet Reynolds numbers, based on particle diameter, of 27, 55, 111, and 216 are considered. The code used employs preconditioning to directly solve for pressure in low-velocity flow regimes. Excellent agreement was found between the MRI and CFD data with relative error between the experimentally determined and numerically predicted flow-fields being in the range of 3-9%. © 2012 American Institute of Chemical Engineers (AIChE).

基于模型的位姿估计中优化方法研究

介绍了基于模型的位姿估计中所使用的一些优化方法。为了提高位姿估计的精度,摄像机的标定参数必须足够精确,这就对标定过程的非线性优化算法提出了很高的要求,采用了一种新的优化目标函数,用来最小化控制点间的三维重建误差,从而使标定参数是全局最优;在双像机位姿估计中,引入了实时遗传算法进行全局搜索,加快了算法的收敛速度。最后的实验证明了这些方法的正确性并显示出这些方法在精度上比传统方法有了较大程度的提高。

基于代理模型的水下滑翔机机翼设计优化方法

在复杂工程系统的概念设计优化中,高精度数值分析方法得到广泛应用,将高精度数值分析与优化方法有机结合,对设计空间展开全面搜索与寻优,已经成为现代设计优化方法的重要发展方向。以水下滑翔机的概念设计为研究对象,引入代理模型,控制高精度分析试验的数量,有效地化解精度与效率之间的矛盾。将参数化几何建模、网格划分以及流体数值模拟分析集成为自动分析流程,并以此为基础采用试验设计理论,构建代理模型,解决水下滑翔机机翼的多目标设计优化问题。给出基于代理模型的设计优化过程,并系统地比较几种试验设计方法的适应性,重点讨论多项式响应面和径向基函数代理模型,所得代理模型相对误差小于2%。采用梯度寻优方法与遗传算法在给定设计空间内进行全面搜索,获得机翼的最佳平面构形,水下滑翔机的升阻比提高6.76%,俯仰力矩的绝对值由0.2760N•m降低为0.0015N•m,提高水下滑翔机的运动性能。

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

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.

Epipolar geometry estimation based on evolutionary agents

This paper presents a novel approach based on the use of evolutionary agents for epipolar geometry estimation. In contrast to conventional nonlinear optimization methods, the proposed technique employs each agent to denote a minimal subset to compute the fundamental matrix, and considers the data set of correspondences as a 1D cellular environment, in which the agents inhabit and evolve. The agents execute some evolutionary behavior, and evolve autonomously in a vast solution space to reach the optimal (or near optima) result. Then three different techniques are proposed in order to improve the searching ability and computational efficiency of the original agents. Subset template enables agents to collaborate more efficiently with each other, and inherit accurate information from the whole agent set. Competitive evolutionary agent (CEA) and finite multiple evolutionary agent (FMEA) apply a better evolutionary strategy or decision rule, and focus on different aspects of the evolutionary process. Experimental results with both synthetic data and real images show that the proposed agent-based approaches perform better than other typical methods in terms of accuracy and speed, and are more robust to noise and outliers.

An optimal algorithm for low power multiplierless FIR filter design using chebychev criterion

In this paper, we propose a novel finite impulse response (FIR) filter design methodology that reduces the number of operations with a motivation to reduce power consumption and enhance performance. The novelty of our approach lies in the generation of filter coefficients such that they conform to a given low-power architecture, while meeting the given filter specifications. The proposed algorithm is formulated as a mixed integer linear programming problem that minimizes chebychev error and synthesizes coefficients which consist of pre-specified alphabets. The new modified coefficients can be used for low-power VLSI implementation of vector scaling operations such as FIR filtering using computation sharing multiplier (CSHM). Simulations in 0.25um technology show that CSHM FIR filter architecture can result in 55% power and 34% speed improvement compared to carry save multiplier (CSAM) based filters.

RSS and LEA adaptation for indoor location using fingerprinting

Fingerprinting is an indoor location technique, based on wireless networks, where data stored during the offline phase is compared with data collected by the mobile device during the online phase. In most of the real-life scenarios, the mobile node used throughout the offline phase is different from the mobile nodes that will be used during the online phase. This means that there might be very significant differences between the Received Signal Strength values acquired by the mobile node and the ones stored in the Fingerprinting Map. As a consequence, this difference between RSS values might contribute to increase the location estimation error. One possible solution to minimize these differences is to adapt the RSS values, acquired during the online phase, before sending them to the Location Estimation Algorithm. Also the internal parameters of the Location Estimation Algorithms, for example the weights of the Weighted k-Nearest Neighbour, might need to be tuned for every type of terminal. This paper focuses both approaches, using Direct Search optimization methods to adapt the Received Signal Strength and to tune the Location Estimation Algorithm parameters. As a result it was possible to decrease the location estimation error originally obtained without any calibration procedure.