This paper presents a biped humanoid robot that is able to walk on a rough terrain while touching a handrail. The contact wrench sum (CWS for short) is used as the criterion to judge if the contact between the robot and the environment is strongly stable under the sufficient friction assumption, where the contact points are not coplanar and the normal vectors at the points are not identical. It is confirmed that the proposed pattern generator can make the robot walk as desired in dynamics simulations and experiments, and the motions can be improved by a hand position control and using waist joints.

This paper presents a motion pattern generator of humanoid robots that walks on a flat plane, steps and a rough terrain. It is guaranteed rigorously that the desired contact between a humanoid robot and terrain should be maintained by keeping the contact wrench sum between them inside the contact wrench cone under the sufficient friction assumption. A walking pattern is generated by solving the contact wrench equations and by applying the resolved momentum control.

We discuss a ZMP-based running pattern generation for a biped robot equipped with toe springs. Our biped robot HRP-2LT has twelve active DoFs for its legs and two passive DoFs for its toes. The trajectory of the center of mass is designed to realize the specified running motion and the foot trajectories are determined to get proper spring action at lift off phases. They are interpreted into joint angles by using the resolved momentum control. By the simulation and the preliminary experiment, it is shown that the toe springs are effectively used for running and hopping.

This paper presents a motion planner of getting up motion using Mahalanobis distance. It is an indispensable function for humanoid robots to get up by itself and some humanoid robots are able to get up by themselves, but the motion can start only from the states specified a prior. The robots have to get up from an arbitrary lying state which may result after an unexpected falling. The proposed method (l) determines the degree of similarity between the current falling state and predefined falling states using Mahalanobis distance, (2) generates a collision-free motion to the most similar state, and (3) plans a sequence of motions using a state transition graph.

This paper proposes a method of a real-time gait planning for humanoid robots which can change stride immediately at every step. Based on an analytical solution of an inverted pendulum model, the trajectories of the COG (center of gravity) and the ZMP (zero-moment point) are parameterized by polynomials. Since their coefficients can be efficiently computed with given boundary conditions, this framework can provide a real-time walking pattern generator for humanoid robots. To handle the unexpected result caused by immediate changes of foot placement, we made single support periods as an additional trajectory parameter and the ZMP fluctuation was suppressed by mixing the opposite phase of the ZMP error. The effectiveness of our method is shown by experiments of the humanoid robot HRP-2.

This paper studies an optimal planning of falling motions of a human-sized humanoid robot to reduce the damage of the robot. We developed a human-sized robot HRP-2FX which has a simplified humanoid robot shape with seven d.o.f. and can emulate motions in the sagittal plane of a humanoid robot. An optimal control is applied to generate the falling motion of HRP-2FX to minimize a performance index, and the optimality has been verified by the experiments on HRP-2FX.

In this paper, we plan the collision free motion for walking pattern generation of a humanoid robot. Our motion planner can take into account several features of the walking pattern generator. We first run the walking pattern generator by considering the contact wrench applied to the robot and monitor the collision among the links and the environments. Then, we plan the collision free motion for the period of time causing the collision. In our motion planner, we can consider the constraint condition which are the functions of time. Also, for keeping balance of the robot, we plan the motion with keeping the horizontal position of the COG as well as the position/orientation of the feet/hand. The effectiveness of the proposed method is confirmed by simulation and experiment.

We propose a simulation system that achieves realistic and efficient simulations of humanoid robots. This paper focuses on a constraint-based contact force solver and virtual spring-damper joints from among the components of the system. The contact force solver can accurately simulate contacts between rigid bodies including articulated rigid bodies. LCP-like formulation of constraint conditions is solved by an iterative calculation method that extends the Gauss-Seidel method. This paper clarifies how to integrate existing methods to implement a robust and efficient solver. Virtual spring-damper joints are proposed to simulate a shock absorbing mechanism that many biped humanoid robots have in their feet to increase the stability of walking motion. The combination of the rigid contact model and the elastic virtual joints can improve the accuracy of the simulation. The simulation system was verified by experiments using humanoid robot HRP-2, and the results shows the validity of the system.

