This paper presents a method for the generation of dynamic walking gaits with a 3D Dual-SLIP model and its application to a simulated Hubo+ based humanoid. Previous approaches with the Dual-SLIP model have only focused on the planar case, wherein self-stable gaits can be found. When extended to 3D here, this model has not been found to exhibit self-stable gaits, requiring new methods for gait optimization and control. By taking advantage of a newly discovered symmetry condition for the Dual-SLIP model, this work proposes a quarter period (half step) optimization process to find periodic walking gaits in 3D. An LQR controller is developed to regulate the state of the model at leg midstance (MS) based on its return map dynamics. The Dual-SLIP model is extended by introducing a bio-inspired leg length actuation scheme in order to describe high-speed walking gaits (up to 2 m/s for human-compatible parameters). Finally, the CoM trajectory and footstep positions from the 3D Dual-SLIP are used as a reference in a task-space controller with a Hubo+ based humanoid model. By tracking these references, the methods successfully produce human-like dynamic walking gaits in simulation which are robust to disturbances. The whole-body control system for walking can handle uneven terrain with variation up to 10% of its leg length. This represents the first humanoid dynamic walking approach based on a 3D Dual-SLIP model.

The Dual-SLIP model has been proposed as a walking template that inherently encodes a rich set of human-like features. Previous work has used the 3D Dual-SLIP with bio-inspired leg actuation to generate a human-like dynamic walking gait over a wide range of speeds. The work presented in this paper extends the 3D Dual-SLIP walking strategy to uneven terrain. With nonlinear optimization based on a multiple-shooting formulation, actuated Dual-SLIP walking gaits over uneven terrain are identified that handle 1-step elevation changes up to ±10 cm. Moreover, this Dual-SLIP actuation strategy enables a constant center of mass (CoM) forward speed at leg midstance to be maintained. The resultant gaits have revealed a leg lengthening/shortening strategy that is similar to that adopted by a human when walking over prepared, uneven terrain. Results demonstrate that the CoM trajectories and ground reaction force patterns found with the approach are comparable to the human data found in the biomechanics literature. The trajectories generated by the Dual-SLIP model are also demonstrated to orchestrate a dynamic walking motion with an anthropomorphic humanoid model in simulation over uneven terrain.

This paper presents new methods to develop a running long jump for a simulated humanoid robot. Starting from a steady-state running motion, a new spring loaded inverted pendulum (SLIP) based 3D template model for a running jump is presented. The use of this model is motivated by a simpler model from biomechanics which describes the dynamics of human long jumpers in the sagittal plane. While previously only used to describe the thrust step of a long jump, this type of model is also shown to generate useful Center of Mass (CoM) trajectories to return to steady-state running upon landing. A principled optimization approach for this new template is described to generate reference CoM trajectories for maximum span which are able to be kinematically and dynamically retargeted to the humanoid. The key features of an optimal long jump are highlighted, and a task-space control approach to realize the motion on a humanoid is summarized. A video attachment to this paper shows an optimal long jump for a 6 m/s approach speed, where the humanoid is able to clear a large gap, and highlights the effects of non-optimal takeoff-velocity angles.

This paper presents new methods to control humanoid turns while running, through the use of a 3D-SLIP template model with steering control. The work builds on a previous controller for straight-ahead running and describes the new methods that enable online humanoid steering for different speeds and turn rates. As opposed to previous research which has studied 3D-SLIP steering with a monopod model, motion optimization for the SLIP here enforces leg separation. This leg separation gives rise to body sway in forward running and allows the template to capture the unique roles that the inside and outside legs each play during a high-speed turn. The trajectory optimization approach for this template is given, and the resultant CoM trajectories are characterized. Modifications to a previous controller for straight-ahead running are shown to enable running turns in a simulated humanoid model. The methods allow the humanoid to change its turn rate and direction from step to step and enable execution of a high-speed turn with a radius that is one fourth that of a standard 400m track. A video attachment to this paper shows the humanoid turning while running at up to 4.0 m/s, and highlights its ability to maintain balance in spite of push disturbances.

This paper presents a new formulation of prioritized task-space control for humanoids that is used to develop a dynamic kick and dynamic jump in a 26 degree of freedom simulated system. The demonstrated motions are controlled through a real-time conic optimization scheme that selects appropriate joint torques and contact forces. More specifically, motions are characterized in appropriate task spaces, and the real-time optimizer solves the task-space control problem while accounting for user-defined priorities between the tasks. In contrast to previous solutions of the Prioritized Task-Space Control (PTSC) problem for humanoids, the solution presented here satisfies the ZMP constraint and ground friction limitations at all levels of priority, and is general to periods of flight as well as support. All generated motions include control of the system's centroidal angular momentum, which leads to emergent whole-body behaviors, such as arm-swing, that are not specified by the designer. In addition, compared to a previous quadratic programming solution of the PTSC problem, our approach gains a factor of 2 speedup in its required computational time. This speedup allows the control approach to operate at real-time rates of approximately 200 Hz.

This paper presents new methods to control highspeed running in a simulated humanoid robot at speeds of up to 6.5 m/s. We present methods to generate compliant target CoM dynamics through the use of a 3D spring-loaded inverted pendulum (SLIP) template model. A nonlinear least-squares optimizer is used to find periodic trajectories of the 3D-SLIP offline, while a local deadbeat SLIP controller provides reference CoM dynamics online at real-time rates to correct for tracking errors and disturbances. The local deadbeat controller employs common foot placement strategies that are automatically generated by a local analysis of the 3D-SLIP apex return map. A task-space controller is then applied online to select whole-body joint torques which embed these target dynamics into the humanoid. Despite the body of work on the 2D and 3D-SLIP models, to the best of the authors' knowledge, this is the first time that a SLIP model has been embedded into a whole-body humanoid model. When running at 3.5 m/s, the controller is shown to reject lateral disturbances of 40 N·s applied at the waist. A final demonstration shows the capability of the controller to stabilize running at 6.5 m/s, which is comparable with the speed of an Olympian in the 5000 meter run.

