This paper proposes a learning-from-demonstration (LfD) method using probability densities on the workspaces of robot manipulators. The method, named PRobabilistically-Informed Motion Primitives (PRIMP), learns the probability distribution of the end effector trajectories in the 6D workspace that includes both positions and orientations. It is able to adapt to new situations such as novel via points with uncertainty and a change of viewing frame. The method itself is robot-agnostic, in that the learned distribution can be transferred to another robot with the adaptation to its workspace density. Workspace-STOMP, a new version of the existing STOMP motion planner, is also introduced, which can be used as a post-process to improve the performance of PRIMP and any other reachability-based LfD method. The combination of PRIMP and Workspace-STOMP can further help the robot avoid novel obstacles that are not present during the demonstration process. The proposed methods are evaluated with several sets of benchmark experiments. PRIMP runs more than 5 times faster than existing state-of-the-art methods while generalizing trajectories more than twice as close to both the demonstrations and novel desired poses. They are then combined with our lab’s robot imagination method that learns object affordances, illustrating the applicability to learn tool use through physical experiments.

Cloth state estimation is an important problem in robotics. It is essential for the robot to know the accurate state to manipulate cloth and execute tasks such as robotic dressing, stitching, and covering/uncovering human beings. However, accurately estimating the cloth state remains challenging due to the high flexibility and self-occlusion of cloth. This paper proposes a diffusion model-based pipeline that formulates the cloth state estimation as an image generation problem by representing the cloth state as an RGB image that describes the point-wise translation (translation map) between a predefined flattened mesh and the deformed mesh in a canonical space. Then we train a conditional diffusion-based image generation model to predict the translation map based on an observation. Experiments are conducted in both simulation and the real world to validate the performance of our method. Results indicate that our method outperforms two recent methods in both accuracy and speed. More results and code are available on our project website: https://chirikjianlab.github.io/RaggeDi/

Reinforcement learning (RL) has long struggled with exploration in vast state-action spaces, particularly for intricate tasks that necessitate a series of well-coordinated actions. Meanwhile, large language models (LLMs) equipped with fundamental knowledge have been utilized for task planning across various domains. However, using them to plan for long-term objectives can be demanding, as they function independently from task environments where their knowledge might not be perfectly aligned, hence often overlooking possible physical limitations. To this end, we propose a goal-based RL framework that leverages prior knowledge of LLMs to benefit the training process. We introduce a hierarchical module that features a goal generator to segment a long-horizon task into reachable subgoals and a policy planner to generate action sequences based on the current goal. Subsequently, the policies derived from LLMs guide the RL to achieve each subgoal sequentially. We validate the effectiveness of the proposed framework across different simulation environments and long-horizon tasks with complex state and action spaces. The LLM prompts we use and more details can be found at https://chirikjianlab.github.io/G2RL-LM/.

This paper proposes a learning-from-demonstration (LfD) method using probability densities on the workspaces of robot manipulators. The method, named PRobabilistically-Informed Motion Primitives (PRIMP), learns the probability distribution of the end effector trajectories in the 6D workspace that includes both positions and orientations. It is able to adapt to new situations such as novel via points with uncertainty and a change of viewing frame. The method itself is robot-agnostic, in that the learned distribution can be transferred to another robot with the adaptation to its workspace density. Workspace-STOMP, a new version of the existing STOMP motion planner, is also introduced, which can be used as a post-process to improve the performance of PRIMP and any other reachability-based LfD method. The combination of PRIMP and Workspace-STOMP can further help the robot avoid novel obstacles that are not present during the demonstration process. The proposed methods are evaluated with several sets of benchmark experiments. PRIMP runs more than 5 times faster than existing state-of-the-art methods while generalizing trajectories more than twice as close to both the demonstrations and novel desired poses. They are then combined with our lab's robot imagination method that learns object affordances, illustrating the applicability to learn tool use through physical experiments.

Representing complex objects with basic geometric primitives has long been a topic in computer vision. Primitive-based representations have the merits of compactness and computational efficiency in higher-level tasks such as physics simulation, collision checking, and robotic manipulation. Unlike previous works which extract polygonal meshes from a signed distance function (SDF), in this paper, we present a novel method, named Marching-Primitives, to obtain a primitive-based abstraction directly from an SDF. Our method grows geometric primitives (such as superquadrics) iteratively by analyzing the connectivity of voxels while marching at different levels of signed distance. For each valid connected volume of interest, we march on the scope of voxels from which a primitive is able to be extracted in a probabilistic sense and simultaneously solve for the parameters of the primitive to capture the underlying local geometry. We evaluate the performance of our method on both synthetic and real-world datasets. The results show that the proposed method out-performs the state-of-the-art in terms of accuracy, and is directly generalizable among different categories and scales. The code is open-sourced at https://github.com/ChirikjianLab/Marching-Primitives.git.

Path planning has long been one of the major research areas in robotics, with probabilistic roadmap (PRM) and rapidly-exploring random trees (RRT) being two of the most effective classes of planners. Though generally very efficient, these sampling-based planners can become computationally expensive in the important case of “narrow passages.” This article develops a path planning paradigm specifically formulated for narrow passage problems. The core is based on planning for rigid-body robots encapsulated by unions of ellipsoids. Each environmental feature is represented geometrically using a strictly convex body with a$\mathcal {C}^{1}$boundary (e.g., superquadric). The main benefit of doing this is that configuration-space obstacles can be parameterized explicitly in closed form, thereby allowing prior knowledge to be used to avoid sampling infeasible configurations. Then, by characterizing a tight volume bound for multiple ellipsoids, robot transitions involving rotations are guaranteed to be collision free without needing to perform traditional collision detection. Furthermore, by combining with a stochastic sampling strategy, the proposed planning framework can be extended to solving higher dimensional problems, in which the robot has a moving base and articulated appendages. Benchmark results show that the proposed framework often outperforms the sampling-based planners in terms of computational time and success rate in finding a path through narrow corridors for both single-body robots and those with higher dimensional configuration spaces. Physical experiments using the proposed framework are further demonstrated on a humanoid robot that walks in several cluttered environments with narrow passages.

Interpreting objects with basic geometric primitives has long been studied in computer vision. Among geometric primitives, superquadrics are well known for their ability to represent a wide range of shapes with few parameters. However, as the first and foremost step, recovering superquadrics accurately and robustly from 3D data still remains challenging. The existing methods are subject to local optima and sensitive to noise and outliers in real-world scenarios, resulting in frequent failure in capturing geometric shapes. In this paper, we propose the first probabilistic method to recover superquadrics from point clouds. Our method builds a Gaussian-uniform mixture model (GUM) on the parametric surface of a superquadric, which explicitly models the generation of outliers and noise. The superquadric recovery is formulated as a Maximum Likelihood Estimation (MLE) problem. We propose an algorithm, Expectation, Maximization, and Switching (EMS), to solve this problem, where: (1) outliers are predicted from the posterior perspective; (2) the superquadric parameter is optimized by the trust-region reflective algorithm; and (3) local optima are avoided by globally searching and switching among parameters encoding similar superquadrics. We show that our method can be extended to the multi-superquadrics recovery for complex objects. The proposed method outperforms the state-of-the-art in terms of accuracy, efficiency, and robustness on both synthetic and real-world datasets. The code is at http://github.com/bmlklwx/EMS-superquadric_fitting.git.

