Search

We discuss online strategies for visibility-based searching for an object hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task is closely related to a number of well-studied problems. Our robot uses a three-dimensional laser scanner in a stop, scan, plan, go fashion for building a virtual three-dimensional environment. Besides planning trajectories and avoiding obstacles, Kurt3D is capable of identifying objects like a chair. We derive a practically useful and asymptotically optimal strategy that guarantees a competitive ratio of 2, which differs remarkably from the well-studied scenario without the need of stopping for surveying the environment. Our strategy is used by Kurt3D, documented in a separate video. Keywords: Searching, visibility problems, watchman problems, online searching, competitive strategies, autonomous mobile robots, three-dimensional laser scanning, Kurt3D. [ABSTRACT FROM AUTHOR]

We present an algorithm for complete path planning for translating polyhedral robots in 3D. Instead of exactly computing an explicit representation of the free space, we compute a roadmap that captures its connectivity. This representation encodes the complete connectivity of free space and allows us to perform exact path planning. We construct the roadmap by computing deterministic samples in free space that lie on an adaptive volumetric grid. Our algorithm is simple to implement and uses two tests: a complex cell test and a star-shaped test. These tests can be efficiently performed on polyhedral objects using max-norm distance computation and linear programming. The complexity of our algorithm varies as a function of the size of narrow passages in the configuration space. We demonstrate the performance of our algorithm on environments with very small narrow passages or no collision-free paths. [ABSTRACT FROM AUTHOR]

In this paper we present our advances in a data structure, the Gap Navigation Tree (GNT), useful for solving different visibility-based robotic tasks in unknown planar environments. We present its use for optimal robot navigation in simply-connected environments, locally optimal navigation in multiply-connected environments, pursuit-evasion, and robot localization. The guiding philosophy of this work is to avoid traditional problems such as complete map building and exact localization by constructing a minimal representation based entirely on critical events in online sensor measurements made by the robot. The data structure is introduced from an information space perspective, in which the information used among the different visibility-based tasks is essentially the same, and it is up to the robot strategy to use it accordingly for the completion of the particular task. This is done through a simple sensor abstraction that reports the discontinuities in depth information of the environment from the robot's perspective (gaps), and without any kind of geometric measurements. The GNT framework was successfully implemented on a real robot platform. [ABSTRACT FROM AUTHOR]

In this paper, we report on the design of a model-based controller that can achieve dynamical self-righting of a hexapod robot. Extending on our earlier work in this domain, we introduce a tractable multi-point contact model with Coulomb friction. We contrast the singularities inherent to the new model with other available methods and show that for our specific application, it yields dynamics which are well-defined. We then present a feedback controller that achieves "maximal" performance under morphological and actuation constraints, while ensuring the validity of the model by staying away from singularities. Finally, through systematic experiments, we demonstrate that our controller is capable of robust flipping behavior. Keywords: legged robot, model based control, contact modeling, flipping, RHex [ABSTRACT FROM AUTHOR]

We address the problem of minimum distance localization in environments that may contain self-similarities. A mobile robot is placed at an unknown location inside a 2D self-similar polygonal environment P. The robot has a map of P and compute visibility data through sensing. However, the self-similarities in the environment mean that the same visibility data may correspond to several different locations. The goal, therefore, is to determine the robot's true initial location while minimizing the distance traveled by the robot. We present two randomized approximation algorithms that solve minimum distance localization. The performance of our algorithms is evaluated empirically. [ABSTRACT FROM AUTHOR]

To investigate the parameters of the protein design problem that we are exploring in collaboration with biochemists, we developed a tool that uses inverse kinematics to support moving small fragments of protein backbone, while respecting biochemists' desires to "remain in favorable regions of the Ramachandran plot" and "preserve ideal geometry." By presenting estimates of derivatives in response to motion, we are able to refine these qualitative desires as we work with our collaborators. We then explore low dimensional bases to parameterize the space of backbone motions. [ABSTRACT FROM AUTHOR]

Although there are many motion planning techniques, there is no method that outperforms all others for all problem instances. Rather, each technique has different strengths and weaknesses which makes it best-suited for certain types of problems. Moreover, since an environment can contain vastly different regions, there may not be a single planner that will perform well in all its regions. Ideally, one would use a suite of planners in concert and would solve the problem by applying the best-suited planner in each region. In this paper, we propose an automated framework for feature-sensitive motion planning. We use a machine learning approach to characterize and partition C-space into regions that are well suited to one of the methods in our library of roadmap-based motion planners. After the best-suited method is applied in each region, the resulting region roadmaps are combined to form a roadmap of the entire planning space. Over a range of problems, we demonstrate that our simple prototype system reliably outperforms any of the planners on their own. [ABSTRACT FROM AUTHOR]