This paper provides a reduced-order algorithm, the Extended-Force-Propagator Algorithm (EFPA), for the computation of operational-space inertia matrices in branched kinematic trees. The algorithm accommodates an operational space of multiple end-effectors, and is the lowest-order algorithm published to date for this computation. The key feature of this algorithm is the explicit calculation and use of matrices that propagate a force across a span of several links in a single operation. This approach allows the algorithm to achieve a computational complexity of O(N +md+m2) where N is the number of bodies, m is the number of end-effectors, and d is the depth of the system's connectivity tree. A detailed cost comparison is provided to the propagation algorithms of Rodriguez et al. (complexity O(N + dm2)) and to the sparse factorization methods of Featherstone (complexity O(nd2+ md2+ m2d)). For the majority of examples considered, our algorithm outperforms the previous best recursive algorithm, and demonstrates efficiency gains over sparse methods for some topologies.

Current biped robots with articulated legs, even the most impressive to date, still lack the ability to execute dynamic motions such as jumping and running with comparable performance to biological systems. This work explores dynamic jumping with the planar biped prototype KURMET, which employs unidirectional series-elastic actuation at each of its joints. While this actuation scheme enables the performance of high-power dynamic movements like the jump, its presence complicates the jumping control problem and has prevented previous researchers from obtaining precise jump control in systems of reasonable complexity. To manage this problem, this paper develops a layered fuzzy control system for KURMET that realizes repeated dynamic hopping and accurate control of both torso height and velocity at each top of flight. An effective two-stage training approach is used for the fuzzy controller to learn the required, yet highly nonlinear, relationships between its inputs and outputs. Finally, the state machine employed at the lowest-level of control is used to achieve a maximal normalized jump height that outperforms most humans and can be sequenced with the hopping movement.

This paper introduces a very efficient, modified resolved acceleration control algorithm for dynamic filtering and control of whole-body humanoid motion in response to upper-body task specifications. The dynamic filter is applicable for general upper-body motions when standing in place. It is characterized by modification of the commanded torso acceleration based on a geometric solution to produce a ZMP which is inside the support. The resulting feasible modified motion is synchronized to the reference motion when the computed ZMP for the reference motion again falls within the support. Contact forces at each foot are controlled through a dedicated force distribution module which optimizes the ankle roll and pitch torques. The proposed approach uses time-local information and is therefore targeted for online control. The effectiveness of the algorithm is demonstrated by means of simulated experiments on a model of the Honda humanoid robot ASIMO using a highly dynamic upper-body reference motion.

Resolved acceleration control is a well-known strategy used in tracking control of robotic systems where the desired motion is specified in task-space. Typically, such controllers are developed for systems which exhibit redundancy with respect to execution of operational tasks. While redundancy fundamentally adds new capabilities (self-motion and subtask performance capability), the degree to which secondary objectives can be faithfully executed cannot be determined in advance unless the motion is planned and the environment is known. Therefore, execution of secondary objectives cannot be guaranteed. In fact, a robot which exhibits redundancy with respect to operational tasks may have insufficient degrees of freedom to fulfill more critical objectives such as enforcing constraints. In this paper, we present a generalized constrained resolved acceleration control framework to handle execution of operational tasks and constraints for redundant and non-redundant task (and constraint) specifications. The approach is particularly well suited for online control of complex robot structures such as humanoid robots. The current formulation considers joint limit and collision constraints. The efficacy of the proposed algorithm is demonstrated by simulated experiments of task level upper-body human motion replication on the Honda humanoid robot.

The remarkable ability of humans and animals to perform dynamic maneuvers, such as a jump, is largely attributed to series-elastic elements in skeletal muscle. Both the degree of elasticity and the coordination of muscular contractions have been shown to impact jump performance. The objective of this paper is to use a genetic algorithm (GA) to optimize the control and actuator parameters of a series-elastic actuator (SEA), which is functionally analogous to skeletal muscle, in an articulated leg to produce the highest jump. Similar to skeletal muscle, the control and stiffness of the SEA is found by the GA to affect jump performance, yielding solutions with biological properties. In particular, the jumps evolved by the GA made use of the stretch and shortening cycle of the series-elasticity, which is commonly seen in nature to increase the force of an explosive movement. The model studied in this paper is of a prototype leg with series-elastic actuation. A detailed leg and actuator model was developed to include the important electrical and mechanical properties of the DC motors as well as the characteristics of the motor amplifiers.

The centroidal momentum of a humanoid robot is the sum of the individual link momenta, after projecting each to the robotpsilas Center of Mass (CoM). Centroidal momentum is a linear function of the robotpsilas generalized velocities and the centroidal momentum matrix is the matrix form of this function. This matrix has been called both a Jacobian matrix and an inertia matrix by others. We show that it is actually a product of a Jacobian and an inertia matrix.

In this paper, an attitude control strategy is developed for a high-speed quadruped trot. The forces in the trot are redistributed among the legs to stabilize the pitch and roll of the system. An important aspect of the strategy is that the controller works to preserve the passive dynamics of quadruped trotting that are accurately predicted by the spring-loaded inverted pendulum (SLIP) model. A hybrid control strategy is presented which allows the quadruped to reach a speed of 4.75 m/s and turn at a rate of 20 deg/s in simulation under operator control. The discrete part of the controller runs once per trot step and outputs a stance thrust energy and hip angles for touchdown. The stance thrust energy accounts for losses during the step, especially at touchdown. Both the stance thrust energy and hip angles dictate the natural dynamics during stance. The force redistribution algorithm continuously operates during stance to stabilize the body's tilt axes, roll and pitch, with minimal effect on the prescribed natural dynamics. The 1.0 m/s increase in speed over previously presented work is largely due to the more dynamically-consistent force redistribution algorithm presented in this paper. The controller also tracks desired changes in heading, for which the biomimetic method of banking into a high-speed turn is also realized.