In this paper, we study the problem of autonomously seating a teddy bear on a previously unseen chair. To achieve this goal, we present a novel method for robots to imagine the sitting pose of the bear by physically simulating a virtual humanoid agent sitting on the chair. We also develop a robotic system which leverages motion planning to plan SE(2) motions for a humanoid robot to walk to the chair and whole-body motions to put the bear on it. Furthermore, to cope with cases where the chair is not in an accessible pose for placing the bear, a human assistance module is introduced for a human to follow language instructions given by the robot to rotate the chair and help make the chair accessible. We implement our method with a robot arm and a humanoid robot. We calibrate the proposed system with 3 chairs and test on 12 previously unseen chairs in both accessible and inaccessible poses extensively. Results show that our method enables the robot to autonomously seat the teddy bear on the 12 previously unseen chairs with a very high success rate. The human assistance module is also shown to be very effective in changing the accessibility of the chair. Video demos and more details are available at https://chirikjianlab.github.io/putbearonchair/.

This paper presents a novel method for smaller-sized humanoid robots to self-calibrate their foot force sensors. The method consists of two steps: 1. The robot is commanded to move along planned whole-body trajectories in different double support configurations. 2. The sensor parameters are determined by minimizing the error between the measured and modeled center of pressure (CoP) and ground reaction force (GRF) during the robot's movement using optimization. This is the first proposed autonomous calibration method for foot force-sensing devices in smaller humanoid robots. Furthermore, we introduce a high-accuracy manual calibration method to establish CoP ground truth, which is used to validate the measured CoP using self-calibration. The results show that the self-calibration can accurately estimate CoP and GRF without any manual intervention. Our method is demonstrated using a NAO humanoid platform and our previously presented force-sensing shoes.

Rearrangement tasks have been identified as a crucial challenge for intelligent robotic manipulation, but few methods allow for precise construction of unseen structures. We propose a visual foresight model for pick-and-place rearrangement manipulation which is able to learn efficiently. In addition, we develop a multi-modal action proposal module which builds on the Goal-Conditioned Transporter Network, a state-of-the-art imitation learning method. Our image-based task planning method, Transporters with Visual Foresight, is able to learn from only a handful of data and generalize to multiple unseen tasks in a zero-shot manner. TVF is able to improve the performance of a state-of-the-art imitation learning method on unseen tasks in simulation and real robot experiments. In particular, the average success rate on unseen tasks improves from 55.4% to 78.5% in simulation experiments and from 30% to 63.3% in real robot experiments when given only tens of expert demonstrations. Video and code are available on our project website: https://chirikjianlab.github.io/tvf/

We aim at improving the computational efficiency of graph convolutional networks (GCNs) for learning on point clouds. The basic graph convolution that is composed of a K-nearest neighbor (KNN) search and a multilayer perceptron (MLP) is examined. By mathematically analyzing the operations there, two findings to improve the efficiency of GCNs are obtained. (1) The local geometric structure information of 3D representations propagates smoothly across the GCN that relies on KNN search to gather neighborhood features. This motivates the simplification of multiple KNN searches in GCNs. (2) Shuffling the order of graph feature gathering and an MLP leads to equivalent or similar composite operations. Based on those findings, we optimize the computational procedure in GCNs. A series of experiments show that the optimized networks have reduced computational complexity, decreased memory consumption, and accelerated inference speed while maintaining comparable accuracy for learning on point clouds.

Probabilistic point cloud registration methods are becoming more popular because of their robustness. However, unlike point-to-plane variants of iterative closest point (ICP) which incorporate local surface geometric information such as surface normals, most probabilistic methods (e.g., coherent point drift (CPD)) ignore such information and build Gaussian mixture models (GMMs) with isotropic Gaussian covariances. This results in sphere-like GMM components which only penalize the point-to-point distance between the two point clouds. In this paper, we propose a novel method called CPD with Local Surface Geometry (LSG-CPD) for rigid point cloud registration. Our method adaptively adds different levels of point-to-plane penalization on top of the point-to-point penalization based on the flatness of the local surface. This results in GMM components with anisotropic covariances. We formulate point cloud registration as a maximum likelihood estimation (MLE) problem and solve it with the Expectation-Maximization (EM) algorithm. In the E step, we demonstrate that the computation can be recast into simple matrix manipulations and efficiently computed on a GPU. In the M step, we perform an unconstrained optimization on a matrix Lie group to efficiently update the rigid transformation of the registration. The proposed method outperforms state-of-the-art algorithms in terms of accuracy and robustness on various datasets captured with range scanners, RGBD cameras, and LiDARs. Also, it is significantly faster than modern implementations of CPD. The source code is available at https://github.com/ChirikjianLab/LSG-CPD.git.

To function autonomously in the physical world, humanoid robots need high-fidelity sensing systems, especially for forces that cannot be easily modeled. Modeling forces in robot feet is particularly challenging due to static indeterminacy, thereby requiring direct sensing. Unfortunately, resolving forces in the feet of some smaller-sized humanoids is limited both by the quality of sensors and the current algorithms used to interpret the data. This paper presents light-weight, low-cost and open-source force-sensing shoes to improve force measurement for popular smaller-sized humanoid robots, and a method for calibrating the shoes. The shoes measure center of pressure (CoP) and normal ground reaction force (GRF). The calibration method enables each individual shoe to reach high measurement precision by applying known forces at different locations of the shoe and using a regularized least squares optimization to interpret sensor outputs. A NAOTMrobot is used as our experimental platform. Experiments are conducted to compare the measurement performance between the shoes and the robot’s factory-installed force-sensing resistors (FSRs), and to evaluate the calibration method over these two sensing modules. Experimental results show that the shoes significantly improve CoP and GRF measurement precision compared to the robot’s built-in FSRs. Moreover, the developed calibration method improves the measurement performance for both our shoes and the built-in FSRs.

Abstract This paper presents a novel, highly distinctive and robust local surface feature descriptor. Our descriptor is predicated on a simple observation: instead of describing the points in the vicinity of a feature point relative to a reference frame at the feature point, all points in the region describe the feature point relative to their own frames. Isometry invariance is a byproduct of this construction. Our descriptor is derived relative to the extended convolution – a generalization of the standard convolution that allows the filter to adaptively transform as it passes over the domain. As such, we name our descriptor the Extended Convolution Histogram of Orientations (ECHO). It exhibits superior performance compared to popular surface descriptors in both feature matching and shape correspondence experiments. In particular, the ECHO descriptor is highly stable under near‐isometric deformations and remains distinctive under significant levels of noise, tessellation, complex deformations and the kinds of interference commonly found in real data.

The treatment of malaria is a global health challenge that stands to benefit from the widespread introduction of a vaccine for the disease. A method has been developed to create a live organism vaccine using the sporozoites (SPZ) of the parasite Plasmodium falciparum (Pf), which are concentrated in the salivary glands of infected mosquitoes. Current manual dissection methods to obtain these PfSPZ are not optimally efficient for large-scale vaccine production. We propose an improved dissection procedure and a mechanical fixture that increases the rate of mosquito dissection and helps to deskill this stage of the production process. We further demonstrate the automation of a key step in this production process, the picking and placing of mosquitoes from a staging apparatus into a dissection assembly. This unit test of a robotic mosquito pick-and-place system is performed using a custom-designed micro-gripper attached to a four degree of freedom (4-DOF) robot under the guidance of a computer vision system. Mosquitoes are autonomously grasped and pulled to a pair of notched dissection blades to remove the head of the mosquito, allowing access to the salivary glands. Placement into these blades is adapted based on output from computer vision to accommodate for the unique anatomy and orientation of each grasped mosquito. In this pilot test of the system on 50 mosquitoes, we demonstrate a 100% grasping accuracy and a 90% accuracy in placing the mosquito with its neck within the blade notches such that the head can be removed. This is a promising result for this difficult and non-standard pick-and-place task.

