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.

Coupled effects of mechanics, geometry, and chemistry on bio-membrane behavior

Lipid bilayer membranes are models for cell membranes--the structure that helps regulate cell function. Cell membranes are heterogeneous, and the coupling between composition and shape gives rise to complex behaviors that are important to regulation. This thesis seeks to systematically build and analyze complete models to understand the behavior of multi-component membranes.

We propose a model and use it to derive the equilibrium and stability conditions for a general class of closed multi-component biological membranes. Our analysis shows that the critical modes of these membranes have high frequencies, unlike single-component vesicles, and their stability depends on system size, unlike in systems undergoing spinodal decomposition in flat space. An important implication is that small perturbations may nucleate localized but very large deformations. We compare these results with experimental observations.

We also study open membranes to gain insight into long tubular membranes that arise for example in nerve cells. We derive a complete system of equations for open membranes by using the principle of virtual work. Our linear stability analysis predicts that the tubular membranes tend to have coiling shapes if the tension is small, cylindrical shapes if the tension is moderate, and beading shapes if the tension is large. This is consistent with experimental observations reported in the literature in nerve fibers. Further, we provide numerical solutions to the fully nonlinear equilibrium equations in some problems, and show that the observed mode shapes are consistent with those suggested by linear stability. Our work also proves that beadings of nerve fibers can appear purely as a mechanical response of the membrane.

Geometric quantization and foliation reduction

A standard question in the study of geometric quantization is whether symplectic reduction interacts nicely with the quantized theory, and in particular whether “quantization commutes with reduction.” Guillemin and Sternberg first proposed this question, and answered it in the affirmative for the case of a free action of a compact Lie group on a compact Kähler manifold. Subsequent work has focused mainly on extending their proof to non-free actions and non-Kähler manifolds. For realistic physical examples, however, it is desirable to have a proof which also applies to non-compact symplectic manifolds.

In this thesis we give a proof of the quantization-reduction problem for general symplectic manifolds. This is accomplished by working in a particular wavefunction representation, associated with a polarization that is in some sense compatible with reduction. While the polarized sections described by Guillemin and Sternberg are nonzero on a dense subset of the Kähler manifold, the ones considered here are distributional, having support only on regions of the phase space associated with certain quantized, or “admissible”, values of momentum.

We first propose a reduction procedure for the prequantum geometric structures that “covers” symplectic reduction, and demonstrate how both symplectic and prequantum reduction can be viewed as examples of foliation reduction. Consistency of prequantum reduction imposes the above-mentioned admissibility conditions on the quantized momenta, which can be seen as analogues of the Bohr-Wilson-Sommerfeld conditions for completely integrable systems.

We then describe our reduction-compatible polarization, and demonstrate a one-to-one correspondence between polarized sections on the unreduced and reduced spaces.

Finally, we describe a factorization of the reduced prequantum bundle, suggested by the structure of the underlying reduced symplectic manifold. This in turn induces a factorization of the space of polarized sections that agrees with its usual decomposition by irreducible representations, and so proves that quantization and reduction do indeed commute in this context.

A significant omission from the proof is the construction of an inner product on the space of polarized sections, and a discussion of its behavior under reduction. In the concluding chapter of the thesis, we suggest some ideas for future work in this direction.

Singularities and horizons in the collisions of gravitational waves

This thesis presents a study of the dynamical, nonlinear interaction of colliding gravitational waves, as described by classical general relativity. It is focused mainly on two fundamental questions: First, what is the general structure of the singularities and Killing-Cauchy horizons produced in the collisions of exactly plane-symmetric gravitational waves? Second, under what conditions will the collisions of almost-plane gravitational waves (waves with large but finite transverse sizes) produce singularities?

In the work on the collisions of exactly-plane waves, it is shown that Killing horizons in any plane-symmetric spacetime are unstable against small plane-symmetric perturbations. It is thus concluded that the Killing-Cauchy horizons produced by the collisions of some exactly plane gravitational waves are nongeneric, and that generic initial data for the colliding plane waves always produce "pure" spacetime singularities without such horizons. This conclusion is later proved rigorously (using the full nonlinear theory rather than perturbation theory), in connection with an analysis of the asymptotic singularity structure of a general colliding plane-wave spacetime. This analysis also proves that asymptotically the singularities created by colliding plane waves are of inhomogeneous-Kasner type; the asymptotic Kasner axes and exponents of these singularities in general depend on the spatial coordinate that runs tangentially to the singularity in the non-plane-symmetric direction.