This paper proposes a universal stability criterion of the foot contact of legged robots. The proposed method checks if the sum of the gravity and the inertia wrench applied to the COG of the robot, which is proposed to be the stability criterion, is inside the polyhedral convex cone of the contact wrench between the feet of a robot and its environment. The criterion can be used to determine the strong stability of the foot contact when a robot walks on an arbitrary terrain and/or when the hands of the robot are in contact with it under the sufficient friction assumption. The determination is equivalent to check if the ZMP is inside the support polygon of the feet when the robot walks on a horizontal plane with sufficient friction. The criterion can also be used to determine if the foot contact is sufficiently weakly stable when the friction follows a physical law. Therefore, the proposed criterion can be used to judge what the ZMP can, and it can be used in more universal cases

A biped walking pattern generator which allows an additional ZMP control (auxiliary ZMP) is presented. An auxiliary ZMP is realized by an inverse system added to a pattern generator based on the ZMP preview control. To compensate the effect of the auxiliary ZMP, we apply virtual time shifting of the reference ZMP. As an application of the proposed method, a walking control on uneven terrain is simulated. The simulated robot can walk successfully by changing its walking speed as the side effect of the auxiliary ZMP control

In this paper we realize a real-time communication on Ethernet and develop an onbody distributed control system for a humanoid robot, HRP-3P. Real-time communication on Ethernet is realized by (1) a communication method using the data link layer directly and (2) timing control using a real-time operating system ARTLinux. This enables us to reduce the cost of embedded systems and improve developmental efficiency. A CORBA implementation which works on this communication layer is also developed to increase compatibility with existing software. Finally a small-size distributed robot controller is developed for the onbody network of HRP-3P and a distributed I/O system is developed on top of this

This paper presents a motion suspension system to suspend humanoid motion in case of emergency. Once humanoids start their motions in human daily environments, there is a possibility that humanoids will meet with several emergencies such as hurting humans and injuring themselves. Even so, humanoids should be controlled so that they avert such emergencies in real-time. To realize this demand, we propose a method of real-time judgment of emergency prediction by humanoids. We also propose a simple and effective method of real-time pattern generation to force humanoids to stop immediately by one step without falling. To verify the validity of the proposed method, we finally present experimental results using a humanoid robot HRP-2, which include experiments at 2.8 [km/h] walks

A motion planner of emergency stop must make an operating humanoid robot to a stationary state under the emergency signal. It plays an important role in prevention of falling over because humanoid robots fall over easily. Immediately after the emergency signal, it must generate the emergency stop motion in real-time. We modeled a humanoid robot as a simple dynamic system consists of ZMP (zero-moment point) and COG (center of gravity) as its states. The emergency stop motion is generated by a state feedback. We determined optimal feedback gains in terms of the initial conditions and the pole assignment. The proposed method realized a reliable emergency stop with low computational cost. Furthermore, it can easily predict the possibility of the successful emergency stop at any time. The validity of the proposed method is confirmed by an experiment using humanoid robot HRP-2

In this paper, we analyze the balance of a humanoid robot during manipulation tasks. By defining the generalized zero-moment point (GZMP), we obtain the region of it for keeping the balance of the robot during manipulation. During manipulation, the convex hull of the supporting points forms the 3-D convex polyhedron. The region of the GZMP is obtained by considering the infinitesimal displacement and the moment about the edges of the convex hull. We show that we can determine whether or not the robot may keep balance for several styles of manipulation tasks, such as pushing and pulling an object. The effectiveness of our proposed method is demonstrated by simulation.

This paper studies the balance of a humanoid robot carrying a heavy object. Without knowing the mass and the position of the center of gravity of the object, the humanoid robot carries a heavy object stably by using the force sensor information attached at the wrists and the ankles. We first show how to generate the motion of a humamoid robot by taking the force sensor information into consideration. We also show the method for generating the gait pattern by taking the dynamics of the carried object. The effectiveness of the proposed method is shown by experiments.

This paper proposes a method for a humanoid robot to generate 3D model of the environment using a stereo vision, find a movable space using it and plan feasible locomotion online. The model is generated by an accumulation of 3D grid maps which are made from the range data of the field of view obtained by a correlation based stereo vision. The locomotion is planned by an online whole body pattern generator which can modify robot’s waist height, an upper body posture and so on according to the size of the movable space.

