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.
Proofs of correctness of conservative advancement (i.e., proof that it generates a lower bound on the time of impact) are provided in @cite_4 . The formula indicates that angular velocities parallel to @math ---the normal to the contact manifold for kissing'' bodies---do not decrease @math , the conservative bound. When bodies are contacting, the safe bound is zero, so a special strategy is necessary. Mirtich kept bodies undergoing sustained contact separated, using a microcollision'' approach, which not only results in poor computation rate on some scenarios (like stacking), but also introduces error that does not disappear as the integration step tends to zero. The approach described in the present work instead leverages knowledge that the geometries are convex polyhedra to address this problem. Note that non-convex polytope geometries may be decomposed into unions of convex polytopes (see, e.g., @cite_24 ).
@cite_24 @cite_4
2099876657 2083093559 2067309337 2075921599
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. This paper investigates the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories. Dynamic movement problems are of fundamental importance to robotics, but their computational complexity has not previously been investigated. We provide evidence that the 3-D dynamic movement problem is intractable even if B has only a constant number of degrees of freedom of movement. In particular, we prove the problem is PSPACE-hard if B is given a velocity modulus bound on its movements and is NP-hard even if B has no velocity modulus bound, where, in both cases, B has 6 degrees of freedom. To prove these results, we use a unique method of simulation of a Turing machine that uses time to encode configurations (whereas previous lower bound proofs in robotic motion planning used the system position to encode configurations and so required unbounded number of degrees of freedom). We also investigate a natural class of dynamic problems that we call asteroid avoidance problems : B, the object we wish to move, is a convex polyhedron that is free to move by translation with bounded velocity modulus, and the polyhedral obstacles have known translational trajectories but cannot rotate. This problem has many applications to robot, automobile, and aircraft collision avoidance. Our main positive results are polynomial time algorithms for the 2-D asteroid avoidance problem, where B is a moving polygon and we assume a constant number of obstacles, as well as single exponential time or polynomial space algorithms for the 3-D asteroid avoidance problem, where B is a convex polyhedron and there are arbitrarily many obstacles. Our techniques for solving these asteroid avoidance problems use “normal path” arguments, which are an intereting generalization of techniques previously used to solve static shortest path problems. We also give some additional positive results for various other dynamic movers problems, and in particular give polynomial time algorithms for the case in which B has no velocity bounds and the movements of obstacles are algebraic in space-time. The value of energy and momentum conserving algorithms has been well established for the analysis of highly non-linear systems, including those characterized by the nonsmooth non-linearities of an impact event. This work proposes an improved integration scheme for frictionless dynamic contact, seeking to preserve the stability properties of exact energy and momentum conservation without the heretofore unavoidable compromise of violating geometric admissibility as established by the contact constraints. The physically motivated introduction of a discrete contact velocity provides an algorithmic framework that ensures exact conservation locally while remaining independent of the choice of constraint treatment, thus making full conservation equally possible in conjunction with a penalty regularization as with an exact Lagrange multiplier enforcement. The discrete velocity effects are incorporated as a post-convergence update to the system velocities, and thus have no direct effect on the non-linear solution of the displacement equilibrium equation. The result is a robust implicit algorithmic treatment of dynamic frictionless impact, appropriate for large deformations and fully conservative for a range of geometric constraints. Copyright © 2001 John Wiley & Sons, Ltd. The present work extends the non-smooth contact class of algorithms introduced by to the case of friction. The formulation specifically addresses contact geometries, e.g. involving multiple collisions between tightly packed non-smooth bodies, for which neither normals nor gap functions can be properly defined. A key aspect of the approach is that the incremental displacements follow from a minimum principle. The objective function comprises terms which account for inertia, strain energy, contact, friction and external forcing. The Euler–Lagrange equations corresponding to this extended variational principle are shown to be consistent with the equations of motion of solids in frictional contact. In addition to its value as a basis for formulating numerical algorithms, the variational framework offers theoretical advantages as regards the selection of trajectories in cases of non-uniqueness. We present numerical and analytical examples which demonstrate the good momentum and energy conservation characteristics of the numerical algorithms, as well as the ability of the approach to account for stick and slip conditions.