We present a dynamic robotic packing approach for autonomously and densely packing unknown objects that arrive continually at a packing site, such as those delivered via a conveyor belt. Our system enables simultaneous online object perception, rapid object modeling, dense packing planning, and object picking and packing in the presence of multi-modal sensing uncertainties, approximations in rapid object modeling, and robot motion inaccuracies. The method can accommodate both rigid and certain non-rigid objects, including in scenes where items are piled. Our approach is validated in real experiments with packing tasks involving unknown objects of various shapes and types. Experimental results demonstrate the effectiveness and efficiency of the introduced method in achieving high-density packing for different kinds of objects.

This paper addresses human-robot collaborative (HRC) precision assembly that complements natural human ability and the strength of an autonomous robot system. Our approach enables both flexibility and efficiency of tight-clearance assembly of various complex-shaped parts in the presence of uncertainty without requiring assembly skills and knowledge of robotics from the human operator. We demonstrated the effectiveness of our approach in a variety of experiments and comparisons with other HRC assembly approaches.

There are many industrial robotic applications which require a robot manipulator’s end-effector to fully cover a 3D surface region in a constrained motion. Constrained surface coverage in this context is focused on placing commonly used coverage patterns (such as raster, spiral, or dual-spiral) onto the surface for the manipulator to follow. The manipulator must continuously satisfy surface task constraints imposed on the end-effector while maintaining manipulator joint constraints. While there is substantial research for coverage on planar surfaces, methods for constrained coverage of 3D (spatial) surfaces are limited to certain (parametric or spline) surfaces and do not consider feasibility systematically given manipulator and task constraints. There is a lack of fundamental research to address the general problem: given a manipulator, a 3D freeform surface, and task constraints, whether there exists a feasible continuous motion plan to cover the surface, and if so, how to produce a uniform coverage path that best satisfies task constraints. In this paper, we introduce a general approach to address this fundamental but largely open coverage problem. We have applied our approach to example 3D freeform surface coverage tasks in simulation and real world environments with a 7-DOF robotic manipulator to demonstrate its effectiveness.Note to Practitioners—This paper was motivated by the constrained coverage path planning problem on 3D freeform surfaces for many industrial applications, such as painting, spray coating, abrasive blasting, polishing, shotcreting, etc. It provides a principled and general approach that includes an automatic robotic system to find feasible robotic end-effector paths for covering a 3D freeform surface with some interaction from a human worker who provides key parameters related to the specific task without being an expert in robotics. Therefore, the approach enables a human worker who only has the domain knowledge of a specific coverage task to operate the general and automatic robotic system effectively for completing the task.

Robotic manipulation tasks rely on a plethora of environmental and payload information. One critical piece of information for accurate manipulation is the center of mass (CoM) of the object, which is essential for estimating the dynamic response of the system and determining the payload placement. Traditionally, the CoM of a payload is provided prior to manipulation. In order to create a more robust and comprehensive system, this information should be collected by the robotic agent before or during the task run time. This paper presents a method for approximating the CoM of a planar object using a small-scale mobile robot to inform manipulation tasks. On average, our system is able to converge on a CoM estimate in under 30 seconds in simulation and 20 seconds in experiment, with a relative error of 4.95% and 5.46%, respectively.

Gripping and manipulating non-rigid and porous objects is an important challenge for manufacturing. Now there are many problems in handling textile materials from a stack or oriented in space. Therefore, the paper presents the design of an improved Bernoulli gripping device with an anti-vibration insert. The inventive gripper structure allows gripping and manipulating textile materials and partially eliminates the shortcomings present in the classic design of the gripper. A technique for theoretical modeling of a gripping device for textile materials has been developed. This made it possible to determine the rational parameters of the gripping device in terms of maximum attraction. Experimental study of power characteristics of gripping device for textile materials has been carried out. The choice of the thickness of the anti-vibration insert made by the 3D printing method is justified. The advantages of the design include enabling gripping of textile materials of manipulation at different position, orientation and from a longer distance. Influence of supply pressure on the beginning of object vibration is analyzed. Parameters of anti-vibration insert are defined for the operation of gripper without object vibration. Note to Practitioners—This paper was motivated by the problem of gripping and holding textile materials during manufacturing. There are many approaches to gripping a piece of textile material that have high energy consumption or can damage it. This paper proposes the design of the gripper that uses compressed air to lift the textile material at different orientations. Using the proposed theoretical model, one can calculate the lifting force of the gripper at different porosity of the material. Knowing the mass of the material, one can determine which parameters to choose for the gripper based on experimental results. Positive results are highlighted in the capture of porous objects without the loss of force at different orientations. Negative aspects are shown in the formation of vibration of the material when reaching a certain pressure level in the gripper. Future research plans to improve the design of the gripper by modeling the gripper using the finite element method and proposing effective methods of manipulating textile materials.

In this paper, we propose a novel and general method for autonomous robotic assembly of arbitrary and complex-shaped parts in the presence of 6-dimensional uncertainty. When a nominal assembly motion of the robot holding a part is stopped by contact due to uncertainty, our method finds the best estimate for the uncertainty and the contact configuration of the part based on sensed force/torque and uses that information to find a more accurate estimate of the goal configuration to guide a recovery motion of the part. It is based on a general, surface-based sphere tree representation of parts, a constrained optimization strategy to find the best estimate of the contact configuration under an uncertainty estimate, and a learned force/torque calibration model to relate computed force/torque and the sensed real force/torque. The method is applied and evaluated on different complex-shaped multi-peg-in-hole tasks. The results show that our method can achieve successful assembly with the presence of realistic 6-D uncertainties more than 10 times of the tight task clearances in terms of orientation clearance$(< 0.015rad)$and position clearance$(< 1.5mm)$, in all the test cases.

It is often desirable to capture and map semantic information of an environment during simultaneous localization and mapping (SLAM). Such semantic information can enable a robot to better distinguish places with similar low-level geometric and visual features and perform high-level tasks that use semantic information about objects to be manipulated and environments to be navigated. While semantic SLAM has gained increasing attention, there is little research on semantic-level data association based on semantic objects, i.e., object-level data association. In this paper, we propose a novel object-level data association algorithm based on bag of words algorithm [1], formulated as a maximum weighted bipartite matching problem. With object-level data association solved, we develop a quadratic-programming-based semantic object initialization scheme using dual quadric and introduce additional constraints to improve the success rate of object initialization. The integrated semantic-level SLAM system can achieve high-accuracy object-level data association and real-time semantic mapping as demonstrated in the experiments. The online semantic map building and semantic-level localization capabilities facilitate semantic-level mapping and task planning in a priori unknown environment.

How to reduce uncertainty in object pose estimation under complex contacts is crucial to autonomous robotic manipulation and assembly. In this paper, we introduce an approach through forecasting contact force from simulated complex contacts with calibration based on real force sensing. A constraint-based haptic simulation algorithm is used with sphere-tree representation of contacting objects to compute contact poses and forces, and through matching the computed forces to measured real force data via a regression model, the least-uncertain estimate of the relative contact pose is obtained. Our approach can handle multi-region complex contacts and does not make any assumption about contact types or contact locations. It also does not have restriction on object shapes. We have applied the force forecast approach to reducing uncertainty in estimating object poses in challenging peg-in-hole robotic assembly tasks and demonstrate the effectiveness of the approach by successful completion of contact-rich two-pin and three-pin real peg-in-hole assembly tasks with complex shapes of pins and holes.