This paper describes a generation method for spatially natural biped walking. By limiting the COG (Center of Gravity) motion space to a sculptured surface, the degree of freedom of the COG matches to the number of the ZMP (Zero Moment Point) equations. The COG motion can be uniquely generated along a specified surface satisfying the ZMP constraint with low calculation cost. Spatial and time parts are separable by representing motion surface of the COG as parametric variables. The motion surface defines the relative height of the COG from the landing foot position. Thus, the proposed method reflects geometric information directly to the motion planning without considering walk stability. In this paper, we show two actual examples, walking pattern including mostly stretched knee and going up stairs. The validity of the proposed method is confirmed by simulation. Walking with mostly stretched knee is also shown in experiment using HRP-2.

This paper presents a slip observer towards stabilizing biped walks on a low friction floor. Although biped humanoid robots are expected to easily adapt to environments designed for human, in fact they tend to tip over easily on real environments. For a practical use, it is one of important issues to stabilize a biped walking on an unexpected slippery floor with a low friction. In this paper, we propose the slip observer detecting skids that would occur at walking on unexpected slippery floor. We also propose a basic study of slip stabilizer towards reducing posture rolling caused by skids. Finally, we present experimental results using a humanoid robot HRP-2 to verify the validity of the proposed control scheme.

This paper presents an emergency stop algorithm of a walking humanoid robot. There are many cases which force a walking robot to stop quickly without falling. Since an emergency occurs at unpredictable timing and at any state of robot, the stopping motion must be generated in real-time. To overcome these problems, our emergency stop motion is divided into four phases according to the role of the zero-moment point (ZMP). In each phase, approximate analytical solutions of the center of gravity (COG) dynamics is used to generate the motion. During the single support phase, a landing time and position are determined by evaluating the average velocity of the swing leg and the horizontal position of the COG. During the double support phase, the travel distance of the COG and the ZMP are evaluated. The validity of the proposed method is confirmed by simulation and experiment using a humanoid robot HRP-2.

A humanoid robot is a real-time system controlled by a complex computer system that requires huge computing power for perception and planning, high energy efficiency for self-contained control, reduction of physical dimensions, and high reliability. This paper proposes a distributed architecture for the humanoid robot control substituting conventional centralized control architectures. In addition to the parallelism that provides scalable computing power at low clock namely at low energy, the distributed architecture contributes to reliable operations by replacing many fragile analog signal wires with a digital network with redundant routes. In order to accomplish a real-time control over the network, RMTP (responsive multi-threaded processor) for parallel and real-time computation has been newly designed. RMTP can synchronize more than thirty nodes distributed over a robot body in less than 5 micro second with a real time network called the responsive link (RL). Architectures of RMTP, RL and Linux-based real-time system software are presented.

We previously reported the first human-sized humanoid robot that can fall down safely and stand up again. This paper examines the falling motion control by supplementary simulations and presents an improvement of the control by optimizing the control parameters. The UKEMI falling over control of a human-sized humanoid robot is simulated, the simulation results are compared with the experimental results of real humanoid robot.

This work proposes a new style of manipulation by a humanoid robot. Focusing on the task of pushing an object, the foot placement of it is planed in real-time according to the result of manipulation of an object. By controlling the arms using the impedance control, a humanoid robot can push an object stably regardless of the mass of an object. If an object is heavy, a humanoid robot pushes an object with walking slowly, and vice versa. Also, for planning the gait in real-time, we newly propose an analytical method where the newly calculated trajectory of the robot motion is smoothly connected to the current one. The effectiveness of the proposed method is confirmed by simulation and experiment.

This work studies locomotion planning of humanoid robots to pass through narrow spaces. Humanoid robots can alter the style of the locomotion while wheeled robots can not. The proposed method generates a 3D local map from visual information and plans the appropriate locomotion based on the map from biped walking with the variable height and the width and from crawling.

A development of humanoid robot HRP-2 is presented in this paper. HRP-2 is a humanoid robotics platform, which we developed in phase two of HRP. HRP was a humanoid robotics project, which had run by the Ministry of Economy, Trade and Industry (METI) of Japan from 1998FY to 2002FY for five years. The ability of the biped locomotion of HRP-2 is improved so that HRP-2 can cope with uneven surface, can walk at two third level of human speed, and can walk on a narrow path. The ability of whole body motion of HRP-2 is also improved so that HRP-2 can get up by a humanoid robot's own self if HRP-2 tips over safely. In this paper, the appearance design, the mechanisms, the electrical systems, specifications, and features upgraded from its prototype are also introduced.

