Dexterous manipulation of objects through fine control of physical contacts is essential for many important tasks of daily living. A fundamental ability underlying fine contact control is compliant control, i.e., controlling the contact forces while moving. For robots, the most widely explored approaches heavily depend on models of manipulated objects and expensive sensors to gather contact location and force information needed for real-time control. The models are difficult to obtain, and the sensors are costly, hindering personal robots' adoption in our homes and businesses. This study performs model-free reinforcement learning of a normal contact force controller on a robotic manipulation system built with a low-cost, information-poor tactile sensor. Despite the limited sensing capability, our force controller can be combined with a motion controller to enable fine contact interactions during object manipulation. Promising results are demonstrated in non-prehensile, dexterous manipulation experiments.

Narrow passages in free space pose great challenges to many sampling-based motion planners. In problems with high-dimensional configuration spaces (C-spaces), narrow passages in free space (C-free) can be hard to find and navigate and, sometimes, even counterintuitive. In this article, we present an algorithm to construct cones of available instantaneous velocities (“free velocity cones” or, briefly, “free cones”) on the boundary of C-free to facilitate finding and navigating narrow passages. This is accomplished by first developing free cones and associated measures of local C-space narrowness for a single rigid link. These results are then extended to kinematic chains (open and closed) of arbitrary degrees of freedom. It turns out that the degeneracy of the free cones dictates the existence of C-space narrow passages, and the locations and orientations of the links in the workspace relate intimately to the corresponding connected component of C-free. This observation leads us to a modified probabilistic roadmap (M-PRM) algorithm and a modified rapidly exploring random vine (M-RRV) algorithm of combining the enumeration of topological components and random sampling of the free cones. Experimental results from applying our algorithms to several challenging examples show that our new algorithms are more efficient than some variants of the PRM algorithms, and several variants of the rapidly exploring random tree (RRT) algorithms, such as RRT-CONNECT and RRV.

Geometric models are crucial for many robotics applications. Current robotic 3D reconstruction systems only focus on specific reconstruction goals which make them hard to adapt to different tasks. In this paper we present a next-best-view framework which allows robots to construct a geometric model incrementally through consecutive sensing actions. Instead of limiting the type and total number of sensors, in each sensing step we evaluate actions from all available sensors and pick the best to execute. Our framework is more comprehensive since the model building process can be designed to best accomplish different tasks. The system has been demonstrated in two experiments on 3D reconstruction and weld seam inspection, yielding promising results.

Due to the limitations of the robotic sensors, during a robotic manipulation task, the acquisition of the object's state can be unreliable and noisy. Combining an accurate model of multi-body dynamic system with Bayesian filtering methods has been shown to be able to filter out noise from the object's observed states. However, efficiency of these filtering methods suffers from samples that violate the physical constraints, e.g., no penetration constraint. In this paper, we propose a Rao-Blackwellized Particle Filter (RBPF) that samples the contact states and updates the object's poses using Kalman filters. This RBPF also enforces the physical constraints on the samples by solving a quadratic programming problem. By comparing our method with methods that does not consider physical constraints, we show that our proposed RBPF is not only able to estimate the object's states, e.g., poses, more accurately but also able to infer unobserved states, e.g., velocities, with higher precision.

Whole body tactile perception via tactile skins offers large benefits for robots in unstructured environments. To fully realize this benefit, tactile systems must support real-time data acquisition over a massive number of tactile sensor elements. We present a novel approach for scalable tactile data acquisition using compressed sensing. We first demonstrate that the tactile data is amenable to compressed sensing techniques. We then develop a solution for fast data sampling, compression, and reconstruction that is suited for tactile system hardware and has potential for reducing the wiring complexity. Finally, we evaluate the performance of our technique on simulated tactile sensor networks. Our evaluations show that compressed sensing, with a compression ratio of 3 to 1, can achieve higher signal acquisition accuracy than full data acquisition of noisy sensor data.

Dynamic system states estimation, such as object pose and contact states estimation, is essential for robots to perform manipulation tasks. In order to make accurate estimation, the state transition model needs to be physically correct. Complementarity formulations of the dynamics are widely used for describing rigid body physical behaviors in the simulation field, which makes it a good state transition model for dynamic system states estimation problem. However, the non-smoothness of complementarity models and the high dimensionality of the dynamic system make the estimation problem challenging. In this paper, we propose a particle filtering framework that solves the estimation problem by sampling the discrete contact states using contact graphs and collision detection algorithms, and by estimating the continuous states through a Kalman filter. This method exploits the piecewise continuous property of complementarity problems and reduces the dimension of the sampling space compared with sampling the high dimensional continuous states space. We demonstrate that this method makes stable and reliable estimation in physical experiments.

