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.

Interpretation of lunar topography : impact cratering and surface roughness

This work seeks to understand past and present surface conditions on the Moon using two different but complementary approaches: topographic analysis using high-resolution elevation data from recent spacecraft missions and forward modeling of the dominant agent of lunar surface modification, impact cratering. The first investigation focuses on global surface roughness of the Moon, using a variety of statistical parameters to explore slopes at different scales and their relation to competing geological processes. We find that highlands topography behaves as a nearly self-similar fractal system on scales of order 100 meters, and there is a distinct change in this behavior above and below approximately 1 km. Chapter 2 focuses this analysis on two localized regions: the lunar south pole, including Shackleton crater, and the large mare-filled basins on the nearside of the Moon. In particular, we find that differential slope, a statistical measure of roughness related to the curvature of a topographic profile, is extremely useful in distinguishing between geologic units. Chapter 3 introduces a numerical model that simulates a cratered terrain by emplacing features of characteristic shape geometrically, allowing for tracking of both the topography and surviving rim fragments over time. The power spectral density of cratered terrains is estimated numerically from model results and benchmarked against a 1-dimensional analytic model. The power spectral slope is observed to vary predictably with the size-frequency distribution of craters, as well as the crater shape. The final chapter employs the rim-tracking feature of the cratered terrain model to analyze the evolving size-frequency distribution of craters under different criteria for identifying "visible" craters from surviving rim fragments. A geometric bias exists that systematically over counts large or small craters, depending on the rim fraction required to count a given feature as either visible or erased.

Mechanisms of substrate selection by the signal recognition particle

The signal recognition particle (SRP) targets membrane and secretory proteins to their correct cellular destination with remarkably high fidelity. Previous studies have shown that multiple checkpoints exist within this targeting pathway that allows ‘correct cargo’ to be quickly and efficiently targeted and for ‘incorrect cargo’ to be promptly rejected. In this work, we delved further into understanding the mechanisms of how substrates are selected or discarded by the SRP. First, we discovered the role of the SRP fingerloop and how it activates the SRP and SRP receptor (SR) GTPases to target and unload cargo in response to signal sequence binding. Second, we learned how an ‘avoidance signal’ found in the bacterial autotransporter, EspP, allows this protein to escape the SRP pathway by causing the SRP and SR to form a ‘distorted’ complex that is inefficient in delivering the cargo to the membrane. Lastly, we determined how Trigger Factor, a co-translational chaperone, helps SRP discriminate against ‘incorrect cargo’ at three distinct stages: SRP binding to RNC; targeting of RNC to the membrane via SRP-FtsY assembly; and stronger antagonism of SRP targeting of ribosomes bearing nascent polypeptides that exceed a critical length. Overall, results delineate the rich underlying mechanisms by which SRP recognizes its substrates, which in turn activates the targeting pathway and provides a conceptual foundation to understand how timely and accurate selection of substrates is achieved by this protein targeting machinery.

Convex model predictive control for vehicular systems

In this work, the author presents a method called Convex Model Predictive Control (CMPC) to control systems whose states are elements of the rotation matrices SO(n) for n = 2, 3. This is done without charts or any local linearization, and instead is performed by operating over the orbitope of rotation matrices. This results in a novel model predictive control (MPC) scheme without the drawbacks associated with conventional linearization techniques such as slow computation time and local minima. Of particular emphasis is the application to aeronautical and vehicular systems, wherein the method removes many of the trigonometric terms associated with these systems’ state space equations. Furthermore, the method is shown to be compatible with many existing variants of MPC, including obstacle avoidance via Mixed Integer Linear Programming (MILP).

Imperfection Insensitive Thin Shells

The buckling of axially compressed cylindrical shells and externally pressurized spherical shells is extremely sensitive to even very small geometric imperfections. In practice this issue is addressed by either using overly conservative knockdown factors, while keeping perfect axial or spherical symmetry, or adding closely and equally spaced stiffeners on shell surface. The influence of imperfection-sensitivity is mitigated, but the shells designed from these approaches are either too heavy or very expensive and are still sensitive to imperfections. Despite their drawbacks, these approaches have been used for more than half a century.

This thesis proposes a novel method to design imperfection-insensitive cylindrical shells subject to axial compression. Instead of following the classical paths, focused on axially symmetric or high-order rotationally symmetric cross-sections, the method in this thesis adopts optimal symmetry-breaking wavy cross-sections (wavy shells). The avoidance of imperfection sensitivity is achieved by searching with an evolutionary algorithm for smooth cross-sectional shapes that maximize the minimum among the buckling loads of geometrically perfect and imperfect wavy shells. It is found that the shells designed through this approach can achieve higher critical stresses and knockdown factors than any previously known monocoque cylindrical shells. It is also found that these shells have superior mass efficiency to almost all previously reported stiffened shells.