This paper studies a falling motion control of a human-size humanoid robot when it falls forward. Safe knee landing of the robot is realized as a first step to minimize the damage of the falling over. The landing follows the detection of the falling, the decrease of the knee height after the detection, and the brake of landing speed. It is confirmed that the proposed method can soften the landing impact significantly by the proposed method.

For cooperative work of robots and humans in the real world, a communicative function based on speech is indispensable for robots. To realize such a function in a noisy real environment, it is essential that robots be able to extract target speech spoken by humans from a mixture of sounds by their own resources. We have developed a method of detecting and extracting speech events based on the fusion of audio and video information. In this method, audio information (sound localization using a microphone array) and video information (human tracking using a camera) are fused by a Bayesian network to enable the detection of speech events. The information of detected speech events is then utilized in sound separation using adaptive beam forming. In this paper, some basic investigations for applying the above system to the humanoid robot HRP-2 are reported. Input devices, namely a microphone array and a camera, were mounted on the head of HRP-2, and acoustic characteristics for sound localization/separation performance were investigated. Also, the human tracking system was improved so that it can be used in a dynamic situation. Finally, overall performance of the system was tested via off-line experiments.

This paper shows some preliminary results on the dynamical balance of a humanoid robot grasping an environment. By grasping an environment, it becomes easier for the robot to keep balance. By using the linear programming, a necessary condition for keeping balance of the robot is formulated taking the grasping force into consideration. We show that the occasion exists where the stronger the hand of a humanoid robot grasps the handrail, the larger the region of ZMP for keeping balance becomes. We further show an experimental result of a humanoid robot climbing up a big gap increasing the stability by grasping a handrail.

Biped walking on a low friction floor is analyzed in this paper. For a given walking pattern, we can calculate a necessary friction coefficient which allows the robot to perform the expected motion. To reduce the maximum necessary friction coefficient, a pattern generation based on preview control theory is explained. We also describe a calculation of slip concerned ZMP, which provides a good prediction of falling caused by slips. Finally, we test a walk of 135 [km/h] on low friction environment using a humanoid robot HRP-2. The robot could successfully walk over the slippery area whose friction coefficient is 0.14.

This paper discusses the pushing manipulation of an object by a humanoid robot. For such a pushing task, we show that there are two kinds of ZMPs, i.e., the conventional "Zero Moment Point (ZMP)" considering all sources of the force/moment acting in the foot supporting area, and the "Generalized Zero Moment Point (GZMP)" which is an generalization of ZMP for a humanoid robot whose hands do not contact with an object. We first obtain the stable region of the GZMP on the floor. Moreover, since the difference between these two ZMPs corresponds to the magnitude of contact force applied by the hands, we propose the pushing manipulation by a humanoid robot by modifying the desired ZMP trajectory for a humanoid. The effectiveness of the proposed method is confirmed by simulation results.

We have developed a software platform, called OpenHRP, for humanoid robotics which consists of a dynamic simulator and motion control library for humanoid robots. This paper attempts to answer a frequently asked question "do the dynamic simulations and the experiments of biped walking of humanoid robots correspond?". Using OpenHRP and humanoid robots HRP-1S and HRP-2P, the comparisons between the simulations and experiments are shown at various aspects.

We introduce a new method of a biped walking pattern generation by using a preview control of the zero-moment point (ZMP). First, the dynamics of a biped robot is modeled as a running cart on a table which gives a convenient representation to treat ZMP. After reviewing conventional methods of ZMP based pattern generation, we formalize the problem as the design of a ZMP tracking servo controller. It is shown that we can realize such controller by adopting the preview control theory that uses the future reference. It is also shown that a preview controller can be used to compensate the ZMP error caused by the difference between a simple model and the precise multibody model. The effectiveness of the proposed method is demonstrated by a simulation of walking on spiral stairs.