Mobile humanoid robots have the capability of accomplishing complex tasks in human dominated environments. In order to execute a task with its arm, a robot needs to place its base reasonably first. In previous work, a positionbased reachability map solved this problem by matching a precomputed inverse kinematics database with discretized versions of the task path. However, its capability is restricted to the end effector with which the database was computed. This paper proposes an orientation-based reachability map which supports on-line end effector frame extensions. The added extension capability enables robots to handle partially constrained task paths with different tool frames, which would be non-trivial for previous methods without recomputing a reachability map. We discuss the differences between the new method and its predecessors, and analyze extension transformation matrix to provide mathematical proof for the extension capability of our reachability map. Our experimental results show that the orientation-based reachability map is as fast as the positionbased reachability map while benefiting from the additional extension capability.

We study the contact-aware state estimation (CASE) problem, i.e., the problem of estimating the state of an object while it is being actively manipulated by a robot. Several researchers have developed particle filters for this problem. They estimate the state (pose and velocity) of manipulated objects, some physical properties (such as mass and shape), and contact information (such as, gain or loss of contact and transitions between sliding and sticking). However, the effects of various contact and noise models, which can have a huge impact on the estimation results, are obfuscated by implementation details. In this paper, we study the CASE problem arising from a simple pushing task with the goal of shedding light on the fundamental contact modeling choices. Specifically, we evaluate four particle filters based upon four probabilistic state transition models generated from a deterministic multibody dynamics models with rigid or compliant contacts, each of which is augmented by one of two different noise models. Comparisons of these state transition models are carried out through the analysis of real and simulated experiments, the results of which, provide guidance to filter designers.

This paper presents a control framework for arm/hand systems aimed at controlling internal forces exchanged between the fingers and the grasped object, and enforcing a compliant behavior in presence of environmental interactions. A dynamic planner computes the motion references for the fingers by using the feedback of the contact forces, while an impedance control, in which dynamic effects exerted by the hand on the wrist are explicitly taken into account, is designed for the arm. The approach is experimentally validated on a 7-DOFs Barrett WAM with a Barrett Hand280.

Model-based approaches to the planning or control of robot locomotion or manipulation requires the solution of complementarity problems that model intermittent contact. Fixed-point iteration is a method of computing fixed points of functions and there are several fixed-point theorems to guarantee the existence of fixed points. With the help of proximal point functions, the complementarity problems that arise in multibody dynamics can be rewritten in a form suitable for solution by a fixed-point iteration method. This fixed-point “prox method” has been popular over the last decades. However, the tuning of the iteration parameter r is difficult, because r affects the convergence of the fixed-point iteration method in ways not understood by current theoretical results. In this paper, we first investigate some factors that affect the choice of r, which further determines the convergence rate. Also we study the loss of accuracy caused by a commonly used relaxation parameter, which is known as “constraint force mixing”.

Abstract Interactive rigid body simulation is an important part of many modern computer tools, which no authoring tool nor game engine can do without. Such high‐performance computer tools open up new possibilities for changing how designers, engineers, modelers and animators work with their design problems. This paper is a self contained state‐of‐the‐art report on the physics, the models, the numerical methods and the algorithms used in interactive rigid body simulation all of which have evolved and matured over the past 20 years. Furthermore, the paper communicates the mathematical and theoretical details in a pedagogical manner. This paper is not only a stake in the sand on what has been done, it also seeks to give the reader deeper insights to help guide their future research .

Contemporary time-stepping methods used in the dynamic simulation of rigid bodies suffer from problems in accuracy, performance, and robustness. Significant allowances for tuning, coupled with careful implementation of a broad phase collision detection scheme is required to make dynamic simulation useful for practical applications. A recently developed formulation method is presented herein that is more robust, and not dependent on broad-phase collision detection or system tuning for its behavior. Several uncomplicated benchmark examples are presented to give an analysis and make a comparison of the new Polyhedral Exact Geometry time-stepping method with the well-known Stewart-Trinkle time-stepping method. The behavior and performance for the two methods are discussed. This includes specific cases where contemporary time-steppers fail, and how they are ameliorated by the new method presented here. The goal of this work is to complete the groundwork for further research into high performance simulation.

In this work, we develop a general solution to a broad class of grasping and manipulation problems that we term as C-SLAM for contact simultaneous localization and modeling, where the robots need to accurately track the motions of the contacted bodies and the locations of contacts, while simultaneously estimating important system parameters, such as body dimensions, masses and friction coefficients between contacting surfaces. Our solution framework is based on a dynamic Bayesian inference framework, and hence, we refer to it as Dynamic Bayesian C-SLAM (DBC-SLAM). DBC-SLAM combines an NCP-based dynamic model with the dynamic Bayesian network, and incorporates model parameter estimation as an intrinsic part of the overall inference procedure. We show two preliminary “proof-of-concept” examples that demonstrate the use of DBC-SLAM in robotic contact tasks.

