This paper presents Contact Mode Guided Manipulation Planning (CMGMP) for 3D quasistatic and quasi-dynamic rigid body motion planning in dexterous manipulation. The CMGMP algorithm generates hybrid motion plans including both continuous state transitions and discrete contact mode switches, without the need for pre-specified contact sequences or pre-designed motion primitives. The key idea is to use automatically enumerated contact modes of environment-object contacts to guide the tree expansions during the search. Contact modes automatically synthesize manipulation primitives, while the sampling-based planning framework sequences those primitives into a coherent plan. We test our algorithm on fourteen 3D manipulation tasks, and validate our models by executing some plans open-loop on a real robot-manipulator system11The video is available at https://youtu.be/JuLlliG3vGc.

This paper explores a novel approach to dexterous manipulation, aimed at levels of speed, precision, robustness, and simplicity suitable for practical deployment. The enabling technology is a Direct-drive Hand (DDHand) comprising two fingers, two DOFs each, that exhibit high speed and a light touch. The test application is the dexterous manipulation of three small and irregular parts, moving them to a grasp suitable for a subsequent assembly operation, regardless of initial presentation. We employed four primitive behaviors that use ground contact as a “third finger”, prior to or during the grasp process: pushing, pivoting, toppling, and squeeze-grasping. In our experiments, each part was presented from 30 to 90 times randomly positioned in each stable pose. Success rates varied from 83% to 100%. The time to manipulate and grasp was 6.32 seconds on average, varying from 2.07 to 16 seconds. In some cases, performance was robust, precise, and fast enough for practical applications, but in other cases, pose uncertainty required time-consuming vision and arm motions. The paper concludes with a discussion of further improvements required to make the primitives robust, eliminate uncertainty, and reduce this dependence on vision and arm motion.

The discontinuities and multi-modality introduced by contacts make manipulation planning challenging. Many previous works avoid this problem by pre-designing a set of high-level motion primitives like grasping and pushing. However, such motion primitives are often not adequate to describe dexterous manipulation motions. In this work, we propose a method for dexterous manipulation planning at a more primitive level. The key idea is to use contact modes to guide the search in a sampling-based planning framework. Our method can automatically generate contact transitions and motion trajectories under the quasistatic assumption. In the experiments, this method sometimes generates motions that are often pre-designed as motion primitives, as well as dexterous motions that are more task-specific1.

This paper derives a closed-form method for computing hybrid force-velocity control. The key idea is to maximize the kinematic conditioning of the mechanical system, which includes a robot, free objects, a rigid environment and contact constraints. The method is complete, in that it always produces an optimal/near optimal solution when a solution exists. It is efficient, since it is in closed form, avoiding the iterative search of our previous work. We test the method on 78,000 randomly generated test cases. The method outperforms our previous search-based technique by being from 7 to 40 times faster, while consistently producing better solutions in the sense of robustness to kinematic singularity. We also test the method in several representative manipulation experiments.

Localizing contacts and collisions is an important aspect of failure detection and recovery for robots and can aid perception and exploration of the environment. Contrary to state-of-the-art methods that rely on forces and torques measured on the robot, this paper proposes a kinematic method for proprioceptive contact localization on compliant robots using velocity measurements. The method is validated on two planar robots, the quadrupedal Minitaur and the two-fingered Direct Drive (DD) Hand which are compliant due to inherent transparency from direct drive actuation. Comparisons to other state-of-the-art proprioceptive methods are shown in simulation. Preliminary results on further extensions to complex geometry (through numerical methods) and spatial robots (with a particle filter) are discussed.

In hybrid force-velocity control, the robot can use velocity control in some directions to follow a trajectory, while performing force control in other directions to maintain contacts with the environment regardless of positional errors. We call this way of executing a trajectory hybrid servoing. We propose an algorithm to compute hybrid force-velocity control actions for hybrid servoing. We quantity the robustness of a control action and make trade-offs between different requirements by formulating the control synthesis as optimization problems. Our method can efficiently compute the dimensions, directions and magnitudes of force and velocity controls. We demonstrated by experiments the effectiveness of our method in several contact-rich manipulation tasks. Link to the video: https://youtu.be/KtSNmvwOenM.

This paper describes a new robotic tabletop rearrangement system, and presents experimental results. The tasks involve rearranging as many as 30 to 100 blocks, sometimes packed with a density of up to 40%. The high packing factor forces the system to push several objects at a time, making accurate simulation difficult, if not impossible. Nonetheless, the system achieves goals specifying the pose of every object, with an average precision of ± 1 mm and ± 2°. The system searches through policy rollouts of simulated pushing actions, using an Iterated Local Search technique to escape local minima. In real world execution, the system executes just one action from a policy, then uses a vision system to update the estimated task state, and replans. The system accepts a fully general description of task goals, which means it can solve the singulation and separation problems addressed in prior work, but can also solve sorting problems and spell out words, among other things. The paper includes examples of several solved problems, statistical analysis of the system's behavior on different types of problems, and some discussion of limitations, insights, and future work.