The goal of this study is a system for a robot to imitate human dances. This paper describes the process to generate whole body motions which can be performed by an actual biped humanoid robot. Human dance motions are acquired through a motion capturing system. We then extract symbolic representation which is made up of primitive motions: essential postures in arm motions and step primitives in leg motions. A joint angle sequence of the robot is generated according to these primitive motions. Then joint angles are modified to satisfy mechanical constraints of the robot. For balance control, the waist trajectory is moved to acquire dynamics consistency based on desired ZMP. The generated motion is tested on OpenHRP dynamics simulator. In our test, the Japanese folk dance, 'Jongara-bushi', was successfully performed by HRP-1S.

We have developed a humanoid robot HRP-2P with a biped locomotion controller, stereo vision software and aural human interface to realize cooperative works by a human and a humanoid robot. The robot can find a target object by the vision, and carry it cooperatively with a human by biped locomotion according to the voice commands by the human. A cooperative control is applied to the arms of the robot while it carries the object, and the walking direction of the robot is controlled by the interactive force and torque through the force/torque sensor on the wrists. The experimental results are presented in the paper.

This paper investigates a method through which human-size humanoid robot can fall over backwards safely. Squatting-extending motion of legs reduce impact of falling and shock-absorbing parts of the robot keep the force at a permissible range. The robot could stand up itself again after falling.

This paper newly considers the ZMP (zero moment point) of a humanoid robot under arm/leg coordination. By considering the infinitesimal displacement and the moment acting on the convex hull of the supporting points, we show that our method for determining the region of ZMP can be applicable to several cases of the arm/leg coordination tasks. We first express two kinds of ZMPs for such coordination tasks, i.e., the conventional ZMP, and the "generalized zero moment point (GZMP)" which is a generalization of the ZMP to the arm/leg coordination tasks. By projecting the edges of the convex hull of the supporting points onto the floor, we show that the position and the region of the GZMP for keeping the dynamical balance can be uniquely obtained. The effectiveness of the proposed method is shown by simulation results.

We introduce a method to generate whole body motion of a humanoid robot such that the resulted total linear/angular momenta become specified values. First, we derive a linear equation, which gives to total momentum of a robot from its physical parameters, the base link speed and the joint speeds. Constraints between the legs and the environment are also considered. The whole body motion is calculated from a given momentum reference by using a pseudo-inverse of the inertia matrix. As examples, we generated the kicking and walking motions and tested on the actual humanoid robot HRP-2. This method, the resolved momentum control, gives us a unified framework to generate various maneuvers of humanoid robots.

For real-time walking control of a biped robot, we analyze the dynamics of a three-dimensional inverted pendulum whose motions are constrained onto an arbitrarily defined plane. This analysis leads us a simple linear dynamics, the Three-Dimensional Linear Inverted Pendulum Mode (3D-LIPM). Geometric nature of trajectories under the 3D-LIPM is discussed, and an algorithm for walking pattern generation is presented. Experimental results of real-time walking control of a 12-DOF biped robot HRP-2L using an input device such as a game pad are also shown.

This paper introduces an open architecture humanoid robotics platform (OpenHRP) on which various building blocks of humanoid robotics can be investigated. OpenHRP is a virtual humanoid robot platform with a compatible humanoid robot, and consists of a simulator of humanoid robots and motion control library for them which can also be applied to a compatible humanoid robot as it is. OpenHRP is expected to initiate the exploration of humanoid robotics on an open architecture software and hardware, due to the unification of the controllers and the examined consistency between the simulator and a real humanoid robot.

This paper presents an advanced leg module developed for HRP-2. HRP-2 is a new humanoid robotics platform,. which we have been developing in phase two of HRP. HRP is a humanoid robotics project, which has been launched by Ministry of Economy, Trade and Industry (METI) of Japan from 1998FY to 2002FY for five years. The ability of the biped locomotion of HRP-2 is improved so that HRP-2 can cope with rough terrain in the open air and can prevent the possible damages to a humanoid robot's own self in the event of tipping over. In this paper the mechanisms and specifications of leg module, electrical system, simulation results utilized for deciding specifications, and experimental results are also introduced.

This paper investigates a method to minimize damage to a humanoid robot when it falls over to the ground. The strategy involves controlling the attitude of the robot while it is falling over so that it lands on the ground at one of shock-absorbing parts of the robot. A simulation study has confirmed that the proposed algorithm can make the robot land at specified shock-absorbing parts.