High-speed legged locomotion is complicated by the challenge of uneven terrain because the system must respond to the fast-changing terrain elevation under each foot, and quickly secure a solid foothold after touchdown. This paper presents a leg stretch reflex and anti-slip retraction algorithm that are added to a previously presented controller to stabilize a high-speed trot over uneven terrain. Together with fuzzy control and a force redistribution algorithm, these control mechanisms stabilize a quadruped trot at 5.25 m/s. The quadruped can turn at 30 deg/s when running at 3.0 m/s, and can maneuver over uneven terrain with standard deviation of height variation of 3 cm at 4.0 m/s. This appears to be the first reported control of high-speed quadrupedal running over uneven terrain.

Dynamic maneuvers are an important part of legged locomotion used to adapt to varying terrain conditions. Quadrupedal dynamic maneuvers have received little attention in the literature due to limitations of traditional analytical approaches. In this study we look at several dynamic maneuvers in a 3D galloping quadruped robot using a multi-objective evolutionary algorithm. In particular, we consider the jump-start, the high-speed turn, the running jump, and the sudden-stop. The control approach and fitness criteria are described for each maneuver, and biological-mode solutions are presented

During a complete running stride, which involves significant periods of flight during which no legs are contacting the ground, a quadruped cannot employ static stability techniques. Instead, the corrective forces necessary to maintain dynamic stability must be applied during the short stance intervals inherent to high-speed running. Because of this complexity and the large coupled forces required to run, much of the research on the control of quadruped running has focused on planar systems which are not required to simultaneously control attitude in all three dimensions. The 3D trot controller presented here overcomes these and other complexities to control a trot up to 3.75 m/s, approximately 3 body lengths per second, and turning rates up to 20 deg/s. The biomimetic method of banking into a high-speed turn is also investigated here. Along with the details of the attitude control algorithm, a set of control principles for high-speed legged motion is presented. These principles, such as the need to counteract the disturbance of swing leg return and the usefulness of force redistribution during stance, are not dependent on a particular scale or actuation scheme and can be applied to a wider range of legged systems

Dynamic simulation requires the computationally expensive calculation of joint accelerations, while in kinematic simulation these accelerations are known based on a given trajectory. This paper describes a hybrid kinematic and dynamic simulation method that can be applied to the simulation of running machines to speed up the computations over that of a dynamic simulation. This is possible because much of the time the legs of a running machine are in the air and their trajectories are directly specified and tightly controlled. The method is more flexible than dynamic simulation alone because it allows joints to be either motion-controlled or force-controlled. It is general to all robotic systems with tree structures, and fully motion-controlled or force-controlled kinematic loops. It should work best for machines with appendages that are motion-controlled, such as those encountered in underwater and space manipulation.

Over the past several decades, there has been a considerable interest in investigating high-speed dynamic gaits for legged robots. While much research has been published, both in the biomechanics and engineering fields regarding the analysis of these gaits, no single study has adequately characterized the dynamics of high-speed running as can be achieved in a realistic, yet simple, robotic system. The goal of this paper is to find the most energy-efficient, natural, and unconstrained gallop that can be achieved using a simulated quadrupedal robot with articulated legs, asymmetric mass distribution, and compliant legs. For comparison purposes, we also implement the bound and canter. The model used here is planar, although we will show that it captures much of the predominant dynamic characteristics observed in animals. While it is not our goal to prove anything about biological locomotion, the dynamic similarities between the gaits we produce and those found in animals does indicate a similar underlying dynamic mechanism. Thus, we will show that achieving natural, efficient high-speed locomotion is possible even with a fairly simple robotic system. To generate the high-speed gaits, we use an efficient evolutionary algorithm called set-based stochastic optimization. This algorithm finds open-loop control parameters to generate periodic trajectories for the body. Several alternative methods are tested to generate periodic trajectories for the legs. The combined solutions found by the evolutionary search and the periodic-leg methods, over a range of speeds up to 10.0 m/s, reveal "biological" characteristics that are emergent properties of the underlying gaits.

For most large quadrupedal mammals, galloping is the preferred gait for high-speed locomotion. In this paper we evolve a gallop gait in a simulated quadruped robot at speeds from 3.0 to 10.0 m/s. To do so, we must generate periodic trajectories for the body and legs. An evolutionary algorithm known as set-based stochastic optimization (SBSO) is used to find the body trajectory while alternative methods are used to find periodic leg trajectories. The focus of this paper will be to evaluate three different methods for generating periodic leg trajectories. The combined solutions for the body and legs yield biological characteristics that are emergent properties of the underlying high-speed dynamic running gait.

Intelligent controllers are being used with increasing effectiveness on complex systems. This work verifies the effectiveness of fuzzy control, an intelligent method, on a single, articulated-leg that was designed to be used on a high-speed galloping quadruped. Intelligent methods are compared to other control methods in simulation and on the OSU DASH (Dynamic Articulated Structure for High-performance) leg. It is shown that the intelligent controllers outperform non-learning methods. Using fuzzy control, the OSU DASH leg performs stable hopping on a treadmill moving at 2.0 m/s.

In this paper, a graphical dynamic simulator is developed that can simulate actively-coordinated wheeled vehicle systems on uneven faceted terrain. Based on the considerations of model fidelity and computational efficiency, a simple geometric modes for wheel-terrain contact is proposed. In addition, a computationally-efficient algorithm for contact detection is developed. We also devise a contact force model based on soil mechanics. Simulation results of a case, where the wheeled actively articulated vehicle traverses a concave edge between facets, are used to demonstrate the good performance of our contact model.

This paper reviews some of the accomplishments in the field of robot dynamics research, from the development of the recursive Newton-Euler algorithm to the present day. Equations and algorithms are given for the most important dynamics computations, expressed in a common notation to facilitate their presentation and comparison.