To enable autonomous robot navigation among unknown dynamic obstacles, a real-time adaptive motion planner (RAMP) plans the robot motion online based on sensing the environment as the robot moves with sensors mounted on the robot. However, the sensed environmental data from the robot's local view is usually incomplete due to occlusions from obstacles and limited sensing range.This paper incorporates learning about the environment into the RAMP framework by leveraging the Hilbert Maps framework to generate a probabilistic model of occupancy of the unknown dynamic environment based on past observations. Utilizing this probabilistic model enables RAMP to reason about trajectory fitness when sensing information is partial and incomplete. This allows the RAMP robot to take advantage of what it has experienced from being in the dynamic environment before to inform its subsequent executions even though the dynamic environment changes in unknown ways. The effectiveness of incorporating such learned probabilistic data into RAMP is shown in both simulation and real experiments.

The recent proliferation of low-cost Micro Aerial Vehicles (MAV) offers an attractive means for inspecting critical infrastructure autonomously. However, to enable such autonomous tasks requires a precise spatial model of the structure and operational area, typically constructed using sensor measurements obtained from the environment. To facilitate autonomous inspection capabilities, we address the problem of autonomous MAV exploration and coverage of an unknown structure to acquire the spatial information necessary for the development of a high-fidelity 3D model of the structure. Key to this problem is to not only cover the entire structure to acquire a complete set of spatial measurements, but also to minimize accumulative data errors during the exploration through direct planning of loop closures. We introduce a real-time waypoint planning approach to guide MAV motions to achieve complete exploration, coverage, and loop closure while respecting limited onboard resources.

This paper introduces a reinforcement learning algorithm with robot manipulation to learn an arbitrary object's center of mass whose physical material composition is unknown. Robot learning is through manipulation of the object in a sequence of actions. The effectiveness of the algorithm is demonstrated in simulation to locate the centers of mass of rocks with complex shapes, with even or uneven mass distributions, and confirmed by vertically stacking the rocks along their learned centers of mass both in simulation and in real experiments.

This paper introduces conflict resolution in task-constrained real-time adaptive motion planning (RAMP) to enable a robot manipulator performing tasks in an environment with dynamically unknown obstacles. The method continuously improves and maintains diverse task constrained as well as unconstrained robot trajectories to allow the manipulator switching to a better trajectory at any time and seamlessly resolving conflicts between satisfying task constraints and avoiding dynamically unknown obstacles. If dynamic obstacles block all available task-constrained trajectories, the algorithm allows the manipulator to change goals on the fly to be free of task constraints and resume the task whenever there is a collision-free, task-constrained trajectory. The method is validated in different dynamic environments with different task constraints in both simulation and real-world experiments.

Immersion, interaction, and imagination are three features of virtual reality (VR). Existing VR systems possess fairly realistic visual and auditory feedbacks, and however, are poor with haptic feedback, by means of which human can perceive the physical world via abundant haptic properties. Haptic display is an interface aiming to enable bilateral signal communications between human and computer, and thus to greatly enhance the immersion and interaction of VR systems. This paper surveys the paradigm shift of haptic display occurred in the past 30 years, which is classified into three stages, including desktop haptics, surface haptics, and wearable haptics. The driving forces, key technologies and typical applications in each stage are critically reviewed. Toward the future high-fidelity VR interaction, research challenges are highlighted concerning handheld haptic device, multimodal haptic device, and high fidelity haptic rendering. In the end, the importance of understanding human haptic perception for designing effective haptic devices is addressed.

It is important to enable a robot to manipulate a target object that has no 3-D model information and is situated in an environment with other unknown objects nearby. This poses an open problem of how to combine perception and manipulation to enable the robot to build an appearance-based model of the target object on the spot to facilitate further manipulation of the object while avoiding the other unknown obstacles in the way. In this paper, we introduce an approach to enable a continuum manipulator, which is apt to maneuver through a crowded environment, to gradually build a 3-D surface model of the target object by moving an RGB-D sensor around the object while also detecting and avoiding surrounding unknown obstacles. Our approach interleaves perception and manipulation such that perception guides the manipulator movement, which in turn allows more perception of the target object for object model building and further manipulator motion. Our approach is characterized by a progressive strategy to register RGB-D images of the target object to build and extend a partial model of the object and the corresponding motion planning strategy for the continuum robot to carry out model building and avoid obstacles at the same time. To demonstrate the effectiveness of our approach, experiments on progressive model building of real objects from real RGB-D images are conducted, where a simulated continuum robot plans and executes its motion to carry the RGB-D camera around a target object for taking those images in an augmented reality setting.

We introduce a novel approach to shape-based object classification and recognition through the use of a continuum manipulator. Noticing the fact that when a continuum manipulator wraps around an object in a whole-arm grasping, its own shape is indicative of the shape of the object, our approach enables learning and recognition of object classes based on the shapes of continuum wraps. It offers the following advantages: (1) recognition of objects that are not easily detected by vision, such as transparent objects, and (2) highly efficient recognition of such objects of varied sizes due to high-level and rich shape information in each wrap, unlike recognition based on tactile sensing via conventional grasping. Simulation and experiments demonstrate the effectiveness of our approach.

This paper addresses the problem of real-time, non-holonomic motion planning in environments with moving obstacles of unforeseen, arbitrary motion. An approach is introduced to smoothly switch trajectories by generating feasible non-holonomic trajectory segments on the fly as the robot moves in such an environment, extending the real-time adaptive motion planning (RAMP) approach that is used for holonomic motion. It allows efficient on-line simultaneous planning and execution of non-holonomic trajectories and enables a robot to adapt to changes in the environment while taking into account robot motion uncertainty. The effectiveness and efficiency of the method has been verified through real experiments with a mobile robot and several dynamic obstacles of unforeseen motion to the robot.

Continuum manipulators are deformable, passively compliant, and apt for manipulation in cluttered space. This paper addresses how to enable an n-section continuum manipulator to probe an object, while gradually forming a whole-arm grasp in a cluttered environment. This approach is effective and efficient as evident from simulation and real experiments.

In this paper, we propose a novel approach for both 3-D object detection and six-degree-of-freedom (6-DoF) pose estimation based on smooth 3-D surface segments and their visual signatures in cluttered scenes with objects partially occluded. It is an appearance-based approach that does not require precise geometric models of the objects. We introduce a robust and flexible strategy to build object models based on segmented smooth surfaces of RGB-D images. We next introduce a strategy to detect objects and estimate their 6-DoF poses from a single image by taking full advantage of the surface-based object models. Our approach can reconstruct objects in cluttered scenes from a single view, where different objects or multiple instances of the same object can be stacked together or physically attached and occlude one another. It detects objects and estimates their 6-DoF poses even if the objects have transparent regions. Experimental results and comparison with related work demonstrate the effectiveness of our approach.