In this paper, the developmental software environment for humanoids is introduced. This environment has the following features: 1) a hardware concealment function which saves the trouble with hardware improvements; 2) an incremental expansion function which supports a long-term development by many developers; and 3) a centralised management of body information which enables the robots to share software among different bodies. These features are realized by the plug-in architecture, the universal robot model and its compilers. Using plug-ins enables one to accumulate functions developed by different developers and to switch computer interfaces of the robot body. The universal robot model and compilers promote the use of external software and share software modules among different bodies.

For 3D walking control of a biped robot we analyze the dynamics of a 3D inverted pendulum in which motion is constrained to move along an arbitrarily defined plane. This analysis yields a simple linear dynamics, the 3D linear inverted pendulum mode (3D-LIPM). Geometric nature of trajectories under the 3D-LIPM and a method for walking pattern generation are discussed. A simulation result of a walking control using a 12-DOF biped robot model is also shown.

This paper presents a virtual humanoid robot platform (V-HRP for short) on which we can develop the identical controller for a virtual humanoid robot and its real counterpart. The unification of the controllers for the virtual and real robot has been realized by introducing software adapters for two robots respectively and employing ART-Linux on which real-time processing is available at the user level. Thanks to the unification, the controllers can share softwares with the dynamics simulator of V-HRP, including the parameter parser, kinematics and dynamics computations and the collision detector. This feature can make the development of the controllers more efficient and the developed controllers more reliable.

Describes motion planning of objects in contact by the silhouette algorithm. The problem is formulated to meet the pre-requisites of the silhouette algorithm, and numeric-symbolic algebraic algorithms are given to solve it. As an example, we have been implementing the algorithm for motion planning of polygons in contact, but it can be extended to that of polyhedra in contact.

The silhouette algorithm developed by Canny (1988, 1993) is a general motion planning algorithm which is known to have the best complexity of all of the general and complete algorithms. The authors present a symbolic-numeric version of the algorithm. This version does not require the symbolic computation of the determinants of resultant matrices, and can work on floating point arithmetic. Though its combinatorial complexity remains the same, but its algebraic complexity has been improved significantly which is very important towards its implementation. Several numerical examples are also presented.

The paper describes an integrated teleoperation system for maintenance tasks with planning functions based on manipulation skills. We embed planning functions into a telerobotics system to make the system more flexible and robust. A motion teaching system based on contact state transition, a geometric modeling system using teaching trees, and a task execution system based on manipulation skills are integrated. The design concept of the system and essential technologies are described. An experimental task is explained to demonstrate the efficiency of the telerobotics system.

We have been developing prototypes of teleoperation systems via a standard protocol with a standard human interface, where VRML2.0 is employed as the protocol and a Web browser as the human interface. Using a Web browser, an operator can plan motions of objects interactively on a manipulation simulator with a world model which was sent from a remote site via VRML. The employment of a standard protocol and human interface enables our teleoperation system to be used by non-specialists from any Internet site, or by anyone from anywhere, without installing any specific software on the client side a priori.

We have been developing a prototype of teleoperation systems via a standard protocol with a standard human interface, where an enhanced VRML is employed as the protocol and a Web browser as the human interface. We clarify what are missing from VRML2.0 to realize teleoperation systems and show how to enhance it. We believe that the employment of a standard communication protocol and a standard human interface can realize teleoperation systems that are able to be used by nonspecialists from any Internet site, or by any people from anywhere.

We have developed a teaching system based on the assumption that the assembly task is a series of operations for achieving a target contact state among objects through changing their contact states. The features of our system are as follows: 1) teaching data for fine motion is extracted from a demonstration by an operator in a virtual world, 2) the operator can edit intermediate expressions on a display, 3) intermediate expressions can be used by any robot system with a skill library which has the ability to achieve the corresponding contact states. This paper describes the configuration of the system, program generation using intermediate expressions and a skill library to achieve each contact state.

We study the following problem: Given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an infinitesimal translation and rotation, without colliding with the rest of the parts, AS. A negative result implies that the object whose constituent parts are the collection A cannot be taken apart with two hands. A positive result, together with the list of movable parts in S and a direction of motion for S, can be used by an assembly sequence planner. This problem has attracted considerable attention within and outside the robotics community. We devise an efficient algorithm to solve this problem. Our solution is based on the ability to focus on selected portions of the tangent space of rigid motions and efficiently access these portions. The algorithm is complete (in the sense that it is guaranteed to find a solution if one exists), simple, and improves significantly over the best previously known solutions. We report experimental results with an implementation of our algorithm.