In robotic manipulation, finding a feasible motion plan doesn't guarantee a successful execution. The real world could bring all kinds of unexpected changes to the planned motion, the most deadly ones are usually marked by or caused by unexpected changes of contacts (object slipping away between fingers; getting stuck somewhere, etc). We notice that some actions are more likely to maintain desired contacts than others. To help finding these actions, in this work we propose a set of criteria to quantify the robustness of contacts against modeling uncertainties and disturbance forces. Under the quasi-static assumption, we analyze the causes of contact mode (sticking, sliding, disengaged) transitions and discuss how to endure larger uncertainties and disturbances. We summarize our results into several physically meaningful and easy-to-compute scores, which can be used to evaluate the quality of each individual contacts in a manipulation system. We illustrate the meaning of the scores with a simple example.

Threaded fasteners are prevalent throughout modern manufacturing. Thus, as the demand for automation in manufacturing increases, so does the demand for automated threaded fastening systems. However, many fundamental issues and engineering challenges still hinder robustness in automation, particularly for smaller screws and critical product finishing requirements. This paper surveys the state of the art in threaded fastening automation and discusses open questions for further research. This survey covers the following areas: 1) fundamentals of threaded fastening, including basic concepts and definitions; 2) analysis of the entire assembly process (consisting of part feeding and orientation, pickup, alignment, and driving), including discussions of tools, control strategies, and other considerations; 3) failure modes and techniques to mitigate them; 4) threaded fastening systems and electromechanical approaches; and 5) open challenges and suggestions for future development. Understanding the current state of automation in threaded fastening will provide a foundation for researchers to advance this field.

In this paper, we consider reorienting 3D objects on a table using a two-finger pinch gripper. Given the 3D mesh model of the object, our algorithm solves for the gripper motions that are required to transit between arbitrary object poses, grasping positions and gripper poses. The two motion primitives we used, pivoting and compliant rolling, enable us to decompose the planning problem and solve it more efficiently. Our algorithm can work with approximated (simplified) mesh models while being robust to approximation errors, thereby allowing us to efficiently handle object shapes with originally thousands of facets. We show the effectiveness of the proposed method by testing on objects with non-trivial geometry in both simulations and experiments. Results show that our algorithm can solve a larger range of reorienting problems with less number of making and breaking contacts when compared to traditional pick-and-place based methods, especially when the gripper workspace is highly constrained.

Hundreds of billions of small screws are assembled in consumer electronics industry every year, yet reliably automating the screwdriving process remains one of the most challenging tasks. Two barriers to further adoption of robotic threaded fastening systems are system cost and technical challenges, especially for small screws. An affordable intelligent screwdriving system that can support online stage and result classification is the first step to bridge the gap. To this end, starting from a state transition graph of screwdriving processes and a labeled screwdriving dataset (1862 runs of M1.4 screws) on multiple sensor signals, we develop classification algorithms and perform sensor reduction. Fast and accurate result classifiers are developed using linear discriminant analysis, while a wrapper method for feature subset selection is used to identify the optimal feature subset and corresponding sensor signals to reduce cost. A stage classifier based on decision tree is developed using the optimal sensor subset. The stage classifier achieves high accuracy in realtime prediction of various stages when augmented with the state transition graph.

Automated grasping has a long history of research that is increasing due to interest from industry. One grand challenge for robotics is Universal Picking: the ability to robustly grasp a broad variety of objects in diverse environments for applications from warehouses to assembly lines to homes. Although many researchers now openly share code and data, it is challenging to compare and/or reproduce experimental results to identify which aspects of which approaches work best due to variations in assumptions and experimental protocols, e.g., sensors, lighting, robot arms, grippers, and objects.

Toward a global picture of the radiation exposure of an area, particularly for fast emergency response, a UAV based exploration method is proposed. Without a priori knowledge of the radiation field, it is difficult to select the region of interest (ROI) which includes all radiation sources. For the case of a single radiation source, a greedy algorithm may localize the source by finding the maximum radiation value. However, when multiple sources generate a hotspot in a cumulative manner, the hotspot position does not coincide with one of the source positions. Therefore, we propose an efficient exploration method to quickly localize the radiation sources using the following procedures: (1) ROI selection using topographic maps with specific radiation level selection methods and (2) source localization estimating the number of sources and their positions with incremental variational Bayes inference of Gaussian mixtures. Under three different conditions according to the number of sources and their positions, we have shown that the proposed model can reduce the ROI and significantly improve the estimation accuracy than existing methods.

We propose a polynomial force-motion model for planar sliding. The set of generalized friction loads is the 1-sublevel set of a polynomial whose gradient directions correspond to generalized velocities. Additionally, the polynomial is confined to be convex even-degree homogeneous in order to obey the maximum work inequality, symmetry, shape invariance in scale, and fast invertibility. We present a simple and statistically-efficient model identification procedure using a sum-of-squares convex relaxation. Simulation and robotic experiments validate the accuracy and efficiency of our approach. We also show practical applications of our model including stable pushing of objects and free sliding dynamic simulations.

