Inverse Kinematics.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.79M 资料格式：pdf 举报版权申诉

whl7711-8889617-4744302542849165947.pdf-第1页.png

第1页 / 共6页

whl7711-8889617-4744302542849165947.pdf-第2页.png

第2页 / 共6页

whl7711-8889617-4744302542849165947.pdf-第3页.png

第3页 / 共6页

whl7711-8889617-4744302542849165947.pdf-第4页.png

第4页 / 共6页

whl7711-8889617-4744302542849165947.pdf-第5页.png

第5页 / 共6页

whl7711-8889617-4744302542849165947.pdf-第6页.png

第6页 / 共6页

文本预览

Triangulation:AnewalgorithmforInverseKinematicsR.M¨uller-Cajar1andR.Mukundan11UniversityofCanterbury,Dept.ComputerScience&SoftwareEngineering.Email:rdc32@student.canterbury.ac.nzAbstractInverseKinematicsisusedincomputergraphicsandroboticstocontrolthepostureofanarticulatedbody.Weintroduceanewmethodutilisingthelawofcosines,whichquicklydeterminesthejointanglesofakinematicchainwhengivenatarget.OurmethodincursalowercomputationalandrotationalcostthanCyclic-CoordinateDescent(CCD),yetisalsoguaranteedtoﬁndasolutionifoneisavailable.Additionallyitmovestheupperjointsofanykinematicchainﬁrst,thusensuringaclosersimulationofnaturalmovementthanCCD,whichtendstooveremphasisethemovementofjointsclosertotheend-eﬀectorofthekinematicchain.Keywords:InverseKinematics,Cyclic-CoordinateDescent,Triangulation1IntroductionItistrivialtodeterminetheﬁnalpositionofakinematicchainwhengivenasetofjointangles.Thereverse,ﬁndingasetofjointanglesgivenatarget,isnon-trivial,asthereareoftenmultipleandsometimesnosolutions.Yetweneedtosolvethisinversekinematicsprobleminanimationandrobotics,whereacharactercomposedofseveralkinematicchainsneedstointeractwithatargetofwhichonlytheCartesiancoordinatesareknown.Currentlymanyalgorithmsthatsolvetheinversekinematicsproblemusenumericalanditerativepro-cedures[1,2,3,4],astheseavoidtheproblemofﬁndingaclosed-formsolution.AnothercommonmethodistoconstructaJacobianmatrixandtheninvertortransposeit[5].Thismethodtendstobecomputationallyexpensive,especiallyforlargematrices.Weproposeanewalgorithmtoﬁndasolutiontotheinversekinematicsproblem.Thisalgorithm,termedtriangulation,usesthecosineruletocal-culateeachjointanglestartingattherootofthekinematicchain.Itisguaranteedtoﬁndasolutionwhenusedwithunconstrainedjointsandthetargetisinrange.ThismethodiscomparabletoCyclic-CoordinateDescent(CCD),aseachjointattemptstoﬁnditsbestorientationwithoutconsideringtheorientationofanyprecedingjoints.Afterreviewingrelatedworkoninversekinematics,wewilldescribeouralgorithmindetail.Thenwewillreportonaexperimentcomparingtriangula-tiontoCCDwhichcommonlyusedinanimationtoday.Laterwewillgoontodiscussfurtherre-searchonthisalgorithminfuturework.2Background2.1InverseKinematicsThestudyofinversekinematicshasrisenwithrobotics.Thusitisnotsurprisingthatsomeoftheﬁrstsolutionsfortheinversekinematicsproblemwererestrictedtocertaintypesofrobotgeometries[4].Pieperpresentedclosed-forminversekinematicsso-lutionsfortwodiﬀerentclassesofrobotgeome-tries[6],butdidnotdosoforageneralkinematicchain.GuptaandKazerounianpresentedanumer-icalsolutionusingtheNewton-Raphsonmethod,whichcouldbeusedasageneralpurposeinversekinematicssolution[1].Althoughthismethodisguaranteedtoconvergeonasolutionifoneexists,itrequiresseveraliterationstodoso.MethodsrequiringtheJacobianInverseareoftencomputationallyexpensiveandcanbenumericallyunstable[7],astheychangeallthejointvariablessimultaneouslyonapaththatwillmovetheend-eﬀectortowardsthetarget.AlsotheJacobianMa-trixcanbesingular,thusmakingitimpossibletoﬁndaninverseforthesolution.CanutescuandDunbrackreviewtheuseofJacobianMatricesandconsiderthemtohavetoomanydrawbackstouseinproteinstructureprediction[8].Criticallytheyﬁndthat“placingconstraintsonsomedegreesoffreedommayproduceunpredictableresults.”TheuseofCCDtosolvetheinversekinematicsproblemwasﬁrstproposedbyWangandChen[9].TheyfoundittobenumericallystableaswellR.M¨uller-Cajar,R.Mukundan,‘Triangulation:ANewAlgorithmforInverseKine-matics’,ProceedingsofImageandVisionComputingNewZealand2007,pp.181–186,Hamilton,NewZealand,December2007.181