In the work on collisions of almost-plane gravitational waves, first some general properties of single almost-plane gravitational-wave spacetimes are explored. It is shown that, by contrast with an exact plane wave, an almost-plane gravitational wave cannot have a propagation direction that is Killing; i.e., it must diffract and disperse as it propagates. It is also shown that an almost-plane wave cannot be precisely sandwiched between two null wavefronts; i.e., it must leave behind tails in the spacetime region through which it passes. Next, the occurrence of spacetime singularities in the collisions of almost-plane waves is investigated. It is proved that if two colliding, almost-plane gravitational waves are initially exactly plane-symmetric across a central region of sufficiently large but finite transverse dimensions, then their collision produces a spacetime singularity with the same local structure as in the exact-plane-wave collision. Finally, it is shown that a singularity still forms when the central regions are only approximately plane-symmetric initially. Stated more precisely, it is proved that if the colliding almost-plane waves are initially sufficiently close to being exactly plane-symmetric across a bounded central region of sufficiently large transverse dimensions, then their collision necessarily produces spacetime singularities. In this case, nothing is now known about the local and global structures of the singularities.

Luminescence properties of electron-hole-droplets in pure and doped germanium

This work contains 4 topics dealing with the properties of the luminescence from Ge.

The temperature, pump-power and time dependences of the photoluminescence spectra of Li-, As-, Ga-, and Sb-doped Ge crystals were studied. For impurity concentrations less than about 10¹⁵cm^-3, emissions due to electron-hole droplets can clearly be identified. For impurity concentrations on the order of 10¹⁶cm^-3, the broad lines in the spectra, which have previously been attributed to the emission from the electron-hole-droplet, were found to possess pump-power and time dependent line shape. These properties show that these broad lines cannot be due to emission of electron-hole-droplets alone. We interpret these lines to be due to a combination of emissions from (1) electron-hole- droplets, (2) broadened multiexciton complexes, (3) broadened bound-exciton, and (4) plasma of electrons and holes. The properties of the electron-hole-droplet in As-doped Ge were shown to agree with theoretical predictions.

The time dependences of the luminescence intensities of the electron-hole-droplet in pure and doped Ge were investigated at 2 and 4.2°K. The decay of the electron-hole-droplet in pure Ge at 4.2°K was found to be pump-power dependent and too slow to be explained by the widely accepted model due to Pokrovskii and Hensel et al. Detailed study of the decay of the electron-hole-droplets in doped Ge were carried out for the first time, and we find no evidence of evaporation of excitons by electron-hole-droplets at 4.2°K. This doped Ge result is unexplained by the model of Pokrovskii and Hensel et al. It is shown that a model based on a cloud of electron-hole-droplets generated in the crystal and incorporating (1) exciton flow among electron-hole-droplets in the cloud and (2) exciton diffusion away from the cloud is capable of explaining the observed results.

It is shown that impurities, introduced during device fabrication, can lead to the previously reported differences of the spectra of laser-excited high-purity Ge and electrically excited Ge double injection devices. By properly choosing the device geometry so as to minimize this Li contamination, it is shown that the Li concentration in double injection devices may be reduced to less than about 10¹⁵cm^-3 and electrically excited luminescence spectra similar to the photoluminescence spectra of pure Ge may be produced. This proves conclusively that electron-hole-droplets may be created in double injection devices by electrical excitation.

The ratio of the LA- to TO-phonon-assisted luminescence intensities of the electron-hole-droplet is demonstrated to be equal to the high temperature limit of the same ratio of the exciton for Ge. This result gives one confidence to determine similar ratios for the electron-hole-droplet from the corresponding exciton ratio in semiconductors in which the ratio for the electron-hole-droplet cannot be determined (e.g., Si and GaP). Knowing the value of this ratio for the electron-hole-droplet, one can obtain accurate values of many parameters of the electron-hole-droplet in these semiconductors spectroscopically.

Complexity of rupture propagation in large earthquakes in relation to tectonic environment

Complexity in the earthquake rupture process can result from many factors. This study investigates the origin of such complexity by examining several recent, large earthquakes in detail. In each case the local tectonic environment plays an important role in understanding the source of the complexity.

