Legged animals can traverse significantly more of the Earth's land mass than man-made wheeled and tracked vehicles~\cite{Anonymous67}. Their impressive mobility is largely due to multiple dexterous legs and the robust algorithms that coordinate and control them. A legged animal such as a squirrel can exhibit multiple locomotion modes such as walking, running and jumping and also multiple gaits or leg phase timings within each mode. A robot that could mimic this level of robust locomotion would be highly useful for planetary exploration, military reconnaissance, and time-critical search and rescue in cluttered or collapsed buildings. A number of biological studies on animal walking have provided information concerning the underlying control system. Studies in insect walking have revealed a distributed local-leg control that generates quasi-rhythmic movement by sensing the environment using local feedback loops. Ground reaction forces produced by an insect during walking and running, along with joint angles, have been recorded by various studies. The primary goal of this research is to develop a distributed local-leg control algorithm to generate walking behaviors on uneven terrain using local force feedback. The intended purpose of this research is to pursue a biologically-inspired control algorithm that can be used as a scientific tool to study walking and provide a better understanding of local-leg control. Control of a multi-jointed robot system has traditionally been done using position control. But as the number of degrees of freedom in systems started increasing, position control of each actuator using a centralized controller became cumbersome. The control of a walking robot is a more complex problem as stability also becomes an issue. Much research has been concentrated towards creating rhythmic or quasi-rhythmic movements which can be used for walking in predictable environments. However, walking on uneven terrain requires one to incorporate different issues, such as but not limited to, the mechanical properties of the leg, coordination between legs, as well as higher level decisions based on external information and internal body states. Much of the current research in legged robots is directed towards sensing the terrain so that the walking sequence of the robot can be pre-determined. This requires a large array of sensors, off-line as well as in real-time, to accurately sense the terrain increasing the cost and complexity of the robot. Even if the body path and footholds are planned, a real-time module is required to handle small perturbations and slips adding to the complexity. Like animal walking, using force feedback can greatly improve walking behavior in a robot. However, due to the unreliable nature of force sensors, no other control algorithm for walking has been able to use continuous force feedback for walking on uneven terrain. The distributed local-leg controller developed in this research, called Force Threshold-based Position (FTP) controller, is able to generate walking behaviors robust to terrain elevations without using visual sensors, a priori terrain information, inertial sensing, or inter-leg communication. The controller uses local force feedback to control each leg and is, therefore, very responsive to terrain changes when compared to a centralized controller arbitrating all of the joint positions in a high degree of freedom system. The controller is implemented with gait phasing dictated by a static timer. By integrating force feedback with position control, the FTP controller combines the advantages of position control with robustness to uneven terrain. This work provides the minimum interaction needed between joints or legs for the robot to navigate a rugged terrain. This work provides insight into the role of active elements in the local leg feedback controller that allow for responsiveness over uneven terrain, and can be used to reveal the underlying structure insects use to generate the forces needed for different behaviors and gaits on flat and uneven terrain. The FTP controller has been realized and studied on a full 3D simulation model and on an experimental hexapod system. Multiple gaits along with turning and side stepping have been implemented and tested on the system. The FTP controller is built as an low-level reflexive system which would be guided by a high level controller overseeing its operation, intermittently passing directional commands and control information. The objective is to make the walking behavior a background process such that the robot can focus on its mission objectives. The FTP controller also has potential for expansion to bipeds, quadrupeds and other biologically-inspired forms.