In this paper, a new fuzzy systems approach to the control of quadrupedal running is presented. The fuzzy controller is capable of learning the necessary leg touchdown angles and leg thrusts required to track the desired running height and velocity of a bounding quadruped in only one stride. This is accomplished through an adaptation mechanism which is based on heuristics similar to those used by Raibert (1986) to design his controllers. The performance of the fuzzy controller is compared to that of a modified Raibert controller and shows better tracking characteristics. The fuzzy controller's ability to respond to significant modeling errors in the quadruped is demonstrated with an example.

In this paper, an efficient and systematic formulation of the force distribution equations for general tree-structured robotic mechanisms is presented. The applicable platforms include not only systems with star topologies, such as walking machines that have multiple legs with a single body but also general tree-structured mechanisms, such as variably configured wheeled vehicles having multiple modules. The force balance equations that govern the relationship between the contact forces and the resultant inertial forces/moments of the vehicle will be derived through a recursive and computationally efficient algorithm. Also, the joint torque constraints that specify the joint actuator limits, and contact friction constraints that may be used to avoid slippage and maintain contact, are efficiently incorporated in the formulation. Based on this formulation, several standard optimization techniques, such as linear programming or quadratic programming, can be applied to obtain the solution. An algorithm summarizing the results developed, and suitable for computer implementation, is included. The algorithm has been applied to an n-module actively articulated wheeled vehicle, and the computational cost evaluated. The efficiency of the algorithm is demonstrated with results showing real-time execution on a Pentium PC.

We propose to include the vehicle body sway motion into the motion planning of a quadruped's wave gaits such that its stability margin can be substantially increased. Two sway motions are proposed: Y-sway and E-sway. The Y-sway motion is simple, which drives the center of gravity (CG) of the vehicle to approach to the y-component of the geometric center of the contact points of the supporting legs. The E-sway motion drives CG to approach to the desired CG locus for considering equal energy stability levels. Both sway motions are reasonably easy to implement. Between them, the E-sway can achieve better stability margin. When sloped terrains are encountered, body tilt is also considered in the initialization phase to improve the stability margin. Simulation results show that the body sway motions and tilt consideration are not mutually exclusive. Therefore, we may combine both actions to further increase the stability margin.

An efficient formulation of the force distribution equations for actively-coordinated vehicles is presented. The applicable platforms include not only systems with star topologies, such as walking machines that have multiple legs with a single body, but also general tree-structured mechanisms, such as variably-configured wheeled vehicles having multiple modules. Based on this formulation, several standard optimization techniques, such as linear programming or quadratic programming, can be applied to obtain the solution. The efficiency of the formulation is demonstrated with results showing real-time execution on a Pentium PC.

We address the problem of finding an energy efficient locomotion scheme for multilegged walking vehicles. Our approach makes use of compliant actuators to store and release the kinetic and potential energy of the body and legs during each gait cycle. An evolutionary strategy algorithm is used to search the initial condition parameter space until a nearly passive cyclic gait is found. The trajectory of this gait can then be used in a specific class of hexapods to significantly reduce the energy used over each gait cycle.

Presents a contact model for polyhedral objects. For a given geometrical description, body state, and viscoelastic properties it is possible to compute the contact wrench between polyhedral bodies of arbitrary shape and complexity. The C-Space Toolkit geometry engine is used to determine interpenetration distances of the multiple points in contact between the bodies. Kinematic equations describing motion of the multiple points of contact are developed. A compliant contact force model is developed which models both impact and sustained contact, as well as elastic effects such as wedging and jamming. As objects rotate relative to one another, rolling effects are included as well. Forces along the surface at the contact model microslip as well as sliding conditions. Results are obtained for the example of a torus jammed on a cone.

Contact modeling is an important aspect of simulation of many robotic tasks. In the paper, a compliant contact model with nonlinear damping is investigated, and many previously unknown characteristics of the model are developed. Compliance is used to eliminate many of the problems associated with using rigid body models with Coulomb friction, while the use of nonlinear damping eliminates the discontinuous impact forces and most sticky tensile forces which arise in Kelvin-Voigt linear models. Two of the most important characteristics of the model are the dependence of the coefficient of restitution on velocity and damping in a physically meaningful manner, and its computational simplicity. A full mathematical development for an impact response is given, along with the effects of the system and model parameters on energy loss. A quasistatic analysis gives results which are consistent with energy loss characteristics of a more complex distributed foundation model under sustained contact conditions. A foot contact example for a walking machine is given which demonstrates the applicability of the model for impact on foot placement, sustained contact during the support phase, and the breaking of the contact upon liftoff of the foot.

Energy efficiency remains a problem in walking machines. One approach to improving energy efficiency involves solving for an optimal set of foot forces which minimizes the power supplied to DC motor actuators at each instant. Energy regenerated by the motors, which may be significant, is generally lost and should be explicitly taken into account to produce the optimal force distribution. A method to produce this optimal solution using quadratic programming is developed in this paper. The results are compared to three suboptimal quadratic programming approaches which minimize internal forces, a weighted norm of joint torques, and finally power without accounting for regeneration, all on a simulated hexapod. It is found that the common approach of minimizing internal forces may often result in poor energy efficiency.

A new method for simulating multilegged vehicles, using the composite rigid body (CRB) method is presented. Previous approaches use hard constraints and result in closed kinematic loops which require the solution of constraint forces. Using the decoupled tree-structure (DTS) approach compliant contact modeling is used when the feet of the vehicle contact the ground. This approach is compared to the articulated body DTS method (AB/DTS), and proves to be the most computationally efficient method for multilegged vehicles when each leg has up to three degrees of freedom.