Regrasping is the process of adjusting the position and orientation of an object in one's hand. The study of robotic regrasping has generally been limited to use of theoretical analytical models and cases with little uncertainty. Analytical models and simulations have so far proven unable to capture the complexity of the real world. Empirical statistical models are more promising, but collecting good data is difficult. In this paper, we collect data from 3300 robot regrasps, and use this data to learn two probability functions: 1) The probability that the object is still in the robot's hand after a regrasp action; and 2) The probability distribution of the object pose after the regrasp given that the object is still grasped. Both of these functions are learned using kernel density estimation with a similarity metric over object pose. We show that our data-driven models achieve comparable accuracy to a geometric model and an off-the-shelf simulator in classification and prediction tasks, while also enabling us to predict probability distributions.

Pivoting is the rotation of an object between two fingers using gravity and inertial forces to impart angular momentum. We present an analysis of the mechanics of pivoting and a framework for planning and execution. Extrinsic dexterity was defined by Chavan-Dafle et al. [1] as the use of external forces, such as gravity and inertial forces in post grasp manipulation. We analyze one such regrasp termed “pivoting” by Rao et al. [2]. We find a grasp and arm trajectory which can rotate an object between stable poses, if any. We demonstrate an implementation of pivoting with an ABB industrial arm and a two fingered gripper.

The goal of this paper is to develop a regrasp planning algorithm general enough to perform statistical analysis with thousands of experiments and arbitrary mesh models. We focus on pick-and-place regrasp which reorients an object from one placement to another by using a sequence of pick-ups and place-downs. We improve the pick-and-place regrasp approach developed in 1990s and analyze its performance in robotic assembly with different work surfaces in the workcell. Our algorithm will automatically compute the stable placements of an object, find several force-closure grasps, generate a graph of regrasp actions, and search for regrasp sequences. We demonstrate the advantages of our algorithm with various mesh models and use the algorithm to evaluate the completeness, the cost and the length of regrasp sequences with different mesh models and different assembly tasks in the presence of different work surfaces. Our results show that spare work surfaces are beneficial to assembly. Tilted work surfaces are only sometimes beneficial, depending on the objects.

This paper presents a novel nonlinear compliant link. It has two major properties: bi-directionality and stiffening compliance. Bi-directionality means it can be stretched and compressed, and is realized by antagonistic arrangement of an extension spring and a compression spring. Stiffening compliance means it becomes stiffer as it is stretched, and is realized by asymmetric geometry. The links are parts of Simple Hand. Because Simple Hand gives limited space for links, current iteration of links is not obviously nonlinear. However, nonlinearity should be more obvious if links are designed for larger grippers.

“In-hand manipulation” is the ability to reposition an object in the hand, for example when adjusting the grasp of a hammer before hammering a nail. The common approach to in-hand manipulation with robotic hands, known as dexterous manipulation [1], is to hold an object within the fingertips of the hand and wiggle the fingers, or walk them along the object's surface. Dexterous manipulation, however, is just one of the many techniques available to the robot. The robot can also roll the object in the hand by using gravity, or adjust the object's pose by pressing it against a surface, or if fast enough, it can even toss the object in the air and catch it in a different pose. All these techniques have one thing in common: they rely on resources extrinsic to the hand, either gravity, external contacts or dynamic arm motions. We refer to them as “extrinsic dexterity”. In this paper we study extrinsic dexterity in the context of regrasp operations, for example when switching from a power to a precision grasp, and we demonstrate that even simple grippers are capable of ample in-hand manipulation. We develop twelve regrasp actions, all open-loop and hand-scripted, and evaluate their effectiveness with over 1200 trials of regrasps and sequences of regrasps, for three different objects (see video [2]). The long-term goal of this work is to develop a general repertoire of these behaviors, and to understand how such a repertoire might eventually constitute a general-purpose in-hand manipulation capability.

This video presents the application of Extrinsic Dexterity to change the pose of an object in the hand, i.e., to regrasp the object.

The ParkourBot climbs in a planar reduced-gravity vertical chute by leaping back and forth between the chute's two parallel walls. The ParkourBot is comprised of a body with two springy legs and its controls consist of leg angles at touchdown and the energy stored in them. During flight, the robot stores elastic potential energy in its springy legs and then converts this potential energy in to kinetic energy at touchdown, when it “kicks off” a wall. This paper describes the ParkourBot's mechanical design, modeling, and open-loop climbing experiments. The mechanical design makes use of the BowLeg, previously used for hopping on a flat ground. We introduce two models of the BowLeg ParkourBot: one is based on a nonzero stance duration using the spring-loaded inverted pendulum model, and the other is a simplified model (the simplest parkour model, or SPM) obtained as the leg stiffness approaches infinity and the stance time approaches zero. The SPM approximation provides the advantage of closed-form calculations. Finally, predictions of the models are validated by experiments in open-loop climbing in a reduced-gravity planar environment provided by an air table.

Given a desired function for an effector, what is its appropriate shape? This paper formulates mechanical function as a product of both effector's shape and motion, and, assuming a fixed motion model, explores the role of shape in satisfying it. We assume that the desired mechanical function is expressed as a set of constraints on the geometry of contact, and develop the tools for transforming these constraints into an effector shape. A previous paper [1] addressed the special case of revolute or prismatic fingers. This paper develops the more general case, including all smooth 1DOF planar mechanisms. The technique is illustrated with the design of finger shapes to improve the stability of a planar grasp of an object.

