Towards a Fast Solution Method for the General Rob

TowardsaFastSolutionMethodfortheGeneralRobotMotionPlanningProblemusingaManhattan-likeDistanceFunctiononaNon-UniformGridinCongurationSpace.(ProposalforPh.D.Thesis)CarlVanGeemRISC-LinzResearchInstituteforSymbolicComputationJoh.KeplerUniversityA-4040Linz,AustriaInternet:[e-mail]13,1993AbstractThegeneralizedPianoMover’sProblemcanbeextendedinseveralways,e.g.bytakinginaccountkinematicsanddynamicconstraints,byallowingobstaclestomoveslightly,byaskingforapaththatcanbeseenasagoodpay-obetweensafestandshortestpath,byplanningwithuncertainty,...Alltheseextensionsareusuallytreatedseparatelyfromeachotherintheliterature.Wewillconsideracombinationofsomeoftheseextensionsandwewillinvestigateadirectionofresearchthatseemstobesuitableforsuchcombination.Theapproachplansincongura-tionspaceandisrelatedtothepotentialeldapproach.ThepotentialfunctionhowevershallbereplacedbyanL1-distance-likefunctiononanon-homogeneoushigher-dimensionalgrid.Thisdistancefunctionshallbecomputedwithawavefrontexpansionalgorithm.Theapproachseemstosuitinanaturalwaytomassivelyparallelimplementation.11IntroductionThistextgivesashortoverviewoftheeldofRobotMotionPlanninginallitsfacetsandindicatesadirectionforfurtherresearchinthisarea.ItisassuchmyresearchproposaltothefacultyofRISC,sinceIintendtoworkonthehereproposedline,alsowiththegoaltowriteaPh.D.Thesisaboutthistopic.InthenextsectiontheMotionPlanningProblemisspeciedexplicitely.Atypicalexample,alsoofhistoricalimportance,isthewellknownpianomover’sproblem,wherearobot(piano)hastobemovedfromonepositiontoano-therwithoutcollidingwithanyobstacle(furniturestandingintheway,gettingthepianothroughthedoororthroughanopenwindow).Ofcourse,thisisthewaytoformulatetherobotmotionplanningproblemasa’puregeometricproblem’,forwhichonecanndplentyofsolutionsandalgorithms,e.g.in[Schwartz,Hopcroft&Sharir87],whicharestillnotalwaysapplicabletorealworldproblems.InSection3wesketchthemostimportantsolutionsforthegeometricpro-blemandaclassicationofsolutionapproaches.InSections4and5wedescribeinmoredetailthetoolsthatwillbeusefulinSection6,namelytheconceptof’CongurationSpace’andthe’PotentialFieldApproach’.InSection6,Ipresentmyideasanddirectionsforfutureresearch.2ProblemSpecicationAformalspecicationofthethree-dimensionalgeneralizedpianomover’spro-blem(O;P;pstart;pgoal)canbegivenasfollows:theobstaclesetOconsistsofanitesetof(rational)polyhedraO1;:::;On1,theobjectPtobemoved,consistsofanitesetof(rational)polyhe-draP1;:::;Pn2,whicharefreelylinkedatdistinguishedlinkageverticesv1;:::;vn3,pstartandpgoalaredistinguishedinitialandnalrationalpositionsofP(see[Schwartz,Hopcroft&Sharir87],page273).Motionplanninginitsmostbasicform,canbedenedasndingacollision-freepathforanobject,oracollectionofobjects,amongstationaryobjects([Latombe91a]).TheobjectiveofRobotMotionPlanningistoautomaticallyguidearoundarobotinanenvironmentlledwithobstaclesandtochooseforcestobeappliedwhenassemblingobjects([Canny88]).Thisbasicformoftheproblemcanbeextended.Onecouldtakeintoaccountthephysicallimitationsoftherobot.Thesearethesocalledkinematicconstraints.Twotypesofconstraintscanbedistin-guished.Theholonomicconstraintscanbeexpressedasequationswhichcan2beusedtoeliminatesomeparametersandthusreducethedimensionofcon-gurationspace(Cspace).Examplesofsuchconstraintsarethelimitationsinmovesoflinksofrobotarms(e.g.theycannotrotatearoundcompletely,somelimitationsarepresentonthejoints)orthelimitationsofmovesofcar-likero-bots(e.g.theycannotmovesidewards).Thenon-holonomicconstraints,whicharemuchhardertodealwith,canbeexpressedasnon-integrableequations.TheyinvolvevelocityanddonotreducethedimensionoftheCspace,butofitsvelocityspace.Onecouldnotonlyplanthepositionoftherobotoneverymomentoftime,butalsothespeedand/oraccelerationinfunctionoftime(thedynamics).Onecouldallowtheobstaclestomove.Sincewewanttoplanthemotionoftherobot,itisreasonabletoassumethattheobstaclesmoveonlyslightly.Onecouldalsotrytoplanwithuncertainty,i.e.takingintoaccountthefactthatduringexecutionofthepath,therobotwillnotfollowtheplannedpathexactly.Arobotarmusuallyoscillatesaroundtheplannedroute.Duetotheweightoftherobot(gravitation),thearmalsotendstobowdownwards,alsodependingonwhetherornottherobot(robotarm)iscarryinganobject.Onecouldaskforndingapath(anarbitrarypath),theshortestpath,thesafestpathorforapaththatestablishesapay-obetweentheshortestandsafestpath.Itwouldbeniceinallcasestondapathwheneverthereexistsone.However,sometimesoneusesheuristicapproachesthatdonotguaranteethis,whileonehopessuchanapproachwillalwaysproduceapathinrealapplicationsandwithinareasonablysmallexecutiontime.In[Canny88],theauthorstatesthatthemostdicultplanningproblemsariseinassembly,whereclearancesbetweenpartsaretypicallysmallerthantherobots’positioningandsensingaccuracy.Adistinctionismadebetweengrossandnemotionplanning.Finemotionplanningisconcernedwiththeplanningforcontactbetweentherobotandanobstacle,e.g.whenagripperhastograpanobject,whilegrossmotionplanningdealswithmovesthatmaybeexecutedina’lesscareful’way,e.g.therobotmight