《无人机 翻译》由会员分享,可在线阅读,更多相关《无人机 翻译(6页珍藏版)》请在金锄头文库上搜索。
1、FPGAImplementationofGeneticAlgorithm forUAV Real-TimePathPlanningFrancois C. J. Allaire MohamedTarbouchiGillesLabonte GiovanniFusinaOriginallypublished intheJournal ofIntelligent andRobotic Systems,Vblume54,Nos 1-3,495510.Springer Science+BusinessMediaB.V.2008Abstract Themainobjective ofanUnmanned-A
2、erial-Vehicle(UA V) istoprovide anoperator withservices from itspayload. Currently, togetthese UAV services, oneextra human operator isrequired tonavigate theUAV. Manytechniqueshave beeninvestigated toincrease UAV navigation autonomy atthePathPlanning level. Themostchallengingaspectofthistaskisthere
3、-planningrequirement, whichcomesfromthefactthatUAVs arecalledupontoflyinunknownenvironments. Onetech- nique thatoutperforms theothers inpathplanning istheGeneticAlgorithm (GA) method because ofitscapacity toexplore the solution space whilepreserving the best solutions already found. However, because
4、 the GA tends to be slowdue to itsiterative process that involves many candidate solutions,theapproach hasnotbeenactivelypursued forrealtimesystems.Thispaperpresents theresearch thatwe havedone toimprove theGA computation timeinorder toobtain apathplanning generator thatcanrecompile apathinreal-time
5、, asunforeseen eventsaremetbythe UAV. The paper details howweachieved parallelism withaField Programmable Gate Array (FPGA)implementation ofthe GA. Our FPGAimplementation notF. C.J.Allaire(B) M.TarbouchiElectrical andComputerEngineeringDepartment, RoyalMilitaryCollegeofCanada, Kingston, ONK7K7L6,Can
6、adae-mail:francois.allairermc.caM.Tarbouchie-mail:tarbouchi mrmc.caG. LabonteMathematics andComputer ScienceDepartment, RoyalMilitaryCollegeofCanada,Kingston, ONK7K7L6,Canadae-mail:labonte grmc.caG.FusinaDefence R&DofCanada -Ottawa,Ottawa, ONK1A0Z4, Canadae-mail:Giovanni.Fusinadrdc rddc.gc.ca495K.P.
7、Valavanis et al.(eds.),UnmannedAircraft Systems. DOI: 10.1007/978-1-4020-9137-726onlyresultsinanexcellent autonomous pathplanner, butitalsoprovides thedesign foundations ofahardware chipthatcouldbeadded toanUAV platform.Keywords UAVPathplanningGenetic algorithmsFPGA Real-time1 IntroductionUAVsareuse
8、dformanydifferentservices.Inthemilitarycontext,research hasbeen performed toimprove the autonomy ofthe UAV withdifferent types ofmissions inview: Suppression ofenemyairdefence 13; Air-to-groundtargeting scenario 4; Surveillance andreconnaissance 5; Avoidance ofdanger zones615;and Command, control, c
9、ommunication, andintelligence 16Intheciviliancontext, UAVs couldalsobeusedforpurposes suchas: Weather forecast/hurricanedetection; Urbane policesurveillance; Farmfieldseeding;and BordersurveillanceAllthese scenarios require acommon task:Path Planning. Thistaskiscrucialto thewellbeingofthemissionandt
10、oensure thesafetyofboth themissionandthe UAV. Facing the reality ofadynamic world, UAVs need tore-plan their path in real-time.Currently, there isahuman operator,dedicated totheUAV navigation, whoisresponsible forthat function. ThispaperexplainsasolutionthatprovidesUAVswithanautonomousreal-time path
11、planningcapabilitybasedontheGeneticAlgorithms(GA)methodimplemented onaFPGA circuitboard. Thissolution not onlymeets thereal-timerequirements ofUAVs, but,withsomeadditionalworks, would provide ahardware design ready to beinserted into UAV military and/or civilianplatforms.Firstly,thepaper presents di
12、fferent existingpathplanning algorithms; itexplains why theGAwasselected.Secondly,thespecificGAmethod usedisdetailed. Thirdly, the paper presents details ofthe GA design implementation onthe FPGAcircuit board. Finally,theresultsobtained will bediscussed.2 PathPlanningTechniquesThere are many path pl
13、anning techniques used within the mobile robot world. Each onehasitsstrengths anditsweaknesses.Sometechniquesbetter fitanindoorenvironment, while others an outdoorenvironment. Some techniquesbetter fita fixedenvironment and others adynamic environment. Some are better suited torover robots, other on
14、es to flyingrobots. This section givesanoverview ofthese existingtechniques, whichcanbedividedinthree groups: deterministic techniques; probabilistictechniques; and heuristics techniquesThis sections aim is to highlight why the GA method, from the heuristics techniques, isanexcellent candidate forth
15、epath planning oftheUAV, whichisa flying robot withinadynamicenvironment.2.1 DeterministicAlgorithmsThe deterministic group covers the techniques that are usingfixedcostequations. Thesealwaysprovide thesameresultsforagivenscenario.Theytendtostrivetoget theshortest path,whichmaynotbetheoptimal soluti
16、on.2.1.1 “A-Star”FamilyThebestknownmember ofthisfamilyisDisjkstras algorithm, whichcomputes the costofgoingthrough acell,andeverycellsurrounding thecurrent position, untilit reaches thegoalposition. Asecondmember, A-Star, improved thisintensive search byadding aheuristic constant that directs thesearch onlytowards cellsthat arein the directio