Rapid protein structure determination relies greatly on the availability of software that can automatically generate a protein model from an experimental electron density map. Tremendous advances in this area have been achieved recently. In favorable cases, available software can build over 90% of the final model. However, in less favorable circumstances, particularly at medium-low resolution, only about 2/3 completeness is attained. Manual completion of these partial models is usually feasible but time-consuming. The electron density in areas of missing fragments is often of poorer quality, especially for flexible loops, making manual interpretation particularly difficult. Except for the beginning and end of the protein chain, the end points of each missing fragment are known from the partial model. Due to the kinematic chain structure of the protein backbone, loop completion can be approached as an inverse kinematics problem. A fast, two-stage inverse kinematics algorithm is presented that fits a protein chain of known sequence to the electron density map between two anchor points. Our approach first samples a large set of candidates that meet the closure constraint and then refines the most promising candidates to improve the fit. The algorithm has been tested and used to aid protein model completion in areas of poor density, closing loops of up to 12 residues to within 0.3 of the final refined structure. It has also been used to close missing loops of the same length in partial models built at medium-low resolution to within 0.6 Å. [ABSTRACT FROM AUTHOR]

The problem of a planning collision-free motion of a planar 3R-manipulator among point obstacles is studied using techniques from topology and homology. By completely characterizing the set of singular configurations (the points in configuration space corresponding to an intersection of the chain with itself or a point obstacle), the complementary space, the free space, is also completely characterized. This characterization dictates an exact, complete, motion planning algorithm that builds on the authors' algorithm developed for 2R-manipulators [9]. Results obtained with a preliminary version of the algorithm are given. [ABSTRACT FROM AUTHOR]

We present algorithms for generating deterministic sample sequences using incremental grid-based sampling. Our algorithms are designed to generate dense sample sequences over spaces common in robotics, such as the unit cube, SO(3), and SE(3). Our sampling techniques provide the advantageous properties of uniformity, lattice structure, and incremental quality. In addition, the inherent structure of grid-based sequences not only enables them to be used in the place of other sampling techniques in existing algorithms, but also permits the development of new algorithms aimed at exploiting this structure. [ABSTRACT FROM AUTHOR]

This paper presents a new motion planning algorithm which we call the Path-Directed Subdivision Tree exploration Planner PDST-EXPLORE. It is a sampling-based method which builds a tree and takes a substantially different approach from other exploration planners such as RRT [18] and EST [12]. PDST-EXPLORE is a general purpose planner but is designed to overcome difficulties inherent in planning for robots with non-trivial dynamics. Specifically, our planner represents samples as path segments rather than individual states and uses non-uniform subdivisions of the state space to estimate coverage. This change avoids many of the problems that previous sampling-based planners have had with milestone placement, metrics and coverage estimation. We use a deterministic update schedule together with randomized path generation to adaptively strike a balance between greedy exploration and methodical search. We have obtained a proof of probabilistic completeness for the planner which assumes very little about the specific robot system that the planner operates on. Finally, we have implemented the planner for planar kinodynamic point robots, differential drive robots and blimp-like robots. The experimental results demonstrate the efficiency of the planner's implementation as well as its robustness in covering the entire reachable free space. [ABSTRACT FROM AUTHOR]

Many macromolecules consist of domains which act more or less as rigid bodies during large conformational changes. These collective motions are thought to be strongly related with the functions of a system. This fact encourages us to model a biomolecular structure as a set of rigid clusters which are interconnected with distance constraints. In this way the intermediate conformations in an anharmonic pathway can be determined by the translational and rotational displacements of large clusters in such a way that steric constraints are observed. In this paper, we present a geometry-based interpolation technique called rigid-cluster interpolation. This is an extension of the coarse-grained elastic network interpolation (ENI) method that we previously developed to generate physically realistic pathways between two different conformations of a macromolecule. We present the derivation of the rigid-cluster model and apply it to various "macromolecular machines". Simulation results show that this method generates sterically feasible pathways of large systems in a very short time. The computational cost of the interpolation does not scale heavily with the size of structures, but rather depends strongly on the number of rigid-clusters. [ABSTRACT FROM AUTHOR]