Since general automatic assembly motion planning using a geometric CAD model is computationally difficult, automation of a general assembly task is not feasible. However, if a human operator roughly specifies an assembly motion, the remainder of the process except for planning can be automated. We construct a teaching system for assembly tasks according to the above concept. This paper describes our teaching system for assembly tasks by using a position/force simulator. We show how to construct the position/force simulator and analyse the hybrid position/force control which is needed when dealing with general rotational motion. We show the example of extracting a sequence of contact state transitions from the motion which the operator performs in the position simulator of our system. The sequence of contact states automatically extracted from the motion shown by the operator makes it feasible to achieve an error-tolerant automated assembly motion. If a sequence of contact states is obtained, studies of the automatic assembly task system can progress based upon this information.

Motion of objects in contact plays an important role in the mechanical assembly by manipulators. This paper presents a motion planning algorithm for the case that a convex polyhedron translates and rotates in contact with another one. The rotation of the moving one is parameterized by a special unitary 2/spl times/2 matrix to have the algebraic representation of the contact conditions between the polyhedra. We present an algorithm to determine a sequence of the topological contact states whose asymptotic time complexity is optimal. We also present an algorithm to obtain a 'roadmap' by solving the algebraic equations. The principle idea is 'astute geometric formulations make the algebraic problem easier to solve'. The algorithms are implemented and examples are shown.>

Planning the motion of objects in contact is an important stage of the analysis of mechanical assembly tasks. This paper concerns with the case of a polyhedron moving within a polyhedral environment. It presents an algorithm to plan the motion of a convex polyhedron translating and rotating in contact with a neither necessarily convex nor connected polyhedral obstacle. This algorithm uses a new description of the obstacle in the configuration space-the C-obstacle-with the help of several contact predicates and of a topological adjacency graph. However, in the nonconvex case, the complete computation of the boundary of the C-obstacle is usually intractable. Our algorithm is lazy: it takes into account progressively and only if it is necessary the nonconvexity of the polyhedra. Indeed, the main idea is to describe the C-obstacle as if it were convex, in order to perform as few computations as possible to find a motion and, in case of failure, to build a new description of the C-obstacle incorporating "some" nonconvexity features, and to repeat this process until a correct motion is planned. We also describe a prototype of implementation of this algorithm and an example it can solve.>

Investigates motions of a polyhedron in contact with a fixed polyhedron under the frictionless assumption. The authors propose a complete algorithm for determining possible velocity of the moving polyhedron and force applicable from the moving one to the fixed one automatically from their geometric models. The algorithm consists of two parts. The first part derives the constraints for the velocity of the moving polyhedron from their shape descriptions. The constraints are represented by linear inequalities of the velocity. The algorithm is complete in the sense that it can be applied to any case in which polyhedra with arbitrary shapes are in contact with arbitrary state. It includes the degenerate case in which a vertex contacts another vertex or edge. The second part solves the inequalities and obtains the set of possible velocity vectors of the moving polyhedron. The authors prove that this part is equivalent to the algorithm for enumerating all vertices of a compact polytope in higher dimensional space. The solution is the direct sum of a nonnegative linear combination of the vectors that break the contact state and a linear combination of the vectors that maintain the state. The minimum set of force vectors that are applicable from the moving polyhedron to the fixed one can be obtained from the set of possible velocity vectors of the moving one. The algorithm is fully implemented in an object-oriented lisp with a solid modeler and in C. The possible applications of the algorithm are also presented.

This paper presents a general algorithm for derivation and analysis of motion constraints of objects in contact. The constraints can be derived as linear inequalities for a general case, even when a vertex contacts another vertex or an edge. The solution of the inequalities is a direct sum of a nonnegative linear combination of motions which change the contact state and a linear combination of them which maintain it. From the singular value decomposition of the coefficient matrix of the inequalities it is possible to find the solution in the minimal dimensional space, where the complexity of the algorithm is also minimal. An algorithm is proposed which is not optimal as asymptotic complexity, but is fast in the practical cases and uniform for the dimension of the cone. The algorithm presented can be applied not only to the sensing and control of motion in contact, but also to the planning of it.>