For robots to exhibit a high level of intelligence in the real world, they must be able to assess objects for which they have no prior knowledge. Therefore, it is crucial for robots to perceive object affordances by reasoning about physical interactions with the object. In this paper, we propose a novel method to provide robots with an ability to imagine object affordances using physical simulations. The class of chair is chosen here as an initial category of objects to illustrate a more general paradigm. In our method, the robot "imagines" the affordance of an arbitrarily oriented object as a chair by simulating a physical sitting interaction between an articulated human body and the object. This object affordance reasoning is used as a cue for object classification (chair vs non-chair). Moreover, if an object is classified as a chair, the affordance reasoning can also predict the upright pose of the object which allows the sitting interaction to take place. We call this type of poses the functional pose. We demonstrate our method in chair classification on synthetic 3D CAD models. Although our method uses only 30 models for training, it outperforms appearance-based deep learning methods, which require a large amount of training data, when the upright orientation is not assumed to be known a priori. In addition, we showcase that the functional pose predictions of our method align well with human judgments on both synthetic models and real objects scanned by a depth camera.

A robot cannot lift up an object if it is not feasible to do so. However, in most research on robot lifting, "feasibility" is usually presumed to exist a priori. This paper proposes a three-step method for a humanoid robot to reason about the feasibility of lifting a heavy box with physical properties that are unknown to the robot. Since feasibility of lifting is directly related to the physical properties of the box, we first discretize a range for the unknown values of parameters describing these properties and tabulate all valid optimal quasi-static lifting trajectories generated by simulations over all combinations of indices. Second, a physical-interaction-based algorithm is introduced to identify the robust gripping position and physical parameters corresponding to the box. During this process, the stability and safety of the robot are ensured. On the basis of the above two steps, a third step of mapping operation is carried out to best match the estimated parameters to the indices in the table. The matched indices are then queried to determine whether a valid trajectory exists. If so, the lifting motion is feasible; otherwise, the robot decides that the task is beyond its capability. Our method efficiently evaluates the feasibility of a lifting task through simple interactions between the robot and the box, while simultaneously obtaining the desired safe and stable trajectory. We successfully demonstrated the proposed method using a NAO humanoid robot.

Collision detection has attracted attention of researchers for decades in the field of computer graphics, robot motion planning, computer aided design, etc. A large number of successful algorithms have been proposed and applied, which make use of convex polytopes and bounding volumes as primitives. However, algorithms for those shapes rely significantly on the complexity of the meshes. This paper deals with collision detection for shapes with simple and exact mathematical descriptions, such as ellipsoids and superquadrics. These primitives have a wide range of applications in representing complex objects and have much fewer parameters than meshes. The foundation of the proposed collision detection scheme relies on the closed-form Minkowski sums between ellipsoids and superquadrics in n-dimensional Euclidean space. The basic idea here is to shrink the ellipsoid into a point and expand each superquadric into a new offset surface with closed-form parametric expression. The solutions for detecting relative positions between a point and a general convex differentiable parametric surface in both 2D and 3D are derived, leading to an algorithm for exact collision detection. To compare between exact and inexact algorithms, an accuracy metric is introduced based on the Principal Kinematic Formula (PKF). The proposed algorithm is then compared with existing wellknown algorithms: Gilbert-Johnson-Keerthi (GJK) and Algebraic Separation Conditions (ASC). The results show that the proposed algorithm performs competitively with these efficient checkers.

The concepts of Fisher Information matrix and covariance are generalized to the setting of probability densities on spheres and rotation groups, and inequalities relating these quantities are derived. Probability density functions on these spaces arise in various scenarios in the fields of structural biology, robotics, and computer vision. The approach taken is to first derive matrix generalizations of Wirtinger's inequality for tori and spheres and generalize these to rotation groups. Then new inequalities are derived that relate the covariances of probability density functions on spheres and rotation groups with their Fisher information. These inequalities are different than the Cramér-Rao bound, and can be used to estimate the rate of increase of the entropy of a diffusion process.

Signal alignment has become a popular problem in robotics due in part to its fundamental role in action recognition. Currently, the most successful algorithms for signal alignment are Dynamic Time Warping (DTW) and its variant `Fast' Dynamic Time Warping (FastDTW). Here we introduce a new framework for signal alignment, namely the Globally Optimal Reparameterization Algorithm (GORA). We review the algorithm's mathematical foundation and provide a numerical verification of its theoretical basis. We compare the performance of GORA with that of the DTW and FastDTW algorithms, in terms of computational efficiency and accuracy in matching signals. Our results show a significant improvement in both speed and accuracy over the DTW and FastDTW algorithms and suggest that GORA has the potential to provide a highly effective framework for signal alignment and action recognition.

Assessing preferred relative rigid-body position and orientation is important in the description of biomolecular structures (such as proteins) and their interactions. For that purpose, techniques from the kinematics community are often used. In this paper, we review parameterization methods that are widely used to describe relative rigid body motions (in particular, orientations). Then we present the extended and updated review of a `symmetrical parameterization' which was newly introduced in the kinematics community. This parameterization is useful in describing the relative biomolecular rigid body motions, where the parameters are symmetrical in the sense that the subunits of a complex biomolecular structure are described in the same way for the corresponding motion and its inverse. The properties of this new parameterization, singularity analysis and inverse kinematics, are also investigated in more detail. Finally the parameterization is applied to real biomolecular structures to show the efficacy of the symmetrical parameterization in the field of computational structural biology.

The hand-eye calibration problem was first formulated decades ago and is widely applied in robotics, image guided therapy, etc. It is usually cast as the “AX = XB” problem where the matrices A, B, and X are rigid body transformations in SE(3). Many solvers have been proposed to recover X given data streams {Ai} and {Bi} with correspondence. However, exact correspondence might not be accessible in the real world due to the asynchronous sensors and missing data, etc. A probabilistic approach named “Batch method” was introduced in previous research of our lab, which doesn't require a prior knowledge of the correspondence between the two data streams {Ai} and {Bj}. Analogous to non-probabilistic approaches which require data selection to filter out ill-conditioned data pairs, the Batch method has restrictions on the data set {Ai} and {Bj} that can be used. We propose two new probabilistic approaches built on top of the Batch method by giving new definitions of the mean on SE(3), which alleviate the restrictions on the data set and significantly improve the calibration accuracy of X.

Robotic-assisted catheter insertion is becoming increasingly popular due to its potential applications including cardiac catheterization. Typically, catheters are tracked during insertion procedures to verify the location of the tip relative to anatomy or features of interest. To this end, many catheter tracking systems have been proposed in the literature. Current approaches such as visual servoing are computationally intensive and sometimes require harmful ionizing radiation (X-rays) for tip localization. Conversely, other approaches use 3D ultrasound probes which can be prohibitively expensive. In contrast, we propose an ultrasound-enabled robotic catheter tracking system that uses a 2D ultrasound probe and an active piezoelectric element to track the tip of a catheter. This approach has the potential to guide catheters from initial insertion, in a vein of the groin, to final placement at a target area inside of the heart. During the tracking process, no information from the ultrasound image is necessary; however, this information can be used to help clinicians guide the catheter or to perform diagnostic procedures. In this paper, we outline this procedure by first discussing the individual components of the system and then by describing our methodology for tracking the catheter tip. Next, we simulate the system in ROS to test its effectiveness, and finally we experimentally verify that a robotic arm equipped with a 2D ultrasound probe can track a catheter in a multi-vein phantom. Furthermore, the data collected during tracking can be used to virtually reconstruct the 3D structure of veins while tracking.