<p> In their daily lives, stroke survivors must often choose between attempting upper-extremity activities using their impaired limb, or compensating with their less impaired limb. Choosing their impaired limb can be difficult and discouraging, but might elicit beneficial neuroplasticity that further reduces motor impairments, a phenomenon referred to as &ldquo;the virtuous cycle&rdquo;. In contrast, compensation is often quicker, easier, and more effective, but can reinforce maladaptive changes that limit motor recovery, a phenomenon referred to as &ldquo;learned non-use&rdquo;. This dissertation evaluated the role of robotic assistance in, and designed a wearable sensing system for, promoting the virtuous cycle. </p><p> In the first half of the dissertation, we use the FINGER robot to test the hypothesis that robotic assistance during clinical movement training triggers the virtual cycle. FINGER consists of two singly-actuated mechanisms that assist individuated movement of the index and middle fingers. 30 chronic stroke participants trained in FINGER using a GuitarHero-like game for nine sessions. Half were guided by an adaptive impedance controller towards a success rate of 85%, while the other half were guided towards 50%. Increasing assistance to enable successful practice decreased effort, but primarily for less-impaired participants. Overall, however, high success practice was as effective (or more) as low success practice and even more effective for highly impaired individuals. Participants who received high assistance training were more motivated and reported using their impaired hand more at home. These results support the hypothesis that high assistance clinical movement training motivates impaired hand use, leading to greater use of the hand in daily life, resulting in a self-training effect that reduces motor impairment. </p><p> The second half of the dissertation describes the development of the manumeter - a non-obtrusive wearable device for monitoring and incentivizing impaired hand use. Contrasted against wrist accelerometry (the most comparable technology), the manumeter uses a magnetic ring and a wristband with mangetometers to detect wrist and finger movement rather than gross arm movement. We describe 1) the inference of wrist and finger movement from differential magnetometer readings using a radial basis function network, 2) initial testing in which distance traveled estimates were within 94.7%&plusmn;19.3 of their goniometricly measured values, 3) experiments with non-impaired participants in which the manumeter detected some functional activities better than wrist accelerometry, and 4) improvements to the hardware and data processing that allow both subject-independent tracking of the position of the finger relative to the wrist (RMS errors &lt; 1cm) and highly reliable detection of whether the hand is open or closed. Its performance and non-obtrusive design make the manumeter well suited for measuring and reinforcing impaired hand use in daily life after stroke. </p><p> The contributions of this dissertation are experimental confirmation that high assistance movement training promotes the virtuous cycle, and development of a wearable sensor for monitoring hand movement in daily life. Training with robotic assistance and hand use feedback may ultimately help individuals with stroke recover to their full potential.</p>

No description available.

As robotic systems become larger and more complex, it is increasingly important to compose them from reusable software components that can be easily deployed in novel systems. To date, efforts in this area have focused on device abstractions and messaging frameworks that promote the rapid and interoperable development of various perception, mapping and planning algorithms. These frameworks typically promote reusability through the definition of message interfaces that are sufficiently generic to cover all supported robot configurations. However, migrating beyond these supported configurations can be highly problematic, as generic data interfaces cannot fully capture the variability of robotic systems. Specifically, there will always be peculiarities of individual robots that must be explicitly coupled to the algorithms that govern their actions, and no single message or device abstraction can express all possible information that a robot might provide. The critical insight underlying this work is that while the information that contributes to a given algorithm may change from one robot to the next, the overall structure of the algorithm will remain largely undisturbed. The difference is made in comparatively small details, such as varying individual weights or thresholds that influence the results of, but do not otherwise interfere with, the algorithm's "main" calculations. This work proposes that exposing a few such points of variation in a given robotic algorithm will allow the modular treatment of a wide array of platform-specific capabilities. A corresponding design methodology is proposed for separating these platform-specific "supplemental effects" from a reusable, platform-independent "core algorithm". This methodology is evaluated through case studies of two distinct software systems, the first drawn from the realm of autonomous urban driving, and the second from the domain of planetary exploration. The central contributions of this work are: A nomenclature and corresponding guidelines for discriminating between platform-independent "primary" data and platform-specific "supplemental" data; Quantified costs and benefits for two technical solutions to isolating the corresponding core algorithms from their supplemental effects; A classification of typical segments of advanced robotic algorithms that can be affected by platform specific data; A set of principles for structuring such algorithms to simplify the accommodation of future supplemental effects.

Recognizing and reasoning about the objects found in an image is one of the key problems in computer vision. This thesis is based on the idea that in order to understand a novel object, it is often not enough to recognize the object category it belongs to (i.e., answering “What is this?”). We argue that a more meaningful interpretation can be obtained by linking the input object with a similar representation in memory (i.e., asking “What is this like?”). In this thesis, we present a memory-based system for recognizing and interpreting objects in images by establishing visual associations between an input image and a large database of object exemplars. These visual associations can then be used to predict properties of the novel object which cannot be deduced solely from category membership (e.g., which way is it facing? what is its segmentation? is there a person sitting on it?). Part I of this thesis is dedicated to exemplar representations and algorithms for creating visual associations. We propose Local Distance Functions and Exemplar-SVMs, which are trained separately for each exemplar and allow an instance-specific notion of visual similarity. We show that an ensemble of Exemplar-SVMs performs competitively to state-of-the-art on the PASCAL VOC object detection task. In Part II, we focus on the advantages of using exemplars over a purely category-based approach. Because Exemplar-SVMs show good alignment between detection windows and their associated exemplars, we show that it is possible to transfer any available exemplar meta-data (segmentation, geometric structure, 3D model, etc.) directly onto the detections, which can then be used as part of overall scene understanding. Finally, we construct a Visual Memex, a vast graph over exemplars encoding both visual as well as spatial relationships, and apply it to an object prediction task. Our results show that exemplars provide a better notion of object context than category-based approaches.