Opening doors is a fundamental skill for mobile robots operating in human environments. In this paper we present an approach to learn a dynamic model of a door from sensor observations and utilize it for effectively swinging the door open to a desired angle. The learned model enables the realization of dynamic door-opening strategies and reduces the complexity of the door opening task. For example, the robot does not need to maintain a grasp of the handle, which would form a closed kinematic chain. Accordingly, it reduces the degrees of freedom required of the manipulator and facilitates motion planning. Additionally, execution is faster, because the robot merely needs to push the door long enough to achieve the right combination of position and speed such that the door stops at the desired state. Our approach applies Gaussian process regression to learn the deceleration of the door with respect to position and velocity of the door. This model of the dynamics can be easily learned from observing a human teacher or by interactive experimentation.

Advanced grasp control algorithms could benefit greatly from accurate tracking of the object as well as an accurate all-around knowledge of the system when the robot attempts a grasp. This motivates our study of the G-SL(AM)2problem, in which two goals are simultaneously pursued: object tracking relative to the hand and estimation of parameters of the dynamic model. We view the G-SL(AM)2problem as a filtering problem. Because of stick-slip friction and collisions between the object and hand, suitable dynamic models exhibit strong nonlinearities and jump discontinuities. This fact makes Kalman filters (which assume linearity) and extended Kalman filters (which assume differentiability) inapplicable, and leads us to develop a particle filter. An important practical problem that arises during grasping is occlusion of the view of the object by the robot's hand. To combat the resulting loss of visual tracking fidelity, we designed a particle filter that incorporates tactile sensor data. The filter is evaluated off-line with data gathered in advance from grasp acquisition experiments conducted with a planar test rig. The results show that our particle filter performs quite well, especially during periods of visual occlusion, in which it is much better than the same filter without tactile data.

To plan a robotic task involving intermittent contact, such as an assembly task, it is helpful to be able to simulate the task accurately and efficiently. In the past ten years, the prox formulation of the equations of motion has arisen as a competitive alternative to the well-known linear and nonlinear complementarity problem (LCP and NCP) formulations. In this paper, we compare these two formulations, showing through a set-based argument that the formulations are equivalent. Second, we provide simple examples to compare the most common approaches for solving these formulations. The prox formulation is solved by fixed-point iteration while the complementarity formulation is solved by a pivoting scheme, known as Lemke's algorithm. The well-known paradox of PAINLEVE¿ is used in a case where two solutions exist to illustrate that the fixed-point scheme can fail while the pivoting scheme will succeed.

Allowing robots to communicate naturally with humans is an important goal for social robotics. Most approaches have focused on building high-level probabilistic cognitive models. However, research in cognitive science shows that people often build common ground for communication with each other by seeking and providing evidence of understanding through behaviors like mimicry. Predictive State Representations (PSRs) allow one to build explicit, low-level models of the expected outcomes of actions, and are therefore well-suited for tasks that require providing such evidence of understanding. Using human-robot shadow puppetry as a prototype interaction study, we show that PSRs can be used successfully to both model human interactions, and to allow a robot to learn on-line how to engage a human in an interesting interaction.

In this paper, we proposed a new physical simulation method that can model non-convex configuration space. The new method employs a novel contact model that take into account geometry information of objects. It can also be shown that it reduces the work for collision detection routines.

Humans rely on a finely tuned ability to recognize and adapt to socially relevant patterns in their everyday face-to-face interactions. This allows them to anticipate the actions of others, coordinate their behaviors, and create shared meaning to communicate. Social robots must likewise be able to recognize and perform relevant social patterns, including interactional synchrony, imitation, and particular sequences of behaviors. We use existing empirical work in the social sciences and observations of human interaction to develop nonverbal interactive capabilities for a robot in the context of shadow puppet play, where people interact through shadows of hands cast against a wall. We show how information theoretic quantities can be used to model interaction between humans and to generate interactive controllers for a robot. Finally, we evaluate the resulting model in an embodied human-robot interaction study. We show the benefit of modeling interaction as a joint process rather than modeling individual agents.

In this paper, we present the use of complementarity-based dynamic simulation algorithms for kinodynamic motion planning. Dynamic simulation algorithms are used as local planning methods in sampling-based motion planning algorithms to find inputs that ensure the resulting trajectory satisfies the dynamics constraints. However, the inputs are not guaranteed to give collision-free path segments. The inputs, chosen either by random sampling or from a discretization of the available inputs, are rejected if the path segment is not collision free. In cluttered environments, finding a feasible input is difficult and sensitive to the duration ¿t of application of the input, and to the discretization resolution of the input set. When the collision constraints (or any inequality constraints on the state of the robot) are modeled as a set of complementarity constraints, the dynamic simulation algorithm gives a path segment that touches the obstacles and a set of contact forces whenever the robot makes contact with the obstacles. The sum of the chosen input forces and the contact forces transformed to the input space gives a control input that guarantees a collision-free path segment (provided it is within the actuator bounds). Thus in cluttered environments, using a complementarity-based dynamic simulation algorithm, we can find a feasible input that is relatively insensitive to the choice of ¿t and the discretization resolution of the input set. We present simple simulation examples showing the advantages of our algorithm in cluttered environments.