Cryo-Electron Microscopy (EM) and Small Angle X-ray Scattering (SAXS) are two different data acquisition modalities often used to glean information about the structure of large biomolecular complexes in their native states. A SAXS experiment is generally considered fast and easy but unveiling the structure at very low resolution, whereas a cryo-EM experiment needs more extensive preparation and post-acquisition computation to yield a 3D density map at higher resolution. In certain applications, one may need to verify if the data acquired in the SAXS and cryo-EM experiments correspond to the same structure (e.g., prior to reconstructing the 3D density map in EM). In this paper, a simple and fast method is proposed to verify the compatibility of the SAXS and EM experiments. The method is based on averaging the 2D correlation of EM images and the Abel transform of the SAXS data. The results are verified on simulations of conformational states of large biomolecular complexes.

Ultrasound imaging can be an advantageous imaging modality for image guided surgery. When using ultrasound imaging (or any imaging modality), calibration is important when more advanced forms of guidance, such as augmented reality systems, are used. There are many different methods of calibration, but the goal of each is to recover the rigid body transformation relating the pose of the probe to the ultrasound image frame. This paper presents a unified algorithm that can solve the ultrasound calibration problem for various calibration methodologies. The algorithm uses gradient descent optimization on the Euclidean Group. It can be used in real time, also serving as a way to update the calibration parameters on-line. We also show how filtering, based on the theory of invariants, can further improve the online results. Focusing on two specific calibration methodologies, the AX = XB problem and the BX-1p problem, we demonstrate the efficacy of the algorithm in both simulation and experimentation.

For the case of an exact set of compatible A's and B's with known correspondence, the AX=XB problem was solved decades ago. However, in many applications, data streams containing the A's and B's will often have different sampling rates or will be asynchronous. For these reasons and the fact that each stream may contain gaps in information, methods that require minimal a priori knowledge of the correspondence between A's and B's would be superior to the existing algorithms that require exact correspondence. We present an information-theoretic algorithm for recovering X from a set of A's and a set of B's that does not require a priori knowledge of correspondences. The algorithm views the problem in terms of distributions on the group SE(3), and minimizing the Kullback-Leibler divergence of these distributions with respect to the unknown X. This minimization is performed by an efficient numerical procedure that reliably recovers an unknown X.

In single-particle electron microscopy (EM), multiple micrographs of identical macromolecular structures or complexes are taken from various viewing angles to obtain a 3D reconstruction. A high-quality EM reconstruction typically requires several thousand to several million images. Therefore, an automated pipeline for performing computations on many images becomes indispensable. In this paper, we propose a modified cross-correlation method to align a large number of images from the same class in single-particle electron microscopy of highly nonspherical structures, and show how this method fits into a larger automated pipeline for the discovery of 3D structures. Our modification uses a probability density in full planar position and orientation, akin to the pose densities used in Simultaneous Localization and Mapping (SLAM) and Assembly Automation. Using this alignment and a subsequent averaging process, high signal-to-noise ratio (SNR) images representing each class of viewing angles are obtained for reconstruction algorithms. In the proposed method, first we coarsely align projection images, and then realign the resulting images using the cross correlation (CC) method. The coarse alignment is obtained by matching the centers of mass and the principal axes of the images. The distribution of misalignment in this coarse alignment is estimated using the statistical properties of the additive background noise. As a consequence, the search space for realignment in the CC method is reduced. Additionally, in order to overcome the false peak problems in the CC, we use artificially blurred images for the early stage of the iteration and segment the intermediate result from every iteration step. The proposed approach is demonstrated on synthetic noisy images of GroEL/ES.

Osteolysis is a debilitating condition that can occur behind the acetabular component of total hip replacements due to wear of the polyethylene liner. Conventional treatment techniques suggest replacing the component, while less-invasive approaches attempt to access and clean the lesion through the screw holes in the component. However, current rigid tools have been shown to access at most 50% of the lesion. Using a recently developed dexterous manipulator, we have adapted a group-theoretic convolution framework to define the manipulator's workspace and its ability to fully explore a lesion. We compared this with the experimental exploration of a printed model of the lesion. This convolution approach successfully contains the experimental results and shows over 98.8% volumetric coverage of a complex lesion. The results suggest this manipulator as a possible solution to accessing much of the area unreachable to the conventional less-invasive technique.

The AX = XB sensor calibration problem must often be solved in image guided therapy systems, such as those used in robotic surgical procedures. In this problem, A, X, and B are homogeneous transformations with A and B acquired from sensor measurements and X being the unknown. It has been known for decades that this problem is solvable for X when a set of exactly measured A's and B's, in a priori correspondence, is given. However, in practical problems, the data streams containing the A' and B's will be asynchronous and may contain gaps (i.e., the correspondence is unknown, or does not exist, for the sensor measurements) and temporal registration is required. For the AX = XB problem, an exact solution can be found when four independent invariant quantities exist between two pairs of A's and B's. We formally define these invariants, reviewing and elaborating results from classical screw theory. We then illustrate how they can be used, with sensor data from multiple sources that contain unknown or missing correspondences, to provide a solution for X.

This work presents a novel test-bed design for demonstrating techniques for team repair in modular robotic systems. The advantages of using modular and team repairable robots are discussed and theoretical constraints for creating a system capable of team repair are enumerated. These constraints are used to develop the Hex-DMR (Hexagonal Distributed Modular Robot) system which centers on a unique repair scheme based on modular components. The proposed system is demonstrated first with computer simulations, which outline the environment navigation scheme and team operation dynamics, and then with a physical prototype, with which a simple repair maneuver is shown.

This paper presents M3Express (Modular-Mobile-Multirobot), a new design for a low-cost modular robot. The robot is self-mobile, with three independently driven wheels that also serve as connectors. The new connectors can be automatically operated, and are based on stationary magnets coupled to mechanically actuated ferromagnetic yoke pieces. Extensive use is made of plastic castings, laser cut plastic sheets, and low-cost motors and electronic components. Modules interface with a host PC via Bluetooth®radio. An off-board camera, along with a set of modules and a control PC form a convenient, low-cost system for rapidly developing and testing control algorithms for modular reconfigurable robots. Experimental results demonstrate mechanical docking, connector strength, and accuracy of dead reckoning locomotion.

We propose a new method for sampling the rotation group that involves decomposing it into identical Voronoi cells centered on rotational symmetry operations of the Platonic solids. Within each cell, Cartesian grids in exponential coordinates are used to achieve almost-uniform sampling at any level of resolution, without having to store large numbers of coordinates, and without requiring sophisticated data structures. We analyze the shape of these cells, and explain how this new method can be used in the context of conformational searches in the fields of Robotics and Structural Biology.

Information Theory is concerned with the reliable transmission of information through noisy environments. This relates to communicating agents, as well as one agent communicating with the environment by taking measurements (e.g., robotic sensing). Typically information theory is formulated in the context of probability on either discrete spaces or continuous Euclidean spaces in which the operation of addition makes sense. Some have extended information theory techniques to differential geometric settings. However, only in the context of group theory can the concept of addition be replaced in a meaningful way with a group operation. This paper presents concepts of information theory on Lie groups developed by the author, and illustrates their application to mobile robotics problems. In particular, the concepts of Shannon entropy, Kullback-Leibler divergence, the Cramér-Rao bound for pose data are developed, and some theorems about their properties are proved. It is also illustrated how these concepts might be integrated into pose estimation, localization, and odor-plume source detection.