Figure1:UsingCCD:Eachjointpcisrotatedsothatθ=0aseﬃcient.Fedorinhiscomparisonofdiﬀerentalgorithmsfoundittobeagoodcompromisebe-tweenspeedandaccuracy[5].Althoughitcantakemanyiterationstoreachthetarget,eachiterationiscomputationallycheap,whichmakesitpossibletousethismethodinrealtimeapplications.FortheabovereasonswehavechosentocompareourmethodtoCCD,asbothmethodsareguar-anteedtoreachorconvergeonthetarget,andarecomputationallyfastenoughtobeusedinrealtime.2.2CyclicCoordinateDescent(CCD)CCDisaniterativemethodthatmovesjointsinoppositeordertotheirimportance.Outerjointsareturnedﬁrst,whichmakesthemovementseemunnatural,especiallywhenthismethodisusedfortheanimationofhumanoidmodels.Asshowninﬁgure1,thealgorithmmeasuresthediﬀerencebetweenajoint’spositionpcandtheend-eﬀectorspositionpe,andajointspositionpcandthetargetspositionpt.Itthencalculatesei-therarotationorquaterniontoreducethisdiﬀer-encetozero.Itdoesthisforeachjoint,iteratingfromtheend-eﬀectortotheimmobilejointattherootofthekinematicchain.Asthejointsclosetotheend-eﬀectorrotatemorethanthejointsclosetotheimmobilejoint,thekinematicchainwillappeartorollinonitself.Theuseofweightsandspringscanmitigatethiseﬀect,butespeciallychainswithmanyjointswilltendtohavesomeunnaturalarrangementofanglesuponreachingthetarget(showninﬁgure2).IfweuserotationtoimplementtheCCD,wesolvethefollowingequationsforeachjoint:cos(θ)=pe−pc||pe−pc||•pt−pc||pt−pc||(1)−→r=pe−pc||pe−pc||×pt−pc||pt−pc||(2)Figure2:UnnaturaljointanglesexhibitedbyCCDaftertheﬁrst(left)andlast(right)iteration.Whereptisthetargetpoint,peistheend-eﬀector,andpcisthecurrentjointthatwearerotating(seeﬁgure1).Thevector−→ristheaxisofrotation.Thuseachjointpcisrotatedbyθabout−→r.Toreachthetargetweiteratethroughthechainrepeatedly,solvingequations(1)and2foreachjoint.Thiswillmovetheendofthekinematicchaintowardsthetarget.ItisworthnotingthatCCDdoesnotattempttoﬁndtheoptimalsolution.WecandeﬁnethecostCofrotatingthekinematicchainusingthesumofalltherequiredrotations.Thisproducesequation(3):C=nXi=1θi(3)AsCCDrotateseachjoint,oftenproducingazig-zagpatternascanbeseeninﬁgure2,thiscostwillbefarfromtheoptimum.2.3LawofCosinesThisisastatementaboutanygeneraltrianglewhichrelatesthelengthsofitssidestothecosinesofitsangles.Themathematicalformulais:b2=a2+c2−2accosδb(4)Wherea,bandcarethethreesidesofatriangleandδbistheangleoppositesideb.Byusingthedotproductoftwonormalisedvectorstoﬁndtheanglebetweenthemwecanadaptthisformulatoﬁndtheanglesrequiredtocompleteatrianglein3-Dspace.3Triangulation3.1MathematicalBackgroundOurmethodusesthepropertiesoftrianglestoac-curatelycalculatetheanglesrequiredtomovethekinematicchaintowardsthetarget.Forthisal-gorithmwerearrangethelawofcosinestotheformula:182