Experimental studies on a design of composite wavy shell obtained through the proposed method are presented in this thesis. A method of making composite wavy shells and a photogrametry technique of measuring full-field geometric imperfections have been developed. Numerical predictions based on the measured geometric imperfections match remarkably well with the experiments. Experimental results confirm that the wavy shells are not sensitive to imperfections and can carry axial compression with superior mass efficiency.

An efficient computational method for the buckling analysis of corrugated and stiffened cylindrical shells subject to axial compression has been developed in this thesis. This method modifies the traditional Bloch wave method based on the stiffness matrix method of rotationally periodic structures. A highly efficient algorithm has been developed to implement the modified Bloch wave method. This method is applied in buckling analyses of a series of corrugated composite cylindrical shells and a large-scale orthogonally stiffened aluminum cylindrical shell. Numerical examples show that the modified Bloch wave method can achieve very high accuracy and require much less computational time than linear and nonlinear analyses of detailed full finite element models.

This thesis presents parametric studies on a series of externally pressurized pseudo-spherical shells, i.e., polyhedral shells, including icosahedron, geodesic shells, and triambic icosahedra. Several optimization methods have been developed to further improve the performance of pseudo-spherical shells under external pressure. It has been shown that the buckling pressures of the shell designs obtained from the optimizations are much higher than the spherical shells and not sensitive to imperfections.

High frequency wave propagation in the earth: theory and observation

The wave-theoretical analysis of acoustic and elastic waves refracted by a spherical boundary across which both velocity and density increase abruptly and thence either increase or decrease continuously with depth is formulated in terms of the general problem of waves generated at a steady point source and scattered by a radially heterogeneous spherical body. A displacement potential representation is used for the elastic problem that results in high frequency decoupling of P-SV motion in a spherically symmetric, radially heterogeneous medium. Through the application of an earth-flattening transformation on the radial solution and the Watson transform on the sum over eigenfunctions, the solution to the spherical problem for high frequencies is expressed as a Weyl integral for the corresponding half-space problem in which the effect of boundary curvature maps into an effective positive velocity gradient. The results of both analytical and numerical evaluation of this integral can be summarized as follows for body waves in the crust and upper mantle:

1) In the special case of a critical velocity gradient (a gradient equal and opposite to the effective curvature gradient), the critically refracted wave reduces to the classical head wave for flat, homogeneous layers.

2) For gradients more negative than critical, the amplitude of the critically refracted wave decays more rapidly with distance than the classical head wave.

3) For positive, null, and gradients less negative than critical, the amplitude of the critically refracted wave decays less rapidly with distance than the classical head wave, and at sufficiently large distances, the refracted wave can be adequately described in terms of ray-theoretical diving waves. At intermediate distances from the critical point, the spectral amplitude of the refracted wave is scalloped due to multiple diving wave interference.

These theoretical results applied to published amplitude data for P-waves refracted by the major crustal and upper mantle horizons (the Pg, P*, and Pn travel-time branches) suggest that the 'granitic' upper crust, the 'basaltic' lower crust, and the mantle lid all have negative or near-critical velocity gradients in the tectonically active western United States. On the other hand, the corresponding horizons in the stable eastern United States appear to have null or slightly positive velocity gradients. The distribution of negative and positive velocity gradients correlates closely with high heat flow in tectonic regions and normal heat flow in stable regions. The velocity gradients inferred from the amplitude data are generally consistent with those inferred from ultrasonic measurements of the effects of temperature and pressure on crustal and mantle rocks and probable geothermal gradients. A notable exception is the strong positive velocity gradient in the mantle lid beneath the eastern United States (2 x 10^-3 sec^-1), which appears to require a compositional gradient to counter the effect of even a small geothermal gradient.

New seismic-refraction data were recorded along a 800 km profile extending due south from the Canadian border across the Columbia Plateau into eastern Oregon. The source for the seismic waves was a series of 20 high-energy chemical explosions detonated by the Canadian government in Greenbush Lake, British Columbia. The first arrivals recorded along this profile are on the Pn travel-time branch. In northern Washington and central Oregon their travel time is described by T = Δ/8.0 + 7.7 sec, but in the Columbia Plateau the Pn arrivals are as much as 0.9 sec early with respect to this line. An interpretation of these Pn arrivals together with later crustal arrivals suggest that the crust under the Columbia Plateau is thinner by about 10 km and has a higher average P-wave velocity than the 35-km-thick, 62-km/sec crust under the granitic-metamorphic terrain of northern Washington. A tentative interpretation of later arrivals recorded beyond 500 km from the shots suggests that a thin 8.4-km/sec horizon may be present in the upper mantle beneath the Columbia Plateau and that this horizon may form the lid to a pronounced low-velocity zone extending to a depth of about 140 km.