This paper discusses the design and current capabilities of a new software tool, dVC, capable of simulating planar systems of bodies experiencing unilateral contacts with friction. Since different problems require different levels of accuracy, dVC provides user-selectable body types (rigid or locally-compliant), motion models (first-order, quasi-static, dynamic), and several state-of-the-art time-stepping methods. One can also choose to include friction between each body and the plane of motion. To support optimal and robust part design, dVC also allows on-the-fly changes to parameters of the geometric and physical models. The results obtained for three representative planar problems are presented: the design of a passive part-orienting device, the planning of a mesoscale assembly operation, and the design of a grasp strategy.

This paper describes a test-bed for planar micro manipulation tasks and a framework for planning based on quasi-static models of mechanical systems with frictional contacts. We show how planar peg-in-the-hole assembly tasks can be designed using randomized motion planning techniques with Mason's models for quasi-static manipulation. Finally, we present simulation and experimental results in support of our methodology

We study the motion problem for planar star-shaped manipulators. These manipulators are formed by joining k "legs" to a common point (like the thorax of an insect) and then fixing the "feet" to the ground. The result is a planar parallel manipulator with k - 1 independent closed loops. A topological analysis is used to understand the global structure of the configuration space so that planning problem can be solved exactly. The worst-case complexity of our algorithm is O(k3N3), where N is the maximum number of links in a leg. A simple example illustrating our method is given

In this paper, we use a linear complementarity problem (LCP) formulation of rigid body dynamics with unilateral contacts to obtain definitions for contact modes. We show how the complementary cones of the LCP correspond to each of the intuitive contact modes: slide right, slide left, roll and separate. These complementary cones allow us to make rigorous definitions for contact modes in three-dimensional systems, where our intuitive understanding fails.

In this paper we develop a systematic topological approach to motion planning for a planar 2-R manipulator with point obstacles. By considering components in the free space for the second joint as the first joint varies, we build a two-dimensional array representing the cells of the free space and an associated graph representing the boundaries of those cells. Using this graph, we derive a closed formula for the number of components of the free space. At the same time we solve the motion existence problem, namely, when are two arbitrary configurations in the same component? If so, we develop two explicit algorithms for constructing the path - a middle path method and a linear interpolation method. These algorithms give complete solutions to the path planning problem. Extensive examples are worked out which verify the correctness and efficiency of the resulting program. Then we briefly discuss how these methods generalize to a 3-R planar manipulator.

We introduce computational support tools for the analysis and design of systems with multiple frictional contacts, with a focus on applications to part feeding and assembly processes. The tools rely on dynamic models of the processes. We describe two approaches to modeling, the Stewart-Trinkle model (1996) and the Song-Pang-Kumar model (2003), that allow the designer to experiment with different geometric, material and dynamic properties and optimize the design for performance. In order to accommodate contact transitions, we introduce a smooth cone model for friction. We illustrate the models and the design process by describing the design optimization of a part feeder.

This paper presents a generalized framework for dynamic simulation realized in a prototype simulator called the Interactive Generalized Motion Simulator (I-GMS), which can simulate motions of multirigid-body systems with contact interaction in virtual environments. I-GMS is designed to meet two important goals: generality and interactivity. By generality, we mean a dynamic simulator which can easily support various systems of rigid bodies, ranging from a single free-flying rigid object to complex linkages such as those needed for robotic systems or human body simulation. To provide this generality, we have developed I-GMS in an object-oriented framework. The user interactivity is supported through a haptic interface for articulated bodies, introducing interactive dynamic simulation schemes. This user-interaction is achieved by performing push and pull operations via the PHANToM haptic device, which runs as an integrated part of I-GMS. Also, a hybrid scheme was used for simulating internal contacts (between bodies in the multirigid-body system) in the presence of friction, which could avoid the nonexistent solution problem often faced when solving contact problems with Coulomb friction. In our hybrid scheme, two impulse-based methods are exploited so that different methods are applied adaptively, depending on whether the current contact situation is characterized as "bouncing" or "steady." We demonstrate the user-interaction capability of I-GMS through on-line editing of trajectories of a 6-degree of freedom (dof) articulated structure.