Figure3:TriangularMethod:Foreachjointaweﬁndtheanglesothatwecanform4abcδb=cos−1(−(b2−a2−c2)2ac)(5)Whereaisthelengthofthejointwearecurrentlymoving,bisthelengthoftheremainingchainandcisthedistancefromthetargettothecurrentjoint.Thiswillgiveustheanglethatthevector−→aneedsinrespecttothevector−→c.Tothencalculatetheangleθasshowninﬁgure3,weneedtoonlysolvetheequation:θ=cos−1(−→a•−→c)−δb(6)Werotateeachjointbyθcalculatedinequation(6),abouttheaxisofrotation−→rdeﬁnedby:−→r=(−→a×−→c)(7)Intheidealcasethismethodwillrotateonlytheﬁrsttwojoints,leavingtheremainderstraight.Thisisanattempttokeepthecostfunctionshowninequation(3)ataminimum.Thereareseveralspecialcasesthatneedtobedealtwithseparately,wheretheaboveequationscannothold.3.1.1UndeﬁnedAxisofRotationWheneverthetargetvector(−→c)isparalleltothecurrentjointdirection(−→a),thentheaxisofrota-tion(−→r)willbeundeﬁned.Inthiscaseanarbi-trary−→rneedstobechosen.Thiscaneitherbethesameaxisasusedbythelastjoint,oraconstantaxissuchastheverticaly-axis.3.1.2FulltrianglehasbeenformedThisoccursassoonasasequations(6)and(7)weresolvedsuccessfully.Themethodhasjustformedatrianglewiththesidesoflengtha,bandc.Thuswesimplyrotatetheremainingjointssothattheirdirection,−→a,isequaltothetargetvector−→c.Figure4:TriangularMethod:Ifthetargetistooclosetoform4abc,weshortenbtoreﬂectthelengthofthecollapsedchain3.1.3AtrianglecannotbeformedIfthetargetistoofarawayfromthecurrentjointthenwecannotreachit.Thuswehavec>a+b.Inthiscasethecurrentjointsimplyrotatessothat−→a=−→c.Thisensuresthattheend-eﬀectorcomesasclosetothetargetasispossible.Ifthetargetistooclosetothecurrentjoint,thenwecannotformatrianglewiththesidesa,bandc.Clearlythiswillhappenwheneverc<|a−b|.Wesolvethisproblemusinganaiveapproach:Assumingthatb>aandeachjointcanrotatefreelyabout360owerotatethecurrentjointsothat−→a=−−→c.Mathematicallythisistheeasiestsolution,as:limc→b−aδb=180o(8)Thereforewesimplyﬁxδbat180o,whenwecannotformatriangle.Thismakesitpossibleforthenextjointtoattemptthesamecalculationfromadiﬀerentposition,withnewvaluesfora,bandc.Ineﬀect,forjointi+1,ci+1=ci+ai.Ifa>bthenthetargetcannotbereachedandthereisnosolutiontotheproblem.Forconstrainedjointstheabovemethodwillocca-sionallyfailtoﬁndasolution.Thuswechangebtonolongerbethelengthoftheremainingchainwhenstraight,butinsteadthelengthofthechainwhenfullycollapsed.Thiscanbeseeninﬁgure4,werebisnowmuchshorterthaninﬁgure3.Ifthetargetisstilltoclosetoformatriangle,thenthereisnosolutiontotheinversekinematicsproblem.Theend-eﬀectoragaincannotreachthetarget.Ifthetargetistoofarfromthecurrentjoint,sothatc>a+b,thenitcannotbereached.Inthis183

