Robot navigation in dense crowds : statistical models and experimental studies of human robot cooperation

This thesis explores the problem of mobile robot navigation in dense human crowds. We begin by considering a fundamental impediment to classical motion planning algorithms called the freezing robot problem: once the environment surpasses a certain level of complexity, the planner decides that all forward paths are unsafe, and the robot freezes in place (or performs unnecessary maneuvers) to avoid collisions. Since a feasible path typically exists, this behavior is suboptimal. Existing approaches have focused on reducing predictive uncertainty by employing higher fidelity individual dynamics models or heuristically limiting the individual predictive covariance to prevent overcautious navigation. We demonstrate that both the individual prediction and the individual predictive uncertainty have little to do with this undesirable navigation behavior. Additionally, we provide evidence that dynamic agents are able to navigate in dense crowds by engaging in joint collision avoidance, cooperatively making room to create feasible trajectories. We accordingly develop interacting Gaussian processes, a prediction density that captures cooperative collision avoidance, and a "multiple goal" extension that models the goal driven nature of human decision making. Navigation naturally emerges as a statistic of this distribution.

Most importantly, we empirically validate our models in the Chandler dining hall at Caltech during peak hours, and in the process, carry out the first extensive quantitative study of robot navigation in dense human crowds (collecting data on 488 runs). The multiple goal interacting Gaussian processes algorithm performs comparably with human teleoperators in crowd densities nearing 1 person/m², while a state of the art noncooperative planner exhibits unsafe behavior more than 3 times as often as the multiple goal extension, and twice as often as the basic interacting Gaussian process approach. Furthermore, a reactive planner based on the widely used dynamic window approach proves insufficient for crowd densities above 0.55 people/m². We also show that our noncooperative planner or our reactive planner capture the salient characteristics of nearly any dynamic navigation algorithm. For inclusive validation purposes, we show that either our non-interacting planner or our reactive planner captures the salient characteristics of nearly any existing dynamic navigation algorithm. Based on these experimental results and theoretical observations, we conclude that a cooperation model is critical for safe and efficient robot navigation in dense human crowds.

Finally, we produce a large database of ground truth pedestrian crowd data. We make this ground truth database publicly available for further scientific study of crowd prediction models, learning from demonstration algorithms, and human robot interaction models in general.

Continuous stochastic processes

A general review of stochastic processes is given in the introduction; definitions, properties and a rough classification are presented together with the position and scope of the author's work as it fits into the general scheme.

The first section presents a brief summary of the pertinent analytical properties of continuous stochastic processes and their probability-theoretic foundations which are used in the sequel.

The remaining two sections (II and III), comprising the body of the work, are the author's contribution to the theory. It turns out that a very inclusive class of continuous stochastic processes are characterized by a fundamental partial differential equation and its adjoint (the Fokker-Planck equations). The coefficients appearing in those equations assimilate, in a most concise way, all the salient properties of the process, freed from boundary value considerations. The writer’s work consists in characterizing the processes through these coefficients without recourse to solving the partial differential equations.

First, a class of coefficients leading to a unique, continuous process is presented, and several facts are proven to show why this class is restricted. Then, in terms of the coefficients, the unconditional statistics are deduced, these being the mean, variance and covariance. The most general class of coefficients leading to the Gaussian distribution is deduced, and a complete characterization of these processes is presented. By specializing the coefficients, all the known stochastic processes may be readily studied, and some examples of these are presented; viz. the Einstein process, Bachelier process, Ornstein-Uhlenbeck process, etc. The calculations are effectively reduced down to ordinary first order differential equations, and in addition to giving a comprehensive characterization, the derivations are materially simplified over the solution to the original partial differential equations.

In the last section the properties of the integral process are presented. After an expository section on the definition, meaning, and importance of the integral process, a particular example is carried through starting from basic definition. This illustrates the fundamental properties, and an inherent paradox. Next the basic coefficients of the integral process are studied in terms of the original coefficients, and the integral process is uniquely characterized. It is shown that the integral process, with a slight modification, is a continuous Markoff process.

The elementary statistics of the integral process are deduced: means, variances, and covariances, in terms of the original coefficients. It is shown that an integral process is never temporally homogeneous in a non-degenerate process.