Several large shallow earthquakes (M_s > 7.0) along the Middle American Trench have similarities and differences between them that may lead to a better understanding of fracture and subduction processes. They are predominantly thrust events consistent with the known subduction of the Cocos plate beneath N. America. Two events occurring along this subduction zone close to triple junctions show considerable complexity. This may be attributable to a more heterogeneous stress environment in these regions and as such has implications for other subduction zone boundaries.

An event which looks complex but is actually rather simple is the 1978 Bermuda earthquake (M_s ~ 6). It is located predominantly in the mantle. Its mechanism is one of pure thrust faulting with a strike N 20°W and dip 42°NE. Its apparent complexity is caused by local crustal structure. This is an important event in terms of understanding and estimating seismic hazard on the eastern seaboard of N. America.

A study of several large strike-slip continental earthquakes identifies characteristics which are common to them and may be useful in determining what to expect from the next great earthquake on the San Andreas fault. The events are the 1976 Guatemala earthquake on the Motagua fault and two events on the Anatolian fault in Turkey (the 1967, Mudurnu Valley and 1976, E. Turkey events). An attempt to model the complex P-waveforms of these events results in good synthetic fits for the Guatemala and Mudurnu Valley events. However, the E. Turkey event proves to be too complex as it may have associated thrust or normal faulting. Several individual sources occurring at intervals of between 5 and 20 seconds characterize the Guatemala and Mudurnu Valley events. The maximum size of an individual source appears to be bounded at about 5 x 10²⁶ dyne-cm. A detailed source study including directivity is performed on the Guatemala event. The source time history of the Mudurnu Valley event illustrates its significance in modeling strong ground motion in the near field. The complex source time series of the 1967 event produces amplitudes greater by a factor of 2.5 than a uniform model scaled to the same size for a station 20 km from the fault.

Three large and important earthquakes demonstrate an important type of complexity --- multiple-fault complexity. The first, the 1976 Philippine earthquake, an oblique thrust event, represents the first seismological evidence for a northeast dipping subduction zone beneath the island of Mindanao. A large event, following the mainshock by 12 hours, occurred outside the aftershock area and apparently resulted from motion on a subsidiary fault since the event had a strike-slip mechanism.

An aftershock of the great 1960 Chilean earthquake on June 6, 1960, proved to be an interesting discovery. It appears to be a large strike-slip event at the main rupture's southern boundary. It most likely occurred on the landward extension of the Chile Rise transform fault, in the subducting plate. The results for this event suggest that a small event triggered a series of slow events; the duration of the whole sequence being longer than 1 hour. This is indeed a "slow earthquake".

Perhaps one of the most complex of events is the recent Tangshan, China event. It began as a large strike-slip event. Within several seconds of the mainshock it may have triggered thrust faulting to the south of the epicenter. There is no doubt, however, that it triggered a large oblique normal event to the northeast, 15 hours after the mainshock. This event certainly contributed to the great loss of life-sustained as a result of the Tangshan earthquake sequence.

What has been learned from these studies has been applied to predict what one might expect from the next great earthquake on the San Andreas. The expectation from this study is that such an event would be a large complex event, not unlike, but perhaps larger than, the Guatemala or Mudurnu Valley events. That is to say, it will most likely consist of a series of individual events in sequence. It is also quite possible that the event could trigger associated faulting on neighboring fault systems such as those occurring in the Transverse Ranges. This has important bearing on the earthquake hazard estimation for the region.

Quantum Mechanics Studies of Fuel Cell Catalysts and Proton Conducting Ceramics with Validation by Experiment

We carried out quantum mechanics (QM) studies aimed at improving the performance of hydrogen fuel cells. This led to predictions of improved materials, some of which were subsequently validated with experiments by our collaborators.

