• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 2078
  • 313
  • 172
  • 160
  • 134
  • 44
  • 41
  • 41
  • 41
  • 41
  • 41
  • 41
  • 40
  • 38
  • 17
  • Tagged with
  • 4074
  • 1149
  • 981
  • 843
  • 640
  • 621
  • 574
  • 523
  • 508
  • 477
  • 476
  • 476
  • 443
  • 424
  • 422
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.

Toward Adaptation and Reuse of Advanced Robotic Algorithms

Baker, Christopher R. 01 April 2011 (has links)
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.

Exemplar-based Representations for Object Detection, Association and Beyond

Malisiewicz, Tomasz 01 August 2011 (has links)
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.

Constrained Manipulation Planning

Berenson, Dmitry 20 June 2011 (has links)
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.

Query-Specific Learning and Inference for Probabilistic Graphical Models

Chechetka, Anton 01 August 2011 (has links)
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.

Improving Memory for Optimizatioin and Learning in Dynamic Environments

Barlow, Gregory John 01 July 2011 (has links)
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.

Light and Water Drops

Barnum, Peter 01 May 2011 (has links)
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.

Graph Planning for Environmental Coverage

Xu, Ling 01 August 2011 (has links)
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.

Parallel Algorithms for Real-time Motion Planning

McNaughton, Matthew 01 July 2011 (has links)
For decades, humans have dreamed of making cars that could drive themselves, so that travel would be less taxing, and the roads safer for everyone. Toward this goal, we have made strides in motion planning algorithms for autonomous cars, using a powerful new computing tool, the parallel graphics processing unit (GPU). We propose a novel five-dimensional search space formulation that includes both spatial and temporal dimensions, and respects the kinematic and dynamic constraints on a typical automobile. With this formulation, the search space grows linearly with the length of the path, compared to the exponential growth of other methods. We also propose a parallel search algorithm, using the GPU to tackle the curse of dimensionality directly and increase the number of plans that can be evaluated by an order of magnitude compared to a CPU implementation. With this larger capacity, we can evaluate a dense sampling of plans combining lateral swerves and accelerations that represent a range of effective responses to more on-road driving scenarios than have previously been addressed in the literature. We contribute a cost function that evaluates many aspects of each candidate plan, ranking them all, and allowing the behavior of the vehicle to be fine-tuned by changing the ranking. We show that the cost function can be changed on-line by a behavioral planning layer to express preferred vehicle behavior without the brittleness induced by top-down planning architectures. Our method is particularly effective at generating robust merging behaviors, which have traditionally required a delicate and failure-prone coordination between multiple planning layers. Finally, we demonstrate our proposed planner in a variety of on-road driving scenarios in both simulation and on an autonomous SUV, and make a detailed comparison with prior work.

Attention-guided Algorithms to Retarget and Augment Animations, Stills, and Videos

Jain, Eakta 13 May 2012 (has links)
Still pictures, animations and videos are used by artists to tell stories visually. Computer graphics algorithms create visual stories too, either automatically, or, by assisting artists. Why is it so hard to create algorithms that perform like a trained visual artist? The reason is that artists think about where a viewer will look at and how their attention will flow across the scene, but algorithms do not have a similarly sophisticated understanding of the viewer. Our key insight is that computer graphics algorithms should be designed to take into account how viewer attention is allocated. We first show that designing optimization terms based on viewers’ attentional priorities allows the algorithm to handle artistic license in the input data, such as geometric inconsistencies in hand-drawn shapes. We then show that measurements of viewer attention enables algorithms to infer high-level information about a scene, for example, the object of storytelling interest in every frame of a video. All the presented algorithms retarget or augment the traditional form of a visual art. Traditional art includes artwork such as printed comics, i.e., pictures that were created before computers became mainstream. It also refers to artwork that can be created in the way it was done before computers, for example, hand-drawn animation and live action films. Connecting traditional art with computational algorithms allows us to leverage the unique strengths on either side. We demonstrate these ideas on three applications: Retargeting and augmenting animations: Two widely practiced forms of animation are two-dimensional (2D) hand-drawn animation and three-dimensional (3D) computer animation. To apply the techniques of the 3D medium to 2D animation, researchers have attempted to compute 3D reconstructions of the shape and motion of the hand-drawn character, which are meant to act as their ‘proxy’ in the 3D environment. We argue that a perfect reconstruction is excessive because it does not leverage the characteristics of viewer attention. We present algorithms to generate a 3D proxy with different levels of detail, such that at each level the error terms account for quantities that will attract viewer attention. These algorithms allow a hand-drawn animation to be retargeted to a 3D skeleton and be augmented with physically simulated secondary effects. Augmenting stills: Moves-on-stills is a technique to engage the viewer while presenting still pictures on television or in movies. This effect is widely used to augment comics to create ‘motion comics’. Though state of the art software, like iMovie, allows a user to specify the parameters of the camera move, it does not solve the problem of how the parameters are chosen. We believe that a good camera move respects the visual route designed by the artist who crafted the still picture; if we record the gaze of viewers looking at composed still pictures, we can reconstruct the artist’s intention. We show, through a perceptual study, that the artist succeeds in directing viewer attention in comic book pictures, and we present an algorithm to predict the parameters of camera moves-on-stills from statistics derived from eyetracking data. Retargeting video: Video retargeting is the process of altering the original video to fit the new display size, while best preserving content and minimizing artifacts. Recent techniques define content as color, edges, faces and other image-based saliency features. We suggest that content is, in fact, what people look at. We introduce a novel operator that extends the classic “pan-and-scan” to introduce cuts in addition to automatic pans based on viewer eyetracking data. We also present a gaze-based evaluation criterion to quantify the performance of our operator.

Toward an Automated System for the Analysis of Cell Behavior: Cellular Event Detection and Cell Tracking in Time-lapse Live Cell Microscopy

Huh, Seungil 01 February 2013 (has links)
Time-lapse live cell imaging has been increasingly employed by biological and biomedical researchers to understand the underlying mechanisms in cell physiology and development by investigating behavior of cells. This trend has led to a huge amount of image data, the analysis of which becomes a bottleneck in related research. Consequently, how to efficiently analyze the data is emerging as one of the major challenges in the fields. Computer vision analysis of non-fluorescent microscopy images, representatively phase-contrast microscopy images, promises to realize a long-term monitoring of live cell behavior with minimal perturbation and human intervention. To take a step forward to such a system, this thesis proposes computer vision algorithms that monitor cell growth, migration, and differentiation by detecting three cellular events—mitosis (cell division), apoptosis (programmed cell death), and differentiation— and tracking individual cells. Among the cellular events, to the best our knowledge, apoptosis and a certain type of differentiation, namely muscle myotubes, have never been detected without fluorescent labeling. We address these challenging problems by developing computer vision algorithms adopting phase contrast microscopy. We also significantly improve the accuracy of mitosis detection and cell tracking in phase contrast microscopy over previous methods, particularly under non-trivial conditions, such as high cell density or confluence. We demonstrate the usefulness of our methods in biological research by analyzing cell behavior in scratch wound healing assays. The automated system that we are pursuing would lead to a new paradigm of biological research by enabling quantitative and individualized assessment in behavior of a large population of intact cells.

Page generated in 0.0835 seconds