Finally, in terms of the original class of admissible coefficients, the statistics of the integral process are explicitly presented, and the integral process of all known continuous processes are specified.

Sulfur-Cycling in Methane-Rich Ecosystems: Uncovering Microbial Processes and Novel Niches

Microbial sulfur cycling communities were investigated in two methane-rich ecosystems, terrestrial mud volcanoes (TMVs) and marine methane seeps, in order to investigate niches and processes that would likely be central to the functioning of these crucial ecosystems. Terrestrial mud volcanoes represent geochemically diverse habitats with varying sulfur sources and yet sulfur-cycling in these environments remains largely unexplored. Here we characterized the sulfur-metabolizing microorganisms and activity in 4 TMVs in Azerbaijan, supporting the presence of active sulfur-oxidizing and sulfate-reducing guilds in all 4 TMVs across a range of physiochemical conditions, with diversity of these guilds being unique to each TMV. We also found evidence for the anaerobic oxidation of methane coupled to sulfate reduction, a process which we explored further in the more tractable marine methane seeps. Diverse associations between methanotrophic archaea (ANME) and sulfate-reducing bacterial groups (SRB) often co-occur in marine methane seeps, however the ecophysiology of these different symbiotic associations has not been examined. Using a combination of molecular, geochemical and fluorescence in situ hybridization coupled to nano-scale secondary ion mass spectrometry (FISH-NanoSIMS) analyses of in situ seep sediments and methane-amended sediment incubations from diverse locations, we show that the unexplained diversity in SRB associated with ANME cells can be at least partially explained by preferential nitrate utilization by one particular partner, the seepDBB. This discovery reveals that nitrate is likely an important factor in community structuring and diversity in marine methane seep ecosystems. The thesis concludes with a study of the dynamics between ANME and their associated SRB partners. We inhibited sulfate reduction and followed the metabolic processes of the community as well as the effect of ANME/SRB aggregate composition and growth on a cellular level by tracking 15N substrate incorporation into biomass using FISH-NanoSIMS. We revealed that while sulfate-reducing bacteria gradually disappeared over time in incubations with an SRB inhibitor, the ANME archaea persisted in the form of ANME-only aggregates, which are capable of little to no growth when sulfate reduction is inhibited. These data suggest ANME are not able to synthesize new proteins when sulfate reduction is inhibited.

Dynamics of rotationally resolved multiphoton ionization processes in molecules

This dissertation presents the results of studies of several rotationally- resolved resonance enhanced multiphoton ionization (REMPI) processes in some simple molecular systems. The objective of these studies is to quantitatively identify the underlying dynamics of this highly state-specific process which utilizes the narrow bandwidth radiation of a laser to ionize a molecule by first preparing an excited state via multiphoton absorption and subsequently ionizing that state before it can decay. Coupled with high-resolution photoelectron spectroscopy, REMPI is clearly an important probe of molecular excited states and their photoioniza tion dynamics.

A key feature of our studies is that they are carried out using accurate Hartree-Fock orbitals to describe the photoelectron orbitals of the molecular ions. The use of such photoelectron orbitals is important in rotationally-resolved studies where the angular momentum coupling in the photoelectron orbital plays a significant role in the photoionization dynamics. In these studies the Hartree-Fock molecular molecular photoelectron orbitals are obtained by numerical solution of a Lippmann-Schwinger integral equation.