This paper addresses the problem of achieving energy efficiency in statically stable walking machines without mechanically constraining the system. In contrast to previous work, power is minimized over an entire locomotion cycle, through optimal selection of walking parameters, rather than for a fixed instant of time only. Dynamic simulation experiments of a hexapod with full three degree-of-freedom legs are used to develop a set of 5 rules for setting velocity, footholds, body height, duty factor, and stroke to achieve maximum energy efficiency. Optimization of walking parameters alone was found to reduce power consumption by up to 50% over a reasonable first set of parameters. The rules presented may be used as the basis for development of energy-efficient behaviors or other intelligent control schemes for walking machines.

In this paper, a simple nonlinear contact model is presented for use in computer simulation. The nonlinear model is shown to maintain the computational simplicity of the linear model while addressing many of its deficiencies. One such advantage is that contact forces vary continuously over time. A new phase plane solution for the nonlinear model is obtained which reveals many previously unnoted properties. These include proper variation of the coefficient of restitution with impact velocity over a wide range of impact velocities, independence of model parameters, and lack of tensile (sticking) forces in simple impacts. An example is presented which demonstrates the use of the contact model in simulating the foot-ground interaction during the locomotion cycle of a walking machine.

An efficient simulation algorithm for an underwater robotic vehicle with a single manipulator was developed by the authors (1994) which included the hydrodynamic effects due to added mass, viscous drag, fluid acceleration, and buoyancy forces. This work has since been extended to the simulation of more general tree-structured mechanisms having star topologies with a number of different joint types while maintaining the O(N) computational complexity (N is the number of links). Using this new algorithm, this paper describes the development of a real-time dynamic simulation system for underwater robotic systems. The primary goal is the efficient implementation of this general algorithm which has been achieved with C++ through the use of object-oriented design techniques of encapsulation, inheritance, and polymorphism. Coupled with realistic 3D graphical models, a powerful tool results for applications ranging from control system development to on-line displays during deployment. The use of this software system has been demonstrated for a number of systems including Aquarobot, an underwater hexapod under development in Japan for seawall construction and surveying.

The articulated-body (AB) algorithm for dynamic simulation of chains of rigid bodies was developed by Featherstone (1983). The mast costly step in this algorithm is the computation of the AB inertias at each link which involves a spatial (6/spl times/6) congruence transformation. The amount of computation required is closely coupled to the kinematic modeling technique used. This paper examines this computation in detail and presents an efficient step-by-step procedure for its evaluation in a serial chain with revolute and prismatic joints using modified Denavit-Hartenberg parameters for modeling the kinematics. The result is a very efficient procedure using successive axial screws that reduces the computational requirements of the AB algorithm by about 15% from results obtained by Brandl, Johanni, and Otter (1986). The procedure developed defines a general approach and can be used to improve the efficiency of spatial congruence transformations of other types of matrices, such as spatial rigid-body inertias (used in the composite rigid-body simulation algorithm).>

In this paper, an efficient dynamic simulation algorithm is developed for an underwater robotic vehicle (URV) with a manipulator. It is based on previous work on efficient O(N) algorithms, where N is the number of links in the manipulator, and has been extended to include the effects of a mobile base (the URV body). In addition, the various hydrodynamic forces exerted on these systems in underwater environments are also incorporated into the simulation. The effects modeled in this work are added mass, viscous drag, fluid acceleration, and buoyancy forces. With efficient implementation of the resulting algorithm, the amount of computation with inclusion of the hydrodynamics is almost double that of the original algorithm for a six degree-of-freedom land-based manipulator with a mobile base. Nevertheless, the amount of computation still only grows linearly with the number of degrees of freedom in the manipulator.>

In this paper, an efficient dynamic simulation algorithm is developed for an unmanned underwater vehicle (UUV) with a robotic manipulator. It is based on an efficient O(N) algorithm where N is the number of links in the manipulator, and has been extended to include the full effects of a mobile base and various hydrodynamic forces that are exerted on these systems in underwater environments. The effects modeled in this paper are added mass, viscous drag, fluid acceleration, and buoyancy forces. With efficient implementation of the resulting algorithm, the amount of computation including hydrodynamics almost doubles over the original algorithm for a six degree-of-freedom land-based manipulator with a mobile base. Nevertheless, the amount of computation still only grows linearly with the number of links in the manipulator.>

A general formulation of the force distribution equations for three-dimensional power grasp is presented. It allows for any number of contacts on the finger surfaces and the palm. The formulation not only includes the active forces and moments applied at the contacts, but also the passive forces resulting from frictional and geometric constraints, such as wedging effects. A grasp matrix is developed for the power grasp case and a new approach is taken to define the hand Jacobian matrix. Contact conditions are modeled to consider both constrained and unconstrained directions for the forces. A stability analysis for power grasp is performed in order to evaluate its stability properties. Due to the inherently stable nature of power grasps, the main objective is not the determination of optimum contact locations, but is the determination of joint torques for optimum force distribution. The stability region is defined and used as a measure to study and compare the different stability aspects of power grasps. Results of stability analysis for power grasps, using the DIGITS Grasping System as a model, are also provided.>

The paper presents an efficient algorithm for the simulation of a system of m manipulators each having N degrees of freedom that are grasping a common object. Algorithms for such a system have been previously developed by others. In Lilly and Orin (1989), an O(mN) algorithm is presented that does not fully consider the case when one or more of the manipulators are in singular configurations. However, it is stated in Rodriguez, Jain, and Kreutz-Delgado (1989) that the algorithm has an O(mN)+O(m/sup 3/) computational complexity when one or more of the chains are singular. This results because the size of the system of equations to be solved grows linearly with the number of chains in the system. The algorithm presented in this paper significantly reduces the size of the system of equations to be solved to one that grows linearly with the number of singular chains, s, and achieves an O(mN)+O(s/sup 3/) complexity. In addition to this result, efficient O(mN) algorithms are also presented for special cases where only one or two chains are in singular configurations. These are particularly useful because it is common to deal with systems consisting of only a few manipulators grasping a common object, and even with more manipulators, it is unlikely that many of them will be singular simultaneously. Finally, by applying the algorithm developed for the case of two singularities to a dual-arm system, an algorithm results that requires fewer computations than that of existing methods, and has the added benefit of being robust in the presence of singular manipulators.>