Sensing the forces applied to the palm of a robot manipulator requires robust compliant sensors guarded against collision. The force sensing palm for the MLab Simple Hand measures three components of net contact force in a simple robust design using flexure springs and optical position sensing. The hand is calibrated in an automatic process. Measurements are included to compare performance to the theoretical model.

This paper revisits the notion of free configuration space and reviews some of its path-connectivity-related properties. The literature on motion planning reveals at least three different definitions for the free configuration space of a robot in the presence of obstacles. This paper shows that, assuming regularity of both object and obstacles, those three definitions are equivalent. We show that the three definitions regularize the free space and therefore prevent the existence of “thin bits,” or low-dimensional strata. The paper concludes by discussing a series of properties regarding the existence and smoothability of contact-free paths between pairs of configurations.

The ParkourBot is an efficient and dynamic climbing robot. The robot comprises two springy legs connected to a body. Leg angle and spring tension are independently controlled. The robot climbs between two parallel walls by leaping from one wall to the other. During flight, the robot stores elastic energy in its springy legs and automatically releases the energy to "kick off" the wall during touch down. This paper elaborates on the mechanical design of the ParkourBot. We use a simple SLIP model to simulate the ParkourBot motion and stability. Finally, we detail experimental results, from open-loop climbing motions to closed-loop stabilization of climbing height in a planar, reduced gravity environment.

We propose a motion planning algorithm that reasons about tradeoffs between the discrete decision problems and continuous optimization problems faced by a mobile robot navigating through a cluttered environment. Discrete decisions typically involve transient options as the robot selects corridors to traverse. By contrast, optimization occurs within open spaces among homotopic paths. We utilize properties of local path sets to detect decisions of immediate importance and select routes that maximize the chance of future success.

Iteration is often sufficient for a simple hand to accomplish complex tasks, at the cost of an increase in the expected time to completion. In this paper, we minimize that overhead time by allowing a simple hand to abort early and retry as soon as it realizes that the task is likely to fail. We present two key contributions. First, we learn a probabilistic model of the relationship between the likelihood of success of a grasp and its grasp signature—the trace of the state of the hand along the entire grasp motion. Second, we model the iterative process of early abort and retry as a Markov chain and optimize the expected time to completion of the grasping task by effectively thresholding the likelihood of success. Experiments with our simple hand prototype tasked with grasping and singulating parts from a bin show that early abort and retry significantly increases efficiency.

This paper investigates a novel minimalistic mechanism that ascends tubes. The mechanism is comprised of only a rigid body, two O-rings, and a motor rotating an eccentric mass. We describe the underlying locomotion principle of rocking and jamming, without the use of special bristles or spines, and demonstrate the robustness of this mechanism.

This paper investigates a novel mechanism, called DSAC for Dynamic, Single Actuated Climber, which propels itself upwards by oscillating its leg in a symmetric fashion using a single actuator. This mechanism achieves dynamic, vertical motion while retaining simplicity in design and control. We explore the local orbital stability of the DSAC mechanism. We use the Poincaré map method with a well chosen Poincaré section to simplify the problem by reducing the dimension of the Poincaré map to 3-dimensions. We find the stable regions while varying the controls input and some of the mechanism's parameters. Moreover, in response to a continuous change in a parameter of the mechanism, the symmetric and steady stable gait of the mechanism gradually evolves through a regime of period doubling bifurcations.

This video shows the investigation of a novel minimalistic, dynamic climbing robot which can climb up tubes of different shapes using a simple dc motor. The motor moves an eccentric mass in a constant velocity. The location of the eccentric mass relative to the contact point determines the stability and the direction of the climbing motion. We present the analysis of this mechanism, simulation and experimental results.

This paper describes a hierarchical planner deployed on a mobile manipulation system. The main idea is a two-level hierarchy combining a global planner which provides rough guidance to a local planner. We place a premium on fast response, so the global planner achieves speed by using a very rough approximation of the robot kinematics, and the local planner begins execution of the next action even without considering subsequent actions in detail, instead relying on the guidance of the global planner. The system exhibits few planning delays, and yet is surprisingly effective at planning collision free motions. The system is deployed on HERB, combining a Segway mobile platform, a WAM arm, and a Barrett hand. The navigation and manipulation components have been tested on the real robot, and the task of simultaneously approaching and grasping a bottle on a countertop was demonstrated in simulation.

The goal of motion planning is to find a feasible path that connects two positions and is free from collision with obstacles. Path sets are a robust approach to this problem in the face of real-world complexity and uncertainty. A path set is a collection of feasible paths and their corresponding control sequences. A path-set-based planner navigates by repeatedly testing each of these robot-fixed paths for collision with obstacles. A heuristic function selects which of the surviving paths to follow next. At each step, the robot follows a small piece of each path selected while simultaneously planning the subsequent trajectory. A path set possesses high path diversity if it performs well at obstacle-avoidance and goal-seeking behaviors. Previous work in path diversity has tacitly assumed that a correlation exists between this dynamic planning problem and a simpler, static path diversity problem: a robot placed randomly into an obstacle field evaluates its path set for collision a single time before following the chosen path in entirety. Although these problems might intuitively appear to be linked, this paper shows that static and dynamic path diversity are two distinct properties. After empirically demonstrating this fact, we discuss some of the factors that differentiate the two problems.

