外文翻译--用区间法解决正向运动学中Gough类型的并联机构问题.pdf

J.-P.MerletINRIASophia-Antipolis,FranceSolvingtheForwardKinematicsofaGough-TypeParallelManipulatorwithIntervalAnalysisAbstractWeconsiderinthispaperaGough-typeparallelrobotandwepresentanefficientalgorithmbasedonintervalanalysisthatallowsustosolvetheforwardkinematics,i.e.,todetermineallthepossibleposesoftheplatformforgivenjointcoordinates.Thisalgorithmisnumer-icallyrobustasnumericalround-offerrorsaretakenintoaccount；theprovidedsolutionsareeitherexactinthesensethatitwillbepos-sibletorefinethemuptoanarbitraryaccuracyortheyareflaggedonlyasa“possible”solutionaseitherthenumericalaccuracyofthecomputationdoesnotallowustoguaranteethemortherobotisinasingularconfiguration.Itallowsustotakeintoaccountphysicalandtechnologicalconstraintsontherobot(forexample,limitedmotionofthepassivejoints).Anotheradvantageisthat,assumingrealis-ticconstraintsonthevelocityoftherobot,itiscompetitiveintermofcomputationtimewithareal-timealgorithmsuchastheNewtonscheme,whilebeingsafer.KEYWORDSforwardkinematics,parallelrobot1.Introduction1.1.RobotGeometryInthispaperweconsiderasix-degrees-of-freedom(6-DOF)parallelmanipulator(Figure1)consistingofafixedbaseplateandamobileplateconnectedbysixextensiblelinks.Legiisattachedtothebasewithaball-and-socketjointwhosecenterisAiwhileitisattachedtothemovingplatformwithauniversaljointwhosecenterisBi.Thelengthofthelegs(thedistancebetweenAiandBi)willbedenotedbyi.Areferenceframe(A1,x,y,z)isattachedtothebaseandamobileframe(B1,xr,yr,zr)isattachedtothemovingplatform.TheInternationalJournalofRoboticsResearchVol.23,No.3,March2004,pp.221-235,DOI:10.1177/02783649040398062004SagePublications1.2.TheForwardKinematicsProblemTheforwardkinematics(FK)problemmaybestatedas:be-inggiventhesixleglengths,findthecurrentposeScoftheplatform,i.e.,theposeoftherobotwhentheleglengthshavebeenmeasured.Althoughitmayseemthatthisproblemhasbeenaddressedinnumerousworks,ithasneverbeenfullysolved.Indeed,aswewillsee,allauthorshaveaddressedasomewhatdifferent(althoughrelated)problemP:beinggiventhesixleglengths,findallthenpossibleposesS1=S1,.,Snoftheplat-form.ItmaybeacceptedthatsolvingPisthefirststepforsolvingtheFKproblemassoonassomemethodallowsustodeterminewhichsolutionSjinthesolutionsetofPisthecurrentposeScoftherobot.Unfortunately,nosuchmethodisknowntodate,evenforplanarparallelrobots.ThispaperwillalsoaddressthePproblem,althoughwewillbeabletotakeintoaccount,duringthecalculation,realisticconstraintsontherobotmotionthatmayreducethenumberofsolutions.ProblemPisnowconsideredasaclassicalprobleminkinematicsandisalsousedinothercommunitiesasadiffi-cultbenchmark.Raghavan(1991)andRongaandVust(1992)werethefirsttoestablishthattheremaybeupto40complexandrealsolutionstoPwhileHusty(1996)succeededinpro-vidingaunivariatepolynomialofdegree40thatallowsustodetermineallthesolutions.Dietmaier(1998)exhibitedcon-figurationsforwhichtherewere40realsolutionposes.1.3.SolvingMethodfortheForwardKinematicsThemethodstraditionallyusedtosolvePmaybeclassifiedas:theeliminationmethod；thecontinuationmethod；theGrebnerbasismethod.221222THEINTERNATIONALJOURNALOFROBOTICSRESEARCH/March2004A1A2A3A4A5A6B1B2B3B4B5B6COxyzyrzrxrFig.1.Goughplatform.Allthesemethodsassumeanalgebraicformulationoftheproblemwithnunknowns,x1,.,xn.Thesemethodswillbedescribedintuitivelywithouttryingtoberigorous.Intheeliminationmethod(Innocenti2001；LeeandShim2001a)eachequationofthesystemisexpressedasalinearequationintermofmonomialsproducttextxi11.xinn(includingtheconstantmonomial1)inwhichoneoftheunknowns,xk,issupposedtobeconstant(i.e.,thecoefficientsoftheequationsarefunctionsofxk).Additionalequationsareobtainedbymul-tiplyingtheinitialequationsbyamonomialuntilweobtainasquaresystemoflinearequationsthatcanbeexpressedinmatrixformasA(xk)X=0(1)whereXisasetofmonomialsincludingtheconstantmono-mial1.Duetothisconstantmonomial,theabovesystemhasasolutiononlyif|A(xk)|=0,whichisaunivariatepolynomialPeinxk.Aftersolvingthispolynomial,abacktrackmecha-nismallowsustodeterminealltheotherunknownsforeachrootofthepolynomialPe.Themainweaknessofthismethodisthecalculationof|A|；usuallyAisaratherlargematrixanditsdeterminantcannotbecalculatedinclosedform.Mostauthorsproposetouseanumericalmethodtoevaluatethecoefficientsofthepolynomial|A|；thedeterminant(ofordern),whichisalinearfunctionofthepolynomialcoefficients,iscalculatednumericallyforn+1valuesofxkandthereforethecoefficientscanbeobtainedbysolvingasystemofn+1linearequations.However,suchaprocedureisnumericallyunstableandhencethereisnoguaranteeofthecorrectnessofthesolutions.AneliminationmethodhasbeenusedbyHusty(1996)toobtaina40th-orderpolynomialbutusingonlysymboliccom-putationandacarefuleliminationprocessthatguaranteethatweobtaintheexactpolynomialcoefficients；unfortunately,thisprocedureseemstobedifficulttoautomate.TosolveasystemofequationsF(X)=0,thecontinua-tionmethod(Raghavan1991；SreenivasanandNanua1992；LiuandYang1995；Wampler1996)usesanauxiliarysystemG(X)=F+(1)(F1F)=0,whereF1isasystem“similar”toF,inthesensethatithasatleastthesamenum-berofsolutionsasF,ofwhichallthesolutionsareknownandisascalar.Whenisequalto0,G=F1andcon-sequentlythesolutionsofGareknown.Thesesolutionsareusedasaninitialguesstosolve,usingaNewtonscheme,anewversionofGobtainedfor=epsilon1whereepsilon1hasasmallvalue.Thisprocessisrepeatedfor=2epsilon1usingthesolutionsofthepreviousrunasaninitialguessandsoonuntil=1forwhichG=F.Inotherwords,startingfromasystemwithknownsolutionswefollowthesolutionbranchesofasys-temthatslowlyevolvestowardF.ThemainweaknessofthisapproachisthatitisnecessarytofollowalargenumberofbranchestofindallthesolutionsofF.Inourcase,F1hastohaveatleast40solutionsandhence40brancheswillbefol-lowed,someofwhichwillvanishiftheFKproblemhaslessthan40solutions.Furthermore,numericalrobustnessisdiffi-culttoensureifasingularityisencounteredwhenfollowingthebranches.IntheGrebnerbasisapproach,thepropertyisusedthatthesolutionsofanyalgebraicsystemFarealsosolutionsofvariousothersystemsofequationsinsomeotherunknownsyi.Amongallthesesystems,oneofthemhasthepropertyofbeingtriangular,i.e.,thesystemhasafirstequationinoneunknowny1,thesecondequationhasonlyy1,y2asunknownsandsoon,untilthelastequationwithunknownsy1,.,yn.Henceallthesolutionsofthissystemcanbeobtainedbysolvinginsequencethefirstequation,thenthesecondandsoon.SuchatriangularsystemcanbeobtainedbyusingtheBuchbergeralgorithm(Lazard1992；FaugreandLazard1995).Althoughthismethodiscurrentlythefastesttosolveinaguaranteedmanner,theFKproblem(usingtheFGbandtheRealSolvingalgorithmsofFaugre1andRouillier(1995,2003)thisapproachcanonlybeusedwhenthecoefficientsoftheequationsarerational(inwhichcasetheresultsarecertified)anditsimplementationinvolvestheuseoflargeintegers.2.SolvingwithIntervalAnalysis2.1.IntervalAnalysisIntervalanalysisisanalternativenumericalmethodthatcanbeusedtodetermineallthesolutionstoasystemofequationsandinequalitiessystemswithinagivensearchspace.1.Seehttp:/www-calfor.lip6.fr/jcf/index.html.Merlet/SolvingtheForwardKinematics223AnintervalXisdefinedasthesetofrealnumbersxver-ifyingxxx.The“width”w(X)ofanintervalXisthequantityxxwhilethe“mid-point”M(X)oftheintervalis(x+x)/2.The“mignitude”(“magnitude”)ofanintervalXisthesmallest(highest)valueof|x|,|x|.A“pointinterval”Xisobtainedifx=x.A“box”isatupleofintervalsanditswidthisdefinedasthelargestwidthofitsintervalmembers,whileitscenterisdefinedasthepointwhosecoordinatesarethemid-pointoftheranges.Letfbeareal-valuedfunctionofnunknownsX=x1,.,xn.AnintervalevaluationFoffforgivenrangesX1,.,XnfortheunknownsisanintervalYsuchthatX=x1,.,xnX=X1,.,XnYf(X)Y.(2)Inotherwords,Y,YarelowerandupperboundsforthevaluesoffwhentheunknownsarerestrictedtoliewithintheboxX.Therearenumerouswaystocalculateanintervalevalua-tionofafunction(Hansen1992；Moore1979).Thesimplestisthenaturalevaluationinwhichallthemathematicalopera-torsinfaresubstitutedbytheirintervalequivalenttoobtainF.Forexample,theclassicaladditionissubstitutedbyanintervaladditiondefinedasX1+X2=x1+x2,x1+x2.Intervalequivalentsexistforalltheclassicalmathematicalop-eratorsandhenceintervalarithmeticsallowsustocalculateanintervalevaluationformostnon-linearexpressions,whetheralgebraicornot.Forexample,iff(x)=x+sin(x),thentheintervalevaluationoffforx1.1,2canbecalculatedasF(1.1,2)=1.1,2+sin(1.1,2)=1.1,2+0.8912,1=1.9912,3.Intervalevaluationexhibitsinterestingproperties,asfollows.1.If0negationslashF(X),thenthereisnovalueoftheunknownsintheboxXsuchthatf(X)=0.Inotherwords,theequationf(X)hasnorootintheboxX.2.TheboundsoftheintervalevaluationFusuallyoveres-timatetheminimumandmaximumofthefunctionovertheboxX,buttheboundsofFareexactlythemini-mumandmaximumifthereisonlyoneoccurrenceofeachunknowninf(PropertyA).3.Intervalarithmeticscanbeimplementedtakingintoac-countround-offerrors.Forexample,theintervaleval-uationoff=x/3whenXisthepointinterval1,1willbetheinterval1,2where1,2aretheclosestfloatingpointnumbers,respectivelylowerandgreaterthan0.3333.Therearenumerousintervalarith-meticspackagesimplementingthisproperty.OneofthemostwellknownisBIAS/Profil2usingtheCdoubleforintervalrepresentation.However,apromisingnewpackageisMPFI(RevolandRouillier2002),basedonthemulti-precisionsoftwareMPFRdevelopedbytheSPACESproject3,inwhichtheintervalisrepresentedbyanumberwithanarbitrarynumberofdigits.2.2.BasicSolvingAlgorithmIntervalanalysisbasedalgorithmshavebeenusedinroboticsforsolvingtheinversekinematicofserialrobots(Kiyoharu,Ohara,andHiromasa2001；Tagawaetal.1999)andparallelrobotsFK(Castellet1998；Didrit,Petitot,andWalter1998；Jaulinetal.2001),workspaceanalysis(Chablat,Wenger,andMerlet2002；Merlet1999),singularitydetection(MerletandDaney2001),evaluatingthereliabilityofparallelrobots(Car-rerasetal.1999),optimalplacementofrobots(Tagawaetal.2001),mobilerobotlocalization(BouvetandGarcia2001)andtrajectoryplanning(PiazziandVisioli1997).However,intervalanalysisisamorecomplexmethodthanmaybethoughtatafirstglanceandwewillpresentinthispapervariousimprovementsthathaveadrasticinfluenceontheefficiency.Westartwiththemostbasicsolvingalgorithmthatmaybederivedfromthepropertiesofintervalarithmetics.LetB0=X1,.,Xnbeaboxandf=f1(X),.,fn(X)asetofequationstobesolvedwithinB0.AlistLwillcontainasetofboxesandinitiallyL=B0.Anindexi,initializedto0,willindicatewhichboxBiinLiscurrentlybeingprocessed,whilenwilldenotethenumberofboxesinthelist.TheintervalevaluationofthefunctionfjfortheboxBiwillbedenotedFj(Bi).Athresholdepsilon1willbeusedand,ifthewidthoftheintervalevaluationofallthefunctionsforaboxBiislowerthanepsilon1andincludes0,thenBiwillbeconsideredasasolutionofthesystem.Thealgorithmproceedalongthefollowingsteps.1.Ifin,thenreturntothesolutionlist.2.IfatleastoneFj(Bi)existssuchthat0negationslashFj(Bi),theni=i+1andgoto1.3.Ifj1,n0Fj(Bi)andw(Fj(Bi)epsilon1,thenstoreBiinthesolutionlist,i=i+1andgoto1.4.SelecttheunknownkwhoseintervalhasthelargestwidthinBi.Bisectitsintervalinthemid-dlepointandcreatetwonewboxesfromBiasX1,.,Xk1,Xk,(Xk+Xk)/2,.,XnandX1,.,Xk1,(Xk+Xk)/2,Xk,.,Xn.StorethesetwoboxesasBn+1,Bn+2,n=n+2,i=i+1andgoto1.2.http:/www.ti3.tu-harburg.de/Software/PROFILEnglisch.html.3..224THEINTERNATIONALJOURNALOFROBOTICSRESEARCH/March2004Notethatthestoragemethodusedherefortheboxesisnotveryefficientasfarasmemorymanagementisconcerned.AfirstimprovementistosubstitutetheboxBibyoneofthetwoboxesthatarecreatedwhenbisectingit.Asecondimprovement,denotedadepthfirststoragemode,istostorethesecondboxatpositioni+1afterashiftoftheexistingboxes.ThisensuresthatthewidthofBiisalwaysdecreasinguntileithertheboxiseliminatedorasolutionisfound.Inthismode,forasystemofnequationsinnunknowns,thewidthofBiisatleastdividedby2afternbisection.IfthewidthoftheinitialboxB0isw0thenumberNofboxesthatareneededissuchthat2(K/n)=w0/epsilon1andhenceN=nlog(w0/epsilon1)/log(2).Forexample,ifn=9,w0=10andepsilon1=106,weobtainthatthenumberofboxesofLshouldbe210(towhichwemustaddthememorytostorethesolutions).Hence,evenwithahighaccuracyforthesolutionandalargeinitialsearchspacethenecessarymemorystorageissmall.Asamatteroffact,thedescribedalgorithmwillusuallynotbeveryefficient,buttherearenumerouswaystoimproveitaswillbeshownlateron.However,notethatthereisaneasywaytoimprovethecomputationtimeofthebasicalgorithm；indeed,wemaynoticethateachboxinLissubmittedtoaprocessingthatdoesnotdependupontheotherboxes.Henceitispossibletoimplementthealgorithminadistributedman-ner.Amastercomputerwillsendtonslavecomputersthefirstnboxesinthelist.Theseslavecomputerswillindividu-allyperformafewiterationsofthebasicalgorithmandwillsendbacktothemastertheremainingboxesinitsLlist(ifany)andthesolutionsithasfound(ifany).ThemasterwillmanageagloballistLandperformafewiterationsofthebasicalgorithmifalltheslavesarebusy.WewilldiscusstheefficiencyofthedistributedimplementationintheExamplesections.3.EquationsfortheForwardKinematicsLetAiandBibetheattachmentpointsofthelegionthebaseandontheplatform,respectively.ThecoordinatesofAiinthereferenceframewillbedenotedxai,yai,zaiwhilethecoordinatesofBiinthesameframearexi,yi,zi.Withoutlackofgeneralitywemaychoosexa1=ya1=za1=0andya2=za2=0.Notethatforagivenrobotandgivenleglengthsitisalwayspossibletochangethenumberingoftheleglengthsandwewillseethatthishasaninfluenceonthecomputationtimeofouralgorithm.Therearenumerouswaystowritetheequationsoftheinversekinematics(whichconstitutethesystemofequationstobesolvedfortheFKproblem)accordingtotheparametersthatareusedtorepresenttheposeoftheplatform.InthispaperaposeoftheplatformwillbedefinedeitherbythecoordinatesofthethreepointsB1,B2,B3(assumedtobenotcollinear；suchatripletcanalwaysbefoundotherwisetherobotisalwayssingular)iftheplatformisplanar,orbythecoordinatesofthefourpointsB1,B2,B3,B4inthegeneralcase.Thechosenpointswillbedenotedthereferencepointsofthesystem,andtheassociatedlegsthereferencelegs.Ifm,m3,4pointsareusedfordefiningtheposeoftheplatformthenforanyjinm+1,6wehaveOBj=k=msummationdisplay