In this paper, parallel algorithms are developed for real-time dynamic simulation of a multiple manipulator system, cooperating to manipulate a large load. In an effort to achieve real-time computational rates on a general-purpose parallel system, temporal and spatial forms of parallelism are implemented to improve performance. Temporal parallelism is obtained with the use of parallel numerical integration methods. A speedup of 3.78 on four processors of a CRAY Y-MPS was achieved with a parallel four-point block predictor-corrector method for the simulation of a four manipulator system. To overcome a loss of efficiency because of a reduction in accuracy with the block integration methods, spatial parallelism is used in which the dynamics of each chain is computed simultaneously. With the same four manipulator system, this form of parallelism in conjunction with a serial integration method results in a speedup of 3.1 on four processors without the degradation in accuracy. In cases where there are more processors than chains, a new multipoint parallel integration method can still be advantageous despite the reduced accuracy. In this case, it is shown that greater effective speedups are achieved when both forms of parallelism are combined to generate more parallel tasks.>

The operational space inertia matrix Lambda reflects the dynamic properties of a robot manipulator to its tip. In the control domain, it may be used to decouple force and/or motion control about the manipulator workspace axes. The matrix Lambda also plays an important role in the development of efficient algorithms for the dynamic simulation of closed-chain robotic mechanisms, such as multiple manipulator systems and walking machines. This paper presents the development of a recursive algorithm for computing the operational space inertia matrix (OSIM) that reduces the computational complexity to O(N). This algorithm, the inertia propagation method, is based on a single recursion that begins at the base of the manipulator and progresses out to the last link. Also applicable to redundant systems and mechanisms with multiple-degree-of-freedom joints, the inertia propagation method is the most efficient method known for computing Lambda for N>or=6. The numerical accuracy of the algorithm is discussed for a PUMA 560 robot with a fixed base.>

The authors present an efficient algorithm for the simulation of a system of m manipulators each having N degrees of freedom that are grasping a common object. They specifically address the problem when a number, s, of the manipulators are in singular configurations, and the resulting algorithm has a computation complexity of O(mN)+O(s/sup 3/). This is a significant improvement over previous algorithms, which cite an O(mN)+O(m/sup 3/) computation. Efficient O(mN) algorithms are also presented for special cases where only one or two chains are in singular configurations. By applying the algorithm for the latter case to a dual-arm system, an algorithm results that requires fewer computations than that of existing methods, and has the added benefit of being robust in the presence of singular manipulators.>

The results of research performed in computational robot dynamics to achieve real-time simulation of a manipulator on a general-purpose vector/parallel computer are presented. After effective vectorization of the complex dynamics equations required in simulation, a coarse-grain parallel block predictor-corrector (BPC) method for performing the motion integration was realized on multiple processors to exploit a form of temporal parallelism. Results on a CRAY Y-MP8/864 show that effective use of vectorization and parallelization yields an order of magnitude speedup resulting in a computational rate 50 times faster than real-time for end-effector position errors on the order of a micron. This translates to real-time performance on a less powerful parallel computing system.>

The implementation of an artificial-neural-network (ANN)-based power grasp controller is discussed. Multiple points of contact between the grasped object and finger surfaces characterize power grasps. However, modeling is especially difficult because of the nature of the contacts and the resulting closed kinematic structure. Linear programming was used to train an ANN to control the force distribution for objects using a model of the DIGITS grasping system. Force control is implemented to insure that the maximum normal force applied to the object at the contacts is set to a prespecified level whenever possible. The ANN was able to learn the appropriate nonlinear mapping between the object size and force levels to an acceptable level of accuracy and can be used as a constant-time power grasp controller.>