A climbing robot mechanism is introduced, which uses dynamic movements to climb between two parallel vertical walls. This robot relies on its own internal dynamic motions to gain height, unlike previous mechanisms which are quasi- static. One benefit of dynamics is that it allows climbing with only a single actuated degree of freedom. We show with analysis, simulations and experiments that this dynamic robot is capable of climbing vertically between parallel walls. We introduce simplifications that enable us to obtain closed form approximations of the robot motion. Furthermore, this provides us with some design considerations and insights into the mechanism's ability to climb.

Characterizing optimal paths for mobile robots is an interesting, important, and challenging endeavor. Not only they are interesting with respect to the optimized criteria, but also they offer a family of motion primitives that can be used for motion planning in the presence of obstacles. This paper presents characterization of shortest paths for differential-drive mobile robots, with the goal of classifying solutions in the spirit of Dubins curves and Reeds-Shepp curves for car-like robots. To obtain a well-defined notion of shortest., the total amount of wheel rotation is optimized. Using Pontryagin maximum principle and other tools, we establish the existence of optimal trajectories, and derive the set of optimal paths. Some Reeds-Shepp curves appear in the set of optimal paths, whereas there are optimal paths which are different from Reeds-Shepp curves. To the best of our knowledge, this is the first progress on the problem

Motivated by an error-recovery locomotion problem, we propose a control technique for a complex mechanical system by decomposing the system dynamics into a collection of simplified models. The robot considered, The Rocking and Rolling Robot (RRRobot), is a high-centered round-bodied robot that locomotes on a plane by swinging its legs and rocking on its shell. We identify the elements contributing to locomotion through two steps: 1) decoupling the leg-body rotation dynamics from the body-plane contact kinematics, and 2) decoupling the body rotational dynamics into dynamics along each rotational axis. We show, using simulation, that such decoupling provides a good approximation to RRRobot's locomotion and use these models to find an approximate control solution for RRRobot: a mapping between planar translation and leg motions

We explore the control synthesis problem for a robot dynamically manipulating an object in the presence of multiple frictional contacts. Contacts occur both between the object and the robot, and between the object and the environment. Two sets of constraints govern the evolution of the system — contact velocity constraints that prevent separation and cause rolling, and, contact force constraints that arise from Coulomb friction. We combine the constraints in the space of contact accelerations, obtaining bounds on the robot acceleration as a function of the system state. We solve the motion planning problem by providing a feasible path for the system and generating the controls and the system trajectory by time-scaling the feasible path. We provide examples that illustrate the merits and limitations of our technique and discuss some of the open problems.

This paper addresses the planning and control of dynamic contact manipulation. In an earlier paper (Srinivasa et al., 2005), we derived a constraint on the robot joint accelerations that needed to be satisfied to obtain a desired contact mode and a desired dynamic motion of the object. We proposed a technique for trajectory planning which involved planning a path in the system configuration space followed by time-scaling the path to satisfy dynamic constraints. This paper tackles a problem where only a small set of paths can be time-scaled to satisfy the constraints. We note that the dynamic constraints depend only on a subspace of the system state space. Projecting the dynamics and the constraints onto the subspace allows us to compute an analytical solution for the trajectory generation problem. We generate controllable simulations by allowing the user to control the system in the space orthogonal to the projection. We also demonstrate the construction of feedback controllers using dynamic programming.

We show through experiment and simulation that a high-centered round-bodied legged robot can locomote by generating out-of-phase motions of reaction masses attached to its legs. These leg motions create body attitude oscillations which, when coupled with the slip-free contact constraints, locomote the robot. By varying the mean position of the leg oscillations, the robot can move in different directions in the plane. We also present some simplified models, where body attitude dynamics and contact kinematics are decoupled, to explain this form of legless locomotion.

Origami, the human art of paper sculpture, is a fresh challenge for the field of robotic manipulation, and provides a concrete example for many difficult and general manipulation problems. This paper presents some initial results, including the world's first origami-folding robot, definition of a simple class of origami for which we have designed a complete automatic planner, an analysis of the kinematics of more complicated folds, and some new theorems about foldability.

We explore the control of a nonholonomic robot subject to additional constraints on the state variables. In our problem, the user specifies the path of a subset of the state variables (the task freedoms X/sub P/), i.e. a curve X/sub P/(s) where s/spl isin/[0,1] is a parameterization that the user chooses. We control the trajectory of the task freedoms by specifying a bilateral time-scaling s(t) which assigns a point on the path for each time t. The time-scaling is termed bilateral because there is no restriction on s(t), the task freedoms are allowed to move backwards along the path. We design a controller that satisfies the user directive and controls the remaining state variables (the shape freedoms X/sub R/) to satisfy the constraints. Furthermore, we attempt to reduce the number of control switchings, as these result in relatively large errors in our system state. If a constraint is close to being violated (at a switchings point), we back up X/sub P/ along the path for a small time interval and move X/sub S/ to an open region. We show that there are a finite number of switching points for arbitrary task freedom paths. We implement our control scheme on the Mobipulator and discuss a generalization to arbitrary systems satisfying similar properties.

