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.

Highly sensitive wave-front sensor with a non-zero-order phase plate

We propose a novel highly sensitive wave front detection method for a quick check of a flat wave front by taking advantage of a non-zero-order pi phase plate that yields a non-zero-order diffraction pattern. When a light beam with a flat wave front illuminates a phase plate, the zero-order intensity is zero. When there is a slight distortion of the wave front, the zero-order intensity increases. The ratio of first-order intensity to that of zero-order intensity is used as the criterion with which to judge whether the wave front under test is flat, eliminating the influence of background light. Experimental results demonstrate that this method is efficient, robust, and cost-effective and should be highly interesting for a quick check of a flat wave front of a large-aperture laser beam and adaptive optical systems. (c) 2005 Optical Society of America.

I. Site effects and exciton structure in molecular crystals - Benzene. II. The first and second triplet states of solid benzene

The effect of intermolecular coupling in molecular energy levels (electronic and vibrational) has been investigated in neat and isotopic mixed crystals of benzene. In the isotopic mixed crystals of C₆H₆, C₆H₅D, m-C₆H₄D₂, p-C₆H₄D₂, sym-C₆H₃D₃, C₆D₅H, and C₆D₆ in either a C₆H₆ or C₆D₆ host, the following phenomena have been observed and interpreted in terms of a refined Frenkel exciton theory: a) Site shifts; b) site group splittings of the degenerate ground state vibrations of C₆H₆, C₆D₆, and sym-C₆H₃D₃; c) the orientational effect for the isotopes without a trigonal axis in both the ¹B_2u electronic state and the ground state vibrations; d) intrasite Fermi resonance between molecular fundamentals due to the reduced symmetry of the crystal site; and e) intermolecular or intersite Fermi resonance between nearly degenerate states of the host and guest molecules. In the neat crystal experiments on the ground state vibrations it was possible to observe many of these phenomena in conjunction with and in addition to the exciton structure.

To theoretically interpret these diverse experimental data, the concepts of interchange symmetry, the ideal mixed crystal, and site wave functions have been developed and are presented in detail. In the interpretation of the exciton data the relative signs of the intermolecular coupling constants have been emphasized, and in the limit of the ideal mixed crystal a technique is discussed for locating the exciton band center or unobserved exciton components. A differentiation between static and dynamic interactions is made in the Frenkel limit which enables the concepts of site effects and exciton coupling to be sharpened. It is thus possible to treat the crystal induced effects in such a fashion as to make their similarities and differences quite apparent.

A calculation of the ground state vibrational phenomena (site shifts and splittings, orientational effects, and exciton structure) and of the crystal lattice modes has been carried out for these systems. This calculation serves as a test of the approximations of first order Frenkel theory and the atom-atom, pair wise interaction model for the intermolecular potentials. The general form of the potential employed was V(r) = Be^-Cr - A/r⁶ ; the force constants were obtained from the potential by assuming the atoms were undergoing simple harmonic motion.

In part II the location and identification of the benzene first and second triplet states (³B_1u and ³E_1u) is given.

Modelling and simulation of the second-order Doppler error of a laser dual-frequency interferometer

Only the first- order Doppler frequency shift is considered in current laser dual- frequency interferometers; however; the second- order Doppler frequency shift should be considered when the measurement corner cube ( MCC) moves at high velocity or variable velocity because it can cause considerable error. The influence of the second- order Doppler frequency shift on interferometer error is studied in this paper, and a model of the second- order Doppler error is put forward. Moreover, the model has been simulated with both high velocity and variable velocity motion. The simulated results show that the second- order Doppler error is proportional to the velocity of the MCC when it moves with uniform motion and the measured displacement is certain. When the MCC moves with variable motion, the second- order Doppler error concerns not only velocity but also acceleration. When muzzle velocity is zero the second- order Doppler error caused by an acceleration of 0.6g can be up to 2.5 nm in 0.4 s, which is not negligible in nanometric measurement. Moreover, when the muzzle velocity is nonzero, the accelerated motion may result in a greater error and decelerated motion may result in a smaller error.

Optimal H2 order-one reduction by solving eigenproblems for polynomial equations