The companion paper (see ibid. "Computing wrench cones for planar contact tasks", p869 (2002)) derives an algorithm that determines the external wrenches consistent with constraints on the contact interactions between two rigid planar bodies. In this paper, we show how this algorithm may be used to create sensorless plans which guarantee that a workpiece is correctly inserted into a fixture. Our method explicitly removes all wrenches consistent with undesirable contact modes, and therefore avoids the frictional indeterminacy problem.

The successful execution of any contact task fundamentally requires the application of wrenches (forces and moments) consistent with the task. We develop an algorithm for computing the entire set of wrenches consistent with achieving a given augmented contact mode (e.g., sliding at contact 1, rolling at contact 2, and approaching potential contact 3) for one fixed and one moving part in the plane.

This paper introduces a hybrid scheme for simulating rigid bodies in contact. We use an adaptive strategy for handling two different contact situations, 'bouncing' and 'steady'. To handle contact for rigid bodies, we use two impulse-based methods to explicitly or implicitly compute impulses due to collision impact. These two methods are used so that different impulse methods are applied adaptively depending on the contact situations. Our experiments show that our simple adaptive simulation scheme enables efficient and physically-correct dynamic simulation involving rigid-body contacts with Coulomb friction. This adaptive scheme was incorporated into our dynamic simulator, called I-GMS, which supports various types of simulations. We demonstrate the simulation results of our scheme using a ball falling on a flat surface in three dimensions.

Maximizing the use of dual-arm robotic systems requires the development of planning algorithms analogous to those available for single-arm operations. In this paper, the global properties of the configuration spaces of planar n-bar mechanisms (i.e., kinematic chains forming a single closed loop) are used to design a complete motion planning algorithm. Numerical experiments demonstrate the algorithm's superiority over a typical algorithm that uses only local geometric information.

Dextrous manipulation is a fundamental problem in the study of multifingered robotic hands. Given a robotic hand and an object to be manipulated by the hand in an environment filled with obstacles, the main objectives of dextrous manipulation are to have the hand grasp the object and transfer it from a start configuration to a goal configuration without collision. To fulfill such a task in general, we will need: (a) a manipulation planner to generate a feasible path for the hand; and (b) a controller to implement the planned path. In this overview paper, we define the manipulation planning problem and present a unified control system architecture for multifingered manipulation (CoSAM/sup 2/). By incorporating the various kinematic and static relationships of a multifingered robotic hand system with proper sensory data inputs at different stages, CoSAM/sup 2/ achieves the various objectives of dextrous manipulation. Theoretical background of the control system design along with real-time experimental results are described.

This paper formally introduces several stability characterizations of fixtured three-dimensional rigid bodies initially at rest and in unilateral contact with Coulomb friction. These characterizations, weak stability and strong stability, arise naturally from the dynamic model of the system, formulated as a complementarity problem. Using the tools of complementarity theory, these characterizations are studied in detail to understand their properties and to develop techniques to identify the stability classifications of general systems subjected to known external loads.

In this paper a new time-stepping method for simulating systems of rigid bodies is given. Unlike methods which take an instantaneous point of view, our method is based on impulse-momentum equations, and so does not need to explicitly resolve impulsive forces. On the other hand, our method is distinct from previous impulsive methods in that it does not require explicit collision checking and it can handle simultaneous impacts. Numerical results are given for one planar and one three dimensional example, which demonstrate the practicality of the method, and its convergence as the step size becomes small.

Describes an interactive dynamic simulator for virtual environments which allows user interaction via a haptic interface. The interactive simulation is performed in our testbed dynamic simulator I-GMS (Interactive Generalized Motion Simulator), which has been developed in an object-oriented framework for simulating motions of free bodies and complex linkages such as those needed for robotic systems or human body simulation. User interaction is achieved by performing push and pull operations via the PHANToM haptic device which runs as on integrated part of I-GMS. We demonstrate the user interaction capability of I-GMS through online editing of trajectories for a 6-DOF robot manipulator.

Three fundamental problems in the study of grasping and dextrous manipulation with multifingered robotic hands are as follows, a) Given a robotic hand and a grasp characterized by a set of contact points and the associated contact models, determine if the grasp has force closure, b) Given a grasp along with robotic hand kinematic structure and joint effort limit constraints, determine if the fingers are able to apply a specified resultant wrench on the object, c) Compute "optimal" contact forces if the answer to problem b) is affirmative. In this paper, based on an early result by Buss et al., which transforms the nonlinear friction cone constraints into positive definiteness constraints imposed on certainty symmetric matrices, we further cast the friction cone constraints into linear matrix inequalities (LMI) and formulate all three of the problems stated above as a set of convex optimization problems involving LMI. The latter problems have been extensively studied in optimization and control communities. Currently highly efficient algorithms with polynomial time complexity have been developed and made available. We perform numerical studies to show the simplicity and efficiency of the LMI formulation to the three grasp analysis problems.