It is important to understand which view is better recognizing and reconstructing a scene for many robotic applications, especially in a cluttered environment, where objects interact and may occlude one another in all views. In this paper, we introduce a novel, learning-based approach to evaluate scene recognizability from a view based on the quality and quantity of recognized objects, the recognition uncertainty, and the background recognizability, rather than the visibility. Our study shows that increasing visibility does not guarantee better recognizability of objects. The introduced view evaluator can better characterize which view is more useful for the purpose of autonomous object recognition and scene reconstruction. The approach is validated through experiments, and the effects of many factors to scene recognizability are discussed based on the experimental results.

Continuum manipulators do not contain rigid links and can deform continuously to perform a whole arm manipulation. Hence, they are much more flexible than articulated manipulators to perform tasks in cluttered space. However, autonomous manipulation constrained by tasks other than grasping has not been studied for continuum manipulators. In this paper, we introduce a general and efficient approach for autonomous continuum manipulation under task constraints. We consider a spatial continuum manipulator with multiple uniform-curvature sections if not deformed. We further apply the approach to an example of inspection task in a cluttered environment to verify its effectiveness. The high-efficiency of our approach makes it suitable to run on-line for guiding task-constrained manipulation in real-time.

3D object detection and pose estimation often requires a 3D object model, and even so, it is a difficult problem if the object is heavily occluded in a cluttered scene. In this paper, we introduce a novel approach for recognizing and localizing 3D objects based on their appearances through segmentation of 3D surfaces. The approach can identify multiple occluded objects in a scene, which may include different instances of the same object, and estimate the pose of each entire object even if the object can only be seen partially due to occlusion.

The handle-avatar mapping from the handle of a desktop haptic device (i.e., the handle) to the virtual tool (i.e., the avatar) is subject to several uncertainties, including uncertain held positions of the human hand, un-modeled hand position on the virtual tool, and difference between the shape of the virtual tool and that of the physical handle. The influence of these uncertainties on the force/torque fidelity of 6-DOF haptic rendering is analyzed in this paper. A model of force/torque error induced by these uncertainties is introduced to measure the influences under different contact scenarios. A method based on adding a handle-hand avatar to the virtual tool is proposed to reduce the uncertainties and thus to improve simulation fidelity. Psychophysical experiments were carried out. Experiment results show that the subjective feeling of the human operator is consistent with the theoretical analysis results. Most subjects can feel the increase on torque fidelity after using the proposed method.

Auditory or visual stimulation has been widely used for brainwave entrainment, i.e. to modulate brain electroencephalograms (EEG) signals into a specific target frequency band. In this work, we study whether similar phenomena exists with haptic stimulation. By using a Phantom desktop to provide a sinusoidal force stimulation to a human subject's hand, and using a Nexus EEG device for real-time brain signal monitoring, we test how the Sensory Motor Rhythm (SMR) signal and the Alpha signal of the subject responds to the haptic stimulation. Our experiments show that the energy level of SMR signal tends to increase considerably (on average 10~30% of 8 human subjects) after 10-15 minutes of haptic stimulation with a 15Hz stimulation signal, and the energy level of Alpha signal tends to decrease considerably (on average 10~30% of 8 human subjects) after 10-15 minutes of haptic stimulation with a 10Hz stimulation signal. These results may have potential application in training human concentration and/or relaxation skills.

A continuum manipulator, such as a multi-section trunk/tentacle robot, is promising for deft manipulation of a wide range of objects under uncertain conditions in less-structured and cluttered environments. With whole arm grasping, it is adaptive to objects of different sizes and shapes. Previously, we introduced a method for automatically computing grasping configurations of a continuum manipulator with three constant-curvature sections was introduced based on minimum bounding circles of object cross-sections. However, using minimum bounding circles (or circumcircles if they exist) alone may not result in tight and stable grasps. In this paper, we introduce an approach for progressively generating tight grasping configurations section by section to achieve a tight and force-closure whole arm grasp. This approach directly applies to n-section continuum manipulators and generates a force-closure grasping configuration efficiently without requiring minimum bounding circles of a target object.

In-vivo measurement of force/torque signals between a surgical tool and human vessels during vascular surgery operations could provide a ground-truth data-set for constructing and evaluating haptics-enabled surgical simulation systems. In this paper, we introduce a novel wearable device for measuring such signals. This new design provides much higher measurement accuracy than a previous prototype. Experimental results by using standard weights provide that the relative force and torque error is about 5%. With time-varying load, the new device is compared with an ATI Nano17 force/torque sensor; average relative errors between the force signals is about 16.85%, and average relative errors between the torque signals is about 28.74%. Preliminary manipulation experiments of inserting a catheter into a vascular phantom model illustrated that the device can detect the collision between the catheter and the vascular walls. Subtle force/torque changes caused by changes of movement direction can be detected. Force/torque changes at some critical point (such as the interaction point of vessels) can also be detected.

A continuum manipulator, such as a multi-section trunk/tentacle robot, is promising for deft manipulation of a wide range of objects of different shapes and sizes. Given an object, a continuum manipulator tries to grasp it by wrapping tightly around it. Autonomous grasping requires realtime determination of whether an object can be grasped after it is identified, and if so, the feasible whole-arm wrapping around configurations of the robot to grasp it, which we call grasping configurations, as well as the path leading to a grasping configuration. In this paper, we describe the process for autonomous grasping from object detection to executing the grasping motion and achieving force-closure grasps, with a focus on a general analysis of all possible types of planar grasping configurations of a three-section continuum manipulator. We further provide conditions for existence of solutions and describe how to find a valid grasping configuration and the associated path automatically if one exists. Experimental results with the OctArm manipulator validate our approach, and shows that the entire process to determine an autonomous grasping operation, which includes automatic detection of the target object and determination of a grasping configuration and a path to the grasping configuration that avoids obstacles, can take just a small fraction of a second. Once a grasping configuration is reached, the manipulator can lift the object stably, i.e., a force-closure grasp can be achieved.

Continuum manipulators, inspired by invertebrate structures in nature, such as octopus arms and elephant trunks, do not contain rigid links, can deform, and are passively compliant, which make them particularly flexible for manipulation in cluttered space. A key open issue here is how to make such a manipulator autonomously grasp an object in cluttered space, especially if the object cannot be completely seen or known before being grasped. In this paper, we address this issue by introducing an approach that enables a multi-section continuum manipulator to probe an object with its tip while gradually form a whole-arm, force-closure grasp by following closely the contour of the probed object. This real-time approach is both effective and efficient for grasping an object in a cluttered space, as evident from the test examples.

Continuum manipulators, featuring “continuous backbone structures”, are promising for deft manipulation of a wide range of objects under uncertain conditions in less-structured and cluttered environments. A multi-section trunk/tentacle robot is such a continuum manipulator. With a continuum robot, manipulation means a continuous whole arm motion, where the arm is often bent into a continuously deforming concave shape. To approximate such an arm with a polygonal mesh for collision detection is expensive not only because a fine mesh is required to approximate concavity but also because each time the manipulator deforms, a new mesh has to be built for the new configuration. However, most generic collision detection algorithms apply to only polygonal meshes or objects of convex primitives. In this paper, we propose an efficient algorithm for Collision Detection between an Exact Continuum Manipulator (CD-ECoM) and its environments, which is applicable to any continuum manipulator featuring multiple constant-curvature sections. Our test results show that using this algorithm is both accurate and more efficient in both time and space to detect collisions than approximating the continuum manipulator as polygonal meshes and applying an existing generic collision detection algorithm. The algorithm is essential for path/trajectory planning of continuum manipulators.