A new self-reconfigurable robot is presented. The robot is a hybrid chain/lattice design with several novel features. An active mechanical docking mechanism provides inter-module connection, along with optical and electrical interface. The docking mechanisms function additionally as driven wheels. Internal slip rings provide unlimited rotary motion to the wheels, allowing the modules to move independently by driving on flat surfaces, or in assemblies negotiating more complex terrain. Modules in the system are mechanically homogeneous, with three identical docking mechanisms within a module. Each mechanical dock is driven by a high torque actuator to enable movement of large segments within a multi-module structure, as well as low-speed driving. Preliminary experimental results demonstrate locomotion, mechanical docking, and lifting of a single module.

This paper presents an autonomous self-replicating robot consisting of four low-complexity modules. The entire system is composed of a parent robot, four unassembled modules provided as resources, and an environment where the self-replication takes place. The parent robot grows itself by attaching the resource modules onto itself until it doubles its physical size, and then splits in the middle thereby returning the parent to its original state and producing a daughter robot. We call these processes expansion and separation, respectively. The environment plays a passive role as a catalyst that helps generating a spiral trajectory for the parent robot and does not hold any information about the resource modules. To assess the physical changes made by self-replication, structural and informational complexities associated with the robotic system and the self-replication process are quantified and compared to previous prototypes.

Flexible needles with bevel tips are being developed as useful tools for minimally invasive surgery and percutaneous therapy. When such a needle is inserted into soft tissue, it bends due to the asymmetric geometry of the bevel tip. This insertion with bending is not completely repeatable. We characterize the deviations in needle tip pose (position and orientation) by performing repeated needle insertions into artificial tissue. The base of the needle is pushed at a constant speed without rotating, and the covariance of the distribution of the needle tip pose is computed from experimental data. We develop the closed-form equations to describe how the covariance varies with different model parameters. We estimate the model parameters by matching the closed-form covariance and the experimentally obtained covariance. In this work, we use a needle model modified from a previously developed model with two noise parameters. The modified needle model uses three noise parameters to better capture the stochastic behavior of the needle insertion. The modified needle model provides an improvement of the covariance error from 26.1% to 6.55%.

A problem associated with motion planning for the assembly of individual modules in a new self-reconfigurable modular robotic system is presented. Modules of the system are independently mobile and can be driven on flat surfaces in a similar fashion to the classic kinematic cart. This problem differs from most nonholonomic steering problems because of an added constraint on one of the internal states. The constraint properly aligns the docking mechanism, allowing modules to connect with one another along wheel surfaces. This paper presents an initial method for generating trajectories and control inputs that allow module assembly. It also provides an iterative method for locally optimizing a nominal control function using weighted perturbation functions, while preserving the final pose and internal states.

A set of modular components is presented for use in reconfigurable robots. The proposed architecture for large systems built with these components is a number of active mobile devices operating within a larger, passive structural grid. The mobile devices and grid are constructed from the same class of heterogeneous modular components. The components themselves are designed for low-cost simple fabrication methods. Results from some experimental demonstrations are presented.

In this paper, we propose an approach for the accurate rotation of a digital image using Hermite expansions. This exploits the fact that if a 2-D continuous bandlimited Hermite expansion is rotated, the resulting function can be expressed as a Hermite expansion with the same bandlimit. Furthermore, the Hermite coefficients of the initial 2-D expansion and the rotated expansion are mapped through an invertible linear relationship. Two efficient methods to compute the mapping between Hermite coefficients during rotation are proposed. We also propose a method for connecting the Hermite expansion and a discrete image. Using this method, we can obtain the Hermite expansion from a discrete image and vice versa. Combining these techniques, we propose new methods for the rotation of discrete images. We assess the accuracy of our methods and compare them with an existing FFT-based method implementing three shears. We find that the method proposed here consistently has better accuracy than the FFT-based method.

In this paper, we propose an algorithm for lossless conversion of data between Cartesian and polar coordinates, when the data is sampled from a 2-D real-valued function (a mapping: R2 --> R) expressed as a particular kind of truncated expansion. We use Laguerre functions and the Fourier basis for the polar coordinate expression. Hermite functions are used for the Cartesian coordinate expression. A finite number of coefficients for the truncated expansion specifies the function in each coordinate system. We derive the relationship between the coefficients for the two coordinate systems. Based on this relationship, we propose an algorithm for lossless conversion between the two coordinate systems. Resampling can be used to evaluate a truncated expansion on the complementary coordinate system without computing a new set of coefficients. The resampled data is used to compute the new set of coefficients to avoid the numerical instability associated with direct conversion of the coefficients. In order to apply our algorithm to discrete image data, we propose a method to optimally fit a truncated expression to a given image. We also quantify the error that this filtering process can produce. Finally the algorithm is applied to solve the polar-Cartesian interpolation problem.

This paper presents a computational method to generate a sequence of uniformly interpolated elements between an arbitrary pair of elements in the special Euclidean group, SE(3). The significance of the proposed method is that the uniformity of the distribution of sequential frames on SE(3) is guaranteed through a metric defined for rigid body motion. The necessity of this computation can be often found in robotics applications. The computational method will be adapted to a kinematic synthesis problem for a class of robotic manipulators as an example application. A "discretely actuated robotic manipulator (D-ARM)", is any member of a class of robotic manipulators powered by actuators such as solenoids that have only discrete stable positional states. One of the most significant kinematic phenomena of D-ARMs is the discreteness of both input range and end-effector frames. The conducted simulations demonstrate the feasibility of the synthesis procedure with the proposed frame interpolation method

Error propagation in hybrid manipulators is addressed here within a rigorous mathematical framework. Understanding how errors propagate in serial manipulators and cascades of platform manipulators is important for developing better designs. In this paper we show that errors propagate by convolution on the Euclidean motion group, SE (3). When local errors are small, they can be described well as distributions on the Lie algebra se(3). We show how the concept of a highly concentrated Gaussian distribution on SE(3) is equivalent to one on se(3). Numerical examples illustrate that convolution and covariance propagation provide the same answers for small errors

A "discretely actuated robotic manipulator", or "D-ARM", is any member of a class of robotic manipulators powered by actuators such as solenoids that have only discrete stable positional states. One of the most significant kinematic phenomena of D-ARMs is the discreteness of both input range and end-effector frames. The main characteristics of D-ARMs are: stability at each state without the need for a feedback loop; high task repeatability; mechanism simplicity; minimal supporting devices; low cost. These are strong advantages for manufacturing automation; mobile robots; space structures; micro/nano mechanisms. The proposed design method is based on an incremental kinematic synthesis of a base-line manipulator using a numerically obtained Jacobian matrix and its generalized inverse matrix. The significance of this method is that it deals with a set of inverse kinematic problems on the special Euclidean group in three space, SE(3), instead of one on the Euclidean space, Ropf3. The conducted simulations demonstrate the feasibility of the synthesis method

A quantity of importance in coherent optical communications is the probability density of a filtered signal in the presence of phase noise (PN). The Fokker-Planck(FP) approach has been recognized as a rigorous way to describe these statistical properties. However, computational difficulties in solving these FP equation shave prevented their widespread application. In this paper, we present a new and simple computational solution method based on techniques from noncommutative harmonic analysis on motion groups. This proposed method can easily solve all the PN FP equations with any kind of intermediate frequency filter. We also present a new derivation of PN FP equations from the viewpoint of stochastic processes.