We propose a locomotion technique for a legged robot that is high-centered, i.e., a robot stuck on a block with its legs dangling in air. By using its legs as reaction masses, the robot might be able to rock and roll on its stomach and incrementally move forward off the block, a form of legless locomotion using halteres. With locomotion of high-centered robots using body attitude oscillations as motivation, this paper focuses on studying the interplay between leg motions and body roll-pitch-yaw dynamics. We present results from simulation of two simplified models in which body motion is restricted to the roll and roll-yaw space respectively.

Previous work has presented the time optimal trajectories for three classes of nonholonomic mobile robots: steered cars that can only go forwards, steered cars that go forwards or backwards, and differential drives. Each of the vehicles is modelled as a rigid body in the plane with velocity and angular velocity controls. The systems are differentiated only by the bounds on the controls, but the optimal trajectories are qualitatively different for each system. We explore this difference by considering the effect that control bounds have on the extremal trajectories of bounded velocity vehicles, where the extremal trajectories are defined to be the set of trajectories that satisfy Pontryagin's maximum principle, a necessary condition for optimality.

This paper summarizes ongoing work with a mo- bile manipulator (Mobipulator ). We describe the sys- tem architecture of the latest version of the robot, a hierarchy of robot motion commands (the Mobipula- tion library) that can be snapped together to generate complicated paths easily, a configuration space plan- ner that plans wheel motions to manipulate paper, and a visual servoing system to monitor and correct errors in robot motion.

This paper applies Pontryagin's maximum principle to the time optimal control of differential drive mobile robots with velocity bounds. The maximum principle gives necessary conditions for time optimality. Extremal trajectories are those which satisfy these conditions, and are thus a superset of the time optimal trajectories. This paper derives a compact geometrical structure for extremal trajectories and shows that extremal trajectories are always composed of rotations about the robot center and straight line motions. Further necessary conditions are obtained.

A differential drive robot is perhaps the simplest type of mobile robot, and the bounded velocity model is perhaps the simplest useful model of the admissible controls. This paper develops the bounded velocity model for differential drive mobile robots, and derives the time-optimal trajectories.

This paper describes a mobile manipulator that uses its wheels for manipulation as well as locomotion. This robot, named the mobipulator, looks like a small car with four independently powered wheels, none of them steered. It is designed to manipulate paper and other objects on the surface of a desk. The wheels are used for locomotion or for manipulation, switching functions dynamically as the task demands. So far we have preliminary demonstrations of a variety of motions, and performance data for the task of moving a sheet of paper in a square while maintaining constant orientation.

Parts orienting, the process of bringing parts in initially unknown orientations to a goal orientation, is an important aspect of automated assembly. Bowl feeders used in industry rely on a sequence of mechanical operations, without using sensors, to orient parts. In our work, we use partial information sensors along with mechanical operations to eliminate uncertainty in part orientation. We show that sensor based orienting plans need O (m) operations, where m is the maximum number of states with the same sensor value. We characterize the relation between part shape, orientability, and recognizability to identify conditions under which a single plan can orient and recognize multiple part shapes. We describe implemented planners and experiments to demonstrate generated plans.

Parts manufactured to tolerances have shape variations. Most work in robotic manipulation assumes that part shape does not vary. Orienting devices such as bowl feeder frequently fail due to variations in part shape. In this paper we develop techniques to orientate parts with shape uncertainty. We present a shape uncertainty model and describe the nondeterminism in parts orienting that arises from shape uncertainty. We characterize a class of parts that can be reliably oriented with sensor-based and sensorless orienting plans under shape uncertainty. We present implemented planners that generate orienting plans for the entire variational class of part shapes given a nominal part shape and shape uncertainty bounds. We describe experiments to demonstrate generated plans and outline issues for future work.

In this paper, we present the results of our experimental effort in one form of impulsive manipulation: tapping. Our previous work studied the mechanics of tapping a planar object which then slides on a support surface, coming to rest due to friction. This work addresses the practical issues in creating a system which uses this mode of manipulation. We begin with the design of tapping devices-end effecters designed to deliver an impulse to an object, and report some of the issues we have found to be important in their design. Our next step was to perform single-tap experiments in order to fit and evaluate the models of impact and sliding. These experiments have shown that objects rotate less than predicted; we have found that the addition of a scaling factor for the torque due to friction enables the models to predict object motion reasonably well. In order to do positioning experiments, we developed a number of planning methods (or feedback control strategies) to compensate for errors in modeling, parameters, and actuation. These planning methods were successfully used to demonstrate a positioning task. We also have experimentally demonstrated that tapping can be used to position an object more precisely than the manipulator can position the tapping device. We offer some sensitivity analysis in support of this result.

This paper explores a sensorless technique for orienting planar parts. We follow an approach described in the ours earlier papers (1995), called one joint over conveyor (1JOC), which can perform planar manipulation using a single controlled joint in combination with a constant-velocity conveyor. Our previous work demonstrated that the IJOC approach can orient and feed planar polygonal parts, given a singulated part in a known initial location. This paper shows that a variation called the sensorless IJOC can orient and feed polygonal parts up to symmetries in the underlying mechanics, without knowing the initial location and without sensors.