Three important problems in the study of grasping and manipulation by multi-fingered robotic hands are: 1) given a grasp characterised by a set of contact points and the associated contact models, determine if the grasp has force closure; 2) if the grasp does not have force closure, determine if the fingers are able to apply a specified resultant wrench on the object; and 3) compute "optimal" contact forces if the answer to problem (2) is affirmative. In this paper, based on an early result by Buss-Hashimoto-Moore (1996), which transforms the nonlinear friction cone constraints into positive definiteness of certain symmetric matrices, we further cast the friction cone constraints into linear matrix inequalities (LMIs) and formulate all three of the problems stated above as a set of convex optimization problems involving LMIs. We perform simulation studies to show the simplicity and efficiency of the LMI formulation to the three problems.

Many practical dextrous manipulation tasks involve large-scale motion of the grasped object while maintaining a stable grasp. To plan such task, one must control both the motion of the object and the contact locations, while also adhering to the workspace constraints typical of multi-fingered hands. We integrate the relevant theories of contact kinematics, nonholonomic motion planning, coordinated object manipulation, grasp stability and finger gaits to develop a general framework for dextrous manipulation planning. To illustrate our approach, the framework is applied to the problem of manipulating a sphere with three hemi-spherical fingertips. The simulation results are presented.

Dextrous manipulation planning is a problem of paramount importance in the study of multifingered robotic hands. In this paper, we show in general, that all system variables (the finger joint, object and contact velocities) need to be included in the differential kinematic equation used for manipulation planning, even if the manipulation task is only specified in terms of the goal configuration of the object or the contacts only. The dextrous manipulation kinematics that relates the finger joint movements to object and contact movements is derived. With the results of inverse and forward instantaneous kinematics, we precisely formulate the problem of dextrous manipulation and cast it in a form suitable for integrating the relevant theory of contact kinematics, nonholonomic motion planning, and grasp stability to develop a general technique for dextrous manipulation planning with multifingered hands.

Dextrous manipulation is a problem of paramount importance in the study of multifingered robotic hands. Given a grasped object, the main objectives are: (a) generate trajectories for the finger joints so that through the effects of contact constraints, the object can be transferred to a goal grasp configuration; and (b) derive control algorithms to realize planned trajectories. In this paper, we integrate the relevant theories of contact kinematics, nonholonomic motion planning and grasp stability to develop a general technique for dextrous manipulation planning with multifingered hands. Experimental results are discussed.

Consider a system of bodies with multiple concurrent contacts. The multi-rigid-body contact problem is to predict the accelerations of the bodies and the normal and friction loads acting at the contacts. This paper presents theoretical results for the multi-rigid-body contact problem under the assumptions that one or more contacts occur over locally planar finite regions and friction forces are consistent with the maximum work inequality. We present an existence and uniqueness result for this problem under some mild assumptions on the system inputs. The application of our results to two examples is discussed.

We propose a new condition to test for the impossibility of jamming in three-dimensional, quasistatic multi-rigid-body systems. Our condition can be written as a feasibility problem for a system of linear inequalities and therefore can be checked using linear programming techniques. To demonstrate the use of our jamming test, we apply it to a simple dexterous manipulation task and to the well-known peg-in-hole insertion problem.

The efficiency of the automatic execution of complex assembly tasks can be enhanced by the identification of the contact state. In this paper we derive a new method for testing a hypothesized contact state using force sensing in the presence of sensing and control uncertainty. The hypothesized contact state is represented as a collection of elementary contacts. The feasibility of the elementary contacts is tested by solving a linear program. No knowledge of the contact pressure distribution or of the contact forces is required, so our method can be used even when the contact forces are statically indeterminate. We give a geometric interpretation of the contact identification problem using the theory of polyhedral convex cones. If more than one contact state is feasible, we use the geometric interpretation to determine the likelihood of each feasible contact formation.

The contact formation cells of a polygonal planar system of rigid bodies in contact have been studied in Farahat et al. There, it was shown that the CF-cells are smooth manifolds, but the methods used were too complicated to extend to three-dimensional polygonal rigid body systems. In this paper, the authors develop an alternative way to define contact formation cells. Under the new definition, the authors show that the contact formation cells are smooth manifolds, and further that all intersections of contact formation cells are smooth manifolds. The simplicity of the new definition makes it easy to prove the smoothness results for three-dimensional systems. Also, the authors investigate other extensions of the results in Farahat et al.

A dynamic model of a dexterous manipulation system can be used for predicting the feasibility of a manipulation plan generated under the quasistatic assumption but executed under dynamic conditions. Contact forces between the object and manipulator are calculated to determine whether contacts can be maintained for the planned motion. Compressive contact forces indicate that contacts can be maintained for the specified manipulation plan and this implies that actual dynamic manipulation succeeds. Results of the solution of dynamic equations are given for selected objects and video images of successful plans are shown.