Six-degree-of-freedom (6-DOF) haptic rendering is challenging when multi-region contacts occur between the graphic avatar of a haptic tool operated by a human user, which we call the graphic tool, and deformable objects. In this paper, we introduce a novel approach for deformation modeling based on a spring-sphere tree representation of deformable objects and a configuration-based constrained optimization method for determining the 6-dimensional configuration of the graphic tool and the contact force/torque response to the tool. This method conducts collision detection, deformation computation, and tool configuration optimization very efficiently based on the spring-sphere tree model, avoids inter-penetration, and maintains stability of haptic display without using virtual coupling. Experiments on typical dental operations are carried out to validate the efficiency and stability of the proposed method. The update rate of the haptic simulation loop is maintained at ~1kHz.

Geometric modeling and haptic simulation of pathological changes is an important topic for high-fidelity surgical simulators. In this paper, we introduce a constraint-based six degree-of-freedom (DOF) haptic simulation method incorporating multi-contact friction. We use this method to simulate periodontal operations on typical pathological tissues, including periodontal pocket and two kinds of calculi. A continuous collision detection method based on sphere-trees is proposed to avoid the pop-through phenomenon during tool manipulation against thin objects (such as small sized calculus adhered to the surface of the target tooth). For particle shaped calculus, a friction model is adapted to simulate decreasing frictions during the removal of the calculus. Experiments using a Phantom Premium 3.0 6DOF were carried out to validate the performance of our method. Stable haptic rendering and about 1 kHz update rate was maintained for all the operations, including depth measurement of the periodontal pocket and removal of the invisible block-shaped and particle-shaped calculi.

Six-degree-of-freedom (6-DOF) haptic rendering for fine manipulation in narrow space is a challenging topic because of frequent constraint changes caused by small tool movement and the requirement to preserve the feel of fine-features of objects. In this paper, we introduce a configuration-based constrained optimization method for solving this rendering problem. The six-dimensional configuration (position and orientation) of the graphic tool is defined as the solution variable of the optimization problem Contact constraints are obtained based on identifying principal contacts between the graphic avatar of the haptic tool, called the graphic tool, and the virtual task environment. In order to maintain stability during contact switch, a hybrid method combining collision detection, local search and parallel optimization is introduced. Based on parallel optimization and selection of local solution, we can maintain the local solution of the optimization model. Our method has been validated in experiments of moving a convex tool to probe a narrow cavity with or without bulges. Force rendering is stable even when the free space is very small and involves fine features of objects. Non-penetration between the tool and the object forming the cavity are maintained under frequent contact switches. Update rate of the simulation loop including the optimization and constraint identification is maintained at about 1kHz.

Unlike a conventional articulated manipulator, where only the gripper manipulates objects, a continuum manipulator, such as a multi-section trunk/tentacle robot, is promising for deft manipulation of a wide range of objects of different shapes and sizes. Given an object, a continuum manipulator tries to grasp it by wrapping around and squeezing it. A main open problem is how to determine if the object can be grasped and if so, the whole-arm wrapping around configurations of the robot to grasp it, which we call grasping configurations. In this paper, we provide a general and complete analysis of grasping configurations of a spatial continuum manipulator consisting of three constant-curvature sections, for any given 3-D object. We formulate conditions for existence of solutions and describe how to determine valid grasping configurations. Our method can extend to general continuum manipulators of n constant-curvature sections (where n ≥ 3).

This paper presents a novel constraint-based six degree-of-freedom (6-DoF) haptic rendering algorithm for simulating both contact forces and torques between interacting rigid bodies. We represent an object using a hierarchy of spheres, i.e., a sphere-tree. Such a representation allows fast detection of multiple contacts/collisions among objects and facilitates contact constraint formulation. Given a moving graphic tool as the avatar of the haptic tool in the virtual environment, we constrain its position and orientation, i.e., its six dimensional configuration, by solving a constrained optimization problem. The constraints in the 6-D configuration space (C-space) of the graphic tool is obtained and updated through on-line mapping of the non-penetration constraint between the spheres of the graphic tool and those of the other objects in the three dimensional physical space, based on the result of collision detection. The problem is further modeled as a quadratic programming problem and solved by classic active-set methods. Our algorithm has been implemented and interfaced with a 6-DoF Phantom Premium 3.0. We demonstrate its performance in dental surgery simulations involving complex, multi-contact virtual environments. Our method enables stable operations and realistic feel of haptic sensation.

On-line, efficient perception based on sensing is essential for an autonomous robot to operate in an unknown and unpredictable environment. An efficient on-line algorithm is introduced to determine whether a robot at a future time t and a configuration q will be guaranteed collision-free, directly from real-world sensor data of the robot's environment at the current time τ, using stereo vision sensor. Such a problem can be formulated as checking the intersection between the so-called dynamic envelope, which relates to the robot at a configuration-time (CT) point (q; t) and the current sensing time τ, and the atomic obstacles, which are obtained directly from low-level sensory data at τ. The algorithm achieves real-time efficiency, as confirmed by the experimental results, by classifying the atomic obstacles possibly intersecting the dynamic envelope and by grouping relevant atomic obstacles on the fly. It is suitable to be used on-line by sensing-based motion planners.

Continuum manipulators, featuring “continuous backbone structures”, are promising for deft manipulation of a wide range of objects under uncertain conditions in less-structured and cluttered environments. A multi-section trunk/tentacle robot is such a continuum manipulator. With a continuum robot, manipulation means a continuous whole-arm motion, often without a clear distinction between transport and grasping. In this paper, we address the novel problem of real-time motion planning for such a robot under uncertain conditions. We present an algorithm for on-line planning the motion of a planar continuum robot for grasping a target object amid an environment of other objects with uncertain movements. Our algorithm substantially extends the RAMP paradigm for real-time adaptive motion planning to this new form of whole-arm manipulation. Simulation results are promising, demonstrating the effectiveness of our approach.

Navigation of a car-like robot in environments with unknowns requires effective on-line planning of nonholonomic trajectories. We propose a set of basic maneuver patterns based on Bezier curves that allow either forward or backward motion as building blocks to create nonholonomic trajectories quickly, given a sequence of knot positions/points (e.g., from some GPS navigator). These maneuver patterns are particularly useful for generating feasible trajectories in crowded environments with many narrow passages. We embed the above techniques in a new planner suitable for on-line planning of nonholonomic and collision-free trajectories, called the ON planner. Our ON planner enables that, given a sequence of rough knot points, a car-like robot can simultaneously plan and move in a geometrically unknown, crowded environment with local sensing towards a goal. Simulation results demonstrate the planner's nice capabilities.

