An effective paradigm for simulating the dynamics of robots that locomote and manipulate is multi-rigid body simulation with rigid contact. This paradigm provides reasonable tradeoffs between accuracy, running time, and simplicity of parameter selection and identification. The Stewart-Trinkle Anitescu-Potra time stepping approach is the basis of many existing implementations. It successfully treats inconsistent (Painleve-type) contact configurations, efficiently handles many contact events occurring in short time intervals, and provably converges to the solution of the continuous time differential algebraic equations (DAEs) as the integration step size tends to zero. However, there is currently no means to determine when the solution has largely converged, i.e., when smaller integration steps would result in only small increases in accuracy. The present work describes an approach that computes the event times (when the set of active equations in a DAE changes) of all contact impact events for a multi-body simulation, toward using integration techniques with error control to compute a solution with desired accuracy. We also describe a first-order, variable integration approach that ensures that rigid bodies with convex polytopic geometries never interpenetrate. This approach permits taking large steps when possible and takes small steps when contact is complex.
Early works in simulating rigid bodies undergoing rigid contact were conducted by L "ostedt @cite_23 @cite_7 and Baraff @cite_27 @cite_9 @cite_19 , and used root finding approaches to locate events. These works described some challenges with theory---inconsistent configurations, exemplified by the Painlev ' e Paradox @cite_26 that was well known to the theoretical mechanics community---and computational complexity: for example, Baraff showed that the problem of classifying a contact configuration as inconsistent is NP-hard @cite_19 . These works do not consider the challenges of locating all possible events or the failure to do so.
@cite_26 @cite_7 @cite_9 @cite_19 @cite_27 @cite_23
2163862895 2030010167 2099876657 2159418100
Rigid-body dynamics with unilateral contact is a good approximation for a wide range of everyday phenomena, from the operation of car brakes to walking to rock slides. It is also of vital importance for simulating robots, virtual reality, and realistic animation. However, correctly modeling rigid-body dynamics with friction is difficult due to a number of discontinuities in the behavior of rigid bodies and the discontinuities inherent in the Coulomb friction law. This is particularly crucial for handling situations with large coefficients of friction, which can result in paradoxical results known at least since Painleve [C. R. Acad. Sci. Paris, 121 (1895), pp. 112--115]. This single example has been a counterexample and cause of controversy ever since, and only recently have there been rigorous mathematical results that show the existence of solutions to his example. The new mathematical developments in rigid-body dynamics have come from several sources: "sweeping processes" and the measure differential inclusions of Moreau in the 1970s and 1980s, the variational inequality approaches of Duvaut and J.-L. Lions in the 1970s, and the use of complementarity problems to formulate frictional contact problems by Lotstedt in the early 1980s. However, it wasn't until much more recently that these tools were finally able to produce rigorous results about rigid-body dynamics with Coulomb friction and impulses. Making use of a perturbed Lagrangian formulation, a finite element procedure for contact problems is developed for the general case in which node-to-node contact no longer holds. The proposed procedure leads naturally to a discretization of the contact interface into contact segments. Within the context of a bilinear interpolation for the displacement field, a mixed finite element approximation is introduced by assuming discont naous contact pressure, constant on the contact segment. Because of this piece-wise constant approximation, the gap function enters into the formulation in an ‘average’ sense instead of through a point-wise definition. Numerical examples are presented that illustrate the performance of the proposed procedure. Current finite element formulations for contact problems based on either the classical Lagrange parameter procedure [l-3, 12, 203 or the penalty-function method [4-6,11], are characterized by a point-wise enforcement of the contact-constraint condition, in the sense that penetration of the bodies is established on a nodal basis. Moreover, in this methods the recovery of the contact pressure over the element from the contact nodal forces generally requires an additional procedure. Within the framework of classical Lagrange multiplier methods the contact condition is exactly satisfied by transforming the constrained problem into an unconstrained one with the introduction of additional variables (Lagrange multipliers). These extra variables add computational effort to the solution process which often requires special procedures to handle the presence of zero diagonal terms. Penalty methods, on the other hand, enable one to transform the constrained problem into an unconstrained one without introducing additional variables. The constraint condition is now satisfied only approximately for finite values of the penalty parameter. The main difhculty associated with these methods, however, lies in the poor conditioning of the problem as the penalty is increased to more accurately enforce the constraint condition. This is a well-understood phenomenon, particularly in the context of the incompressible and nearly incompressible problem in solid and fluid mechanics (e.g. see [l&22,25] for a review). Recently, augmented Lagrangian procedures have been proposed as a promising way to partially overcome these difficulties and ‘regularize’ the penalty formulation (e.g. see the survey in [7,8]). Within the framework of Zinearited e u c , it is possible to restrict the finite element formulation of contact problems by assuming that node-to-node contact occurs. This is in fact the case often considered in the literature [l, 2, 4, 6, 12, 20, 211. In the general context of fully We propose a new explicit contact algorithm for finite element discretized solids and shells with smooth and non-smooth geometries. The equations of motion are integrated in time with a predictor-corrector-type algorithm. After each predictor step, the impenetrability constraints and the exchange of momenta between the impacting bodies are considered and enforced independently. The geometrically inadmissible penetrations are removed using closest point projections or similar updates. Penetration is measured using the signed volume of intersection described by the contacting surface elements, which is well-defined for both smooth and non-smooth geometries. For computing the instantaneous velocity changes that occur during the impact event, we introduce the decomposition contact response method. This enables the closed-form solution of the jump equations at impact, and applies to non-frictional as well as frictional contact, as exemplified by the Coulomb frictional model. The overall algorithm has excellent momentum and energy conservation characteristics, as several numerical examples demonstrate. Copyright © 2005 John Wiley & Sons, Ltd. Algorithms and computational complexity measures for simulating the motion of contacting bodies with friction are presented. The bodies are restricted to be perfectly rigid bodies that contact at finitely many points. Contact forces between bodies must satisfy the Coulomb model of friction. A traditional principle of mechanics is that contact forces are impulsive if and only if non-impulsive contact forces are insufficient to maintain the non-penetration constraints between bodies. When friction is allowed, it is known that impulsive contact forces can be necessary even in the absence of collisions between bodies. This paper shows that computing contact forces according to this traditional principle is likely to require exponential time. An analysis of this result reveals that the principle for when impulses can occur is too restrictive, and a natural reformulation of the principle is proposed. Using the reformulated principle, an algorithm with expected polynomial time behaviour for computing contact forces is presented.