This paper studies the recognition of low-degree polynomial curves based on minimal tactile data. Differential and semi-differential invariants have been derived for quadratic curves and special cubic curves that are found in applications. Such an invariant, independent of translation and rotation, is computed from the local geometry at up to three points on a curve. Recognition of the curve reduces to invariant verification with its canonical parametric form determined along the way. In addition, the contact locations are found on the curve, thereby localizing it relative to the touch sensor. Simulation results support the method in the presence of small noise. Preliminary experiments have also been carried out. The presented work distinguishes itself from traditional model-based recognition in its ability to simultaneously recognize and localize a shape from one of several classes, each consisting of a continuum of shapes, by the use of local data. [ABSTRACT FROM AUTHOR]

This paper contains two main results: First, we revisit the well-known visibility based pursuit-evasion problem and show that, in contrast to deterministic strategies, a single pursuer can locate an unpredictable evader in any simply-connected polygonal environment using a randomized strategy. The evader can be arbitrarily faster than the pursuer and it may know the position of the pursuer at all times but it does not have prior knowledge of the random decisions made by the pursuer. Second, using the randomized algorithm together with the solution of a known lion and man problem [12] as subroutines, we present a strategy for two pursuers (one of which is at least as fast as the evader) to quickly capture an evader in a simply-connected polygonal environment. [ABSTRACT FROM AUTHOR]

Most mobile robot mapping and exploration research makes use of longrange, powerful sensors such as laser range.nders to create maps. In this paper we take a different approach, creating maps using robots with limited sensing capabilities, most notably in their sensor range. Our prototype robots use only five infrared range sensors with a maximum range of 80 cm; in general, these robots cannot "see" both sides of a hallway. We present an algorithm for such a robot to build a topological map in the presence of sensing and odometry error. In doing so, we develop a paradigm to extend topological mapping to open spaces, long considered a deficiency of topological mapping; we also introduce an evidential approach to the problem of "closing the loop." [ABSTRACT FROM AUTHOR]

This paper presents an approach to coordinate the motions of droplets in digital microfluidic systems used for biochemical analysis. A digital microfluidic system typically consists of a planar array of cells with electrodes that control the droplets. The primary challenge in using droplet based systems is that they require the simultaneous coordination of a potentially large number of droplets on the array as the droplets move, mix, and split. This paper describes a general-purpose system that uses simple algorithms and yet is versatile. First, a semi-automated approach to generate the array layout in terms of components is explained. Next, simple algorithms to select destination components for the droplets and a decentralized scheme for components to route the droplets on the array are discussed. These are then combined into a reconfigurable system that has been simulated in software to perform DNA polymerase chain reaction and other analyses. The algorithms have been able to successfully coordinate hundreds of droplets simultaneously and perform one or more chemical analyses in parallel. Since it is challenging to analytically characterize the behavior of such systems, methods to detect potential instabilities are proposed. [ABSTRACT FROM AUTHOR]

In prior work, we extended the well-known form closure grasp framework for rigid parts to a class of deformable parts, modeled as frictionless polygons with a finite element mesh and given stiffness matrix. We define the D-space (deformationspace) of a part as the C-space of all its mesh nodes and deform closure in terms of the work needed to release the part from a set of finger contacts. In the present paper, we define a measure of grasp quality for two-point deformclosure grasps. This metric is based on balancing the potential energy needed to release the part against the potential energy that would result in plastic deformation. Given two jaw contacts at the perimeter nodes, we give a numerical algorithm to determine the optimal jaw separation based on this metric. For a part with n mesh nodes and p perimeter nodes, the algorithm computes an approximation to the optimal separation in time O(n3p2 + ( p2 /ε) log p). [ABSTRACT FROM AUTHOR]

Manually following a moving object through a cluttered virtual environment can be challenging for the user. Instead, one would typically rather focus on watching the object and its environment. In this paper, we present an approach to automatically generate a camera motion, such that the user maintains visibility with an object moving along a known path through a virtual environment. To begin, the user specifies the camera placement at the start and end of the object path, and constraints on the camera placement relative to the object. Given this input, the system computes a smooth camera path, satisfying the constraints: Firstly, an initial camera path is generates by applying a single-shot probabilistic road map technique. We augmented this technique with several optimisations, speeding up the path generation considerably. Then, the initial path is smoothed to present the user with a pleasant camera motion. The approach has been implemented and tested: it is fast and computes paths through complicated 2D and 3D environments in less than a second. [ABSTRACT FROM AUTHOR]