An efficient serial algorithm for the dynamic simulation of a single closed chain is developed. The algorithm is valid for a manipulator with any number of degrees of freedom, N, and it is still applicable when the manipulator is in a singular position. A moving base may also be incorporated into the system. Arbitrary joints are allowed, including multiple-degree-of-freedom joints, and a general contact model is used. The operational space inertia matrix of the chain is used to solve for the unknown contact force vector at the tip, which is then used in the solution for the closed chain joint accelerations. The final solution requires only an additional n/sub c/*n/sub c/ matrix inverse for the closed chain part, where n/sub c/ is the number of degrees of constraint at the manipulator tip. The computational complexity of the algorithm is (ON/sup 3/). The reduction of the order of computation complexity of O(N) is briefly discussed.>

The authors present the results of research performed in computational robot dynamics to achieve real-time simulation of a manipulator on a general-purpose vector/parallel computer. Once the complex dynamics equations required in the simulation have been effectively vectorized, a coarse-grain parallel block predictor-corrector method for performing the motion integration is realized on multiple CPUs to exploit a form of temporal parallelism. Results on a CRAY Y-MP8/864 show that effective use of vectorization and parallelization yields an order-of-magnitude speedup, resulting in a computational rate 50 times faster than real-time for reasonable end-effector position errors on the order of a micron. This translates to real-time performance on a less powerful parallel computing system.>

The force-distribution problem in multiple-chain robotic systems is to solve for the setpoints of the chain contact forces and input joint torques for a particular system task. It is usually underspecified, and an optimal solution may be obtained. The generality of the compact-dual linear programming (LP) method that can accept a variety of linear objective functions for different applications over a wide range of multiple-chain systems (multilegged vehicles, dexterous hands, and multiple manipulators) is demonstrated; and the solutions for several common problems of force distribution including slippage avoidance, minimum effort, load balance, and temporal continuity are proposed. This is illustrated by solving the force-distribution problem of a grasping system being developed called Digits. Efficiency considerations and elimination of redundant constraints are also discussed. With four fingers grasping an object, considering a conservative friction coefficient (for safety margins on friction constraints) and using a combined objective function for achieving the goals of minimum effort, load balance, and temporal continuity, the CPU time on a VAX-11/785 computer is less than 45 ms (using a linear programming package in the IMSL library). Therefore, it is believed that rather general use of the compact-dual LP method may be made to define a suitable objective function for a particular application and to solve the corresponding force-distribution problem in real time.>

Force distribution is the inverse dynamics problem for multiple-chain systems in which the motion is completely specified and the internal forces/torques to effect this motion are to be determined. A computationally efficient formulation for the force-distribution problem is presented. This formulation is applicable to a number of simple closed-chain robotic mechanisms, including dexterous hands, multiple manipulators, and multilegged vehicles. Modeling of chain contacts is relatively general so that hard point contact, soft finger contact or rigid contact with an irregularly-shaped object or with uneven terrain may be handled. The dynamic effects of the chains and physical limits on their actuators are efficiently included in the formulation through the use of the inverse dynamics and Jacobian relationships for each chain. Based on this efficient formulation, a variety of methods may then be developed to solve the force-distribution problem.>

The development of a recursive algorithm for the operational space inertia matrix, the inertia propagation method, which reduces the computational complexity to O(N) for any manipulator is presented. The algorithm is based on a single recursion which begins at the base of the manipulator and progresses out to the last link. Spatial articulated transformations are utilized in the recursion procedure. The algorithm is the most efficient method known for N>or=6. The numerical accuracy of the algorithm is tested for a PUMA 560 robot with a fixed base. The results demonstrate the accuracy of the inertia propagation method for such a configuration.>

A neural-network-based interface between an operator and the DIGITS (dexterous integrated grasping with intrinsic tactile sensing) grasping system is proposed, and the initial results of the network training are presented. The neural network is responsible for accepting the description of an object to be held in a power grasp, and mapping these data into a set of actuator torques which will allow DIGITS to firmly grasp the object. The network should attempt to maximize the normal forces on the object to provide the best possible grasp while not exceeding a set level provided by the operator. The backpropagation neural network was trained with various quantities of hidden nodes and learning rates and then tested for stability and error with respect to the optimal solution. Useful results concerning the effect of learning rate and number of hidden nodes were obtained, as well as results indicating that the network can accurately determine torques for both trained and untrained objects

An efficient algorithm, the compact-dual linear programming (LP) method, is presented to solve the force distribution problem. In this method, the general solution of the linear equality constraints is obtained by transforming the underspecified matrix into row-reduced echelon form; then, the linear equality constraints of the force distribution problem are eliminated. In addition, the duality theory of linear programming is applied. The resulting method is applicable to a wide range of systems, constraints, and objective functions and yet is computationally efficient. The significance of this method is demonstrated by solving the force distribution problem of a grasping system under development at Ohio State called DIGITS. With two fingers grasping an object and hard point contact with friction considered, the CPU time on a VAX-11/785 computer is only 1.47 ms. If four fingers are considered and a linear programming package in the IMSL library is utilized, the CPU time is then less than 45 ms.>

The authors present a general and efficient algorithm, the compact-dual LP method, to solve the force distribution problem for multiple-chain robotic systems. In this method, the general solution of the linear equality constraints is obtained by transforming the underspecified matrix into row-reduced echelon form; then the linear equality constraints of the force distribution problem are eliminated. The duality theory of linear programming is also applied. The resulting method is applicable to a wide range of systems, constraints (friction constraints, joint torque constraints, etc.), and objective functions and yet is computationally efficient. The significance of this method is demonstrated by solving the force distribution problem for a grasping system. For an example involving two-finger grasping of an object and hard point contact with friction, the CPU time on a VAX-11/785 computer is only 1.47 ms. If four fingers are considered, then the CPU time is less than 45 ms, which should be suitable for real-time application.>

The authors propose a restructurable architecture based on a VLSI robotics vector processor (RVP) chip. It is specially tailored to exploit parallelism in the low-level matrix/vector operations characteristic of the kinematics and dynamics computations required for real-time control. The RVP is composed of three tightly synchronized 32-bit floating-point processors to provide adequate computational power. Besides adder and multiplier units in each processor, the RVP contains a triple register-file, dual shift network, and dual high-speed input/output (I/O) channels to satisfy the storage and data movement demands of the computations targeted. Efficiently synchronized multiple-RVP configurations, which may be viewed as variable very-long-instruction-word architectures, can be constructed and adapted to match the computational requirements of specific robotics computations. The use of the RVP is illustrated through a detailed example of the Jacobian computation, demonstrating good speedup over conventional microprocessors even with a single RVP. The RVP has been developed to be implementable on a single VLSI chip using 1.2- mu m CMOS technology, so that a single-board multiple-RVP system can be targeted for use on a mobile robot.>

A VLSI robotics vector processor (RVP) for real-time control is described. Hardware parallelism and pipelining is used to exploit potential concurrency in the low-level matrix/vector operations characteristic of the kinematics and dynamics computations required for control. Three floating point processors (FPP), each with a adder, multiplier, and register file, all operating in parallel in an SIMD (single-instruction, multiple data stream) fashion are incorporated. Data exchange between the FPPs is facilitated by a dual shift-broadcast network. High-speed dual I/O channels are provided so that input/output bottlenecks are avoided. The RVP uses a RISC (reduced-instruction-set-computer) architecture with seven basic instructions. Composite vector operations such as matrix-vector multiply and vector cross product may be readily programmed using the basic instruction set to given considerable overlap. The RVP can be implemented on a single VLSI chip using 1.2- mu m CMOS.>

A formulation of reflex control is presented which has been developed and used in the control of a prototype leg of the adaptive suspension vehicle to implement reflex actions. In particular, the concept of reflex control has been demonstrated experimentally in high-speed contact and foot slippage. A constraint analysis of the leg-environment interaction is found to be especially useful in deriving the invitation and completion conditions. To reduce the total processing required, only simple Boolean conditions are generally checked on the sensor variables. Also, because of the often critical nature of such action, reflex control is executed at the lowest level of control without high-level intervention to achieve maximum response speed; the high-level motion planner is informed of such action so that appropriate steps can be taken when reflex control is relinquished.>

A motion planning algorithm for uneven-terrain locomotion for a multilegged vehicle is described. The algorithm has been developed based on the vehicle/terrain kinematic relationships. The vehicle model is chosen from a hexapod vehicle, named the Adaptive Suspension Vehicle (ASV), which has been constructed at Ohio State University (OSU) and is currently being tested. A simple body-regulation plan has been designed based on the local slope of the terrain and should increase the safety and adaptability of the vehicle. The local terrain is estimated by using the support points of the supporting legs and proximity information from the transfer legs. The adjustment of the position and dimensions of the constrained working volume for each leg, which increases the vehicle stability over sloped terrain, is discussed. The algorithm has been implemented in simulation on a PDP-11/70 minicomputer, from which test results are given.>

A novel algorithm is described for omnidirectional control of a multilegged robot vehicle using periodic gaits. The vehicle model is chosen from a hexapod robot vehicle, named the Adaptive Suspension Vehicle, which is under development. To implement periodic gaits for omnidirectional control, the notion of the constrained working volume (CWV) is introduced on the basis of reachability of the leg and the kinetic maximum locomotion period is defined using the CWV. As a result, the leg touchdown and liftoff points are constrained within the CWV during vehicle locomotion. Based on this constraint, the foothold selection problem is addressed. The algorithm was developed through a computer graphics simulation; results of the simulations are discussed.>

Systolic architectures consisting of 1, N, and N(N+1)/2 processors are presented for computing the manipulator inertia matrix. A VLSI-based robotics processor which is under development is the fundamental component of the architecture. Its major elements are a 32-bit floating-point multiplier, a 32-bit floating-point adder, a triple-port memory, and four I/O ports for external communication which are interconnected to facilitate implementation of robotics operations. The algorithm used is based on recursive computation of the inertial parameters of sets of composite rigid bodies and is programmed to exploit any inherent parallelism. Good results are obtained for the N-processor and N(N+1)/2-processor configurations that give a compute-time delay of O(N). I/O time and idle time due to processor synchronization as well as CPU utilization and on-chip memory size are fully included in the evaluation and indicate the feasibility and effectiveness of the design.>

Systolic architectures consisting of 1, N, and N(N + 1)/2 processors are presented for computing the inertia matrix. A VLSI-based Robotics Processor which is under development is the fundamental component of the architecture. Its major elements are a 32-bit floating-point multiplier, 32- bit floating-point adder, triple-port memory, and four I/O ports for external communication which are interconnected to facilitate implementation of robotics operations. The algorithm used is based on recursive computation of the inertial parameters of sets of composite rigid bodies and is programmed to exploit any inherent parallelism. Good results are obtained for the N-processor and N(N + 1)/2- processor configurations which give a compute time delay which is of O(N). In addition, I/O time and idle time due to processor synchronization as well as CPU utilization and on-chip memory size are fully included in the evaluation and indicate the feasibility and effectiveness of the design.

This paper describes a complete motion-planning algorithm for uneven-terrain locomotion for a multilegged vehicle. The algorithm has been developed based on the vehicle/terrain kinematic relationships. The vehicle model is chosen from a hexapod vehicle, named the Adaptive Suspension Vehicle (ASV), which has been constructed at OSU and is currently being tested. A simple body regulation plan has been designed based on the local slope of the terrain and should increase the safety and adaptability of the vehicle. The local terrain is estimated by using the support points of the supporting legs and proximity information from the transfer legs. The algorithm has been implemented in simulation on the PDP-11/70 minicomputer and test results are given.

The direct problem of dynamics for robotic systems with multiple simple closed chains has been formulated and solved. These systems include multiple robot manipulators performing assembly or cooperative tasks as well as multilegged walking machines. The basic problem in direct dynamics is to determine joint accelerations given the applied torques or forces and the system state. As such its solution will allow control designers to test and evaluate the performances of various control algorithms through computer simulation without having to build several costly prototypes. A unified approach is taken so that a single set of equations may describe dynamics of both multiple manipulators and legged vehicles.

A special-purpose computer architecture has been developed for Inverse Kinematics so as to achieve real-tlme capabilities. The algorithm used is based on a modified predictor-corrector method for numerical integration and shows robustness even near points of singularity. The architecture is based on a 32-blt floating point unit that is equipped with data paths that facilitate computation of the most common matrix-vector operations used in robotics control. Special algorithms are used for the sine/ cosine and reciprocal, and these use a mix of computation and table lookup. The algorithm has been simulated on the proposed architecture and the results show its robustness and real-time capability. Two manipulator models are used, one of which does not have an analytical solution to its kinematics. The results indicate that its Inverse Kinematics solution may be obtained at more than 2000 points per second with an error within standard repeatability limits for industrial robots.

Using a proximity ranging system to step over objects has been tested by using two sensors mounted on a Prototype Leg for the Adaptive Suspension Vehicle which is under development at the Ohio State University. The results show that the control algorithm provides the capability to step over many different types of objects at speeds of up to 100 in./ sec. Details of the hardware used, algorithm developed, and experimental results obtained are all shown in the paper.

Algorithms have been developed for the Jacobian and Inverse Dynamics analyses in order to implement them on pipeline/parallel computing arrays. The results indicate that the sampling rate in either case may be significantly increased by adding processors to a pipelined array while, on the other hand, the compute time delay decreases very little. The results further show that a parallel structure is needed if the compute time is to be significantly reduced.

Pipeline techniques are used to assign the computation modules required in Inverse Plant plus Jacobian Control of robot manipulators to a multiple set of processors. With example execution times for each of the modules, the compute time, initiation rate, and CPU utilization are used to evaluate the performance. For three processors, with more than 90% CPU utilization, the compute time is reduced by more than 25% and the initiation rate is almost tripled over that of a single processor.