This paper introduces a novel and flexible simulation platform for studying pursuit and evasion in unknown 2-D environments of arbitrary obstacles, in an effort to expand the practical application of pursuit-evasion research. The platform provides realistic simulation of the sensing capability of each robotic agent (either a pursuer or an evader). Each agent uses real-time local sensing to collect information from the environment while it simultaneously plans and executes its motion to best satisfy one or more objectives. The evader's objectives are to reach a specific goal location as quickly as possible and to avoid being caught by the pursuer. The pursuer's objectives are to locate and capture the evader whose motion is unknown, and when the evader is not seen, explore the environment and predict where the evader may be. Under a common real-time planning paradigm, each agent's planner dynamically adapts its goals and objectives to the agent's changing circumstances so that the agent can always choose the best course of action. Simulation results have shown that the introduced approach is an effective means to study sophisticated pursuit-evasion scenarios and accomplish objectives for both the pursuer and the evader in an unknown environment. The platform can be easily expanded to accommodate multiple agents in more complex pursuit-evasion tasks.

In this paper, a new method to model the global deformation between a rigid object and an elastic object with a hole is presented. This method extends the idea of beam-skeletons [10] by introducing curved cantilever beams for efficient modeling of global deformation of elastic objects with holes. The method is implemented and tested on different examples. Results from three examples are given to demonstrate the efficiency and effectiveness of the approach.

This paper addresses continuous collision-checking of a high-DOF robot trajectory in a completely unknown and unpredictable environment (i.e., obstacles are unknown and their motions are also unknown). In, the authors introduced how to discover, if a robot at configuration q at a future time t is guaranteed collision-free or not using the novel concept of the dynamic envelope and atomic obstacles based on sensing in such an unknown and unpredictable environment. In this paper, we further show that if a point (q, t) in the robot's configuration-time space (CT-space) is discovered collision-free, a neighborhood (CT-region) of (q, t) is also guaranteed collision-free. Based on that, given a continuous robot trajectory, we present a method to compute a set of discrete CT-points such that, if these points are discovered to be guaranteed collision-free, their associated collision-free neighborhood CT-regions contains the continuous trajectory, i.e., the trajectory is guaranteed continuously collision-free.

This paper addresses a largely open problem in haptic simulation and rendering: contact force and deformation modeling for haptic simulation of grasping a deformable object with a realistic virtual human hand, especially in power grasps. The virtual hand model consists of meshes of realistic shapes for the finger links and palm of a hand. We tackle the problem by adopting the non-linear contact force model and the beam-skeleton model for global shape deformation introduced in [5]. The results verify the efficiency of contact force and deformation modeling for both power grasp and precision grasp of deformable objects with reasonable realism.

This paper introduces a new approach to establish a good grasp for a novel object quickly. A comprehensive knowledge base for grasping is learned that takes into account the geometrical and physical knowledge of grasping. To automate the learning process as much as possible, learning happens in a virtual environment. We used the GraspIt! [16] simulation environment with the Barrett hand for this work. As only approximate features of objects are used for training the grasping knowledge base (GKB), the knowledge gained is rather robust to object uncertainty. Based on the guidance of the GKB, a suitable grasp for a novel object can be found quickly. The newly gained grasping information of the new object can also be feedback to the GKB so that the knowledge base continues to improve as it is exposed to more grasping cases. The GKB serves as the “experience” of the robotic gripper to make grasping more and more skillful. We implemented the approach and tested it on a wide variety of objects. The results show the effectiveness of this approach to achieve quick and good grasps of novel objects.

This paper introduces a novel and general real-time adaptive motion planning (RAMP) approach suitable for planning trajectories of high-DOF or redundant robots, such as mobile manipulators, in dynamic environments with moving obstacles of unknown trajectories. The RAMP approach enables simultaneous path and trajectory planning and simultaneous planning and execution of motion in real time. It facilitates real-time optimization of trajectories under various optimization criteria, such as minimizing energy and time and maximizing manipulability. It also accommodates partially specified task goals of robots easily. The approach exploits redundancy in redundant robots (such as locomotion versus manipulation in a mobile manipulator) through loose coupling of robot configuration variables to best achieve obstacle avoidance and optimization objectives. The RAMP approach has been implemented and tested in simulation over a diverse set of task environments, including environments with multiple mobile manipulators. The results (and also the accompanying video) show that the RAMP planner, with its high efficiency and flexibility, not only handles a single mobile manipulator well in dynamic environments with various obstacles of unknown motions in addition to static obstacles, but can also readily and effectively plan motions for each mobile manipulator in an environment shared by multiple mobile manipulators and other moving obstacles.

This paper considers the problem of planning motions for a team of mobile manipulators working in the same environment with a common task objective. It presents a distributed, real-time algorithm to plan motion trajectory for each team member that allows dynamic and spontaneous division of work among team members to meet the common task objective. A mobile manipulator has to perform its share of the task while avoiding other moving mobile manipulators in the team in addition to other obstacles in the environment. To each robot team member, none of the trajectories of the other team members or moving obstacles are known beforehand. The approach is implemented and tested in simulated task environments, which demonstrates its high effectiveness and efficiency.

Contact and deformation modeling for interactive environments has seen many applications, from surgical simulation and training, to virtual prototyping, to teleoperation, etc., where both visual feedback and haptic feedback are needed in real-time (kHz). In this paper, we consider contacts between a rigid body and an elastic object and address a little studied problem: the modeling and rendering of compliant twisting or rotation of the rigid body on the surface of the elastic object and the associated effects in the deformation of the elastic object. We present a unique strategy to model the contact torques applied to the rigid body and the resulted shape deformation of the elastic object. This strategy extends the general paradigm of contact and deformable modeling introduced by the authors earlier [1] so that not only contact forces but also contact torques, not only compliant translations but also compliant rotations of the rigid body, as well as the resulted deformations of the elastic object can all be simulated in a combined update rate of over lfeHz. The strategy is implemented, and the experimental results confirm its effectiveness and efficiency.

Information of high-level, topological contact states is useful and sometimes even necessary for a wide range of robotic tasks involving interactions between a robot and its environment or objects of manipulation. While most of the existing research is focused on contact states between two rigid bodies, this paper presents a practical approach to represent concisely and generate automatically graphs of contact states between a polygonal object and an articulated planar object, i.e., a planar kinematic chain. The approach effectively exploits topological and geometrical constraints associated with such contact states to ensure both correctness and efficiency, as demonstrated by the implementation and applied examples.

This paper considers the problem of planning closed-chain motion for a pair of mobile manipulators to transport a common payload in a dynamically unknown environment (i.e., an environment with moving obstacles of unknown motion). We present a novel algorithm to plan the actions of the two robots in the team, one leader and one helper, in real-time to accomplish the task while avoiding other obstacles in the unknown dynamic environment. Our algorithm does not assign fixed roles to the two team members, but rather it dynamically decides who should lead based on circumstances to optimize the team’s performance. The planner is readily extensible to handle a team of more than two robots in tight collaboration. The approach is implemented and tested in simulated task environments, which demonstrate the planning algorithm’s effectiveness and efficiency.

