Transcription
International Journal of Solids and Structures 47 (2010) 1711–1722Contents lists available at ScienceDirectInternational Journal of Solids and Structuresjournal homepage: www.elsevier.com/locate/ijsolstrReal-time self-collision detection algorithms for tensegrity systemsMassimo Cefalo a,*, J.M. Mirats Tur b,1abInstitut de Robòtica i Informàtica Industrial, CSIC-UPC, C/Llorens i Artigas 4-6 2nd Floor, 08028 Barcelona, SpainCetaqua, Passeig dels Til.lers 3, 08034 Barcelona, Spaina r t i c l ei n f oArticle history:Received 6 July 2009Received in revised form 9 March 2010Available online 19 March 2010Keywords:Collisions detectionTensegrityHeuristic algorithma b s t r a c tThis work addresses the problem of real-time self-collision detection for a movable tensegrity structure.We show that it can be tackled as the collision detection between two generic cylinders moving in R3 . It isa simplified version of the more general problem of dynamic collision detection between two generalshaped rigid bodies in the space. Two algorithms are proposed. The first presented approach is basedon the exact value of the distance between two cylinders, the second is based on a new theorem whichallows to estimate the exact distance for a given maximum desired error. In some circumstances, the second approach can be preferred because faster.Ó 2010 Elsevier Ltd. All rights reserved.1. IntroductionThe term Tensegrity was coined by Fuller, in the early 1960s, asthe contraction for tensile integrity (Fuller, 1961). A tensegrity is amechanical structure made out of compressive and tensile elements where each element plays a fixed role in the structure: compressive elements only exert compression while tensile ones onlycarry tensions. The stability of such systems depends on the equilibrium between tensions and compressions exerted by the elements. Fig. 1 shows an example of a class-1 tensegrity.Different patents have been applied for tensegrity systems almost simultaneously: Fuller (1962) and Snelson (1965) in EEUU,and Emmerich (1963) in France. A deeper historical backgroundon tensegrity structures was given by Motro (1992, 2003).The static analysis of tensegrities has reached a certain level ofmaturity, with lots of contributions by different authors and fieldsof study. See for instance Roth and Whiteley (1981), Connelly(1999) for a mathematic perspective, Calladine and Pellegrino(1992), Motro et al. (1986), Hanaor (1988) for studies about theself-stress states of the structure, or Tarnai (1989), Vassart et al.(2000) talking about the prestressability problem. A recent reviewabout tensegrity statics was given in Hernandez and Mirats-Tur(2008b) presenting different existing definitions for tensegritystructures, as well as their main properties.The dynamics of tensegrities was first studied by Motro et al.(1986). Kanchanasaratool and Williamson (2002) studied dynamicparticle models while considering the bars to be massless; other* Corresponding author. Tel.: 34 934015752; fax: 34 934015750.E-mail addresses: mcefalo@iri.upc.edu (M. Cefalo), jmirats@cetaqua.com (J.M.Mirats Tur).1Tel.: 34 933124879; fax: 34 933124801.0020-7683/ - see front matter Ó 2010 Elsevier Ltd. All rights , as those by Skelton et al. (2001) or Sultan (1999) considermass on bars. Also non-linear models and their linearization havebeen considered by Sultan et al. (2002). A recent survey on thedynamics of tensegrity structures including current open researchproblems was given in Mirats-Tur and Hernández (2009).It has not been until this last decade that tensegrity systems received attention from the robotics community. For instance, Aldrich (2004) put together several simple tensegrity structures tobuild a redundant manipulator robot. Paul et al. (2006) and Masicand Skelton (2004) proposed different self-propelled tensegrityarchitectures to build mobile robots. Recently, Mirats-Tur (2010)demonstrated the feasibility of mobile robots made from tensegrity systems.Compressive elements are usually rigid bars while tensile arecables. Both, bars and cables, can be actuated. A motor can be usedto change their length and, hence, change the configuration of thesystem. Two bars can only be in contact at their endpoints, like twocables or a cable and a bar, and only because they are connected. Toensure and preserve the integrity of the structure any contact between the elements must be avoided (unless, obviously, on theconnection points), specially during a motion.1.1. Collision detectionThe problem of avoiding contact between different bodies, i.e.,collision avoidance, has extensively been studied in different disciplines as robotics, computer animation and simulated environments, physical based modeling and molecular modeling.3D collision detection algorithms can be mainly grouped inspace-time volume intersection, Cameron (1990), swept volumeinterference, Gilbert and Foo (1990), multiple interference detection, Chazelle and Palios (1997), and trajectory parametrization,
1712M. Cefalo, J.M. Mirats Tur / International Journal of Solids and Structures 47 (2010) 1711–1722The non-contact conditions among the elements of a tensegrityin motion may be seen as time-dependent, holonomic, unilateralconstraints. In general, to guarantee that there are no self-collisions, it is necessary to consider any possible couple of differentelements and writenlinks ðnlinks 1Þ2Fig. 1. Example of a tensegrity structure of class 1.Lin and Canny (1991) approaches. The multiple interference approach has been the most widely used, reducing the collisiondetection to multiple calls to static interference tests, in mostcases, between simple geometric entities. Among those, four ofthe most used algorithms are the ones relying on bounding boxes,bounding spheres, binary space partition (BSP) trees and the Hubbard algorithm. Bounding boxes and spheres have a complexity ofOðn2 Þ where n is the number of objects. BSP trees algorithms arewell suited for complicated objects, although its complexity ishigh, Oðn2 þ m hÞ where h is the number of levels of the treeand m the number of intersections found. The Hubbard algorithmmakes use of sphere trees and space-time bounds to iteratively refine its accuracy, although it has the problem of reporting falsepositives. Its complexity is Oðn2 þ m2 Þ. It is difficult to evaluateand compare collision detection algorithms, because in generalthey are very sensitive to specific scenarios, i.e., the relative sizeof the two objects, the relative position to each other, the distance,etc., and it is beyond the scope of this paper to perform nor a complete literature review neither a comparison of collision detectionmethods.Despite the huge literature on collision detection methods, onlyrecently they have been used for tensegrity systems in order tocompute free-collision trajectories allowing a shape change ofthe structure. Le Saux et al. (2004a,b) dealt with the problem ofcollision between two slender steel bars by using Moreau’s numerical model of collisions involving restitution coefficients. Authorsconclusion was that the Newton coefficient of restitution variesaccording to the impact location on the rods. Later on, de Wijdevenand de Jager (2005) introduced this problem for shape changingtensegrity structures, yet not providing a general solution. Hernandez and Mirats-Tur (2008a) proposed adding constraints to theform-finding optimization process which take into account all collision related issues for the quasi-static case. Later on, from a control point of view, Hernandez et al. (2009) proposed the use ofpredictive control techniques to avoid self-collisions between elements during a motion, although not providing a general framework to solve the problem.In this paper, we present two methods that cannot be classified inthe groups above discussed. We provide a general and efficientframework for collision detection in the specific case of shape changing tensegrity structures. The first method (the exact approach) isthe solution of an optimal problem and its complexity is close tothose of the literature applied to a tensegrity structure, therefore itcan be taken as a reference to evaluate the computational efficiencyof the second algorithm (the approximate method).ð1Þconstraints, where nlinks is the sum of all bars and cables. For instance, in the case of Fig. 1, there are 27 elements (21 cables and6 bars) and 351 non-contact constraints. Eq. (1) gives the numberof constraints in the worst case. It can be easily seen that it becomesquickly unmanageable as nlinks increases. However, in a well definedcontrol task, some of the non-contact constraints between the barsand/or the tendons may be eliminated by carefully evaluating thespecific structure. For example, sometimes it is known in advancethat some bars or tendons always move far away from other barsor tendons, being impossible for them to collide.The necessary and sufficient condition so that there are no selfcontacts is:i;jd P 0 8i; j 2 L; i – jð2Þi;jwhere L is the set union of all bars and tendons and d is the distance between the ði; jÞ elements. In the following, and without lossof generality, we shall consider bars to be regular cylinders. Hence,(2) can be substituted by:m;ndm;nP dmin 0 8m; n 2 K; m – nð3Þwhere K is the set of segments in R3 representing the cables (theyoverlap with the cables) and the rods (they lie on the axis of the cylm;ninders) and dmin is one half of the two bodies thickness sum.The paper layout is as follows. Next section, hands in a methodm;nto compute the exact value of d as a solution of an optimal problem while in Section 3 we propose an heuristic algorithm to overm;nestimate d with a user defined minimum error. In Section4 somesimulation results comparing the two algorithms are shown together with an estimate of the computation times.2. A real-time algorithm for exact collision detectionConsider two bars in R3 disposed in whichever orientation (seeFig. 2). The case of two cables or a cable and a bar is identical. LetFig. 2. Two bar in the space: definitions of nodes and bar vectors.
1713M. Cefalo, J.M. Mirats Tur / International Journal of Solids and Structures 47 (2010) 1711–172201uxB Cb1 ¼ @ uy A;0uz0x01B Cp1 ¼ @ y0 A;vx 1a ¼ u2x þ u2y þ u2z ¼ kb1 k2B Cb2 ¼ @ v y A0vzx00b ¼ v þ v þ v ¼ kb2 k2x1z00The following parametric equations describe a vector associated toa given point on the first bar, see Fig. 2,0x0 þ ux t1BCp ¼ p1 þ b1 t ¼ @ y0 þ uy t A t 2 ½0; 1 ð4Þx00 þ v x t 01BCq ¼ p3 þ b2 t 0 ¼ @ y00 þ v y t0 A t 0 2 ½0; 1 z00 þ v z t 0ð5ÞThe distance between two genericpointsP and Q, belonging to,!!respectively, the segments P 1 P 2 and P 3 P 4 �ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 0 2 2 2d¼x0 þ v x t 0 x0 ux t þ y00 þ v y t 0 y0 uy t þ z00 þ v z t 0 z0 uz tt; t 0 2 ½0; 1 ð6ÞComputing d can be seen as an optimization problem where thecost function JðzÞ ¼ dðt; t 0 Þðz ¼ ðtt0 ÞT Þ must be minimized with respect to z in the admissible set D defined by the followingconstraints:g 1 ðzÞ ¼ t 6 0ð7Þg 2 ðzÞ ¼ t 1 6 0ð8Þg 3 ðzÞ ¼ t 0 6 0ð9Þ0g 4 ðzÞ ¼ t 1 6 0ð10Þ2Minimizing d on the set D is equivalent to minimize d , with theadvantage that the latter is C2 in all points of D. So, from now on,2it is convenient to consider JðzÞ ¼ d ðt; t 0 Þ.D is a compact set (in finite dimensional space the compactnessproperty is equivalent to those of closeness and boundedness) andJðzÞ is continuous on D. Therefore, thanks to Weierstrass theoremwe know that there exists a global minimum of JðzÞ in D (even ifit is possible that the minimum is not unique).Consider the following function (Lagrangian):Lðz; k0 ; gÞ ¼ k0 JðzÞ þ gT gðzÞð11Þ4where k0 2 R and g 2 R . The minimum of JðzÞ in D must be foundbetween the candidates given by: @L ¼ 0T@z ð12Þg i g i ðz Þ ¼ 0 i ¼ 1 . . . 4ð13Þg i ðz Þ 6 0 i ¼ 1 . . . 4ð14ÞP0ð15Þg i P 0 i ¼ 1 . . . 4ð16Þwith k 0 ; g i not all null.We rewrite JðzÞ as:2JðzÞ ¼ d ðt; t 0 Þ ¼ a t2 þ b t 02 þ c t t 0 þ d t þ e t 0 þ fwherea 0ð18Þb 0ð19Þc ¼ 2ux v x 2uy v y 2uz v z ¼ b2ð20Þ 0 0 0 Td ¼ 2 x0 x0 ux 2 y0 y0 uy 2 z0 z0 uz ¼ 2 s3 b1 ð21Þ e ¼ 2 x00 x0 v x þ 2 y00 y0 v y þ 2 z00 z0 v z ¼ 2 sT3 b2ð22Þ 0 2 0 2 0 2f ¼ x0 x0 þ y0 y0 þ z0 z0¼ sT3 s3 ) f P 0ðf ¼ 0 () P 1 P3 Þð23ÞApplying Eqs. (12)–(16) and recalling the constraints defining theadmissible set D we obtain:k0 ð2 b t0 þ c t þ eÞ þ g3 g4 ¼ 0in the same way, for the second bar,k 02k0 ð2 a t þ c t0 þ dÞ þ g1 g2 ¼ 0z0 þ uz t02zT 2b1B Cp3 ¼ @ y00 Az02yg1 ðt 1Þ ¼ 0g2 t ¼ 0g3 ðt0 1Þ ¼ 0g4 t0 ¼ 0k0 P 0; g1 P 0; g2 P 0; g3 P 0; g4 P 0t P 0;t 6 1;t0 P 0;ð24Þt0 6 1with k0 ; gi not all null. The reader can refer to the Appendix for details on the calculation of the solutions.Summarizing, the problem of computing the distance betweentwo segments in R3 always has maximum nine candidatesðzT ; gT ÞT :0 10B0CB CB CB0CB CB C;BdCB CB C@0A0BBBBBBBBBB@0001B e CB2b CCBB 0 CCBC;BCB d c e2b CBCB@ 0 Aed 2a0000e c d2a10CB1CBCBCB0CBC;BB cþd CCBCB@ e 2b A0100CCCCCC;CCCCACB0CBCBB d 2a CCBC;BCB0CBCB0A@ cþd2a11eþc1 00011CB1CBCBB d 2a c CCBC;BCB0CBCB@ e c 2b A011CB1CBCBCB0CBC;BCB0CBCBA@ e 2b þ c cþd2aCB cþeCB2bCBB 2a d þ c cþe CB2b CC;BCB0CBCB0A@000e c 2 b d12B 4 a b c CB c d 2 e a2 CB 4 a b c CCBB 0 CCBCBB 0 CCBB 0 CA@0Each one of the above candidates is a real candidate for the minimum only if z 2 D and gi P 0 8i 2 ½1 . . . 4 . Note that, the first eightsolutions always take into account the endpoint of, at least, one segment (t and/or t 0 ¼ 0 or 1). For the last candidate (the ninth), alsonote that, from the Schwartz inequality applied to the vectors b1and b2 T b1 b2 6 kb1 k kb2 kð25Þwe haveð17Þ 2 T 4 b1 b2 6 4kb1 k2 kb2 k2ð2
Real-time self-collision detection algorithms for tensegrity systems Massimo Cefaloa,*, J.M. Mirats Turb,1 a Institut de Robòtica i Informàtica Industrial, CSIC-UPC, C/Llorens i Artigas 4-6 2nd Floor, 08028 Barcelona, Spain bCetaqua, Passeig dels Til.lers 3, 08034 Barcelona, Spain article info Article history: Received 6 July 2009 Received in revised form 9 March 2010