In part I, the challenge was to find a replacement for the Pt cathode that would lead to improved performance for the Oxygen Reduction Reaction (ORR) while remaining stable under operational conditions and decreasing cost. Our design strategy was to find an alloy with composition Pt3M that would lead to surface segregation such that the top layer would be pure Pt, with the second and subsequent layers richer in M. Under operating conditions we expect the surface to have significant O and/or OH chemisorbed on the surface, and hence we searched for M that would remain segregated under these conditions. Using QM we examined surface segregation for 28 Pt₃M alloys, where M is a transition metal. We found that only Pt₃Os and Pt₃Ir showed significant surface segregation when O and OH are chemisorbed on the catalyst surfaces. This result indicates that Pt₃Os and Pt3Ir favor formation of a Pt-skin surface layer structure that would resist the acidic electrolyte corrosion during fuel cell operation environments. We chose to focus on Os because the phase diagram for Pt-Ir indicated that Pt-Ir could not form a homogeneous alloy at lower temperature. To determine the performance for ORR, we used QM to examine all intermediates, reaction pathways, and reaction barriers involved in the processes for which protons from the anode reactions react with O₂ to form H₂O. These QM calculations used our Poisson-Boltzmann implicit solvation model include the effects of the solvent (water with dielectric constant 78 with pH 7 at 298K). We found that the rate determination step (RDS) was the O_ad hydration reaction (O_ad + H₂O_ad -> OH_ad + OH_ad) in both cases, but that the barrier for pure Pt of 0.50 eV is reduced to 0.48 eV for Pt₃Os, which at 80 degrees C would increase the rate by 218%. We collaborated with the Pu-Wei Wu’s group to carry out experiments, where we found that the dealloying process-treated Pt2Os catalyst showed two-fold higher activity at 25 degrees C than pure Pt and that the alloy had 272% improved stability, validating our theoretical predictions.

We also carried out similar QM studies followed by experimental validation for the Os/Pt core-shell catalyst fabricated by the underpotential deposition (UPD) method. The QM results indicated that the RDS for ORR is a compromise between the OOH formation step (0.37 eV for Pt, 0.23 eV for Pt_2ML/Os core-shell) and H₂O formation steps (0.32 eV for Pt, 0.22 eV for Pt_2ML/Os core-shell). We found that Pt_2ML/Os has the highest activity (compared to pure Pt and to the Pt₃Os alloy) because the 0.37 eV barrier decreases to 0.23 eV. To understand what aspects of the core shell structure lead to this improved performance, we considered the effect on ORR of compressing the alloy slab to the dimensions of pure Pt. However this had little effect, with the same RDS barrier 0.37 eV. This shows that the ligand effect (the electronic structure modification resulting from the Os substrate) plays a more important role than the strain effect, and is responsible for the improved activity of the core- shell catalyst. Experimental materials characterization proves the core-shell feature of our catalyst. The electrochemical experiment for Pt_2ML/Os/C showed 3.5 to 5 times better ORR activity at 0.9V (vs. NHE) in 0.1M HClO₄ solution at 25 degrees C as compared to those of commercially available Pt/C. The excellent correlation between experimental half potential and the OH binding energies and RDS barriers validate the feasibility of predicting catalyst activity using QM calculation and a simple Langmuir–Hinshelwood model.

In part II, we used QM calculations to study methane stream reforming on a Ni-alloy catalyst surfaces for solid oxide fuel cell (SOFC) application. SOFC has wide fuel adaptability but the coking and sulfur poisoning will reduce its stability. Experimental results suggested that the Ni4Fe alloy improves both its activity and stability compared to pure Ni. To understand the atomistic origin of this, we carried out QM calculations on surface segregation and found that the most stable configuration for Ni₄Fe has a Fe atom distribution of (0%, 50%, 25%, 25%, 0%) starting at the bottom layer. We calculated that the binding of C atoms on the Ni4Fe surface is 142.9 Kcal/mol, which is about 10 Kcal/mol weaker compared to the pure Ni surface. This weaker C binding energy is expected to make coke formation less favorable, explaining why Ni₄Fe has better coking resistance. This result confirms the experimental observation. The reaction energy barriers for CHx decomposition and C binding on various alloy surface, Ni₄X (X=Fe, Co, Mn, and Mo), showed Ni₄Fe, Ni₄Co, and Fe₄Mn all have better coking resistance than pure Ni, but that only Ni₄Fe and Fe₄Mn have (slightly) improved activity compared to pure Ni.