casewealsorotatethejointsothatitsdirection,−→a,isequaltothetargetvector−→c.3.2AlgorithmThealgorithmforourmethoditeratesthroughev-eryjointtotheend-eﬀector.Ateachjointwesolvethesamesetofequations,thusbythelastjointasolutionwillhavebeenfoundifpossible.Thuswerequireonlyoneiterationtoreachthetarget.Werotatethemostsigniﬁcantjoints(thefurthestawayfromtheend-eﬀector)ﬁrst,whichissimilartothewayhumansmovetheirarms.Thisisusefulincharacteranimation.foreachJointidoCalculate−→ci,c;ifc≥a+bthen−→ai=−→ci;endelseifc<|a−b|then−→ai=−−→ci;endelseθ=cos−1(−→a•−→c)−cos−1(−(b2−a2−c2)2ac);if−→ai=−−→cior−→ai=−→cithen−→r=(0,1,0);endelse−→r=(−→a×−→c);endrotate(−→aibyθabout−→r);endendAlgorithm1:ThetriangulationalgorithmforakinematicchainwithnoconstraintsThisalgorithmassumesthateachjointistoresitsorientationrelativetothelastjoint,andthencal-culatesitsorientationinglobalspaceasai.Ifthisisnotthecase,thenaftercalculatingthenewaiwewouldneedtoiteratethrougheachjointbelowiandrotatethejointbyθ.Thiswouldalmostsquarethenumberofcalculationsrequired,thusmakingthealgorithmsigniﬁcantlylesseﬃcient.Eachjointalsoneedstostorethemaximumlengthofthechaininfrontofit(b).Thiscanbecalculatedonce,asitdoesnotchange.Constraintsthatrestrictthemaximumanglerel-ativetotheprecedingjointcanbeimplementedbycheckingθbeforerotatingandreducingitasrequired.Thismakesthealgorithmsloweraswecannolongersimplyassigntheorientationascanbeseenintheﬁrsttwoifstatementsinalgorithm1,butinsteadhavetoalwayscalculateθ.Figure5:Thestartingpositionsofbothkinematicchains4ComparingCCDandTriangu-lationInthissectionwerunasmallexperimenttocom-paretwoinversekinematicsalgorithmswitheachother.ThecomparedalgorithmsareCCDandournewmethodcalledtriangulation.4.1ApplicationWecreatedasimpleOpenGLapplicationinC++,whichanimatesasimplekinematicchainwithoneend-eﬀector.Thechainhasalengthof40units,splitintofourjointsoflengthnine,andonejointoflengthfour,orintotwojointsoflengtheighteenandonejointoflengthfour.Thelatterchainhasthejointsrestrictedsothatjointtwo(theelbow)cannotrotatebymorethan126orelativetojointone,andjointthree(thewrist)cannotrotatebymorethan90orelativetojointtwo.Thisisasimpleapproximationofahumanarm.Bothchainsasshownbytheapplicationcanbeseeninﬁgure5.Thetargetwhicheachchainwillattempttoreachisrepresentedbyawireframesphere.Itspositioniscreatedrandomly,tobewithinaboxofsidelength60.Thismakesitpossiblethatthetargetisoutsidetherangeofthekinematicchain,whichiscentredattheorigin.4.2ExperimentalSetupToexperimentallycompareCCDwithournewmethod,wemovethetargetto10000diﬀerentpositions.AteachpositionweuseboththeCCDalgorithmandtriangulationtomovetheend-eﬀectorasclosetothetargetaspossible.Thetargetisconsideredreachedassoonastheend-eﬀectormoveswithin0.5unitsofit.IfittakesCCDmorethan99iterationstoreachthetargetthealgorithmaborts.Thisexperimentisrepeatedforbothkinematicchains.Fortheconstrainedchain,itispossible184