Contact and deformation modeling for interactive environments has seen many applications, from surgical simulation and training, to virtual prototyping, to teleoperation, etc., where both visual feedback and haptic feedback are needed. High-quality feedback demands a high level of physical realism as well as a high update rate in rendering, which are often conflicting requirements. In this paper, we present a unique approach to modeling force and deformation between a rigid body and an elastic object under complex contacts, which achieves a good compromise of reasonable physical realism and real-time update rate (at least 1 kHz). We simulate contact forces based on a nonlinear physical model. We further introduce a novel approximation of material deformation suitable for interactive environments based on applying Bernoulli-Euler bending beam theory to the simulation of elastic shape deformation. Our approach is able to simulate the contact forces exerted upon the rigid body (that can be virtually held by a user via a haptic device) not only when it forms one or more than one contact with the elastic object, but also when it moves compliantly on the surface of the elastic object, taking friction into account. Our approach is also able to simulate the global and local shape deformation of the elastic object due to contact. All the simulations can be performed in a combined update rate of over 1 kHz, which we demonstrate in several examples.

This paper addresses representation and automatic generation of topological contact states between two 3-D curved objects. Information of contact states is useful for a wide range of applications, from robotic tasks involving compliant motion to virtual prototyping and simulation. As contact states between 3D curved objects are more commonplace and yet more complex and less studied, this work is more necessary. The approach has been implemented, and the implemented examples demonstrate the effectiveness of the approach

Contact detection based on computing minimum distance is a fundamental issue important to many applications. A largely unsolved problem is how to detect multiple contacts that are formed simultaneously between non-convex and non-polyhedral general objects both accurately and in real-time. This paper presents an effective solution to the problem. Our approach first locates the pairs of closest components by fast intersection checking based on hybrid bounding volume hierarchies of surface components. For each pair of such components, it then finds the pairs of closest points and corresponding pairs of closest parametric features by combining collision detection or minimum distance query between polygonal meshes of those components and exact distance computation between the parametric features. Implementation results show that this approach can compute multiple simultaneous contacts between general objects both very accurately and efficiently in the order of several milliseconds regardless of the numbers of features on the objects

While there are very high industry demands on optical fiber, little research has been done on the modeling and simulation of the optical fiber assembly. In this paper, the interaction forces in the micro/nano joining step of the optical fiber assembly are modeled. Simulation of assembly in a virtual environment via a haptic device is performed, and experimental results are discussed, which could be used for designing leaning-based controller for automated micro/nano-scale optical fiber assembly

This video demonstrates a real-time adaptive motion planner for a mobile manipulator to accomplish place-to-place tasks in a dynamic environment with obstacles of unknown motion. Paths and trajectories are planned simultaneously as the robot moves and globally subject to some optimization criteria based on evolutionary computation. The robot always follows the current best trajectory with respect to predictions of obstacle motions through sensing. At any time the robot may switch seamlessly to a better trajectory as the planner continues to improve or adapt trajectories to the changing environment. To minimize energy and time, the planned arm and base trajectories are loosely-coupled so that the arm may stop its motion (relative to base) for some period while the base moves, or vice versa, in handling obstacles.

In this paper a novel formalism to characterize contact states between an articulated polyhedral object and a polyhedral environment for the generation of the graph of feasible contact states between them is presented. This formalism is based upon a particular representation of the stratification of the configuration space of the articulated object by means of oriented matroid theory. A stratification is a decomposition of a set into a collection of manifolds which in our case correspond to the different contact states between the articulated object and the environment. In the representation of the stratification of the configuration space using oriented matroid theory the topological properties of the different strata are represented at a purely combinatorial level. An algorithm to enumerate the existing strata and to find the adjacency relationships among them is proposed. It will be shown that the symbolic computation based on oriented matroids simplifies and in some cases even replaces the computation with coordinates.

Information of high-level, topological contact states is useful and even necessary for a wide range of applications, including many robotics applications. While there is considerable research related to topological contact states between two polyhedral objects, little is studied about how to characterize, represent, and automatically generate topological contact states between curved objects. In this paper we extend the representation of topological contact states between polyhedral objects to general planar curved objects in terms of contacting curve elements, obtained from curvature monotonic segmentation [6]. We further introduce an approach to generate automatically graphs of such contact states between two planar curved objects, which represent not only valid contact states but also adjacency relations among those contact states. Implementation results of the related algorithms demonstrate the effectiveness of our approach. The approach can be naturally extended to generation of contact states between 3-D curved objects.

This paper presents the compliant task generator: a new approach for the automatic conversion of a geometric path generated by a compliant path planner to a force based task specification for a compliant robot controller. Based on the geometric model of a moving object and its environment, a compliant path planner generates a set of six-dimensional positions x/sub 1...m/ and their corresponding contact formations CF/sub 1...n/. The compliant force controller, which executes a planned path under force feedback using the hybrid control paradigm, expects a desired force w/sub d/, velocity t/sub d/ and position x/sub d/ at each time-step, together with their force and velocity controlled subspaces W and T. To specify these controller primitives, we add information about the desired dynamic interaction between the moving object and its environment, in the form of the desired kinetic energy E/sub kin/ of the moving object and the potential energy E/sub pot/ in the contacts with the environment, together with the inertia and stiffness matrix M and S. We fully automated the conversion process of the compliant planner output together with the added information about the dynamic interaction, to a force based task specification. This eliminates the requirement of human intervention between the planning and execution phase. The presented approach applies to all compliant motions between polyhedral objects, and is verified in a real world experiment.

Haptic rendering has the potential to increase the quality of human-computer interaction with virtual environment by accommodating the sense of touch. In this paper, a 7 DOF arm type exoskeleton device is designed and implemented. Human user can haptically interact with virtual environment by using this light-weight device. The principles of measuring user's arm motions are presented, which include the dimensional mechanism. The motion of each joint of the proposed haptic device is nearly independent. The virtual contact force is also calculated in real time to meet the stringent requirement of real time haptic rendering. Experiments results show promising feasibility of the arm type exoskeleton device.

Information of high-level, topological contact states is useful and even necessary for a wide range of applications, including many robotic applications. A contact state between two polyhedral objects can be effectively represented as a contact formation in terms of a set of principal contacts between faces, edges, and vertices of the two objects. However, little is done to characterize and represent contact states between curved objects. In order to facilitate the representation of contact states between such objects, we introduce a novel approach to segment the boundary of curved objects based on monotonic changes of curvatures, which we call the curvature monotonic segmentation. We specifically apply this approach to curved 2D and 3D objects with boundary curves or surfaces represented by algebraic polynomials of degrees up to 2. The segmentation yields curvature monotonic faces and edges (or pseudo edges), and vertices (or pseudo vertices). With these faces, (pseudo) edges, and (pseudo) vertices, we effectively extend the concept of contact formation to curved objects to represent high-level, topological contact states between such objects with the same desirable characteristics as the contact formations between polyhedral objects.

Compliant motion is required or desirable in many robotic tasks, especially assembly tasks. Both planning and execution of autonomous compliant motion requires the knowledge of contact states between parts in contact beforehand. Previous research has addressed automatic generation of contact states between rigid objects. However, not all such contact states can be possibly reached if a rigid object is attached to and moved by a manipulator due to the manipulator constraints. In this paper, we study the problem of finding feasible contact states between a polyhedral part A held by a manipulator with a fixed base and a fixed polyhedral part B. Given a contact state graph between the unattached part A and the fixed part B, our approach then attaches A to the manipulator model and checks the reachability of each contact state and the connection between two neighboring contact states by applying a virtual compliant controller to the manipulator to test possible compliant motions of A. Implementation results validate the effectiveness of our method.