Error propagation on the Euclidean motion group arises in a number of areas such as errors that accumulate from the base to the distal end of manipulators. We address error propagation in rigid-body poses in a coordinate-free way, and explain how this differs from other approaches proposed in the literature. In this paper, we show that errors propagate by convolution on the Euclidean motion group, SE(3). When local errors are small, they can be described well as distributions on the Lie algebra se(3). We show how the concept of a highly concentrated Gaussian distribution on SE(3) is equivalent to one on se(3). We also develop closure relations for these distributions under convolution on SE(3). Numerical examples illustrate how convolution is a valuable tool for computing the propagation of both small and large errors

This paper describes a new algorithm for the efficient mass-matrix inversion of serial manipulators. Whereas several well-known O(n) algorithms already exist, our presentation is an alternative and completely different formulation that builds on Fixman’s theorem from the polymer physics literature. The main contributions here are therefore adding a new perspective to the manipulator dynamics literature and providing an alternative to existing algorithms. The essence of this theory is to consider explicitly the band-diagonal structure of the inverted mass matrix of a manipulator with no constraints on link length, offsets or twist angles, and then build in constraints by appropriate partitioning of the inverse of the unconstrained mass matrix. We present the theory of the partitioned mass matrix and inverse of the mass matrix for serial revolute manipulators. The planar N-link manipulator with revolute joints is used to illustrate the procedure. Numerical results verify the O(n) complexity of the algorithm. Exposure of the robotics community to this approach may lead to new ways of thinking about manipulator dynamics and control.

Fine needles facilitate diagnosis and therapy because they enable minimally invasive surgical interventions. This paper formulates the problem of steering a very flexible needle through firm tissue as a nonholonomic kinematics problem, and demonstrates how planning can be accomplished using diffusion-based motion planning on the Euclidean group, SE(3). In the present formulation, the tissue is treated as isotropic and no obstacles are present. The bevel tip of the needle is treated as a nonholonomic constraint that can be viewed as a 3D extension of the standard kinematic cart or unicycle. A deterministic model is used as the starting point, and reachability criteria are established. A stochastic differential equation and its corresponding Fokker-Planck equation are derived. The Euler-Maruyama method is used to generate the ensemble of reachable states of the needle tip. Inverse kinematics methods developed previously for hyper-redundant and binary manipulators that use this probability density information are applied to generate needle tip paths that reach the desired targets.

When inserted into soft tissues, flexible needles with bevel tips have been shown experimentally to follow a path of constant curvature in the direction of the bevel. By controlling 2 degrees of freedom at the needle base (bevel direction and insertion distance), these needles can be steered around obstacles to reach targets inaccessible to rigid needles. Motion planning for needle steering is a type of nonholonomic planning for a Dubins car with no reversal. We develop a motion planning algorithm based on dynamic programming where the path of the needle is uncertain due to uncertainty in tissue properties, needle mechanics, and interaction forces. The algorithm computes a discrete control sequence of insertions and direction changes so the needle reaches a target in an imaging plane while minimizing expected cost due to insertion distance, direction changes, and obstacle collisions. We efficiently sample the state space of needle tip positions and orientations and define bounds on the errors due to discretization. We formulate the motion planning problem as a Markov decision process (MDP) and use infinite horizon dynamic programming to compute an optimal control sequence. We first apply the method to the deterministic motion case where the needle precisely follows a path of constant curvature and then to the uncertain motion case where state transitions are defined by a probability distribution. Our implementation generates motion plans for bevel-tip needles that reach targets inaccessible to rigid needles and demonstrates that accounting for uncertainty can lead to significantly different motion plans.

In traditional trajectory planning it is usually assumed that the mean path of an ensemble of open-loop trajectories is the same as would be obtained if no noise were present. However, even zero-mean noise tends to cause the mean trajectory to deviate from the nominal one. This paper introduces a stochastic model-based motion planning method to compensate for this bias. An implementation for nonholonomic mobile robots based on the kinematic cart model is provided. The examples show that the proposed method takes full advantage of the results of existing optimal trajectory planning methods, and makes the resulting mean trajectory conform to the pre-selected nominal trajectory. As a result, the average amount of online trajectory correction required of a controller is minimized.

This paper addresses the issue of obtaining the optimal rotation to match two functions on the sphere by minimizing the squared error norm and the Kullback–Leibler information criteria. In addition, the accuracy in terms of the band-limited approximations in both cases are also discussed. Algorithms for fast and accurate rotational matching play a significant role in many fields ranging from computational biology to spacecraft attitude estimation. In electron microscopy, peaks in the so-called "rotation function" determine correlations in orientation between density maps of macromolecular structures when the correspondence between the coordinates of the structures is not known. In X-ray crystallography, the rotational matching of Patterson functions in Fourier space is an important step in the determination of protein structures. In spacecraft attitude estimation, a star tracker compares observed patterns of stars with rotated versions of a template that is stored in its memory. Many algorithms for computing and sampling the rotation function have been proposed over the years. These methods usually expand the rotation function in a bandlimited Fourier series on the rotation group. In some contexts the highest peak of this function is interpreted as the optimal rotation of one structure into the other, and in other contexts multiple peaks describe symmetries in the functions being compared. Prior works on rotational matching seek to maximize the correlation between two functions on the sphere. We also consider the use of the Kullback–Leibler information criteria. A gradient descent algorithm is proposed for obtaining the optimal rotation, and a measure is defined to compare the convergence of this procedure applied to the maximal correlation and Kullback–Leibler information criteria.

Hyper-redundant manipulators have a large number of redundant degrees of freedom. They have been recognized as a means to improve manipulator performance in complex and unstructured environments. However, the high degree of redundancy also causes difficulty in the calculation of workspaces and inverse kinematics. This paper develops a diffusion-based algorithm for workspace generation of hyper-redundant manipulators. This algorithm makes the workspace generation problem as simple as solving a diffusion equation which has an explicit solution. This diffusion equation is a partial differential equation defined on the motion group SE(N), and describes the evolution of the workspace density function, depending on manipulator length and kinematic properties. This paper also solves the inverse kinematics problem in an elegant way by dividing the manipulator into virtual segments and cascading the corresponding workspace densities generated by the diffusion equation.

In this paper, dead-reckoning error in mobile robots is studied in the context of several different models. These models are derived first in the form of stochastic differential equations (SDEs). Corresponding Fokker-Planck equations are derived, and desired probability density functions (PDFs) of robot pose are computed by using the Fourier transform for SE(2).

This paper describes a unique robotics project, Comprehensive Access to Printed Materials (CAPM), within the context of libraries. As libraries provide a growing array of digital library services and resources, they continue to acquire large quantities of printed material. This combined pressure of providing electronic and print-based resources and services has led to severe space constraints for many libraries, especially academic research libraries. Consequently, many libraries have built or plan to build off-site shelving facilities to accommodate printed materials. An autonomous mobile robotic library system has been developed to retrieve items from bookshelves and carry them to scanning stations located in the off-site shelving facility. In subsequent stages, remote users will be able to trigger this process through a web interface in order to achieve real-time browsing of printed materials. Enhanced commercial robot systems are used in this project. The developments of the robot design, control systems, simulations, experiments and results are presented.

Motivated by a physical phenomenon, the diffusion process, this paper develops a diffusion-based algorithm for workspace generation of highly articulated manipulators. This algorithm makes the workspace generation problem as simple as solving a diffusion-type equation which has an explicit solution. This equation is a partial differential equation defined on the motion group and describes the evolution of the workspace density function depending on the manipulator length and kinematic properties. Numerical simulations using this algorithm are also presented.

