硕士论文-基于栅格法的汽车路径规划

华中科技大学硕士学位论文基于栅格法的汽车路径规划姓名：黄耀申请学位级别：硕士专业：系统工程指导教师：郭敏20080606I()ALADijkstraDijkstraIIAbstractThepathplanningisthatamobilerobotsearchesanoptimalpathorasub-optimalpathfromtheinitialstatetothetargetstateinaccordancewithaperformanceindex(suchasdistance,time,energy,etc.).Inthisthesis,takingautomobileallocationandtransportationassistantdecision-makingsystemasbackground,wediscussthepathplanningapplicationinengineering.Theobjectivesofthisprojectareprovidingacertainnumberofoptimizedpathforsometypicaldistributedmapsandsometypicaltasksandsortingpossiblepath.Themaindifficultiesareenvironmentalmodelingforsystemandtherequirementofmeetingreal-timeinpathsearch.Firstly,thisthesisintroducesthecurrentresearchstatusaboutpathplanningfromtheenvironmentalmodelingandpathsearch,andgivesthemaincontentsandtheorganizationalstructure.Secondly,combiningwithcharacteristicsoftheproject,weproposeimprovedgridmethodforenvironmentalmodeling.AndweproposetousetheALAmethodforfittingandsmoothinglinesbetweengrids.Thirdly,weproposetwosearchmethodsbasedonimprovedgridmethod.Oneglobalsearchalgorithmtakesbreadth-firstsearchalgorithmasbase.Weusehashtabletopreventtheduplicationofstatesinthismethod.Andthismethodgreatlyimprovessearchingspeed.Inthisthesisweresearchhowtocreatehashtable,andweproposetousetwomethodstosettlehashcollision.AnotherapproximatesearchmethodbasesonDijkstraalgorithm.Takingcertainperformanceaspremise,thismethodcanrealizefastersearchingspeed.Inthisthesis,wegivedetailedprogrammingfortwosearchmethods.Andweusethesetwomethodstocalculatethepathformovingcarinaccordancewithsometypicaldistributedmaps.Intheendwecomparethetwomethodsfromthesearchingspeedandtheresults.Finally,thedevelopmentproject,functionsandsomeinterfacesofthesoftwareareintroduced.KeywordsPathPlanningGridMethodBreadth-FirstSearchAlgorithmDijkstraAlgorithmHashTable111.1()()[1]()()(1)(2)(V-graph)[2](FreeSpaceApproach)(Grid)[3]DijkstraA*[4]Dijkstra(O(n2))2[5]Dijkstra[6-7][8][9-10][7]30×3041.7s1.2Dijkstra31.2.11CC-SC-CC-S[11-13][14]Voronoi[15-17][18](1-1)1-21-141-2Voronoi2[19-22]1.2.21(GeneticAlgorithmGA)N(N3)NN3Holland[23-26]5123GA[27]1988CleghornA*Davidor(1991)J.Olsan(1993)ChenZalzala(1994)OsanmuOno(1996)1-36DNABalakrishman[28]9(Completeness)(Closure)(Compactness)(Scalability)(Multiplicity)(Flexibility)(Modularity)(Redundancy)(NoRedundancy)(Complexity)1-37nPcPc=0.250.75PmPm=0.010.22[29-30]KhatibSatoLaplace[31]UartUart=UO+Ug1.11.1UOUgFgFOFartFart=FO+Fg1.28()()gggggUUUFgrudUijkxyz∂∂∂=−=−++∂∂∂1.3()()oooooUUUFgrudUijkxyz∂∂∂=−=−++∂∂∂1.41.2Fart=0KorenBorenstein1(Deadlock)[32]234YungYe3SebastianThrun[33]1OccupancyValue(C)(C)2(BasicPoints)C(xy)(x′y′)C93(Clearance)C(xy)(x′y′)4VoronoiVoronoi5(CriticalPoints)(CriticalLines)VoronoiVoronoi671.310ALADijkstra1122.1[34-37]HowdenWE19682-1xy12[38-39]2-1[40]13[41][42]14ASRobASAS0XYASXYXmaxYmax[0R]RXYN=Xmax/RN=Ymax/RASAS2.22.2.12152-22-311232456237891011121322323455633788991021113125891312-4222-416123456782-22-32-43X17360°845°45°180360°42-52-2245X2-6X452-72-52-61182-71415X2-82-82.2.211912341122121222121212-127878872-93123202-912-12427822-131117312-10212-1012-112-11112424413566153881791010194111213141512152212-122-12122-132-1322.32.3.1ALACAabALA[43]2.1P=A(ac1)⊕L(c1c2)⊕A(c2b)forcertainc1c2C2.1ALAabALA1ALAA(a*)⊕L(**)⊕A(*b)A(a*)CR(a)A(*b)CR(b)ALAL(**)2-14232-14ALA(1)2-14abALACR(a)CR(b)2ALAA(a*)⊕L(**)⊕A(*b)A(a*)CL(a)A(*b)CL(b)ALAL(**)2-152-15ALA(2)242-15abALACL(a)CL(b)3CR(a)CL(b)abALAA(a*)⊕L(**)⊕A(*b)A(a*)CR(a)A(*b)CL(b)ALAL(**)CR(a)CL(b)ALA2-162-16ALA(3)2-16abALACR(a)CL(b)4CL(a)CR(b)abALAA(a*)⊕L(**)⊕A(*b)A(a*)CL(a)A(*b)CR(b)ALAL(**)CL(a)CR(b)ALA2-17252-17ALA(4)2-17abALACL(a)CR(b)ALA48ALAALA2.3.22-18c=(xcycΘc)xcycXYΘc262-182-18ccRcFcRcRcFclcΦmax1lc2RclcR≥|L/tan(Φmax)|Rmin=|L/tan(Φmax)|1Lf(ab)=ab2Lb(ab)=ab3Af(ab)=ab4Ab(ab)=abcCL(c)CR(c)2-19272-19ALA1AB()2-202-20AB2ABR()2-21CL(A)CL(B)CR(A)CR(B)2-21AB322-22CR(A)28CL(B)2(4)42-224ALA2-232-232.4ALA293Dijkstra3.13.1.1123-113-23-3303-13-2(1)3-3(2)()131233.1.2(Breadth-FirstSearch)vvv“”“”vv123-4v1v1v2v3v2v4v5v3v6v7v4v8v1→v2→v3→v4→v5→v6→v7→v83-432int32n1n1n1n2n2n3121A[1]A[2]A[3]A[1]A[2]2{A[1]for(i=1i=ni++){//nP1=A[i]P2=A[i+1]for(j=1j=P1j++){B=P1[j]//PjBBP2//P2P1}}}33A[1]A[1]???n1n1{Abegin=end=for(i=begini=endi++){//n}for(i=begini=endi++){//}begin=end+1//34end=end+child_count//child_countdep++//}}1233.1.3()“”“”“≠”B-“”“”“”3ffKf(K)Kf(K)f(Hash)3035C(1:30)C[i]iiC[i]1C[i]f(key)=keyf(key)=key(1)BEIJINGB02(2)30()30TIANJINTN3404key1≠key2f(key1)=f(key2)(collision)(synonym)n0n-1C8()C152*C152*7!=1.09388*101210000999H(key)()“”36(Uniform)“”1H(key)=key3.1H(key)=a*key+b3.2ab()2r(10)34()()(folding)37(ISBN)10100005mpH(key)=keyMODpp≤m3.3(MOD)pp()p=266a1i1temp1cp1p206H(key)=random(key)3.4random1()2383456int321()241024k(20)h=(h1&0x000FFFFF)^(h120)h1n1=(p[1]4)+(p[2]1)+p[0]//n2=(p[3]3)+(p[4]2)n3=p[5]m0=(n23)^(n12)h1=n1+n2+m0+n30~(n-1)j(0≤j≤n-1)“”Hii=12k(Hi[0n-1])H139H2H2H3HkHk1Hi=(H(key)+di)MODmi=12k(k≤m-1)3.5H(key)mdi3di=123m-1di=12-1222-2232±k2(k≤m/2)di=11176029(H(key)=keyMOD11)38567884ii+1i+2ii+1i+2i+3i+3Hkm4j+3(j)2Hi=RHi