移动机器人全覆盖路径规划研究

上海交通大学硕士学位论文移动机器人全覆盖路径规划研究姓名：王俭申请学位级别：硕士专业：控制工程指导教师：陈卫东;仲嘉霖20030601COMPLETECOVERAGEPATHPLANINGOFMOBILEROBOTABSTRACTAsaspecialapplicationofintelligentmobilerobot,theoreticallyandtechnologicallyspeaking,autonomousvacuumcleanerinvolvesseveralkeytechniquesinmobilerobot.Andalso,fromthepointofviewofmarket,autonomousvacuumcleanerhasverywideforeground.It’sachallengetodevelopautonomousvacuumcleaner.Thispaperstudiesthemethodofcompletecoveragepathplanningofmobilerobotinaregionwithobjects.Itbringsforwardapracticalandoptimalschemeofcompletecoveragepathplanningmethod.Asaprinciple,thispaperthinksthattheregiondecomposition,thewalkingmannerinsub-regionandthelinkingofsub-regionsactoneachotherandinfluencestheefficiencyofcoverageactiontogether.Sotheyshouldbetakenintoaccounttogetherwhenstudyingtheissueofoptimalpathplanning.Theschemeinthispapercontainsseveralmainpointsasfollows:robotwalksinsub-regionalonginnerspiralpath,“doubleline-sweep”methodisappliedtodecomposewholeregion,theregionmodelisdescribedbymeansofadjacencygraph,somemorelink-linesbetweennodesareaddedaccordingtomodels,theHopfieldArtificialNeuralNetworksalgorithmisusedtomakedirectionaladjacencygraph,robotdeterminesdynamicallyitsdestinationpointinnextsub-region.Then,thispaperprovidesasimulationprogramandrunittoverifyiftheschemeisrational.Thecomputersimulatingresultissatisfactory.Finally,wemakeaprototypeofvacuumcleanerwiththreewheelsandsomesensorssuchasinfrareddetectors,photoelectricencoderandbumpingdetectors.TheprototypemakesuseofMotorolasinglechipmicroprocessorasCPUandInteractiveCasprogramdesigninglanguage.Theprototypecanwalkalonginnerspiralpathinsub-regionsandcangofromonesub-regiontoanother.Theprototypehasthemainfunctionsofamobilerobot.Thecoveragetestontheprototypeillustratesthispaper’smethodispracticabilityandvalidity.KEYWORDSmobilerobot,pathplanning,completecoverage,graphtheory,artificialneuralnetworks31.14———51.2——————67——8——————9——101.311122.1132.214Fig.2-1innerspiralpathmayleaveuncoveredarea2.315162.4Fig.2-2innerspiralpathmayleaveuncoveredarea172.5182.6193.1Fig.3-1margineffectFig.3-2variableendpointofrobot20Fig.3-3innerspiralpathisbetteratlinkingbetweensub-areas[2324]]21Fig.3-4thetrianglewithshadowhastoosmallarea1426735Fig.3-5adjacencygraph[22]——3.222Fig.3-6theendpointofrobotinsub-regionisnearthecenterofgravitynn3-1nn+13-73-23-323Fig.3-7thecomparisonbetweentheback-and-forthtracktheinner-spiraltracknn+13-2123……n123……n(3-1)wnL-()()wLn-+1()kwwn+-1()wkwLn21-++()()()()()[]nwLwLwLwLwL-++-+-+-+-Λ32()[]()[]()[](){}kwkwwkwwnkwwnkwwn+++++-++-++-Λ3213-3()()()wnkwkwLn1121----++24Lwk13-23-3(1–k)(n–1)wFig.3-8“doubleline-sweep”methodFig.3-9withouttoosmallarea25D1D2D3D1D2D2D1D3D2D2D3263.3————27Fig.3-10dealingwiththegeometrydimensions3.4xxyyxxyyxxyy10cm15cm25cmdot-robotatcirclecenter28Fig.3-11themapofareabycoordinates3.5xxxxxxxxxxFig.3-12thefiveareaswithsameheighty4y6y5y3y2y1x1x2x6x5x3x4x1x2x6x5x3x429xxyyxxyyxxyyxxyyxxyyxxyyxxyyFig.3-13furtherdecompositioninto7sub-regionsKy–yKy–yKy–yKy–yKx1x2x6x5x3x4y1y3y2y5y4y6123456730Fig.3-14narrowcorridormakesrobottostopnotincenterFig.3-15somekindsofthesituationsofwithoutone(some)sub-region(s)3.631xxyyxyxy3-43-5⎥⎦⎤⎢⎣⎡⎟⎠⎞⎜⎝⎛-⎟⎠⎞⎜⎝⎛-2,21211yyxx22122122⎟⎠⎞⎜⎝⎛-+⎟⎠⎞⎜⎝⎛-yyxx32xxyyxxyyxxyyxxyyxxyyxxyyGGijGijGFig.3-16theabutmatrixofadjacencygraphGGijijGij3.733NN3-6()!121-=NM34N=5N=101.210–71.8110–3N=20N=301.410133635Fig.3-17continuousXiiVjjIiiWij——jiVjfXjfSSFig.3-18thefunctionbetweeninputandoutputofnervecellW1W2Wn1InIiI2I1VnViV2V1XnXiX2X1ni21W1iW2iWniW1W2Wnn3-8()xxeexf--+-=1110xf(x)-1∑=++-=njijjiiiIVWXdtdX1t3-736EWijWjidViXiViWINNNC1C2C3d12d23d3-9()hhtdfIVVVWEiVnjniniiijijini∫∑∑∑∑-====+--=01111112137d12d23dNNC1C2C3C4C5NC3C1C5C2C4C3dd31d15d52d24d43C1C2C3C4C5Fig.3-19therelatingmatrixofTSPhVVxiVyjxyijVxixxdxy3-10()()∑∑∑=-+≠==+=NyiyiyxixyNyxiNxVVVdDVh11,1,11238gVNVxiNABCDdxyEEN3-113-133-143-153-12()∑∑∑∑∑∑∑∑====≠==≠==⎟⎠⎞⎜⎝⎛-++=NjNyxiNiNxyixyNyxxNixjxiNjiiNxNVCVVBVVAVg112111111222()()VgVhE+=iiXEdtdX∂∂-=⎟⎠⎞⎜⎝⎛-----=∑∑∑∑==≠==NixiNxNxyyyiNjxjixixiNVCVBVARXdtdX1111⎟⎟⎠⎞⎜⎜⎝⎛+=⎟⎟⎠⎞⎜⎜⎝⎛-+=00tanh1212exp11XXXXViixi39Fig.3-20theadjacencygraphconstructedaccordingtorealsituation136754240——Fig.3-21adjacencygraphafteraddingsomelink-lines(1)Fig.3-22adjacencygraphafteraddingsomelink-lines(2)13675421367542167542(3)1375(6)42AB41Fig.3-23the10modesofthewholearea1256789103442GG433.8ABCABBCBBC——3.94490Fig.3-24amorecomplexarea45Fig.3-25dividinginto4sub-areasafterturningit90clockwise46——474.1Fig.4-1theframeplotofprogramfunctionmodules484.2xxyyxxyyxxyyxxxxxxxxxxxxxxyyxxyyyyxxxxyxxyyxxxxyxxyy49xxyyxxyyKy–yKy–yKy–yKy–yKxxyyxxyy50ijii51Fig.4-2the10generalizedadjacencygraphsaccordingto8modes52ijijx’y’x’’y’’ttXxitXinitxxXxitVxit4-14-24-34-44-5⎥⎥⎦⎤⎢⎢⎣⎡⎟⎟⎠⎞⎜⎜⎝⎛-+⎟⎟⎠⎞⎜⎜⎝⎛-2'''2'''22yyxx()1ln210-=NXXinit()()⎥⎦⎤⎢⎣⎡⎟⎟⎠⎞⎜⎜⎝⎛+=000tanh121XtXtVxixi()∑∑∑∑∑=-+==≠==+-⎟⎠⎞⎜⎝⎛-----=NyiyiyxyNixiNxNxyyyiNjxjixixiVVdDNVCVBVARXdtdX11,1,11110ttxidtdX=53XxittVxiC1C2C3C4C5Fig.4-3therelatingmatrixshowingtheresultofrunningprogramsC3C1C5C4C2C3C1C5C4C24-6()()tdtdXtXttXttxixixiΔ×+=+=0005484.3CHNNXABCDABCDA—B—C—DJK