Given a collection of robots sharing a common environment, assume that each possesses an individual roadmap for its C-space and a cost function for attaining a goal. Vector-valued (or Pareto) optima for collision-free coordination are by no means unique: in fact, continua of optimal coordinations are possible. However, for cylindrical obstacles (those defined by pairwise interactions), we prove a finite bound on the number of optimal coordinations. For such systems, we present an exact algorithm for reducing a coordination scheme to its Pareto optimal representative. [ABSTRACT FROM AUTHOR]

This paper is concerned with on-line problems where a mobile robot of size D has to achieve a task in an unknown planar environment whose geometry is acquired during task execution. The critical parameter in such problems is physical motion time which corresponds to length or cost of the path traveled by the robot. The competitiveness of an on-line algorithm measures its performance relative to the optimal off line solution to the problem. While competitiveness usually means constant relative performance, this paper generalizes competitiveness to any functional relationship between on-line performance and optimal off-line solution. Given an on-line task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of all on-line algorithms for the task, such that the two bounds satisfy the same functional relationship. We classify some common online motion planning problems into competitive classes. In particular, navigation to a target whose position is either a priori known or recognized only upon arrival belongs to a quadratic competitive class. The hardest on-line problems belong to exponential and even non-boundable competitive classes. We present examples of such problems, which involve navigation in unknown variable traversibility environments. [ABSTRACT FROM AUTHOR]

A topological theory initiated in [4,5] uses methods of algebraic topology to estimate numerically the character of instabilities arising in motion planning algorithms. The present paper studies random motion planning algorithms and reveals how the topology of the robot's configuration space influences their structure. We prof that the topological complexity of motion planning TC(X) coinsides with the minimal n such that there exist an n-valued random motion planning algorithm for the system; here X the configuration space. We study in detail the problem of collision free motion of several objects in the graph Γ. We describe an explicit motion planning algorithm for this problem. We prove that if Γ is a tree and if the number of objects is large enough, then the topological complexity of this motion planning problem equals 2m(Γ)+1 where m(Γ) is the number of the essential vertices of Γ. It turns out (in contrast with the results on the collision free control of many objects in space [7]) that the topological complexity is independent of the number of particles. [ABSTRACT FROM AUTHOR]

Most robot control and planning algorithms are complex, involving a combination of reactive controllers, behavior-based controllers, and deliberative controllers. The switching between different behaviors or controllers makes such systems hybrid, i.e. combining discrete and continuous dynamics. While proofs of convergence, robustness and stability are often available for simple controllers under a carefully crafted set of operating conditions, there is no systematic approach to experimenting with, testing, and validating the performance of complex hybrid control systems. In this paper we address the problem of generating sets of conditions (inputs, disturbances, and parameters) that might be used to "test" a given hybrid system. We use the method of Rapidly exploring Random Trees (RRTs) to obtain test inputs. We extend the traditional RRT, which only searches over continuous inputs, to a new algorithm, called the Rapidly exploring Random Forest of Trees (RRFT), which can also search over time invariant parameters by growing a set of trees for each parameter value choice. We introduce new measures for coverage and tree growth that allows us to dynamically allocate our resources among the set of trees and to plant new trees when the growth rate of existing ones slows to an unacceptable level. We demonstrate the application of RRFT to testing and validation of aerial robotic control systems. [ABSTRACT FROM AUTHOR]

Given two compact, simply connected manifolds with boundary, and a navigation function (NF) on each manifold, this paper presents a simple composition law that yields a new NF on the cross product space. The method provides tunable "hooks" for shaping the new potential function while still guaranteeing obstacle avoidance and essentially global convergence. The composition law is associative, and successive compositions fold into a single, computational simple expression, enabling the practical construction of NFs on the Cartesian product of several manifolds. [ABSTRACT FROM AUTHOR]