We develop a methodology for absolute encoding of spherical motion. This is accomplished by painting the surface of a moving sphere in two colors and sensing the color at a finite set of points. We show how point measurements on the sphere can resolve an arbitrary rotation to within a range depending on the number of sensors and the painting of the sphere. These techniques are applied to a prototype. The implementation of this prototype is discussed.

Presents an artificial potential field method for path planning of non-spherical single-body robots. The model simulates steady-state heat transfer with variable thermal conductivity. The optimal path problem is then the same as a heat flow with minimal thermal resistance. The novelty of this technique is that the thermal resistance in the configuration space for all different orientations of the robot can be superimposed. This reduces a search on R/sup n//spl times/SO(n) to one on R/sup n/ followed by a search on SO(n). Examples are presented to demonstrate the approach.

In this paper we develop a correlation method for the template matching problem in pattern recognition which includes translations, rotations, and dilations in a natural way. The correlation method is implemented using Fourier analysis on the “discrete motion group” and fast Fourier transform methods. A brief introduction to Fourier methods on the discrete motion group is given and the efficiency of these methods is discussed. Results of the numerical implementation are given for particular examples.

The concept of a convolution product of real-valued functions on the special Euclidean group is applied to the determination of workspaces of discretely actuated manipulators. If a discretely actuated manipulator has n actuators each with K states, then it can reach K/sup n/ frames in space. Given this exponential growth in the number of reachable frames, brute force representation of discretely actuated manipulator workspaces is not feasible in the highly actuated case. However, by partitioning a discretely actuated manipulator into segments, and approximating the workspace of each segment as a density function on a compact subset of the special Euclidean group, the whole workspace can be approximated as an n-fold convolution of these densities. A numerical approximation of this convolution is presented in this paper that requires O(logn) computation time as compared to the O(K/sup n/) computations required by brute force workspace generation.

In this work, the concept of a convolution product of real-valued functions on the special Euclidean group, SE(D) (which describes all rigid body motions in D-dimensional Euclidean space), is applied to the determination of workspaces of discretely actuated manipulators. These manipulators have a finite number of joint states. If a discretely actuated manipulator consists of P actuated modules, each with K states, then it can reach K/sup p/ frames in space. Given this exponential growth in the number of reachable frames, brute force representation of discretely actuated manipulator workspaces is not feasible in the highly actuated case. However, by partitioning a discretely actuated manipulator into P modules, and approximating the workspace of each module as a density function on a compact subset of the special Euclidean group, the whole workspace can be approximated as an P-fold convolution of these densities. A numerical approximation of this convolution is presented in this paper which is O(P) for fixed taskspace dimension. In the special case when the manipulator is composed of P identical actuated modules, the workspace density for the whole manipulator can be calculated in O(log P) computation time. In either case, the O(K/sup p/) computations required by brute force workspace generation are avoided.

In this paper the problem of dynamic self-reconfiguration of a class of modular robotic systems referred to as metamorphic systems is examined. A metamorphic robotic system is a collection of mechatronic modules, each of which has the ability to connect, disconnect, and climb over adjacent modules. We examine the near-optimal reconfiguration of a metamorphic robot from an arbitrary initial configuration to a desired final configuration. Concepts of distance between metamorphic robot configurations are defined, and shown to satisfy the formal properties of a metric. These metrics, called configuration metrics, are then applied to the automatic self-reconfiguration of metamorphic systems in the case when one module is allowed to move at a time. There is no simple method for computing the optimal sequence of moves required to reconfigure. As a result, heuristics which can give a near optimal solution must be used. We use the technique of simulated annealing to drive the reconfiguration process with configuration metrics as cost functions. The relative performance of simulated annealing with different cost functions is compared and the usefulness of the metrics developed in this paper is demonstrated.

A metamorphic robotic system is a collection of mechatronic modules, each of which has the ability to connect, disconnect, and climb over adjacent modules. A change in the macroscopic morphology results from the locomotion of each module over its neighbors. In this paper, lower and upper bounds are established for the minimal number of moves needed to change such systems from any initial to any final specified configuration. These bounds are functions of initial and final configuration geometry and can be computed very quickly, while solving for the precise number of minimal moves cannot be done in polynomial time. These bounds can be used to 'weed out' and improve inefficient reconfiguration strategies, and provide a benchmark for the evaluation of heuristics in general.

Hyper-redundant manipulators present an alternative to conventional 6 DOF manipulators for inspection, space, and medical applications. The additional degrees of freedom facilitate obstacle avoidance and allow tasks to be performed even if some of the actuators fail. In this paper the authors consider hyper-redundant manipulators that are actuated discretely, e.g. using two-state actuators or motors with finite resolution. The inverse kinematics problem for a discretely actuated manipulator is intrinsically different from the one for its continuously actuated counterpart. The authors present a framework for the discussion of the discretely actuated case and propose an algorithm for the inverse kinematics. The algorithm generates solutions in linear time with respect to the number of manipulator actuators, as opposed to the exponential time required by brute force search.

Binary actuators have only two discrete states (denoted '0' and '1'), both of which are stable without feedback. As a result, manipulators built with binary actuators have a finite number of states. Compared to a manipulator built with continuous actuators, a binary manipulator provides good performance, and is also relatively inexpensive. However, the number of states of a binary manipulator grows exponentially with the number of actuators. While this makes the calculation of its inverse kinematics quite difficult, the discrete nature of a binary manipulator makes it possible to compute its forward kinematics more efficiently than for a continuously actuated manipulator. By pre-computing all possible configurations of each module of a binary manipulator (a finite and usually small number) it is possible to compute the forward kinematics from a set of joint parameters without using any transcendental functions.

Binary manipulators are powered by actuators which have only two stable states. Therefore, they can reach only a discrete (but possibly large) number of locations. Compared to a manipulator built with continuous actuators, a binary manipulator provides reasonable performance, and is relatively inexpensive (up to an order of magnitude cheaper). The number of states of a binary manipulator grows exponentially with the number of actuators. This makes the calculation of its inverse kinematics quite difficult. This paper presents a combinatorial method for computing the inverse kinematics of a binary manipulator that reduces the search space to a manageable size. It also creates reasonably smooth motions that follow a specified trajectory accurately (in both position and orientation), despite the discrete nature of binary actuation.

In this paper we examine the problem of dynamic self-reconfiguration of a class of modular robotic systems referred to as metamorphic systems. A metamorphic robotic system is a collection of mechatronic modules, each of which has the ability to connect, disconnect, and climb over adjacent modules. We define a concept of distance between metamorphic robot configurations which satisfies the formal properties of a metric. This metric, called the optimal assignment metric, is then applied to the automatic self-reconfiguration of metamorphic systems from any initial to any final specified configuration. The technique of simulated annealing is used to drive the re-configuration process with the optimal assignment metric as the cost function. By driving the distance between the present and the goal configuration to zero, sequences of configurations are generated.

Binary actuators have only two discrete states, both of which are stable without feedback. As a result, manipulators built with binary actuators have a finite number of states. The major benefits of binary actuation are that extensive feedback control is not required, task repeatability can be very high, and two-state actuators are generally very inexpensive, resulting in low cost robotic mechanisms. These manipulators therefore have great potential for use in the service sector, where the cost of standard, high performance, robotic manipulators is often difficult to justify. A binary manipulator by contrast, provides good performance, and is also relatively inexpensive. The most difficult challenge with a binary manipulator is to control it efficiently. Given that the number of configurations attainable by binary manipulators grows expotentially in the number of actuated degrees of freedom, calculation of inverse kinematics by direct enumeration of joint states and calculation of forward kinematics is not feasible in the highly actuated case. This paper presents an efficient method for performing binary manipulator inverse kinematics based on a continuum approach.