Every planning problem in robotics involves constraints. Whether the robot must avoid collision or joint limits, there are always states that are not permissible. Some constraints are straightforward to satisfy while others can be so stringent that feasible states are very difficult to find. What makes planning with constraints challenging is that, for many constraints, it is impossible or impractical to provide the planning algorithm with the allowed states explicitly; it must discover these states as it plans. The goal of this thesis is to develop a framework for representing and exploring feasible states in the context of manipulation planning. Planning for manipulation gives rise to a rich variety of tasks that include constraints on collision- avoidance, torque, balance, closed-chain kinematics, and end-effector pose. While many researchers have developed representations and strategies to plan with a specific constraint, the goal of this the- sis is to develop a broad representation of constraints on a robot’s configuration and identify general strategies to manage these constraints during the planning process. Some of the most important con- straints in manipulation planning are functions of the pose of the manipulator’s end-effector, so we devote a large part of this thesis to end-effector placement for grasping and transport tasks. We present an efficient approach to generating paths that uses Task Space Regions (TSRs) to specify manipulation tasks which involve end-effector pose goals and/or path constraints. We show how to use TSRs for path planning using the Constrained BiDirectional RRT (CBiRRT2) algorithm and describe several extensions of the TSR representation. Among them are methods to plan with object pose uncertainty, find optimal base placements, and handle more complex pose constraints by chaining TSRs together. We also explore the problem of automatically generating end-effector pose constraints for grasping tasks and present two grasp synthesis algorithms that can generate lists of grasps in extremely clut- tered environments. We then describe how to convert these lists of grasps to TSRs so they can be used with CBiRRT2. We have applied our framework to a wide range of problems for several robots, both in simulation and in the real world. These problems include grasping in cluttered environments, lifting heavy objects, two-armed manipulation, and opening doors, to name a few. These example problems demonstrate our framework’s practicality, and our proof of probabilistic completeness gives our approach a theoretical foundation. In addition to the above framework, we have also developed the Constellation algorithm for finding configurations that satisfy multiple stringent constraints where other constraint-satisfaction strategies fail. We also present the GradienT-RRT algorithm for planning with soft constraints, which outper- forms the state-of-the-art approach to high-dimensional path planning with costs.

In numerous real world applications, from sensor networks to computer vision to natural text processing, one needs to reason about the system in question in the face of uncertainty. A key problem in all those settings is to compute the probability distribution over the variables of interest (the query) given the observed values of other random variables (the evidence). Probabilistic graphical models (PGMs) have become the approach of choice for representing and reasoning with high-dimensional probability distributions. However, for most models capable of accurately representing real-life distributions, inference is fundamentally intractable. As a result, optimally balancing the expressive power and inference complexity of the models, as well as designing better approximate inference algorithms, remain important open problems with potential to significantly improve the quality of answers to probabilistic queries. This thesis contributes algorithms for learning and approximate inference in probabilistic graphical models that improve on the state of the art by emphasizing the computational aspects of inference over the representational properties of the models. Our contributions fall into two categories: learning accurate models where exact inference is tractable and speeding up approximate inference by focusing computation on the query variables and only spending as much effort on the remaining parts of the model as needed to answer the query accurately. First, for a case when the set of evidence variables is not known in advance and a single model is needed that can be used to answer any query well, we propose a polynomial time algorithm for learning the structure of tractable graphical models with quality guarantees, including PAC learnability and graceful degradation guarantees. Ours is the first efficient algorithm to provide this type of guarantees. A key theoretical insight of our approach is a tractable upper bound on the mutual information of arbitrarily large sets of random variables that yields exponential speedups over the exact computation. Second, for a setting where the set of evidence variables is known in advance, we propose an approach for learning tractable models that tailors the structure of the model for the particular value of evidence that become known at test time. By avoiding a commitment to a single tractable structure during learning, we are able to expand the representation power of the model without sacrificing efficient exact inference and parameter learning. We provide a general framework that allows one to leverage existing structure learning algorithms for discovering high-quality evidence-specific structures. Empirically, we demonstrate state of the art accuracy on real-life datasets and an order of magnitude speedup. Finally, for applications where the intractable model structure is a given and approximate inference is needed, we propose a principled way to speed up convergence of belief propagation by focusing the computation on the query variables and away from the variables that are of no direct interest to the user. We demonstrate significant speedups over the state of the art on large-scale relational models. Unlike existing approaches, ours does not involve model simplification, and thus has an advantage of converging to the fixed point of the full model. More generally, we argue that the common approach of concentrating on the structure of representation provided by PGMs, and only structuring the computation as representation allows, is suboptimal because of the fundamental computational problems. It is the computation that eventually yields answers to the queries, so directly focusing on structure of computation is a natural direction for improving the quality of the answers. The results of this thesis are a step towards adapting the structure of computation as a foundation of graphical models.