010203040506070809010001020304050607080DistanceIterationsFigure6:GraphshowingthenumberofiterationsrequiredbyCCDtoreachthetarget,comparedtotheoriginaldistanceofthehandtothetarget.thatsometargetsevenwithintheradiusofthechainareunreachable.WerecordthenumberofiterationsrequiredbytheCCDmethodtoeitherreachthetargetortoreachastableposition.ForbothmethodswerecordhowcloselythetargetisreachedandthesumofthejointanglesascostC.5Results8.27%oftargetswereoutsidetheradiusofthechain.Afurther2.23%wereunreachablebytheconstrainedchain.CCDreached92.97%ofallreachabletargetswhenconstrainedwithin20iterations,withameannum-berof8.727iterations.Whenunconstraineditreached92.12%ofthetargetswithin20iterationswithameanof8.351.Notethatthemeanalsodoesnotincludethosetargetsthatwereunreachable.Ascanbeseeninﬁgure6,thenumberofiterationsincreasesexponentiallywiththeoriginaldistanceoftheend-eﬀectortothetarget.Theoriginalangleofthetargetvectortothechainisalsosigniﬁcant.Asitincreasessodoesthenumberofiterations.Triangulationreachedeachtargetontheﬁrstiter-ationasexpected.TheaveragecostofCCDusingtheunconstrainedchainwas315.5o,comparedto173.9owhenus-ingtheconstrainedchain.Thetriangularmethodwhenunconstrainedhadameancostof159.9o;Whenconstrainedthisvaluewas141.5o.6DiscussionEverytargetthatcouldtheoreticallybereachedwasreachedbybothalgorithms,asexpected.ItisinterestingtonotethattheconstrainedversionofCCDperformedslightlyfasterthantheuncon-strainedversion.Thereareseveralreasonsforthis:Figure7:5-Jointedkinematicchainreachingforaclosetarget.•Theconstraintspreventedthechainfrom’rollingin’onitselfasshowninﬁgure2.Thusthechaindidnothavetounrollitselfbeforereach-ingthetarget.•Theconstrainedchainhadfewerbutlongerjointsthantheunconstrainedchain.Thustherotationofeachjointhadmoreofaneﬀectontheremainingchain,especiallyinlateriterations.Ascanbeseeninﬁgure7,triangulationachievedmorenaturalposeswhenreachingforthesametargetasCCDinﬁgure2.Thisiscausedbythemajorjointsrotatingbeforethejointsclosetotheend-eﬀector.Itisalsoworthnoticingthatmostjointssimplyremainstraight,insteadoftwistinginseveraldiﬀerentdirections.Thishadaneﬀectonthecostfunction,whichwaslowerforthetrian-gularmethodthanforCCDusingbothkinematicchains.Wecancomparethecomplexityofthetwoalgo-rithmsusingthenumberofcalculationsrequiredforeachjoint.Thedotproductoftwovectorsinthree-dimensionalspacerequiresthreemulti-plicationstocompute.Thecrossproductneedssixmultiplications.Solvingthecosineequationasshowninequation(5)needs5multiplicationsandonedivision.Thisisapproximatelyascomplicatedasacrossproduct.Wedeﬁnethenumberofcalcu-lationsrequiredfortherotationortransormationasr.Ifwelabelthenumberofcalculationsre-quiredforadotproductn,thenboththecrossproductandthecosineequationbothrequire2ncalculations.Wecanrepresentthesevaluesbythefollowingequa-tions:185