In part III, we used QM to examine the proton transport in doped perovskite-ceramics. Here we used a 2x2x2 supercell of perovskite with composition Ba₈X₇M₁(OH)₁O₂₃ where X=Ce or Zr and M=Y, Gd, or Dy. Thus in each case a 4⁺ X is replace by a 3⁺ M plus a proton on one O. Here we predicted the barriers for proton diffusion allowing both includes intra-octahedron and inter-octahedra proton transfer. Without any restriction, we only observed the inter-octahedra proton transfer with similar energy barrier as previous computational work but 0.2 eV higher than experimental result for Y doped zirconate. For one restriction in our calculations is that the O_donor-O_acceptor atoms were kept at fixed distances, we found that the barrier difference between cerates/zirconates with various dopants are only 0.02~0.03 eV. To fully address performance one would need to examine proton transfer at grain boundaries, which will require larger scale ReaxFF reactive dynamics for systems with millions of atoms. The QM calculations used here will be used to train the ReaxFF force field.

I. Electronic states of heavily-doped molecular crystals--naphthalene. I. Theoretical. II. Experimental. II. Lowest singlet and triplet excited states of pyrazine

PART I

The energy spectrum of heavily-doped molecular crystals was treated in the Green’s function formulation. The mixed crystal Green’s function was obtained by averaging over all possible impurity distributions. The resulting Green’s function, which takes the form of an infinite perturbation expansion, was further approximated by a closed form suitable for numerical calculations. The density-of-states functions and optical spectra for binary mixtures of normal naphthalene and deuterated naphthalene were calculated using the pure crystal density-of-state functions. The results showed that when the trap depth is large, two separate energy bands persist, but when the trap depth is small only a single band exists. Furthermore, in the former case it was found that the intensities of the outer Davydov bands are enhanced whereas the inner bands are weakened. Comparisons with previous theoretical calculations and experimental results are also made.

PART II

The energy states and optical spectra of heavily-doped mixed crystals are investigated. Studies are made for the following binary systems: (1) naphthalene-h₈ and d₈, (2) naphthalene--h₈ and αd₄, and (3) naphthalene--h₈ and βd₁, corresponding to strong, medium and weak perturbations. In addition to ordinary absorption spectra at 4˚K, band-to-band transitions at both 4˚K and 77˚K are also analyzed with emphasis on their relations to cooperative excitation and overall density-of-states functions for mixed crystals. It is found that the theoretical calculations presented in a previous paper agree generally with experiments except for cluster states observed in system (1) at lower guest concentrations. These features are discussed semi-quantitatively. As to the intermolecular interaction parameters, it is found that experimental results compare favorably with calculations based on experimental density-of-states functions but not with those based on octopole interactions or charge-transfer interactions. Previous experimental results of Sheka and the theoretical model of Broude and Rashba are also compared with present investigations.

PART III

The phosphorescence, fluorescence and absorption spectra of pyrazine-h₄ and d₄ have been obtained at 4˚K in a benzene matrix. For comparison, those of the isotopically mixed crystal pyrazine-h₄ in d₄ were also taken. All these spectra show extremely sharp and well-resolved lines and reveal detailed vibronic structure.

The analysis of the weak fluorescence spectrum resolves the long-disputed question of whether one or two transitions are involved in the near-ultraviolet absorption of pyrazine. The “mirror-image relationship” between absorption and emission shows that the lowest singlet state is an allowed transition, properly designated as ¹B_3u ← ¹A_1g. The forbidden component ¹B_2g, predicted by both “exciton” and MO theories to be below the allowed component, must lie higher. Its exact location still remains uncertain.

The phosphorescence spectrum when compared with the excitation phosphorescence spectra, indicates that the lowest triplet state is also symmetry allowed, showing a strong 0-0 band and a “mirror-image relationship” between absorption and emission. In accordance with previous work, the triplet state is designated as ³B_3u.

The vibronic structure of the phosphorescence spectrum is very complicated. Previous work on the analysis of this spectrum all concluded that a long progression of v_6a exists. Under the high resolution attainable in our work, the supposed v_6a progression proves to have a composite triplet structure, starting from the second member of the progression. Not only is the v_9a hydrogen-bending mode present as shown by the appearance of the C-D bending mode in the d₄ spectrum, but a band of 1207 cm^-1 in the pyrazine in benzene system and 1231 cm^-1 in the mixed crystal system is also observed. This band is assigned as 2v_6b and of a_1g symmetry. Its anonymously strong intensity in the phosphorescence spectrum is interpreted as due to the Fermi resonance with the 2v_6a and v_9a band.

To help resolve the present controversy over the crystal phosphorescence spectrum of pyrazine, detailed vibrational analyses of the emission spectra were made. The fluorescence spectrum has essentially the same vibronic structure as the phosphorescence spectrum.