While there has been a large body of literature addressing offline path planning for manipulators, there is relatively less study on real-time motion planning that occurs as a manipulator moves in an environment with unknown obstacles or unknown changes. This paper introduces a unified and general motion planning approach based on evolutionary computation that is suitable for both offline and real-lime adaptive motion planning for manipulators under various optimization criteria and manipulator constraints in environments with obstacles or changes not known a priori. The implementation and testing results demonstrate the effectiveness and efficiency of the approach.

As digital cameras become more affordable, digital video now plays an important role in medical education and healthcare. In this paper, we propose a novel framework to facilitate semantic classification of surgery education videos. Specifically, the framework includes: (a) semantic-sensitive video content characterization via principal video shots, (b) semantic video classification via a mixture Gaussian model to bridge the semantic gap between low-level visual features and semantic visual concepts in a specific surgery education video domain.

This paper models the effects of different contact formations and compliant motion on haptic rendering, taking into account friction and gravity. When a held rigid object interacts with another rigid object (in a task such as assembly), the force and moment felt by the operator at any instant depend not only on the contact region but also on the type of the contact state and the type of motion of the held object prior to reaching the current contact configuration, especially in the presence of friction and gravity. We address the modeling of such haptic effects by extending our study for the case of two interacting convex polyhedral rigid bodies to the more general case of interacting non-convex polyhedral objects involving more complex contact formations and compliant motion.

This paper presents a new algorithm for real-time tracking of pairs of closest points as well as their corresponding surface features between certain general types of objects (which can be non-convex) with parametric curved surfaces. The fact that the algorithm works directly on accurate parametric descriptions of curved surfaces rather than polygonal approximation of surfaces (i.e., polygonal meshes) enables it to not only provide accurate collision detection among certain curved objects in real-time, but more importantly, also provide accurate description of the state of a collision, i.e., the actual regions of contact in real-time. Such capability is very useful in applications requiring high accuracy in real-time, including certain haptic rendering tasks for virtual prototyping or virtual training. Test results show that the algorithm achieves correct tracking in the rate of 1 kHz.

Stratification of compliant control requires that we know whether, for any contact configurations under the same contact formation, them exists a CF-compliant motion connecting them. This motivates the question of whether a given CF has disjoint regions of configurations. It is the geometric features of the contacting objects that may cause disjoint regions of contact configurations under the same topological contact formation. In this paper we further analyze such geometric features between two contacting polygons. This paper presents a vocabulary and a hierarchical method that we have found useful in analyzing CFs to determine the connectedness of their regions of CF-compliant configurations. The hierarchical analysis method simplifies the detection of disjoint regions in a CF through a series of tests of increasing complexity on the geometric relations between the two objects in contact under the CF.

When a held object interacts with another object (in a task such as assembly), the haptic force and moment felt by the operator at any instant depend not only on the contact region but also on the type of the contact state and the type of motion of the held object prior to reaching the current contact configuration, especially in the presence of friction and gravity. In this paper, we address the influence of contact state and motion types on haptic force and moment and present an efficient method to model such haptic effects resulted from the interaction of two convex polyhedral solids, taking into account friction and gravity.

In robotic tasks and in mechanism design, planning motion compliant to contacts is often desired, but planning such motion poses special challenges not present in collision-free motion planning. One challenge is how to achieve exactness, i.e., how to make sure that a planned path is exactly compliant to a desired contact state, especially when the configuration manifold of such a contact state is hard to describe analytically due to high geometrical complexity and/or high dimensionality. We tackle the problem with a hybrid approach of direct computation to exploit contact constraints and randomized planning. We describe such a planner for planning motion compliant to a contact formation between two arbitrary polyhedra and present results of implementation.

Random sampling strategies play critical roles in randomized motion planners, which are promising and practical for motion planning problems with many degrees of freedom (dofs). In this paper, we explore random sampling in a constrained configuration space-the contact configuration space between two polyhedra, motivated by the need for generating contact motion plans. Given a contact formation (CF) between two polyhedra A and B, our approach is to randomly generate configurations of A satisfying the contact constraints of the CF. Key to the approach is to guarantee that sampling happens only in the constrained space to be efficient, which has not been addressed in the literature. We have implemented a strategy for random sampling of configurations constrained by CF consisting of a single principal contact (PC) with good results. We plan to further extend the approach to CFs with multiple PCs, and apply the results to contact motion planning.

An object with certain geometric features, when it is in contact with another object, may cause disjoint regions of contact configurations under the same topological contact formation (CF). In this paper we analyze such geometric features and introduce the concept of limiting channel element of CF-compliance (LIMITEL). We further develop a simple algorithm for finding potential LIMITELs of an arbitrary polygon that may cause disjoint regions of contact configurations, given a second, contacting polygon. The algorithm is purely geometric and assumes exact knowledge of the geometries of the objects.

Planning contact motion is important for many robotic tasks but difficult in general due to high variability and geometrical complexity of contact states. It is desirable to decompose the problem into simpler subproblems. A promising decomposition treats the problem as consisting of: 1) automatic generation of a discrete contact state graph, and 2) planning contact transitions between neighboring contact states and contact motions within the same contact state. This paper addresses a divide-and-merge approach on solving the general problem by such a decomposition. It discusses issues related to solving the two subproblems and provides examples of automatically generated contact state graphs between two contacting 3D polyhedra by the approach, which extend the results for 2D polygons reported by Ji et al. (1999).

Planning in contact state space is very important for many robotics tasks. This paper introduces a general and novel approach for automatic creation of high-level, discrete contact state space between two objects, called contact formation (CF) graphs. A complete CF graph is the result of merging several special subgraphs, called the goal-contact relaxation graphs. We have implemented our algorithm for arbitrary contacting polygons, and the results obtained are presented in this paper. The implementation is extended for arbitrary contacting polyhedra. The time complexity of our algorithm is bounded by O(M/sup 2/), where M characterizes the maximum complexity of the two objects.

Recognition of contact states is often necessary or preferred in planning and executing contact-based assembly motions in the presence of uncertainties. However, due to inevitable uncertainties, not all contact states can be identified at all contact configurations. A crucial question is what kinds of contact states at what kinds of configurations are impossible to be distinguished or identified. We address the question by analyzing the recognizability of contact states between convex polyhedral objects with both position/orientation and force/moment sensing in the presence of sensing uncertainties, i.e., by characterizing configurations where contact states are intrinsically indistinguishable with those sensing means. To reflect contact recognizability in contact representation, we propose a fuzzy definition of contact states. We further introduce a practical approach towards real-time automatic contact state identification based on the recognizability analysis.