NCCD=numIter∗numJoints∗(n+2n+r)(9)NTriangulation=numJoints∗(n+2n+2n+r)(10)ClearlyNCCD>NTriangulation,whenCCDre-quiresmorethanoneiteration.Ifwecomparethiswithourdata,thenfortheunconstrainedchainwehaveameannumberof8.351∗5∗(3n+r)=125.265n+41.755rcalcu-lationsusingCCD,comparedto5∗(5n+r)=25n+5rcalculationsusingtriangulation.Obvi-ouslyourmethodrequiressigniﬁcantlyfewercalcu-lations,andisthusfastertoimplementthanCCD.7FutureWorkOurimplementationofthetriangularmethodhasonlybeenforkinematicchainswithoneend-eﬀector.Ifthisalgorithmweretobemodiﬁedintoaformthatcouldﬁndsolutionsforseveralendeﬀectors,itcouldbeusedformorecomplexcharactermodels.Thealgorithmasitstandscannotacceptconstric-tionsontheaxisofrotation.Bothincharacteranimationandroboticstheserestrictionsoftenex-ist.Thusourmethodneedstobeadaptedtoalsoaccepttheserestrictions.Modifyingthealgorithm,bychangingδbto90oinsteadof180owhenatrianglecannotbeformed,shouldalsobeinvestigated.Thisalternativemightreducethecostfurther,especiallyforconstrainedjoints.8ConclusionInthispaperwehavepresentedanovelmethodofsolvingtheinversekinematicsproblem.Thisnewmethod,whichisguaranteedtoﬁndasolutionwhenitisavailable,isnotiterative,thereforemak-ingitpossibletopredictthenumberofcalculationsrequiredtoreachatarget.LikemethodsusingtheJacobianMatrixthealgorithmwillﬁndasolutionimmediately,insteadofconvergingonasolutionafterseveraliterations.YetunlikethesemethodsitcandealwithsingularitiesasitdoesnotrequiretheJacobianMatrixforitscalculations.OurexperimentshowsthatthetriangularmethodrequiresonaveragemanyfewercalculationsthanCCD,bothwithconstrainedandunconstrainedkinematicchains.Atthesametimeitisjustasaccurate,ﬁndingasolutioneverytimeCCDdoes.Thusthetriangulationmethodcombinesthebestofbothworlds.ItiscomputationallycheaperthanCCD,yetjustasaccurateasalgorithmscalculat-ingtheJacobianinverseortransposeofanin-versekinematicsproblem.UsingacostfunctionwecouldshowthatitconsistentlyrequireslessrotationsthanCCD,yetitisworthnotingthatourmethoddoesnotguaranteeoptimalrotations(whereeachjointmovesbyaminimalamount);LikeCCDitcalculatesanglesonejointatatime,thusitisnotpossibleforittoﬁndsuchaminimalsolutionfortheentirekinematicchain.References[1]K.C.GuptaandK.Kazerounian,“Improvednumericalsolutionsofinversekinematicsofrobots,”inProceedingsofthe1985IEEEInter-nationalConferenceonRoboticsandAutoma-tion,vol.2,March1985,pp.743–748.[2]A.Goldenberg,B.Benhabib,andR.Fenton,“Acompletegeneralizedsolutiontothein-versekinematicsofrobots,”IEEEJournalofRoboticsandAutomation,vol.1,pp.14–20,March1985.[3]V.J.Lumelsky,“Iterativecoordinatetrans-formationprocedureforoneclassofrobots,”IEEETransactionsonSystemsManandCy-bernetics,vol.14,pp.500–505,Jun.1984.[4]V.D.TourassisandJ.Ang,M.H.,“Amodu-lararchitectureforinverserobotkinematics,”IEEETransactionsonRoboticsandAutoma-tion,vol.5,pp.555–568,October1989.[5]M.Fedor,“Applicationofinversekinematicsforskeletonmanipulationinreal-time,”inSCCG’03:Proceedingsofthe19thspringconferenceonComputergraphics.NewYork,NY,USA:ACMPress,2003,pp.203–212.[6]D.L.Pieper,“Thekinematicsofmanipulatorsundercomputercontrol,”Ph.D.dissertation,StanfordUniversityDepartmentofComputerScience,October1968.[7]J.Lander,“Makingkinemoreﬂexible,”GameDeveloper,vol.1,pp.15–22,November1998.[8]A.CanutescuandR.Dunbrack,Jr.,“Cycliccoordinatedescent:Aroboticsalgorithmforproteinloopclosure,”ProteinScience,vol.12,pp.963–972,May2003.[9]L.-C.T.WangandC.C.Chen,“Acombinedoptimizationmethodforsolvingtheinversekinematicsproblemsofmechanicalmanipu-lators,”IEEETransactionsonRoboticsandAutomation,vol.7,pp.489–499,August1991.186

分享到：

赞收藏

资料库

Inverse Kinematics.pdf

相关推荐

开发技术

热门标签

最新资料