Exciplexes in fluorescence quenching of aromatic hydrocarbons by tertiary aliphatic amines

Strong quenching of the fluorescence of aromatic hydrocarbons by tertiary aliphatic amines has been observed in solution at room temperature. Accompanying the fluorescence quenching of aromatic hydrocarbons, an anomalous emission is observed. This new emission is very broad, structureless and red-shifted from the original hydrocarbon fluorescence.

Kinetic studies indicate that this anomalous emission is due to an exciplex formed by an aromatic hydrocarbon molecule in its lowest excited singlet state with an amine molecule. The fluorescence quenching of the aromatic hydrocarbons is due to the depopulation of excited hydrocarbon molecules by the formation of exciplexes, with subsequent de-excitation of exciplexes by either radiative or non-radiative processes.

Analysis of rate constants shows the electron-transfer nature of the exciplex. Through the study of the effects on the frequencies of exciplex emissions of substituents on the hydrocarbons, it is concluded that partial electron transfer from the amine molecule to the aromatic hydrocarbon molecule in its lowest excited singlet state occurs in the formation of exciplex. Solvent effects on the exciplex emission frequencies further demonstrate the polar nature of the exciplex.

A model based on this electron-transfer nature of exciplex is proposed and proves satisfactory in interpreting the exciplex emission phenomenon in the fluorescence quenching of aromatic hydrocarbons by tertiary aliphatic amines.

Kinematics and Local Motion Planning for Quasi-static Whole-body Mobile Manipulation

This thesis studies mobile robotic manipulators, where one or more robot manipulator arms are integrated with a mobile robotic base. The base could be a wheeled or tracked vehicle, or it might be a multi-limbed locomotor. As robots are increasingly deployed in complex and unstructured environments, the need for mobile manipulation increases. Mobile robotic assistants have the potential to revolutionize human lives in a large variety of settings including home, industrial and outdoor environments.

Mobile Manipulation is the use or study of such mobile robots as they interact with physical objects in their environment. As compared to fixed base manipulators, mobile manipulators can take advantage of the base mechanism’s added degrees of freedom in the task planning and execution process. But their use also poses new problems in the analysis and control of base system stability, and the planning of coordinated base and arm motions. For mobile manipulators to be successfully and efficiently used, a thorough understanding of their kinematics, stability, and capabilities is required. Moreover, because mobile manipulators typically possess a large number of actuators, new and efficient methods to coordinate their large numbers of degrees of freedom are needed to make them practically deployable. This thesis develops new kinematic and stability analyses of mobile manipulation, and new algorithms to efficiently plan their motions.

I first develop detailed and novel descriptions of the kinematics governing the operation of multi- limbed legged robots working in the presence of gravity, and whose limbs may also be simultaneously used for manipulation. The fundamental stance constraint that arises from simple assumptions about friction and the ground contact and feasible motions is derived. Thereafter, a local relationship between joint motions and motions of the robot abdomen and reaching limbs is developed. Baseeon these relationships, one can define and analyze local kinematic qualities including limberness, wrench resistance and local dexterity. While previous researchers have noted the similarity between multi- fingered grasping and quasi-static manipulation, this thesis makes explicit connections between these two problems.

The kinematic expressions form the basis for a local motion planning problem that that determines the joint motions to achieve several simultaneous objectives while maintaining stance stability in the presence of gravity. This problem is translated into a convex quadratic program entitled the balanced priority solution, whose existence and uniqueness properties are developed. This problem is related in spirit to the classical redundancy resoxlution and task-priority approaches. With some simple modifications, this local planning and optimization problem can be extended to handle a large variety of goals and constraints that arise in mobile-manipulation. This local planning problem applies readily to other mobile bases including wheeled and articulated bases. This thesis describes the use of the local planning techniques to generate global plans, as well as for use within a feedback loop. The work in this thesis is motivated in part by many practical tasks involving the Surrogate and RoboSimian robots at NASA/JPL, and a large number of examples involving the two robots, both real and simulated, are provided.

Finally, this thesis provides an analysis of simultaneous force and motion control for multi- limbed legged robots. Starting with a classical linear stiffness relationship, an analysis of this problem for multiple point contacts is described. The local velocity planning problem is extended to include generation of forces, as well as to maintain stability using force-feedback. This thesis also provides a concise, novel definition of static stability, and proves some conditions under which it is satisfied.