Vibratory manipulation is any mode of manipulation involving repeated impacts due to a striker which follows some periodic motion. In this paper, we study vibratory manipulation in the context of tapping planar objects which slide on a fixed support surface. We are interested in the behaviors an object exhibits under such excitation. There are two distinct types of tapping that can result: continuous tapping, in which the object is always in motion, and intermittent tapping, in which the object comes to rest between taps. We first examine vibratory manipulation in one dimension, adapting results from related work to find conditions for stable periodic motion. The general two dimensional case is closely related to our previous work in impulsive manipulation which examined the mechanics of a sliding rotating object. In fact, vibratory manipulation is an approximation to the limiting cases of impulsive manipulation. We develop the limiting cases for intermittent and continuous tapping for rotationally symmetric objects and conclude with some examples.

We are interested in using low degree-of-freedom robots to perform complex manipulation task without grasping. The robot can use rolling, slipping, and free flight to control more degrees-of-freedom of the part. To demonstrate this we study the controllability properties of planar dynamic nonprehensile manipulation. We show that almost any planar object is small-time locally controllable by point contact, and the controlling robot requires only two degrees-of-freedom (a point translating in the plane). We then focus on a one joint manipulator (with a two-dimensional state space) and show that even this simplest of robots, by using slipping and rolling, can control an object to a full-dimensional subset of its six-dimensional state space. We have developed a one joint robot to perform a variety of dynamic tasks, including snatching an object from a table, rolling an object on the surface of the arm, and throwing and catching.

By exploiting centrifugal and Coriolis forces, simple, low-degree-of-freedom robots can control objects with more degrees-of-freedom. For example, by allowing the object to roll and slip, a one-degree-of-freedom revolute robot can take a planar object to a full-dimensional subset of its state space. We present a dynamic manipulation planner that finds manipulator trajectories to move an object from one state to another without grasping it. The trajectories have been successfully implemented on a one-degree-of-freedom direct drive arm to perform dynamic tasks such as snatching an object from a table, rolling an object on the surface of the arm, and throwing and catching.

Programmable parts orienting is an important capability for flexible automation systems. Here we study how a part grasped in an unknown orientation by a force-controlled robot can be oriented by a sequence of push-align actions against a wall followed by sensor measurements of the distance from the grasp point to the wall. This paper concentrates on three issues: planning a sequence of actions to orient a part, exploring design changes that enable the part to be oriented in fewer steps, and the effect of shape uncertainty, due to manufacturing tolerances, on part orientability.

Examines a little-studied method of manipulation-manipulation by striking an object and letting it slide. There are two parts to this problem: The inverse sliding problem, determining the velocities required to send an object to a desired configuration, and the impact problem, determining how to strike the object in order to achieve those velocities. The authors present a solution to these two problems for the class of rotationally symmetric objects and conclude with some observations about this method of manipulation.

This paper addresses the question "Can the object be pushed from here to there?" The authors characterize the set of objects that are controllable (can be positioned arbitrarily), with and without obstacles, for the cases of point and line pushing contact. For the case of line contact, the authors find a set of pushing directions that keep the object fixed to the pusher and they use these pushing directions to find sensorless plans to reposition the object among obstacles.

Dynamic manipulation is defined, and a brief survey of dynamic operations is given. The design, control, and planning of dynamic manipulation is addressed. An example of dynamic manipulation, club-throwing using dynamic closure, is described.

The authors study the use of pushing actions with a fence to orient and translate objects in the plane. They describe a planner which a guaranteed to construct a sequence of pushing actions to move any polygonal object from any initial configuration to any final configuration. This planner, which utilizes an analysis of the mechanics of pushing an object, generates open-loop plans which do not require feedback sensing. These plans are guaranteed to succeed provided certain physical assumptions are met. Results of experiments conducted to demonstrate the generated plans are presented.>

The problem of orienting a part resting on a table by tilting the table is considered. The initial orientation of the part is assumed to be completely unknown. The objective is to tilt the table in a manner that reduces the uncertainty in the part's orientation. This work focuses on three-dimensional polyhedral parts, with finite friction between the parts and the table, and for which all transitions between different face-table contacts may be regarded as rotations across edges. A planner that determines a sequence of tilting operations designed to minimize the uncertainty in the part's orientation is proposed. The planner runs in time O(n/sup 4/), where n is the number of faces of the polyhedron. The planner produces a sequence of O(n) distinct tilts.>

A programmable parts feeder, a mechanism that can be reprogrammed to handle differently shaped parts, is discussed. The authors present a planning algorithm that accepts an n-sided polygonal part as input and, in time O(n/sup 2/), generates a program (plan) for the feeder that maximizes expected feedrate. They have implemented the planner and verified some of the resulting plans in the laboratory. This work illustrates a stochastic framework for manipulation planning.>

Graphical methods are often applied to planar mechanics problems, especially in the context of robotic manipulation, but there are limitations. In particular, the friction cone is an elegant representation of the set of forces generated by a single frictional contact, but there was previously no simple extension to problems of multiple frictional contacts. The paper shows a simple generalization of the friction cone to include multiple contacts. It demonstrates applications to dynamics problems and manipulation planning problems.>