Based on evolutionary computation (EC) concepts, we developed an adaptive evolutionary planner/navigator (EP/N) as a novel approach to path planning and navigation. The EP/N is characterized by generality, flexibility, and adaptability. It unifies off-line planning and online planning/navigation processes in the same evolutionary algorithm which 1) accommodates different optimization criteria and changes in these criteria, 2) incorporates various types of problem-specific domain knowledge, and 3) enables good tradeoffs among near-optimality of paths, high planning efficiency, and effective handling of unknown obstacles. More importantly, the EP/N can self-tune its performance for different task environments and changes in such environments, mostly through adapting probabilities of its operators and adjusting paths constantly, even during a robot's motion toward the goal.

A complete, precise, and systematic analysis on the geometrical nature of contacts between two arbitrary polygons and derivation of the geometric contact constraints between two such polygons are provided. Based on the results, a general algorithm is presented to identify the geometrically valid contact formations (CFs) from a given set S/sub pc/ of possible principal contacts (PCs) between two polygonal objects with location uncertainties. For any (nonempty) subset of S/sub pc/, the algorithm tests if the PCs in the set form a possible CF by verifying the geometrical contact constraints. The obtained set of geometrically valid CFs can serve as input to an additional verifier based on force sensing which can extract the actual CF from the set. The notion of equivalent CFs is introduced to describe those contact situations constraining the relative location between two objects to the same region. This concept proves to be extremely useful to the completeness of the analysis and efficiency of the algorithm. Of the many discoveries, a particularly significant one is that despite uncertainties in object locations, in many cases, if two or more PCs are formed between two objects, their relative location is fixed or can take up to only four solutions.

Distance computation is essential for collision prediction and/or detection in real-world robotic tasks, computer simulation and animation, and CAD/CAM. This paper addresses distance computation to deal with a rarely researched type of collision prediction/detection problem: Given two objects in certain contact, determine if and when a relative rotation constrained by contact will cause a collision (which results in a new contact state) between the two objects. The authors use the positive angle of rotation as the measure of rotation distance and present a method to compute, given two contacting convex polyhedra G and H and a rotation axis containing contact point(s) between them, the shortest rotation distance (SRD) of G which will cause new collision between G and H. The method is fully implemented and used in a computer simulation system for a contact-based fine motion planning scheme. The algorithm is also efficient. If each vertex of G or H is the intersection of n/sub e//spl nu// edges, the worst-case time complexity of the algorithm is O(n/sup 2//sub e//spl nu//). This means that for two arbitrary trihedral polyhedra, the algorithm has a constant worst-time complexity.

A large number of robotic tasks require precision and thus the dealing with uncertainties. The effects of various uncertainties often manifest to location (i.e., position and orientation) uncertainties of objects. Thus, an important problem that often arises is how to assess the region that an object may occupy in the presence of uncertainties. This paper addresses the problem by describing how to grow exactly an arbitrary polyhedral object in the three-dimensional Cartesian space by its position and/or orientation uncertainties. Three types of related regions for the object are described: (1) the grown regions, regions possibly occupied by the object due to uncertainties in its position, orientation, or both, (2) the grown shell regions, regions possibly occupied by the boundary (surfaces) of the object due to uncertainties in its position, orientation or both, and (3) the core regions, regions (which could be empty) definitely occupied by the object in spite of uncertainty. The exact representations introduced in this paper can serve as benchmarks against which efficient but approximate algorithms may be evaluated. A particularly important application of the grown shell regions is in obtaining the set of all possible topological contacts among polyhedral objects due to location uncertainties. Such a set can serve as a basis from which more precise contact information can be extracted by additional sensing means, such as vision and force/moment sensing. The approach for this application and its implementation is introduced and discussed.

An implemented algorithm is presented for finding all principal contacts possibly established between two surface features (i.e. faces, edges, or vertices) of two polyhedral objects due to location (i.e. position and orientation) uncertainties. The algorithm FAPRIC (finding all principal contacts) requires as inputs: the estimated locations of the two objects, the geometric models of the objects, and the bounds on position and orientation uncertainties. The algorithm is based on checking intersections between the grown regions of the objects by location uncertainties with the S-tope model. It is very efficient and apt for real-time processing. The information obtained can serve as a guide for more accurate extraction and further reasoning of the contact data, possibly with additional sensors. As the surface of an arbitrary object can be approximated by planar patches, the algorithm can also be applied to general objects. The work is motivated by the need for automatically recognizing contacts in spite of uncertainties in robotic tasks.

A general strategy is presented to determine the geometrically valid contact formations (CFs) from a given set S/sub pc/ of possible principal contacts (PCs) between two arbitrary polygonal objects in the presence of location uncertainties. For any (non-empty) subset of S/sub pc/, the strategy tests if the PCs in the set form a possible CB by analyzing the geometrical contact constraints. The obtained set of geometrically valid CFs can serve as input to a verifier based on force sensing which will identify the actual CF occurred. Our analyses of contact constraints are complete and general. The results demonstrate that despite uncertainties in object locations, if two or more PCs are formed between two objects, their relative location in many cases is fixed or can take up to only 4 solutions. In such cases, we can accurately identify a valid CF. From a different perspective, these results could also be useful in grasp planning. Our future work includes taking into account modeling uncertainties of objects and extending this method to three-dimensional objects.

An Evolutionary Navigator (EN) is presented for mobile robot navigation through an environment with unknown obstacles. Based on the concept of genetic algorithms, the EN can search paths of different user-defined levels of near-optimization in the entire, continuous free space using only a simple data structure. It unifies off-line and online planning processes and provides the flexibility to solve the conflict between efficiency and optimality. It also provides high safety measures without requiring complete information about the obstacles sensed.>

This paper provides a general and exact method of growing a polyhedral object in three-dimensional Cartesian space to take into account its orientation and position uncertainties. The work is particularly motivated by the need for automatically recognizing contact situations among objects in spite of uncertainties. The technique of growing surface elements of a polyhedron by uncertainty can be used to extract the set of all possible contact situations among polyhedral objects in the presence of location uncertainties, which can then serve as a basis for further and more accurate extraction of contact information by additional sensing means, such as vision and force/moment sensing.>

High-precision assembly tasks cannot be successfully done by robots without taking into account the uncertainties that can cause failure of robot motion. The authors address this problem by planning robot motions at two levels: nominal planning, which assumes no uncertainty, and dynamic replanning, to deal with uncertainties that would cause nominal plans to fail. They introduce a replanning approach based on knowledge of contacts among assembly parts. It consists of patch planning to resolve the case when a commanded robot motion prematurely stops at a contact other than those planned, and motion strategy planning, to regulate robot motions in order to guarantee the eventual success of a task. A task-independent strategy for patch-plan generation based on concepts of contact planes and abstract obstacles is developed. It is also shown how to apply motion strategies so that, under proper design and motion constraints, the replanning can be guaranteed to succeed.>

The authors assume a nominal motion plan for the zero-error situation and devise a simple replanning strategy based on the availability of force, moment, and position sensors to handle errors that may arise during program execution. They develop design constraints relating the parameters of the strategy, parameters of the sensor, control and manufacturing errors, and nominal design parameters. If the constraints are satisfied, the replanning strategy can theoretically be guaranteed to be successful. The constraints are shown to be reasonable in the sense that they do not impose unrealistic conditions on typical design. Simulation results uphold the theoretical derivations and show empirically that the theoretical constraints can be relaxed somewhat with excellent results obtained.>