Many problems considered in optimization and artificial intelligence research are static: information about the problem is known a priori, and little to no uncertainty about this information is presumed to exist. Most real problems, however, are dynamic: information about the problem is released over time, uncertain events may occur, or the requirements of the problem may change as time passes. One technique for improving optimization and learning in dynamic environments is by using information from the past. By using solutions from previous environments, it is often easier to find promising solutions in a new environment. A common way to maintain and exploit information from the past is the use of memory, where solutions are stored periodically and can be retrieved and refined when the environment changes. Memory can help search respond quickly and efficiently to changes in a dynamic problem. Despite their strengths, standard memories have many weaknesses which limit their effectiveness. This thesis explores ways to improve memory for optimization and learning in dynamic environments. The techniques presented in this thesis improve memories by incorporating probabilistic models of previous solutions into memory, storing many previous solutions in memory while keeping overhead low, building long-term models of the dynamic search space over time, allowing easy refinement of memory entries, and mapping previous solutions to the current environment for problems where solutions may become obsolete over time. To address the weaknesses and limitations of standard memory, two novel classes of memory are introduced: density-estimate memory and classifier-based memory. Density-estimate memory builds and maintains probabilistic models within memory to create density estimations of promising areas of the search space over time. Density-estimate memory allows many solutions to be stored in memory, builds long-term models of the dynamic search space, and allows memory entries to be easily refined while keeping overhead low. Density-estimate memory is applied to three dynamic problems: factory coordination, the Moving Peaks benchmark problem, and adaptive traffic signal control. For all three problems, density-estimate memory improves performance over a baseline learning or optimization algorithm as well as state-of-the-art algorithms. Classifier-based memory allows dynamic problems with shifting feasible regions to capture solutions in memory and then map these memory entries to feasible solutions in the future. By storing abstractions of solutions in the memory, information about previous solutions can be used to create solutions in a new environment, even when the old solutions are now completely obsolete or infeasible. Classifier-based memory is applied to a dynamic job shop scheduling problem with sequence-dependent setup times and machine breakdowns and repairs. Classifier-based memory improves the quality of schedules and reduces the amount of search necessary to find good schedules. The techniques presented in this this thesis improve the ability of memories to guide search quickly and efficiently to good solutions as the environment changes.

Water drops are present throughout our daily lives. Microscopic droplets create fog and mist, and large drops fall as rain. Because of their shape and refractive properties, water drops exhibit a wide variety of visual effects. If not directly illuminated by a light source, they are difficult to see. But if they are directly illuminated, they can become the brightest objects in the environment. This thesis has two main components. First, we will show how to create two-and three-dimensional displays using water drops and a projector. Water drops act as tiny spherical lenses, refracting light into a wide angle. To a person viewing an illuminated drop, it will appear that the drop is the same color as the incident light ray. Using a valve assembly, we will fill a volume with non-occluding water drops. At any instant in time, no ray from the projector will intersect with two drops. Using a camera, we will detect the drops locations, then illuminate them with the projector. The final result is a programmable, dynamic, and three-dimensional display. Second, we will show how to reduce the effect of water drops in videos via spatio-temporal frequency analysis, and in real life, by using a projector to illuminate everything except the drops. To remove rain (and snow) from videos, we will use a streak model in frequency space to find the frequencies corresponding to rain and snow in the video. These frequencies can then be suppressed to reduce the effect of rain and snow. We will also suppress the visual effect of water drops by selectively “missing” them by not illuminating them with a projector. In light rain, this can be performed by tracking individual drops. This kind of drop-avoiding light source could be used for many nighttime applications, such as car headlights.

Tasks such as street mapping and security surveillance seek a route that traverses a given space to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or searching the space for objects. When these tasks are performed autonomously by robots, the constraints of the environment must be considered in order to generate more feasible paths. Additionally, performing these tasks in the real world presents the challenge of operating in dynamic, changing environments. This thesis addresses the problem of effective graph coverage with environmental constraints and incomplete prior map information. Prior information about the environment is assumed to be given in the form of a graph. We seek a solution that effectively covers the graph while accounting for space restrictions and online changes. For real-time applications, we seek a complete but efficient solution that has fast re-planning capabilities. For this work, we model the set of coverage problems as arc routing problems. Although these routing problems are generally NP-hard, our approach aims for optimal solutions through the use of low-complexity algorithms in a branch-and-bound framework when time permits and approximations when time restrictions apply. Additionally, we account for environmental constraints by embedding those constraints into the graph. In this thesis, we present algorithms that address the multi-dimensional routing problem and its subproblems and evaluate them on both computer-generated and physical road network data.