A description is given of a robot, possessing limited sensory and effectory capabilities but no initial model of the effects of its actions on the world, that acquires such a model through exploration, practice, and observation. By acquiring an increasingly correct model of its actions, it generates increasingly successful plans to achieve its goals. In an apparently nondeterministic world, achieving reliability requires the identification of reliable actions and a preference for using such actions. Furthermore, by selecting its training actions carefully, the robot can significantly improve its learning rate.>

A Bayesian approach to the problem of autonomous manipulation in the presence of state uncertainty is described. Uncertainty is modeled with a probability distribution on the state space. Each plan (sequence of actions) defines a mapping on the state space and hence a posterior probability distribution. An attempt is made to find a plan for optimizing expected performance. The Bayesian framework is applied to a grasping problem. A planar polygon whose initial orientation is described by a uniform distribution and a frictionless parallel-jaw gripper is assumed in order to plan automatically a sequence of open-loop squeezing operations to reduce orientational uncertainty and grasp the object. Although many different performance measures are possible depending on the application, the approach is illustrated by searching for plans that optimize the robot's expected throughput.>

The problem of a thin rigid rod sliding on a horizontal surface in the plane is considered. This problem is commonly cited as an example of the inconsistency of planar rigid-body Newtonian mechanics. The existence of a consistent solution, using Routh's analysis of rigid-body impact is demonstrated.>

The use of motion strategies to eliminate uncertainty, without the use of sensors, is considered. The approach is demonstrated within the context of a simple method to orient planar objects. A randomly oriented object is dropped into a tray. When the tray is tilted, the object can slide into walls, along walls, and into corners, sometimes with the effect of reducing the number of possible orientations. For some objects a sequence of tilting operations exists that leaves the object's orientation completely determined. An automatic planner is described that constructs such a tilting program, using a simple model of the mechanics of sliding. The planner has been implemented, the resulting programs have been executed using a tray attached to an industrial manipulator, and sometimes the programs work. The authors explore the issue of sensorless manipulation, tray tilting in particular, within the context of a formal framework described by T. Lozano-Perez, M.T. Mason, and Rolf Taylor (1984). It is observed that sensorless motion strategies perform conditional actions using mechanical decisions in place of environmental inquiries.>

The motion of an object to be manipulated is determined by the forces applied to the object. During a collision, impulsive forces may dominate all other forces, and determine the ultimate success or failure of a task. More effective planning and control of manipulators should be possible if the impact process, including the effects of friction and elasticity, is better understood. This paper explores the planar impact of two objects, and develops simple graphical methods for predicting the mode of contact, the total impulse, and the resultant motions of the objects. In the special case of a perfectly plastic collision, the fundamental motion of the object-whether an angular acceleration will occur, and if so in what direction-is the same as predicted in earlier work on quasi-static pushing.

An autonomous robotic manipulator can reduce uncertainty in the locations of objects in either of two ways: by sensing, or by motion strategies. This paper explores the use of motion strategies to eliminate uncertainty, without the use of sensors. The approach is demonstrated within the context of a simple method to orient planar objects. A randomly oriented object is dropped into a tray. When the tray is tilted, the object can slide into walls, along walls, and into corners, sometimes with the effect of reducing the number of possible orientations. For some objects a sequence of tilting operations exists that leaves the object's orientation completely determined. The paper describes an automatic planner that constructs such a tilting program, using a simple model of the mechanics of sliding. The planner has been implemented, the resulting programs have been executed using a tray attached to an industrial manipulator, and sometimes the programs work. The paper also explores the issue of sensorless manipulation, tray-tilting in particular, within the context of a formal framework first described by Lozano-Pérez, Mason, and Taylor [1984]. It is observed that sensorless motion strategies perform conditional actions using mechanical decisions in place of environmental inquiries.

Many manipulator operations eliminate uncertainty in the locations and shapes of objects by purely mechanical means. Rather than relying on sensors, or on auxiliary parts-feeding machinery, these operations use the intrinsic mechanics of the task environment to eliminate uncertainty. Effective use of these operations requires that a planner be able to analyze the mechanics of a given task.

In this paper we explore a method for automatic planning of robot fine-motion programs, first described in [Lozano-Pérez, Mason, and Taylor 1983]. The primary result is a variation that is shown to be "bounded-complete"-the method obtains a solution whenever a solution consisting of a bounded number of motions exists.

Compliant motion of a manipulator occurs when the manipulator position is constrained by the task geometry. Compliant motion may be produced either by a passive mechanical compliance built in to the manipulator, or by an active compliance implemented in the control servo loop. The second method, called force control, is the subject of this paper. In particular a theory of force control based on formal models of the manipulator and the task geometry is presented. The ideal effector is used to model the manipulator, the ideal surface is used to model the task geometry, and the goal trajectory is used to model the desired behavior of the manipulator. Models are also defined for position control and force control, providing a precise semantics for compliant motion primitives in manipulation programming languages. The formalism serves as a simple interface between the manipulator and the programmer, isolating the programmer from the fundamental complexity of low-level manipulator control. A method of automatically synthesizing a restricted class of manipulator programs based on the formal models of task and goal trajectory is also provided by the formalism.