The efficient planning of contact tasks for intelligent robotic systems requires a thorough understanding of the kinematic constraints imposed on the system by the contacts. In this paper, we derive closed-form analytic solutions for the position and orientation of a passive polygon moving in sliding and rolling contact with two or three active polygons whose positions and orientations are independently controlled. This is accomplished by applying a simple elimination procedure to solve the appropriate system of contact constraint equations. We also prove that the set of solutions to the contact constraint equations is a smooth submanifold of the system's configuration space and we study its projection onto the configuration space of the active polygons. By relating these results to the wrench matrices commonly used in grasp analysis, we discover a previously unknown and highly nonintuitive class of nongeneric contact situations. In these situations, for a specific fixed configuration of the active polygons, the passive polygon can maintain three contacts on three mutually nonparallel edges while retaining one degree of freedom of motion.>

A stability cell is a subset of the configuration space (C-space) of a set of actively controlled rigid bodies (e.g., a manipulator) in contact with a passive body in which the contact state is guaranteed to be stable under Coulomb friction and external forces. A first-order stability cell is a subset of a stability cell with the following two properties: the state of contact uniquely determines the rate of change of the object's configuration given the rate of change of the manipulator's configuration; and the contact state cannot be altered by any infinitesimal variation in the generalized applied force. First-order stability cells can be used in planning whole-arm manipulation tasks in a manner analogous to the use of free-space cells in planning collision-free paths: a connectivity graph is constructed and searched for a path connecting the initial and goal configurations. A path through a free-space connectivity graph represents a motion plan that can be executed without fear of collisions, while a path through a stability-cell connectivity graph represents a whole-arm manipulation plan that can be executed without fear of "dropping" the object. The paper gives a conceptual and analytical development of first-order stability cells of 3D rigid-body systems as conjunctions of equations and inequalities in the C-space variables. Additionally, our derivation leads to a new quasi-static jamming condition that takes into account the planned motion and kinematic structure of the active bodies.>

Planning the motion of bodies in contact requires a model of contact mechanics in order to predict sliding, rolling, and jamming. Such a model typically assumes that the bodies are rigid and that tangential forces at the contacts obey Coulomb's law. Though, usually assumed to be constant, the static and dynamic coefficients of friction vary in space and time and are difficult to measure accurately. In this paper, we study a quasistatic, multi-rigid-body model for planar systems, in which the coefficients of friction are treated as independent variables. Our analysis yields inequalities defining regions in the space of friction coefficients for which a particular contact mode is feasible. The geometrical interpretation of these inequalities leads to a simple graphical technique to test contact mode feasibility. This technique is then used to generate a nontrivial example in which several contact modes are simultaneously feasible. Despite model ambiguity, there are factors which argue in favor of using a quasistatic, rigid-body model. This point is highlighted by the successful application of our results to the planning of two manipulation tasks.>

The efficient planning of contact tasks for intelligent robotic systems requires a thorough understanding of the kinematic constraints imposed on the system by rolling and sliding contacts. In this paper, we derive closed-form analytic solutions for the position and orientation of a passive polygon moving in contact with two or three active polygons whose positions and orientations are independently controlled. This is done by applying elimination techniques to solve the systems of appropriate contact constraint equations. We prove that the systems of contact constraint equations are smooth submanifolds of configuration space.>

The most secure type of grasp of a frictionless workpiece is the form-closure grasp. However, task constraints may make achieving form-closure impossible or undesirable. In this case, one needs to employ a force-closure grasp. In this paper, we study the subclass of force-closure grasps known as second-order stable grasps, which typically have a small number of contacts. We derive conditions for second-order stability and represent second-order stability cells as conjunctions of equations and inequalities in the configuration variables of the system. These cells are the subsets of the system's configuration space for which the frictionless workpiece is second-order stable. We also determine the minimum and maximum numbers of contacts necessary for second-order stability. Our results are applied to a simple planar whole-arm manipulation system to generate one of its second-order stability cells.>

During the assembly of a product, it is vital that the partially completed assembly be stable. If the assembly is unstable, then it must be fixtured to stabilize it before retrieving the next part or subassembly This paper presents a stability test and a new approach to automatically generating the positions of a small set of fixture elements (fixels) that will stabilize an assembly. The stability test and the fixel positioning approach consider both the translational and rotational degrees of freedom of each part. Since all the relevant mechanical constraints are linear functions of the contact force magnitudes and the components of the velocities of the parts, linear programming techniques can be used with great efficiency.>