Studies reported here include investigations of (i) ionic rotational branching ratios and their energy dependence for REMPI via the A^2Σ^+(3sσ) and D^2Σ^+(3pσ)states of NO, (ii) the influence of angular momentum constraints on branching ratios at low photoelectron energies for REMPI via low-J levels of the resonant intermediate state, (iii) the strong dependence of photoelectron angular distributions on final ionic rotational state and on the alignment in REMPI of the A^2Σ^+ state of NO, (iv) vibrational state dependence of ionic rotational branching ratios arising from rapid orbital evolution in resonant states (E'^2Σ^+(3pσ) of CH), (v) the influence of rovibronic interactions on the rotational branching ratios seen in REMPI via the D^2Σ^+(3pσ) state of NO, and (vi) effects of laser intensity on the photoionization dynamics of REMPI.

I. Application of multi-Regge theory to production processes. II. High energy model for proton-proton scattering

This dissertation consists of two parts. The first part presents an explicit procedure for applying multi-Regge theory to production processes. As an illustrative example, the case of three body final states is developed in detail, both with respect to kinematics and multi-Regge dynamics. Next, the experimental consistency of the multi-Regge hypothesis is tested in a specific high energy reaction; the hypothesis is shown to provide a good qualitative fit to the data. In addition, the results demonstrate a severe suppression of double Pomeranchon exchange, and show the coupling of two "Reggeons" to an external particle to be strongly damped as the particle's mass increases. Finally, with the use of two body Regge parameters, order of magnitude estimates of the multi-Regge cross section for various reactions are given.

The second part presents a diffraction model for high energy proton-proton scattering. This model developed by Chou and Yang assumes high energy elastic scattering results from absorption of the incident wave into the many available inelastic channels, with the absorption proportional to the amount of interpenetrating hadronic matter. The assumption that the hadronic matter distribution is proportional to the charge distribution relates the scattering amplitude for pp scattering to the proton form factor. The Chou-Yang model with the empirical proton form factor as input is then applied to calculate a high energy, fixed momentum transfer limit for the scattering cross section, This limiting cross section exhibits the same "dip" or "break" structure indicated in present experiments, but falls significantly below them in magnitude. Finally, possible spin dependence is introduced through a weak spin-orbit type term which gives rather good agreement with pp polarization data.

Electronic and kinetic processes in the Cu/CuCl double pulse laser

Kinetic and electronic processes in a Cu/CuCl double pulsed laser were investigated by measuring discharge and laser pulse characteristics, and by computer modeling. There are two time scales inherent to the operation of the Cu/CuCl laser. The first is during the interpulse afterglow (tens to hundreds of microseconds). The second is during the pumping pulse (tens of nanoseconds). It was found that the character of the pumping pulse is largely determined by the initial conditions provided by the interpulse afterglow. By tailoring the dissociation pulse to be long and low energy, and by conditioning the afterglow, one may select the desired initial conditions and thereby significantly improve laser performance. With a low energy dissociation pulse, the fraction of metastable copper obtained from a CuCl dissociation is low. By maintaining the afterglow, contributions to the metastable state from ion recombinations are prevented, and the plasma impedance remains low thereby increasing the rate of current rise during the pumping pulse. Computer models for the dissociation pulse, afterglow, pumping pulse and laser pulse reproduced experimentally observed behavior of laser pulse energy and power as a function of time delay, pumping pulse characteristics, and buffer gas pressure. The sensitivity of laser pulse properties on collisional processes (e.g., CuCl reassociation rates) was investigated.

Combustion of CS₂/O₂ in a laminar mixing layer and processes in the CO chemical laser

The combustion of CS₂ and O₂ in a free burning laminar mixing layer at low pressure was investigated using emission spectroscopy. The temperature fields, CO vibrational distributions, and CO concentrations were measured. The data indicate that vibration ally excited CO was produced in the mixing layer flames, but that there were no vibrational population inversions. In comparison with the CS₂/O₂ premixed flames, the mixing layer flames favored greater production of COS and CO₂. Computer modeling was used to study the mechanisms responsible for the production of COS and CO₂, and to study how the branching chain mechanism responsible for production of CO affects the behavior of the mixing layer flame. The influences of the gas additives, N₂O, COS, and CNBr, were also investigated.

Experimental and theoretical developments in extended x-ray absorption fine structure (EXAFS) spectroscopy

To obtain accurate information from a structural tool it is necessary to have an understanding of the physical principles which govern the interaction between the probe and the sample under investigation. In this thesis a detailed study of the physical basis for Extended X-ray Absorption Fine Structure (EXAFS) spectroscopy is presented. A single scattering formalism of EXAFS is introduced which allows a rigorous treatment of the central atom potential. A final state interaction formalism of EXAFS is also discussed. Multiple scattering processes are shown to be significant for systems of certain geometries. The standard single scattering EXAFS analysis produces erroneous results if the data contain a large multiple scattering contribution. The effect of thermal vibrations on such multiple scattering paths is also discussed. From symmetry considerations it is shown that only certain normal modes contribute to the Debye-Waller factor for a particular scattering path. Furthermore, changes in the scattering angles induced by thermal vibrations produces additional EXAFS components called modification factors. These factors are shown to be small for most systems.

A study of the physical basis for the determination of structural information from EXAFS data is also presented. An objective method of determining the background absorption and the threshold energy is discussed and involves Gaussian functions. In addition, a scheme to determine the nature of the scattering atom in EXAFS experiments is introduced. This scheme is based on the fact that the phase intercept is a measure of the type of scattering atom. A method to determine bond distances is also discussed and does not require the use of model compounds or calculated phase shifts. The physical basis for this method is the absence of a linear term in the scattering phases. Therefore, it is possible to separate these phases from the linear term containing the distance information in the total phase.

Reconstructing Past Depositional and Diagenetic Processes through Quantitative Stratigraphic Analysis of the Martian Sedimentary Rock Record

High-resolution orbital and in situ observations acquired of the Martian surface during the past two decades provide the opportunity to study the rock record of Mars at an unprecedented level of detail. This dissertation consists of four studies whose common goal is to establish new standards for the quantitative analysis of visible and near-infrared data from the surface of Mars. Through the compilation of global image inventories, application of stratigraphic and sedimentologic statistical methods, and use of laboratory analogs, this dissertation provides insight into the history of past depositional and diagenetic processes on Mars. The first study presents a global inventory of stratified deposits observed in images from the High Resolution Image Science Experiment (HiRISE) camera on-board the Mars Reconnaissance Orbiter. This work uses the widespread coverage of high-resolution orbital images to make global-scale observations about the processes controlling sediment transport and deposition on Mars. The next chapter presents a study of bed thickness distributions in Martian sedimentary deposits, showing how statistical methods can be used to establish quantitative criteria for evaluating the depositional history of stratified deposits observed in orbital images. The third study tests the ability of spectral mixing models to obtain quantitative mineral abundances from near-infrared reflectance spectra of clay and sulfate mixtures in the laboratory for application to the analysis of orbital spectra of sedimentary deposits on Mars. The final study employs a statistical analysis of the size, shape, and distribution of nodules observed by the Mars Science Laboratory Curiosity rover team in the Sheepbed mudstone at Yellowknife Bay in Gale crater. This analysis is used to evaluate hypotheses for nodule formation and to gain insight into the diagenetic history of an ancient habitable environment on Mars.

Generalizations and extensions of the Fokker-Planck-Kolmogorov equations

The problem of determining probability density functions of general transformations of random processes is considered in this thesis. A method of solution is developed in which partial differential equations satisfied by the unknown density function are derived. These partial differential equations are interpreted as generalized forms of the classical Fokker-Planck-Kolmogorov equations and are shown to imply the classical equations for certain classes of Markov processes. Extensions of the generalized equations which overcome degeneracy occurring in the steady-state case are also obtained.

The equations of Darling and Siegert are derived as special cases of the generalized equations thereby providing unity to two previously existing theories. A technique for treating non-Markov processes by studying closely related Markov processes is proposed and is seen to yield the Darling and Siegert equations directly from the classical Fokker-Planck-Kolmogorov equations.

As illustrations of their applicability, the generalized Fokker-Planck-Kolmogorov equations are presented for certain joint probability density functions associated with the linear filter. These equations are solved for the density of the output of an arbitrary linear filter excited by Markov Gaussian noise and for the density of the output of an RC filter excited by the Poisson square wave. This latter density is also found by using the extensions of the generalized equations mentioned above. Finally, some new approaches for finding the output probability density function of an RC filter-limiter-RC filter system driven by white Gaussian noise are included. The results in this case exhibit the data required for complete solution and clearly illustrate some of the mathematical difficulties inherent to the use of the generalized equations.

Investigation of Fundamental Processes Governing Secondary Organic Aerosol Formation in Laboratory Chambers

Our understanding of the processes and mechanisms by which secondary organic aerosol (SOA) is formed is derived from laboratory chamber studies. In the atmosphere, SOA formation is primarily driven by progressive photooxidation of SOA precursors, coupled with their gas-particle partitioning. In the chamber environment, SOA-forming vapors undergo multiple chemical and physical processes that involve production and removal via gas-phase reactions; partitioning onto suspended particles vs. particles deposited on the chamber wall; and direct deposition on the chamber wall. The main focus of this dissertation is to characterize the interactions of organic vapors with suspended particles and the chamber wall and explore how these intertwined processes in laboratory chambers govern SOA formation and evolution.

A Functional Group Oxidation Model (FGOM) that represents SOA formation and evolution in terms of the competition between functionalization and fragmentation, the extent of oxygen atom addition, and the change of volatility, is developed. The FGOM contains a set of parameters that are to be determined by fitting of the model to laboratory chamber data. The sensitivity of the model prediction to variation of the adjustable parameters allows one to assess the relative importance of various pathways involved in SOA formation.

A critical aspect of the environmental chamber is the presence of the wall, which can induce deposition of SOA-forming vapors and promote heterogeneous reactions. An experimental protocol and model framework are first developed to constrain the vapor-wall interactions. By optimal fitting the model predictions to the observed wall-induced decay profiles of 25 oxidized organic compounds, the dominant parameter governing the extent of wall deposition of a compound is identified, i.e., wall accommodation coefficient. By correlating this parameter with the molecular properties of a compound via its volatility, the wall-induced deposition rate of an organic compound can be predicted based on its carbon and oxygen numbers in the molecule.

Heterogeneous transformation of δ-hydroxycarbonyl, a major first-generation product from long-chain alkane photochemistry, is observed on the surface of particles and walls. The uniqueness of this reaction scheme is the production of substituted dihydrofuran, which is highly reactive towards ozone, OH, and NO3, thereby opening a reaction pathway that is not usually accessible to alkanes. A spectrum of highly-oxygenated products with carboxylic acid, ester, and ether functional groups is produced from the substituted dihydrofuran chemistry, thereby affecting the average oxidation state of the alkane-derived SOA.

The vapor wall loss correction is applied to several chamber-derived SOA systems generated from both anthropogenic and biogenic sources. Experimental and modeling approaches are employed to constrain the partitioning behavior of SOA-forming vapors onto suspended particles vs. chamber walls. It is demonstrated that deposition of SOA-forming vapors to the chamber wall during photooxidation experiments can lead to substantial and systematic underestimation of SOA. Therefore, it is likely that a lack of proper accounting for vapor wall losses that suppress chamber-derived SOA yields contribute substantially to the underprediction of ambient SOA concentrations in atmospheric models.

Spectroscopic investigations of inter- and intramolecular processes in crystalline benzene

I. Introductory Remarks

A brief discussion of the overall organization of the thesis is presented along with a discussion of the relationship between this thesis and previous work on the spectroscopic properties of benzene.

II. Radiationless Transitions and Line broadening

Radiationless rates have been calculated for the ³B_1u→¹A_1g transitions of benzene and perdeuterobenzene as well as for the ¹B_2u→¹A_1g transition of benzene. The rates were calculated using a model that considers the radiationless transition as a tunneling process between two multi-demensional potential surfaces and assuming both harmonic and anharmonic vibrational potentials. Whenever possible experimental parameters were used in the calculation. To this end we have obtained experimental values for the anharmonicities of the carbon-carbon and carbon-hydrogen vibrations and the size of the lowest triplet state of benzene. The use of the breakdown of the Born-Oppenheimer approximation in describing radiationless transitions is critically examined and it is concluded that Herzberg-Teller vibronic coupling is 100 times more efficient at inducing radiationless transitions.

The results of the radiationless transition rate calculation are used to calculate line broadening in several of the excited electronic states of benzene. The calculated line broadening in all cases is in qualitative agreement with experimental line widths.

III. ³B_1u←¹A_1g Absorption Spectra

The ³B_1u←¹A_1g absorption spectra of C₆H₆ and C₆D₆ at 4.2˚K have been obtained at high resolution using the phosphorescence photoexcitation method. The spectrum exhibits very clear evidence of a pseudo-Jahn-Teller distortion of the normally hexagonal benzene molecule upon excitation to the triplet state. Factor group splitting of the 0 – 0 and 0 – 0 + v exciton bands have also been observed. The position of the mean of the 0 – 0 exciton band of C₆H₆ when compared to the phosphorescence origin of a C₆H₆ guest in a C₆D₆ host crystal indicates that the “static” intermolecular interactions between guest and hose are different for C₆H₆ and C₆D₆. Further investigation of this difference using the currently accepted theory of isotopic mixed crystals indicates that there is a 2cm^-1 shift of the ideal mixed crystal level per hot deuterium atom. This shift is observed for both the singlet and triplet states of benzene.

IV. ³E_1u←¹A_1g, Absorption Spectra

The ³E_1u←¹A_1g absorption spectra of C₆H₆ and C₆D₆ at 4.2˚K have been obtained using the phosphorescence photoexcitation technique. In both cases the spectrum is broad and structureless as would be expected from the line broadening calculations.

Stochastic optimal control

H. J. Kushner has obtained the differential equation satisfied by the optimal feedback control law for a stochastic control system in which the plant dynamics and observations are perturbed by independent additive Gaussian white noise processes. However, the differentiation includes the first and second functional derivatives and, except for a restricted set of systems, is too complex to solve with present techniques.

This investigation studies the optimal control law for the open loop system and incorporates it in a sub-optimal feedback control law. This suboptimal control law's performance is at least as good as that of the optimal control function and satisfies a differential equation involving only the first functional derivative. The solution of this equation is equivalent to solving two two-point boundary valued integro-partial differential equations. An approximate solution has advantages over the conventional approximate solution of Kushner's equation.

As a result of this study, well known results of deterministic optimal control are deduced from the analysis of optimal open loop control.

High-energy scattering processes with cuts in the angular momentum plane

The experimental consequence of Regge cuts in the angular momentum plane are investigated. The principle tool in the study is the set of diagrams originally proposed by Amati, Fubini, and Stanghellini. Mandelstam has shown that the AFS cuts are actually cancelled on the physical sheet, but they may provide a useful guide to the properties of the real cuts. Inclusion of cuts modifies the simple Regge pole predictions for high-energy scattering data. As an example, an attempt is made to fit high energy elastic scattering data for pp, ṗp, π^±p, and K^±p, by replacing the Igi pole by terms representing the effect of a Regge cut. The data seem to be compatible with either a cut or the Igi pole.

I. Electronic processes in α-sulfur. II. Polaron motion in a D.C. electric field

Part I: The mobilities of photo-generated electrons and holes in orthorhombic sulfur are determined by drift mobility techniques. At room temperature electron mobilities between 0.4 cm²/V-sec and 4.8 cm²/V-sec and hole mobilities of about 5.0 cm²/V-sec are reported. The temperature dependence of the electron mobility is attributed to a level of traps whose effective depth is about 0.12 eV. This value is further supported by both the voltage dependence of the space-charge-limited, D.C. photocurrents and the photocurrent versus photon energy measurements.

As the field is increased from 10 kV/cm to 30 kV/cm a second mechanism for electron transport becomes appreciable and eventually dominates. Evidence that this is due to impurity band conduction at an appreciably lower mobility (4.10^-4 cm²/V-sec) is presented. No low mobility hole current could be detected. When fields exceeding 30 kV/cm for electron transport and 35 kV/cm for hole transport are applied, avalanche phenomena are observed. The results obtained are consistent with recent energy gap studies in sulfur.

The theory of the transport of photo-generated carriers is modified to include the case of appreciable thermos-regeneration from the traps in one transit time.

Part II: An explicit formula for the electric field E necessary to accelerate an electron to a steady-state velocity v in a polarizable crystal at arbitrary temperature is determined via two methods utilizing Feynman Path Integrals. No approximation is made regarding the magnitude of the velocity or the strength of the field. However, the actual electron-lattice Coulombic interaction is approximated by a distribution of harmonic oscillator potentials. One may be able to find the “best possible” distribution of oscillators using a variational principle, but we have not been able to find the expected criterion. However, our result is relatively insensitive to the actual distribution of oscillators used, and our E-v relationship exhibits the physical behavior expected for the polaron. Threshold fields for ejecting the electron for the polaron state are calculated for several substances using numerical results for a simple oscillator distribution.