Kinematic loop-closure constraints significantly increase the difficulty of motion planning for articulated mechanisms. Configurations of closed-chain mechanisms do not form a single manifold, easy to parameterize, as the configurations of open kinematic chains. In general, they are grouped into several subsets with complex and a priori unknown topology. Sampling-based motion planning algorithms cannot be directly applied to such closed-chain systems. This paper describes our recent work [7] on the extension of sampling-based planners to treat this kind of mechanisms. [ABSTRACT FROM AUTHOR]

This paper studies non-gaited, multi-step motion planning, to enable limbed robots to free-climb vertical rock. The application of a multi-step planner to a real free-climbing robot is described. This planner processes each of the many underlying one-step motion queries using an incremental, sample-based technique. However, experimental results point toward a better approach, incorporating the ability to detect when one-step motions are infeasible (i.e., to prove disconnection). Current work on a general method for doing this, based on recent advances in computational real algebra, is also presented. [ABSTRACT FROM AUTHOR]

This papers introduces the stealth tracking problem, in which a robot, equipped with visual sensors, tries to track a moving target among obstacles and, at the same time, remain hidden from the target. Obstacles impede both the tracker's motion and visibility, but on the other hand, provide hiding places for the tracker. Our proposed tracking algorithm uses only local information from the tracker's visual sensors and assumes no prior knowledge of target motion or a global map of the environment. It applies a local greedy strategy, and chooses the best move at each time step by minimizing the target's escape risk, subject to the stealth constraint. The algorithm is efficient, taking O(n) time at each step, where n is the complexity of the tracker's visibility region. Simulation experiments show that the algorithm performs well in difficult environments. [ABSTRACT FROM AUTHOR]

We develop a procedure for automated trajectory generation for robotic spray painting applications. Painting requires that the spray gun deposit paint at each point on the target surface such that the variation of the resultant paint deposition is within acceptable limits; we term this the uniform coverage problem. To understand the key issues in the uniform coverage problem, we consider surface patches that are geodesically convex and topologically simple to represent realistic automotive surfaces. Our goal is to understand the relationship between the spray gun trajectory and the following output characteristics: deposition uniformity, cycle time, and paint waste. Our planning approach decomposes the coverage trajectory generation problem into three subproblems: selection of the start curve, selection of the speed pro.les along each pass, and selection of the spacing between the passes. Using concepts such as area magni.cation, the Gauss-Bonnet theorem from differential geometry, and standard optimization procedures, we present procedures to solve each subproblem independently of the others. Finally, we demonstrate our trajectory planning procedures in simulation as well as experimentally on simple surfaces that approximate real automobile surfaces. [ABSTRACT FROM AUTHOR]

The Dutch robot soccer team Clockwork Orange is a research project of the Delft University of Technology and the University of Amsterdam. In this project we study multi-robot collaboration, robot vision and robot control. Our research focus, overviewed in this paper, is on automatic calibration for robust colour segmentation, behaviour based robotics and reinforcement trained dribbling with the ball. [ABSTRACT FROM AUTHOR]

As a feasibility study in 1994, we built a system that allows a robot manipulator to be teleoperated by the public via the Internet. Access control became a primary issue: in subsequent networked robot systems we explore techniques ranging from user queues, multitasking, vector averaging, and geometric optimization. These systems are also designed to suggest questions about human perception and expectations about technology. [ABSTRACT FROM AUTHOR]

This paper reviews our research in computational biology and chemistry. Some of the most challenging and influential opportunities for Physical Geometric Algorithms (PGA) arise in developing and applying information technology to understand the molecular machinery of the cell. Our recent work (e.g., [1-20]) shows that many PGA techniques may be fruitfully applied to the challenges of computational molecular biology. PGA research may lead to computer systems and algorithms that are useful in structural molecular biology, proteomics, and rational drug design. Concomitantly, a wealth of interesting computational problems arise in proposed methods for discovering new pharmaceuticals. I'll briefly discuss some recent results from my lab, including new algorithms for interpreting X-ray crystallography [14, 17, 16] and NMR (nuclear magnetic resonance) data [3, 9, 6, 19, 10, 5, 7, 18, 4], disease classification using mass spectrometry of human serum [12], and protein redesign [13]. Our algorithms have recently been used, respectively, to reveal the enzymatic architecture of organisms high on the CDC bioterrorism watch-list [17, 16], for probabilistic cancer classification from human peripheral blood [12], and to redesign an antibioticproducing enzyme to bind a novel substrate [13]. I'll overview these projects, and highlight some of the algorithmic and computational challenges. [ABSTRACT FROM AUTHOR]