A method is given for solving an optimal H2 approximation problem for SISO linear time-invariant stable systems. The method, based on constructive algebra, guarantees that the global optimum is found; it does not involve any gradient-based search, and hence avoids the usual problems of local minima. We examine mostly the case when the model order is reduced by one, and when the original system has distinct poles. This case exhibits special structure which allows us to provide a complete solution. The problem is converted into linear algebra by exhibiting a finite-dimensional basis for a certain space, and can then be solved by eigenvalue calculations, following the methods developed by Stetter and Moeller. The use of Buchberger's algorithm is avoided by writing the first-order optimality conditions in a special form, from which a Groebner basis is immediately available. Compared with our previous work the method presented here has much smaller time and memory requirements, and can therefore be applied to systems of significantly higher McMillan degree. In addition, some hypotheses which were required in the previous work have been removed. Some examples are included.

Semi-implicit second order finite volume jet stream computations

Semi-implicit, second order temporal and spatial finite volume computations of the flow in a differentially heated rotating annulus are presented. For the regime considered, three cyclones and anticyclones separated by a relatively fast moving jet of fluid or "jet stream" are predicted. Two second order methods are compared with, first order spatial predictions, and experimental measurements. Velocity vector plots are used to illustrate the predicted flow structure. Computations made using second order central differences are shown to agree best with experimental measurements, and to be stable for integrations over long time periods (> 1000s). No periodic smoothing is required to prevent divergence.

APPLICATION OF ULTRAMICROELECTRODES IN STUDIES OF HOMOGENEOUS CATALYTIC REACTIONS .3. THE CONDITION FOR QUASI-1ST AND 2ND-ORDER HOMOGENEOUS CATALYTIC REACTIONS AT ULTRAMICRODISK ELECTRODES IN THE STEADY-STATE

The conditions for quasi-first and second order homogeneous catalytic reactions and their variation with each other at an ultramicrodisk electrode in the steady state are discussed in this paper. The order of reaction can be controlled by changing the dimension of the ultramicroelectrode: the second order reaction can be changed to quasi-first by decreasing the dimension of the ultramicroelectrode. An example of this is given. The main factor effect on the reaction order is the dimension of the ultramicroelectrode. The K4Fe(CN)6-aminopyrine system is selected to confirm the theory, the experiments showing that the system is a second order reaction at a 432 mum microelectrode, and a quasi-first order reaction at a 19 mum ultramicroelectrode. The kinetic constant of the system can be determined by applying the previous theory of homogeneous catalytic reaction.

Second-order Stokes solutions for internal waves in three-layer density-stratified fluid

In this paper, internal waves in three-layer stratified fluid are investigated by using a perturbation method, and the second-order asymptotic solutions of the velocity potentials and the second-order Stokes solutions of the associated elevations of the interfacial waves are presented based on the small amplitude wave theory. As expected, the first-order solutions are consistent with ordinary linear theoretical results, and the second-order solutions describe the second-order modification on the linear theory and the interactions between the two interfacial waves. Both the first-order and second-order solutions derived depend on the depths and densities of the three-layer fluid. It is also noted that the solutions obtained from the present work include the theoretical results derived by Umeyama as special cases.

Representation of microscale ocean wavenumber spectrum correct to the second order

In this paper, the analytical representations of four wave source functions in high-frequency spectrum range are given on the basis of ocean wave theory and dimensional analysis, and the perturbation method is used to solve the governing equations of ocean wave high-frequency spectrum on the basis of the temporally stationary and locally homogeneous scale relations of microscale wave. The microscale ocean wavenumber spectrum correct to the second order has an explicit structure, its first order part represents the equilibrium between different source functions, and its second order part represents the contribution of microscale wave propagation.

Second-order Stokes wave solutions for intefacial waves in three-layer stratified fluid with background current

In this paper, interfacial waves in three-layer stratified fluid with background current are investigated using a perturbation method, and the second-order asymptotic solutions of the velocity potentials and the second-order Stokes wave solutions of the associated elevations of the interfacial waves are presented based on the small amplitude wave theory, and the Kelvin-Helmholtz instability of interfacial waves is studied. As expected, for three-layer stratified fluid with background current, the first-order asymptotic solutions (linear wave solutions), dispersion relation and the second-order asymptotic solutions derived depend on not only the depths and densities of the three-layer fluid but also the background current of the fluids, and the second-order Stokes wave solutions of the associated elevations of the interfacial waves describe not only the second-order nonlinear wave-wave interactions between the interfacial waves but also the second-order nonlinear interactions between the interfacial waves and currents. It is also noted that the solutions obtained from the present work include the theoretical results derived by Chen et al (2005) as a special case. It also shows that with the given wave number k (real number) the interfacial waves may show Kelvin-Helmholtz instability.