This paper considers the kinematics of hyper-redundant (or "serpentine") robot locomotion over uneven solid terrain, and presents algorithms to implement a variety of "gaits". The analysis and algorithms are based on a continuous backbone curve model which captures the robot's macroscopic geometry. Two classes of gaits, based on stationary waves and traveling waves of mechanism deformation, are introduced for hyper-redundant robots of both constant and variable length. We also illustrate how the locomotion algorithms can be used to plan the manipulation of objects which are grasped in a tentacle-like manner. Several of these gaits and the manipulation algorithm have been implemented on a 30 degree-of-freedom hyper-redundant robot. Experimental results are presented to demonstrate and validate these concepts and our modeling assumptions.

"Hyper-redundant" robots have a very large or infinite degree of kinematic redundancy. This paper develops new methods for determining "optimal" hyper-redundant manipulator configurations based on a continuum formulation of kinematics. This formulation uses a backbone curve model to capture the robot's essential macroscopic geometric features. The calculus of variations is used to develop differential equations, whose solution is the optimal backbone curve shape. We show that this approach is computationally efficient on a single processor, and generates solutions in O(1) time for an N degree-of-freedom manipulator when implemented in parallel on O(N) processors. For this reason, it is better suited to hyper-redundant robots than other redundancy resolution methods. Furthermore, this approach is useful for many hyper-redundant mechanical morphologies which are not handled by known methods.

A metamorphic robotic system is a collection of mechatronic modules, each of which has the ability to connect, disconnect, and climb over adjacent modules. A change in the macroscopic morphology results from the locomotion of each module over its neighbors. That is, a metamorphic system can dynamically self-reconfigure. Metamorphic systems can therefore be viewed as a large swarm of physically connected robotic modules which collectively act as a single entity. What separates metamorphic systems from other reconfigurable robots is that they possess all of the following properties: (1) self-reconfigurability without outside help; (2) a large number of homogeneous modules; and (3) physical constraints ensure contact between modules. In this paper, the kinematic constraints governing a particular metamorphic robot are addressed.>

Traditionally, kinematics and motion planning paradigms have addressed robots with continuous range-of-motion actuators (e.g. motors, hydraulic cylinders, etc.). Unlike motors, binary actuators have only two discrete states, both of which are stable. As a result, binary manipulators (i.e. those which are actuated with binary actuators) have a finite number of states. Major benefits of binary actuation are that extensive feedback control is not required, task repeatability can be very high, and two-state actuators are generally very inexpensive (e.g. solenoids, pneumatic cylinders, etc.), thus resulting in low cost robots. This paper presents a new paradigm in robotics based on binary actuation, and develops algorithms for the optimal design of binary manipulators for pick-and-place tasks.>

This paper presents novel and efficient kinematic modeling techniques for "hyper-redundant" robots. This approach is based on a "backbone curve" that captures the robot's macroscopic geometric features. The inverse kinematic, or "hyper-redundancy resolution," problem reduces to determining the time varying backbone curve behavior. To efficiently solve the inverse kinematics problem, the authors introduce a "modal" approach, in which a set of intrinsic backbone curve shape functions are restricted to a modal form. The singularities of the modal approach, modal non-degeneracy conditions, and modal switching are considered. For discretely segmented morphologies, the authors introduce "fitting" algorithms that determine the actuator displacements that cause the discrete manipulator to adhere to the backbone curve. These techniques are demonstrated with planar and spatial mechanism examples. They have also been implemented on a 30 degree-of-freedom robot prototype.>

Hyper-redundant, or snakelike, manipulators have a very large number of actuatable degrees of freedom. This paper develops an efficient formulation of approximate hyper-redundant manipulator dynamics. The most efficient methods for representing manipulator dynamics in the literature require serial computations proportional to the number of degrees of freedom and are not fully parallelizable. For hyper-redundant manipulators, which may have tens, hundreds, or thousands of actuators, these formulations preclude real time implementation. This paper therefore looks at the mechanics of hyper-redundant manipulators from the point of view of an approximation to an infinite degree-of-freedom problem. The dynamics for this infinite dimensional case is developed. The approximate dynamics of actual hyper-redundant manipulators is then reduced to a problem which is O(1) in the number of serial computations, i.e., the algorithm is O(n) in the total number of computations, but these computations are completely parallelizable. Applications to practical computed torque control schemes are demonstrated.

Hyper-redundant robots have a very large or infinite degree of kinematic redundancy. This paper formulates generalized resolved rate methods for solving hyper-redundant manipulator inverse kinematics using a backbone curve. These methods are applicable even when explicit representation of the backbone curve intrinsic geometry cannot be written in closed form. Problems of end-effector trajectory tracking and singularity analysis which were previously intractable can now be handled easily. Examples include configurations generated using the calculus of variations. Also, the method is naturally parallelizable for fast digital and/or analog computation.

Hyper-redundant robots have a very large or infinite degree of kinematic redundancy. The authors develop methods for determining the optimal configurations which satisfy task constraints while minimizing a weighted measure of mechanism bending and extension. These methods are based on a continuous backbone curve which captures the robot's essential macroscopic geometric features. The calculus of variations is used to develop differential equations whose solution is the optimal backbone curve shape. The optimal distribution of frames along the backbone curve is also considered.>

A method is presented for generating inverse kinematic solutions for hyper-redundant manipulators of fixed or variable length. This method uses a continuous backbone curve to capture the macroscopic geometric features of the manipulator. The inverse kinematics of the backbone curve can be used directly to specify the geometry of a wide variety of hyper-redundant manipulator morphologies. The hyper-redundant manipulators are broken nonredundant segments which have closed form inverse kinematic solutions. The kinematic constraints for each segment are specified independently by the backbone curve, and the kinematics of the total manipulator can therefore be solved in parallel. The method is demonstrated with planar and spatial variable geometry truss manipulators.>

Simple schemes for analyzing the kinematics of hyper-redundant robot locomotion over solid terrain are considered. These schemes are based on the concepts of amplitude varying and traveling wave gaits, which are idealized models of inchworm and caterpillar locomotion. The kinematics of these gaits is formulated for hyper-redundant robots of both constant and variable length for locomotion over both flat and irregular terrain. Hyper-redundant locomotion concepts are applied to a novel grasping and fine manipulation scheme based on a grasping wave.>

Hyper-redundant robots have a large or infinite number of degrees of freedom. Such robots are analogous to snakes or tentacles and are useful for operation in highly constrained environments and novel forms of locomotion. The paper reviews newly developed methods for the kinematic analysis of hyper-redundant manipulators. These methods can be applied to a wide variety of hyper-redundant morphologies and lead to very efficient inverse kinematic, path planning, obstacle avoidance, locomotion, and grasping schemes. It also reviews the design and implementation of a planar 30 degree of freedom variable geometry truss hyper-redundant robot.>

Novel kinematic algorithms for implementing planar hyperredundant manipulator obstacle avoidance is presented. Unlike artificial potential field methods, the method outlined is strictly geometric. Tunnels are defined in a workspace in which obstacles are presented. Methods of differential geometry are then used to formulate equations which guarantee that sections of the manipulator are confined to the tunnels and therefore avoid the obstacles. A general formulation is given with examples to illustrate this approach.>