The establishment of a unique infrastructure for distributed robotics and remote operations research within an educational environment is reported. The distributed laboratory consists of sites at four universities and NASA's Johnson Space Center. The distributed laboratory configuration provides the opportunity to quantitatively study the effects of various system components and technologies on overall telerobotic task performance. The ability to execute representative inspection and manipulation tasks with multiple control, robot, and performance/workload monitoring sites simultaneously connected has been demonstrated. Operations are carried out on a routine basis. During the process, needs for hardware and software standards development have been identified. The current implementation provides a basis for linking government, industrial, and university facilities to realize a truly collaborative research and development environment, enabling graduate students to experience educational opportunities that would otherwise not be possible.>

Grasp and manipulation planning of slippery objects often relies on the 'lform'closure grasp, which can he maintained regardless of the external force applied to the object. Despite its importance, a quantita- tive test ,for form closure valid for any number of contact points is not availuhle. The primary contribution of this paper is the introduction of such a test formulated as a lineor program, of which the optimal objective value provides a measure of how far a grasp is from losing ,form While the test is formulated for frictionless grasps, we discuss how it can be modified to identify grasps with 'yrictional fortn closure. I. IX'l'IiODUClTOX

An efficient quantitative test for form closure valid for any number of contact points is formulated as a linear program, the optimal objective value of which provides a measure of how far a grasp is from losing form closure. When the grasp does not have form closure, manipulation planning requires a means for predicting the object's stability and instantaneous velocity, given the joint velocities of the hand. The classical approach to computing these quantities is to solve the systems of kinematic inequalities corresponding to all possible combinations of separating or sliding at the contacts. All combinations resulting in the interpenetration of bodies or the infeasibility of the equilibrium equations are rejected. The remaining combination is consistent with all the constraints and is used to compute the velocity of the manipulated object and the contact forces, which indicate whether or not the object is stable. A linear program whose solution yields the same information as the classical approach, usually without explicit testing of all possible combinations of contact interactions, is formulated.>

The authors present a general methodology based on R.S. Desai's (1988) concept of contact formations and combine it with a model of contact mechanics to solve the dexterous manipulation planning problem. The model of contact mechanics supports the analysis of contact situations with multiple sliding contacts, allowing it to solve problems not solvable if only rolling contacts are allowed. Based on the proposed methodology, a planner would effectively solve two-point boundary value problems by using contact formation transitions to discretize the configuration space of, for example, a hand/object system. Within each discrete cell, or contact formation a model of contact mechanics is used to generate trajectories joining the cells and building a contact formation tree. If a solution exists, the tree grows until it contains a path from the initial grasp to the goal grasp. Then the individual input trajectories (assigned to the arcs of the tree) are combined to generate the complete manipulation trajectories.>

M.A. Peshkin and A.C. Sanderson's minimum power principle (see IEEE Int. Conf. on Rob. & Autom., p.421-6, April 25-29, 1988) for quasi-static systems is used to combine force and kinematic relationships into a nonlinear mathematical program called the forward object motion problem. Given the joint velocities of the robot's hand and arm, the solution of the forward object motion problem predicts not only the velocity of the object (as determined by kinematic analyses), but also the contact forces. In kinematic analyses one must guess as to the nature of all contact interactions (i.e. sliding, rolling, or separating). The solution of the forward object motion problem definitively determines these interactions and the contact forces as a byproduct of determining the velocity of the manipulated object.>

Engineering mechanics is used to develop the initial grasp liftability chart, or IGLIC. Its primary usefulness is in planning and analyzing grasps for lifting frictionless objects. Candidate grasp configurations can be mapped onto the IGLIC to determine, first, whether the grasp can be used to lift the object and, second, the nature of liftoff. Even though the development is undertaken for the two-dimensional case, the results can be applied to three-dimensional objects which can be approximated as generalized cylinders, by considering appropriate cross sections of the cylinders.>

The author studies the mechanics of lifting a slippery two-dimensional object initially at rest on a supporting surface. The equilibrium relationships are solved to define five liftability regions, and a graphical technique for their construction is given. One of the liftability regions provides a simple way to lift the object away from its support by dexterous manipulation (moving only the fingers, not the palm). The same region can also be used to plan stable manipulation after the object loses contact with the support. The analysis can be applied to any three-dimensional object which can be modeled as a generalized cylinder, by considering a suitable cross section of the cylinder. Friction effects are easily taken into account using the graphical technique.>

Grasping by a two-dimensional hand comprised of a palm and two hinged fingers is studied. The mathematics of frictionless grasping is presented and used in the development of a planner/simulator, The simulator computes the motion of the object using an active constraint set method and assuming exact knowledge of the physical properties of the polygonal object, hand, and support.

This paper specifies constraints based on the geometry of the grasped object, on geometry of the hand and the kinematics of the constrained object which determine how to grasp an object.