Reified temporal logics: an overview

There are three main approaches to the representation of temporal information in AI literature: the so-called method of temporal arguments that simply extends functions and predicates of first-order language to include time as the additional argument; modal temporal logics which are extensions ofthe propositional or predicate calculus with modal temporal operators; and reified temporal logics which reify standard propositions of some initial language (e.g., the classical first-order or modal logic) as objects denoting propositional terms. The objective of this paper is to provide an overview onthe temporal reified approach by looking closely atsome representative existing systems featuring reified propositions, including those of Allen, McDermott, Shoham, Reichgelt, Galton, and Ma and Knight. We shall demonstrate that, although reified logics might be more complicated in expressing assertions about some given objects with respect to different times, they accord a special status to time and therefore have several distinct advantages in talking about some important issues which would be difficult (if not impossible) to express in other approaches.

Second-order distorted wave calculation for electron impact ionization of hydrogen

The triple differential cross sections for ionization of atomic hydrogen by electron impact are analysed in the case of coplanar, asymmetric geometry within the framework of second- order distorted wave theory. Detailed calculations are performed without making any approximations (other than numerical) in the evaluation of the second-order amplitude. The present results are compared with experimental measurements and other theoretical calculations for incident energies of 250, 150 and 54.4 eV. It is found that the second-order calculations represent a marked improvement over the results obtained from first-order theories for impact energies of 150 eV and higher. The close agreement between the present second-order plane wave calculation and those of Byron et al calculated using the closure approximation at an incident energy of 250 eV implies that the closure approximation is valid for this energy. The large difference between the present second-order distorted wave calculations and experiment at an incident energy of 54.4 eV suggests that higher order effects are important for incident energies less than 100 eV.

Second-order NMR spectra at high field of common organic functional groups

The proton NMR spectra of aryl n-propyl sulfides gave rise to what may appear to be first-order proton NMR spectra. Upon oxidation to the corresponding sulfone, the spectra changed appearance dramatically and were clearly second-order. A detailed analysis of these second-order spectra, in the sulfone series, provided vicinal coupling constants which indicated that these compounds had a moderate preference for the anti-conformer, reflecting the much greater size of the sulfone over the sulfide. It also emerged, from this study, that the criterion for observing large second-order effects in the proton NMR spectra of 1,2-disubstituted ethanes was that the difference in vicinal coupling constants must be large and the difference in geminal coupling constants must be small. n-Propyl triphenylphosphonium bromide and 2-trimethylsilylethanesulfonyl chloride, and derivatives thereof, also exhibited second-order spectra, again due to the bulky substituents. Since these spectra are second-order due to magnetic nonequivalence of the nuclei in question, not chemical shifts, the proton spectra are perpetually second-order and can never be rendered first-order by using higher field NMR spectrometers.

Distinguished algebraic semantics for t-norm based fuzzy logics:Methods and algebraic equivalencies

This paper is a contribution to Mathematical fuzzy logic, in particular to the algebraic study of t-norm based fuzzy logics. In the general framework of propositional core and ?-core fuzzy logics we consider three properties of completeness with respect to any semantics of linearly ordered algebras. Useful algebraic characterizations of these completeness properties are obtained and their relations are studied. Moreover, we concentrate on five kinds of distinguished semantics for these logics-namely the class of algebras defined over the real unit interval, the rational unit interval, the hyperreals (all ultrapowers of the real unit interval), the strict hyperreals (only ultrapowers giving a proper extension of the real unit interval) and finite chains, respectively-and we survey the known completeness methods and results for prominent logics. We also obtain new interesting relations between the real, rational and (strict) hyperreal semantics, and good characterizations for the completeness with respect to the semantics of finite chains. Finally, all completeness properties and distinguished semantics are also considered for the first-order versions of the logics where a number of new results are proved. © 2009 Elsevier B.V. All rights reserved.

Propositional and Relational Bayesian Networks Associated with Imprecise and Qualitative Probabilistic Assessments

This paper investigates a representation language with flexibility inspired by probabilistic logic and compactness inspired by relational Bayesian networks. The goal is to handle propositional and first-order constructs together with precise, imprecise, indeterminate and qualitative probabilistic assessments. The paper shows how this can be achieved through the theory of credal networks. New exact and approximate inference algorithms based on multilinear programming and iterated/loopy propagation of interval probabilities are presented; their superior performance, compared to existing ones, is shown empirically.