2015年美赛O奖论文B题Problem_B_32879

2015MathematicalContestinModeling(MCM)SummarySheet

IntotheVoid:AProbabalisticApproachtotheSearchforMissingAircraft

Inrecentyears,thedisappearanceofmajorcommercialaircraftoveropenoceanhasledtoexpensiveinternationalsearche?orts.Thesesearchesrequirethee?cientallocationofresourcesandtimeinorderto?ndsurvivorsofthecrashandtheairplaneitself.

Wedevelopagenericprobabilisticmodeltonotonlypredictthelocationofthedownedaircraft,buttoalsoaidinoptimizingthesearchinatimee?ectivemanner.Thismodelassumesthatatthemomentoflostsignal,theplaneexperiencesafailureandisnolongerpowered.Speci?cally,weaccomplishthefollowing:

?InitialProbabilityDistribution:Wecreateapriorprobabilitydensityfunctiontomodelthepotentiallocationsofthemissingplane.Thisdistributionisbasedsolelyontheknowledgethatwehaveabouttheplaneatthetimeoflostcontact:itslocation,bearing,cruisealtitude,andlift-to-dragratio.

?SearchPatterns:Weimplementfourindependentsearchpatternsanddevelopamethodtomeasuretheire?ectivenessbasedonthetotalprobabilityof?ndingtheaircraft.Weconstructanoptimizationalgorithmtodeterminethemoste?ectivemeansofconductingeachsearch.

?DynamicProbabilityModel:WeemployBayesianInferencetocontinuouslyadjusttheprobabilitiesofourdistributionasinformationfromthesearchiscollectedandprocessed.Thisallowsustocreateaposteriorprobabilitydistributionwhichre?nesthedatautilizedinsubsequentsearches.

?Versatility:Weexplorevariationsofcrashandsearchscenariosthatrealisticallysimulateactualincidents.Thisadaptabilityisachievedthroughtheincorporationofadjustableinputparametersthatre?ectuniquecircumstances.

Ultimately,ourmodeldemonstratesthataneasily-packedandspacially-e?cientpattern,suchastherectangularparallel-sweep,moste?cientlymaximizestheprobabilityof?ndingalostaircraftovertime.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

1

Team#32879Page2of35

Contents

1Introduction

1.1Overview......................................1.2Nomenclature...................................1.3SimplifyingAssumptions.............................2ModelTheory

2.1PriorProbability:RandomDescent.......................2.2Bayes’Theorem..................................2.3PosteriorProbability:SearchPaths.......................2.4OptimizationCriteria........

.......................3ModelImplementationandResults

3.1PriorProbabilityModel:ADiscreteGrid....................3.2GeneralSearchModelMethods.........................3.3SimpleSquareSearchModel...........................3.4OptimizedRectangleSearchModel.......................3.5SpiralSquareSearchModel...........................3.6OctagonalSectorSearchModel.........................3.7ModelVariationandComparison.......

.................3.7.1SinglePlaneSearchModelComparison.................3.7.2FivePlaneModelComparison......................3.7.3HighLikelihoodofStall.........................3.7.4ShortRangeSearchAircraft.......................3.7.5ComparisonofVariedSearchPatterns.................3.7.6TheE?ectivenessParameter......

.................

4FinalRemarks

4.1StrengthsandWeaknesses............................4.2FutureModelDevelopment...........................4.3Conclusions....................................

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

2

3334558911131314151718212324252527282932323233

Team#32879Page3of35

1

1.1

Introduction

Overview

Sincethedawnoftheaviationage,crashesandotherincidentshavehelpedshapedthetechnologyintheaviationindustry.Notonlyhavetheyguidedthedesignofairframes,propulsionsystems,wings,andmanyothercomponentsofanaircraft,theyhavealsoheavilyin?uencedthetechnologyoftheentireindustry,includingthatofsearchandrescue.Inthelastdecade,worldwideattentionhasbeendirectedtowardsthesearchformissingaircraft,especiallyoverwater,duetotwomajorincidents:

?June,2009:AirFranceFlightFlight447(AirbusA-330)wentmissingovertheAtlanticOceanwithoutatrace.Ittook?vedaysforsearchersto?ndanysignsofwreckageandnearlytwoyearsforthe?ightdatarecorderstoberecovered[1].

?March,2014:MalaysianAirlinesFlight370(Boeing777)disappearedovertheSouthChinaSea.Anearlyyear-longinternationalsearche?orthasstillfoundnotraceoftheaircraft[2].

Inbothoftheabovecases,allcrewandpassengerswerelost(orareassumedtobelost),andmanymillionsofdollarswerespentinthesearche?ort.Thee?cientsearchandrecoveryofaircraftinthefuturecouldsavelivesandmoney.Inthisreport,wewilldetailaseriesofgenericmathematicalmodelsthatdescribeandoptimizethesearchforamissingaircraft.

1.2Nomenclature

Description

Areaofthesearchgrid

CruisealtitudeformissingaircraftLift-to-dragratioformissingaircraft

Numberofsearchpassesinasearchregion

ProbabilityofagridpointcontainingtheaircraftPosteriorprobabilityforasearchedlocation

ProbabilityofdetectingtheaircraftgivenitiswithinthesearchregionProbabilityofagridpointcontainingtheaircraft,wherenosearchisconducted

r??Posteriorprobabilityforanun-searchedlocationREntiresearchregion

sSquareregionsidelengthWLateralsearchrange

xEast-WestdistancefromthepointoflosingcontactyNorth-SouthdistancefromthepointoflosingcontactzDistancetraveledbythesearchplanewithinasearcharea

Wewillbeginbyde?ningalistofthenomenclatureusedinthisreport:Abbreviation

AhL/Dnpp??qr

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

3

Team#32879

AbbreviationDescription

αParameterdescribingtheeaseof?ndingthemissingplaneβParameterdescribingthee?ectivenessofasearchplaneλE?ectivenessparameterφAngleofchangeinbearingσStandarddeviationθGlideangle

Page4of35

1.3SimplifyingAssumptions

Theaccuracyofourmodelsrelyoncertainkey,simplifyingassumptions.Theseassumptionsarelistedbelow:

?Theplaneispreciselytrackeduntilthemomentthatcontactislost.Atthatpoint,itisnolongerpowered(i.e.theenginesprovidenothrustandnosignalsaretransmitted).?Theplanelostcontactduringthecruisephaseofits?ight.

?Thepilotcanmakeasingleturnofnomorethan180?ineitherdirectionimmediatelyafterlosingcontact.Thisturnisassumedtooccurinstantaneously,asthetheoreticalrangelostduringthisturnisinsigni?cant.?Thereisnowind.

?Therearenooceancurrents.

?Theplane/debriswill?oatinde?nitely.

?Theentiresearchareaiswater(i.e.thesearchareadoesnotextendontoland).?Thesearchplanesonlysearchintheirsearcharea.Althoughtheir?ightfromtherunwaytotheirspeci?edsearchareamaybeoverothersearchareas,theplaneisassumedtonotbesearchingduringthistime.?Thesearchplanescanmakeinstantaneousturns.

?Thereisnolocalcurvatureoftheearth–thesearchareaisaperfectly?at,two-dimensionalsurface.

?Onagivensearchday,thereare12hoursofdaylightduringwhichasearchaircraftcanbe?ying.

Therearealsoseveralparametersofthesearchthatwerede?nedarbitrarilyinordertopresentconsistentresultsinthisreport.Theseparameters,however,canbeeasilyvariedtoaccommodateaspeci?ccaseofamissingaircraft:?Theplaneis?yingdueNorthwhenitlosescontact.

?Arunway,fromwhichsearchandrescuee?ortscanbebased,liesexactly400milesSouthofthepointoflostsignal.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

4

Team#32879Page5of35

2

2.1

ModelTheory

PriorProbability:RandomDescent

First,wemodelthepotentiallocationsforthemissingaircraftwiththeirassociatedproba-bilities.Weassumethattheplaneisnotpoweredafterthelossofsignal,sotheinformationonwhichtobasethesearchislimitedtothelastknownpositionoftheaircraft,thedirectiontheaircraftwastraveling,andthetypeofaircraftthatismissing.Thislastknownpositionwillbeusedtode?netheoriginofaregionRinwhichtheplanecouldbelocated.RegionRwillbede?nedintheCartesiancoordinatesystem,withNorthinthepositiveydirectionandEastinthepositivexdirection.Therearetwopropertiesofthelostaircraftthatareusefulindeterminingwheretheaircraftmaybelocated:lift-to-dragratio(L/D)andaltitude(h).Wewillde?neθastheglideangleoftheplanebelowthehorizontalandφastheaircraft’spossiblechangeinbearingwithrespecttoitsinitialbearing.ThesequantitiesareillustratedinFigures1a&1bbelow:

(a)Visualde?nitionofθ.

(b)Visualde?nitionofφ.

Theminimumvaluefortheunpoweredglideslopeangleθisde?nedbyL/Doftheaircraft[3]:

????

1

θmin=tan?1(1)

L/DAcommonplaneusedfortrans-ocean,longdistance?ightistheBoeing747,having?ownmorethan42billionnauticalmilesinitslifetime[4].ForaBoeing747-400,themostcommonvarietyofthe747,thelift-to-dragratiois17andthecruisealtitudeis35000ft[5].Duetoitsfrequencyoftraveloveroceans,the747-400willbethe?rstaircraftconsideredasthemissingaircraftinthisreport.Itisimportanttonotethattheprobabilisticmodeldescribedlaterisgeneralandcanthereforebeappliedtoanymissingaircraft;thevaluesofL/Dandcruisealtitudesimplyneedtobechangedinthemodel.FromEquation1,theminimumglideslopeanglefora747isabout3.37?.Bygeometricallyanalyzingtheglideangle,asshowninFigure2below,anexpressionde?ningthemaximumrange,rmax,ofthe

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

5

Team#32879Page6of35

planewithoutpowercanbede?ned,seeninEquation2.Sincetheplaneisassumedtolosesignalduringcruise,hwillbeequaltothecruisealtitude.A747hasanimpressivetheoreticalmaximumgliderangeofnearly113miles.

Figure2:DerivationofMaximumGlideRange.

rglide=hcot(θ)

(2)

Ourinitialprobabilitydensityfunctionisbasedonthelikelihoodofeverypossiblecrashtrajectory.Eachcrashtrajectoryisde?nedbyavalueofθandφ.Bothofthesevariablesarerandomandindependent,asθandφcharacterizedi?erentaspectsoftherandom?ightpathexperienceduponthelossofsignal.TheregionRoftheprobabilityfunctionisboundedbythecalculatedmaximumunpoweredrangeoftheaircraft,sweptinalldirectionsfromthepointoflostsignal.Becausetheyareindependent,θandφareassignedtheirownprobabilityfunctions.

Aθvalueveryclosetotheminimumglideangleθminrepresentsapoweroutageintheplaneandthepilot’sdecisiontoglideatthatsetangle,maximizingdistanceandminimizingchanceofdamageuponimpactwiththewater.θvaluescloserto90?signifycatastrophicfailures,suchassuddenlossofliftduetoastalloranexplosion,bothofwhichwouldcauserapiddescent.Theθprobabilitydistributionismodeledasabimodalnormaldistribution,withweightingtowardtheextremecasesofanoptimalglideandacatastrophicfailure.Thedistributionitselfisthesumoftwomutuallyexclusivenormaldistributions.Theweightingofeachisshownbelowasaratiooftheprobabilityofasuddencrash,pcrash,tothatofaglide,pglide=1?pcrash.

θ?θmax)2pglide?1pcrash?1(θ?θ(σmin)2

2σ212e+√e(3)f(θ)=pcrash?f(θcrash)+pglide?f(θglide)=√2πσ12πσ2

Thequantitiesσ1andσ2correspondtothestandarddeviationsofthecrashandglide

distributions,respectively.Similarly,themeanofthecrashangledistributionisθmax=90?,whilethemeanoftheglideangledistributionisθmin.

φiseitherarandomvalue,ifthelossofpowercausesalossofcontrol,orapilot-dependentvaluethatdescribesthedegreeofturningdeemedsuitableforaccidentmitigation.However,sincenothingisknownaboutthedecisionsofthepilotorthecontrollabilityoftheaircraftatthistime,φwillbevariedaccordingtoanormaldistributionwithameanofzero,correspondingtothemostlikelyscenariothattheplanedoesnotalteritscourse.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

6

Team#32879Page7of35

1φ21

√e?2(σ3)(4)σ32πThestandarddeviationoftheφprobabilitydistributionisdenotedasσ3,withameanofzeroexplainedpreviously.Thestandarddeviationsofboththeφandθdistributionswerechosenarbitrarilytoapproximatealikelyscenario.Thesemaybeadjustedbasedoncrashstatisticsandstandardsofthemissingaircraft.Weletσ1=15?,σ2=20?andσ3=30?.Sincethesetwovariablesareindependentandrandom,theirprobabilityfunctionscanbemultipliedtoobtainaprobabilityfunctionthatspanstheentirepossiblesearchspace,in(θ,φ)coordinates.

f(φ)=

p(θ,φ)=f(θ)f(φ)(5)

Thisprobabilityin(θ,φ)spacedoesrepresenttheprobabilitiesweareinterestedin;however,itismoremeaningfultosearcherstomaptheseprobabilitiestoaCartesian(x,y)coordinatesystem.Thesetransformationsaregivenbythefollowingequations,whereρisthecharacteristicturningradiusofthelostplaneinaφ-radianturn.Fromtheseequations,theprobabilitydistributioncannowbetransformedfromp(θ,φ)?p(x,y).

x=

????

2ρ2(1?cos(φ))cos(

π?φ

))+(hcot(θ)?|ρφ|)sin(φ)2

(6)

π?φ

y=?cos(φ))sin())+(hcot(θ)?|ρφ|)cos(φ)(7)

2

Equations6and7applytoapreciseconversionofθandφtoCartesiancoordinates,accountingforelevationlostbothduringastraightglideandduringanyinitialturnthattheplanemayhavemade.However,theseequationsmaybesimpli?edsuchthattheturnismadeinstantaneouslywithnoelevationloss,andtheplaneisthenfreetoglideatanyanglewithinthepossiblevalues.Thissimpli?cationoftheaircrafttrajectoryisallowableduetotheinsigni?cantlossofaltitudeduringtheplane’sturnwithrespecttothefullcruisingaltitude.Usingthissimpli?cationandsubstitutingρ=0intotheaboveequations,theinitialprobabilitydistributionoftheplane’slandinglocationismappedintoCartesianspace.Figure3belowdisplaystheinitialprobabilitydistributionforourexampleaircraft,theBoeing747-400,in(x,y)space.Thereisaspikeattheorigin,correspondingtotheprob-abilityofthesuddencrashcase,andamoregradualincreaseintheinitialdirectionoftheplaneuntilthemaximumgliderangeisreached,atwhichpointtheprobabilitiesdecreasetozero.

2ρ2(1

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

7

Team#32879Page8of35

Figure3:InitialProbabilityDistributionofPlaneLocation.

2.2Bayes’Theorem

Aftertheinitialprobabilityhasbeendetermined,wemustmodelhowthisprobabilitydis-tributionisa?ectedbythesearch.Toaccomplishthis,weseparatetheinformationknownbeforethesearchisconductedfrominformationgatheredduringthesearch.Bayes’Theoremwillbeusedtoderiveageneralexpressionfortheprobabilityof?ndingthewreckage.Bayes’theoremstatedmathematicallyis

P(A|B)=

P(B|A)P(A)

P(B)

(8)

foreventsAandB.P(A)andP(B)aretheprobabilitiesofAandB,whileP(A|B)istheprobabilityofAgiventhatBistrue.Inourcase,eventAis?ndingtheplaneandeventBistheplanebeinginthelocationwearesearching.ThevariableqwillrepresentP(A|B)infurtherequations[6].

Thistheoremcanberewrittentomodelthemannerinwhichsearchinformationa?ectstheprobabilitydistribution.Ifalocationissearchedandtheplaneisnotfoundwithinthatregion,thenewprobabilityof?ndingtheplaneinthatsearchareashouldnotequalzero.Thisisduetothefactthatthereremainsthepossibilityoftheplanebeingtherewhilenotbeingseen.Bayes’theoremcanberewrittentomodelexactlyhowtheprobabilitydistributionshouldchangeafteralocationissearchedandnothingisfound.Forthegridpointthatwassearched,

p??=

p(1?q)

(1?p)+p(1?q)

(9)

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

8

Team#32879Page9of35

wherep??istheposteriorprobability;inourcase,thisisthelikelihoodof?ndingtheplaneinthefutureafterhavingnotfounditpreviouslyinthesamelocation.Similarly,pisthepriorprobabilityof?ndingtheplaneatanygivenlocation.Giventhispoint,thequantityp(1?q)representsthelikelihoodofthelocationcontainingtheaircraftandtheaircraftnotbeingfound,and(1?p)isthelikelihoodthattheaircraftisnotatthelocation.Thisformulaappliestolocationsthataresearched,reducingtheposteriorprobability,p??[7].

Afteralocationischeckedandtheaircraftisnotfound,thelikelihoodoftheaircraftbeinginadi?erentlocationmustbeincreased.Torevisetheseprobabilities,weusethefollowingformula:

r

(10)

1?pq

r??andraretheposteriorandpriorprobabilitiesrespectively,andareanalogoustop??andpinlocationsthatweresearched[7].

Theseformulaeallowustocontinuallymodelnewprobabilitydistributionsbasedonnewdataaboutsearchesthathavealreadytakenplace.Theyalsorenormalizetheprobabilitydistributionsothatateverytime,theplanehasa100%chanceofbeinginthefullsearcharea.

r??=

2.3PosteriorProbability:SearchPaths

Havingalreadysetupthetheoryformodelinganinitialprobabilitydistributionandhowthatdistributionwillchangeovertime,wenowaddressthelikelihoodthattheplaneisdetectedgiventhatitisatalocationthatisbeingsearched.Thisprobability,q,willbede?nedasafunctionofthreevariables:thelateralsearchrange,thetotaldistancetraveledbythesearchvehicle,andtheareathatboundsagivenlocation.LetthelateralsearchrangebeW,whichcanvarywiththeelectronicsbeingusedandthevisibilityintheregionofinterest.Thetotaldistancethatthesearchaircrafttravelswhilesearching,z,cangreatlya?ectthesuccessofthesearch.Inthesamevein,A,theareacontainingthegridsquaresalsoa?ectsthee?ciencywithwhichthesearchisconducted.

Tovisualizethesearchpath,thefollowing?guredepictsasamplepath:

Figure4:Visualde?nitionofW.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

9

Team#32879Page10of35

Toderiveanexpressionfortheprobabilityof?ndingtheaircraftinthisregionA,we?rstneedtomakemoresimplifyingassumptionsaboutthesearchpath.First,thetargetdistributionmustbeuniformovertherectangle.Second,disjointsectionsoftrackmustbeuniformlyandindependentlydistributedintherectangle.Lastly,noe?ortwillfalloutsidethissearchregion.Compliancewiththesethreeassumptionsconstitutesarandomsearch[8].

Nowconsidersomeincrementalstep,h,inthistrack.Letg(h)beafunctionthatdescribestheprobabilityof?ndingthetargetintheincrementhgiventhefailureto?nditpreviously.Therectanglesweptoutinthisnewincrementalstepisshownbelow:

Figure5:Visualde?nitionofh.

Itfollowsthat

Wh

(11)

A

becausethegreaterthewidthanddistanceofthesearch,thehighertheprobabilityofsuccess,butwhentheareaisincreased,thisprobabilitydecreases.

To?ndtheexpressionwewantforq,wewillfollowaderivationoutlinedbyStone[8].Letb(z)betheprobabilitythatthetargetisdetectedaftertravelingsomelengthz.Then,byBayes’Theorem,[1?b(z)][g(h)]isthechanceoffailingtodetecttheobjectafterlengthzbutofsucceedinginthenextsteph.So,

g(h)=

b(z+h)=b(z)+[1?b(z)]

with

b(z+h)?b(z)W

=[1?b(z)](13)

h→∞hA

Theabovedi?erentialequationissimplyanon-homogeneous,lineardi?erentialequationwithconstantcoe?cientsforb(0)=0.Itssolutionisthen

b??(z)=lim

b(z)=1?e?

10

zWAWA

(12)

(14)

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

Team#32879Page11of35

Thiswillde?neq:=b(z,W,A),ortheconditionalprobabilitytobeusedinrevisingthepriorprobabilitymodel.

2.4OptimizationCriteria

Theprimaryobjectiveofourmodelistomaximizethecumulativeprobabilityofsuccessforanygivensearchregion.Thiswillbeaccomplishedthroughminimizingtheposteriorprobabilityp??forsomeregiontobesearched,aslowerposteriorprobabilitycorrelatestoamorethoroughsearchwithinthatregion.Athoroughsearchisrepresentedinourmodelasthemaximizationofq,theprobabilityof?ndingtheplanegiventhatitislocatedwithintheregionsearched.Becauseourinitialmodelproducesaninitialdensitydistributionoveratwo-dimensionalplane,weneedtointegrateoveraspeci?edregionto?ndthetotalprobabilitythatasearchwithinthatregionwillbesuccessful.Mathematically,thisisstatedinEquation15,whereAistheareaoftheregionthathasbeensearched.

????

p(?ndplane|planeisinregion)=q(z?)=maxb(z)dA(15)

z∈R

A

Similarly,throughBayes’Theorem,theprobabilityof?ndingtheplaneintheregionis

theproductoftheprobabilitythatitisintheregionandtheprobabilityof?ndingtheplanegivenitisintheregion.ThisisshowninEquation16.

????

b(z)?p(x,y)dA(16)p(?ndplane)=q(z?)p(x,y)=

A

AsseeninthetheoreticalapplicationofBayes’Theorem,BayesianInferenceisused

tocontinuouslyadjusttheprobabilitiesofadistributionasnewinformationiscollectedandprocessed[9].AsBayesianInferencewillbeusedintheoptimizationofoursearchmethods,wemustincorporatebothqandthechangeofprobabilitywhenagivenregionhasbeenchecked.Essentially,everytimearegionischeckedandtheplaneisnotfoundthere,BayesianInferencewillbeappliedtoreducetheprobabilityoftheplanebeinginthatlocationwhilesimultaneouslyre-normalizingtherestoftheprobabilitydistributiontoaccountforthischange.

AninterestingfacetofBayesianInferenceappearswhenimplementingthismethodacrossalargearea.WhensearchinganareaA,theprobabilityofthatareacontainingtheplaneisreducedbythecorrectfactorandeveryprobabilityoutsideofthatareaisrenormalized.However,thesameresultsareachievedwhentheprobabilitychangeandrenormalizationoccurforanincrementalareadAwithinthelargerareaA.Infact,anentireregionofthedistributioncanbecheckedforasuccessoneincrementalareaelementatatime.Thisisveryapplicablewhentheprocessisimplementedthroughacomputersimulationwhereadistributionismappedtoagridofdiscreteprobabilities.Atwo-dimensionalapplicationofBayesianInferenceisshownbelowinFigure6,wherethemiddlesectionis“searched.”

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

11

Team#32879

Discrete Application of Bayes TheoremPrior ProbabilityPosterior ProbabilityPage12of35

0.020.0180.0160.014Probability0.0120.010.0080.0060.0040.00202040Index6080100120Figure6:TwoDimensionalExampleofBayesianInference.

Astheprobabilityof?ndingtheplaneatanygivenpointwillcontinuouslychangewitheachsuccessivesearch,theoptimallocationtosearchfortheplanewillchangeoverthecourseofmultipledays.Similarly,theprobabilityof?ndingtheplaneonanygivendaywillchange.Forinstance,overthecourseofmanydaystheprobabilitydistributionwillbemuchmoreuniformasthelocationsofhighprobabilityhavealreadybeenchecked.Meanwhile,thelocationsofinitiallylowprobabilityhavebeenincreasinginrelativeprobabilityduetotherenormalizationprocess.Becauseofthisrenormalization,agivenday’sprobabilityofsuccessisde?nedastheproductofallofthepreviousday’sprobabilitiesoffailurewiththegivenday’sprobabilityofasuccess.ThisprobabilityforsuccessondayN,P(N),isdescribedbelowinEquation17.

P(N)=

N?1??k=1

(1?P(k))?

????

A

b(z)?p(x,y)dA(17)

Theoptimizationofthisprobabilityisnoticeablydependentuponthepathlengthofthe

searchpath,z.Eachofthedi?erenttypesofsearchpathswillhavedi?erentlengths,aseachlengthwillvaryduetotherangeofthesearchplaneandthedistancethesearchplanemusttraveltoreachthesearcharea.Duetothislengthdependence,theareaabletobecovered(andthereforemaximumprobabilitytobechecked)willalsovaryforeachtypeofsearch.Throughsoftwareoptimization,theidealpathlengthforanygivenpathtypeandsearchplanerangewillbedetermined.Asthisisaniterativeprocessoverthecourseofmultipledaysandplanes,newregionstobesearchedanddi?erentsearchpathswillbeoptimizedoverthecourseofeachday.Thedetailsofchosensearchpathsandtheprocessofourmodelsimulationaredetailedbelow.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

12

Team#32879Page13of35

3

3.1

ModelImplementationandResults

PriorProbabilityModel:ADiscreteGrid

Inordertomaptheprobabilitydensityfunctionontoamatrixthatcanbeanalyzed,adiscretesquaregridofpointsisde?nedinthe(x,y)-coordinatesystem,witheachgridsectionexactlyonesquaremileinareaforsimplicity.Theboundsofthisgridaredeterminedbasedonrmax,whichisbasedonthepropertiesofthemissingaircraft.Thisyieldsasquaregrid;aninscribedcirclerepresentstheactualsearcharea,butthematrixmustremainsquare.Afterestablishingthissetof(x,y)gridpoints,Equation5,withsubstitutionsfromEquations6and7,isoverlaidonthisgridforeachcorrespondingpoint(x,y)toproducethediscreteinitialprobabilitymassdistribution:

Figure7:Contourmapoftheprobabilitymassdistribution.

Thischoiceofgridsystemwilla?ectlaterderivationsinthemodel,sowewillde?neWtobethelengthofasinglegrid.Thisisalsothelateralsearchrange,andtheoriginofthecoordinatesystemisthepointoflostcontact.Forsimpli?cation,W:=1.WewillalsoadjustEquation16tobeapproximatedoverourgrid:

????

A

p(x,y)dA≈

b??d??i=aj=c

pij

(18)

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

13

Team#32879Page14of35

wherepijdescribestheprobabilityoftheaircraftbeingateachpointinthegrid,whosexandycoordinatesareindexedoveriandj,respectively.aandbarethexboundsofthedoubleintegralandcanddaretheybounds.Thiswillallowustodoagrid-wisecomputationoftheprobabilitiesusingEquations9and10.

3.2GeneralSearchModelMethods

Inthefollowingsubsections,fourdi?erenttypesofsearchmodelswillbediscussed.Thissectionwilldescribethecommonaspectsofallofthemodelstoavoidredundancyintheexplanations.AllofthemodelsweredevelopedinMATLABbecauseitcatersverynicelytotheprocessofiteratingoverasetofCartesianpoints.

Allofthesimulations,unlessnotedotherwise,arebasedononeC-130searchplanewitharangeof2360miles[10].Someofthesimulationswererunusingadi?erenttypeofsearchaircraftwithadi?erentrange.Ineachcase,theactualdailyrangeoftheaircraftwascalculatedusingthataircraft’scruisespeedanda12-hour?ightlimit.Ifthisrangewaslessthanthemaximumrangetoreachthesearchgriditwasusedastherangeforthecalculations.

Ineachmodel,theoptimalsearchlocationandcorrespondingsearchsizeisdeterminedbycheckingtheprobabilityofsuccessforasearchcenteredateverygridpoint.Thecentralgridpointcorrespondingtothemaximumprobabilityofsuccessde?nestheoptimalsearchlocation.Inordertocalculatethismaximumprobabilityofsuccess,thefollowingstepsarefollowedforeachgridsquare:

1.Determinethedistancetoandfromtherunway(arbitrarilyde?ned400milesSouthofthepointoflostcontact)andusethisvaluetodeterminethepossiblerangeremainingfortheactualsearch.2.Convertthisusablerangeintomaximumdimensionsofthesearcharea.

3.Usingthismaximumsearchareaandtheshapeofthesearchmodel,calculatethetotalprobabilityofsuccessovereachgridpointthatispassedoverinthepath.Theoptimalsearchlocationisthendeterminedbythelocationwiththemaximumprob-abilityofsuccess.Thislocationisthen“searched”inthemodel;theprobabilitiesineachsearchedandun-searchedsquareareadjustedaccordingtoEquations9&10.Thisentireprocessisrepeatedforeachdayofsearching.Theposteriorprobabilityfromdayonebe-comesthepriorprobabilityfordaytwo,andsoon.ThecumulativeprobabilityisdeterminedusingEquation17describedpreviously.Theonlyvariationswithinthemodelforeachtypeofsearchpatternoccurinthecalculationofmaximumsearchareafromusablerange,to-talprobabilityofsuccess,andconditionalprobabilityq.Thesedi?erences,alongwiththeresultsfromeachmodel,arediscussedinthenextsubsections.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

14

Team#32879Page15of35

3.3SimpleSquareSearchModel

The?rsttypeofsearchpathwewillconsiderisaparallelsweepofasquarearea.ConsiderapartitionofthegridspaceR,withareaA.Ifrestrictedtothesetofsquares,thisregionRhasacorrespondingsidelengths.Supposethatasearchplanesearchesthisregionwiththe“parallelsweep”searchmethod[11],withalateralsearchrangeofW,allowingittoseetheentiregridsquare:

Figure8:“ParallelSweep”throughasearchsquare.

TheparametersofthissearchprovidealloftheinformationinEquation14,allowingustocomputeq,theconditionalprobabilitythatwe?ndtheaircraft.SinceeachsquarehaslengthW,andareaW2,qforeachofthesesquaresisthesame:1?e?1.

Wenowneedawayto?ndthesizeofapotentialsearchsquarefromacalculatedusablesearchdistance.Weintroducen,thenumberofpassestheplanemakesinthegridspace.s

(19)

W

Thetotaldistanceztraveledinthesearchsquarecanbefoundbytakingnhorizontalpasseswithlength(s?W)(from?gure8),plusadistancesvertically.Thisrelationshipisshownbelow:

n=z=n(s?W)+s

SubstitutingtheexpressionfromEquation19andsolvingfors,wegetthat

s=

√Wz

(21)(20)

Usingthisvalueofscalculatedateachgridpoint,thelargestsquaresearchareacenteredonthatgridpointisdetermined.Thislargestsquareforeachgridpointisusedintheoptimizationdescribedintheprevioussection.After?vedaysofasingleplanesearchwiththismodel,theprobabilitydistributionfunctionisshownbelow:

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

15

Team#32879Page16of35

Figure9:ProbabilityDensityDistributionaftera5-daysearch.

Theoptimizationisclear;?vedistinctsquareregionswereremovedfromtheprobabilitydistributionfunctionwheretheprobabilitieswithineachassociatedareaweremaximized.Thecumulativeprobabilityofsuccessisalsoshownbelow:

0.8Single Plane Simple Square Search ModelCumulative Probability of SuccessDaily Probability of Success0.70.60.5Probability0.40.30.20.1002468Search Day101214161820Figure10:CumulativeProbabilityofSuccessaftera20-daysearch.

Thisstrengthofthismodelliesinitssimplicityandcomputationale?ciency;however,asthesearchareaisconstrainedtoasquareshapeitdoesnotnecessarilyoptimizetheparallel-sweepmethod.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

16

Team#32879Page17of35

3.4OptimizedRectangleSearchModel

Arectangularparallelsweepsearchpatternissimplyageneralizationofthesquarepatterndetailedabove.Theonlychangeistherelationshipbetweenthesearchdimensionsandtheusablerange.Thearea,whichwaspreviouslycon?nedtoasquare,cannowbemadeupbyanyorderedpairof(length,width)forA≥length?width.Themoregeneralizedrelationshipbetweensearchsizeandusablerangeisshownhere:

A=Wz

(22)

Fromthisarea,theoptimizationcodealsotestedthetotalprobabilityofsuccessforallpossiblecombinationsof(length,width)ateachgridpoint.Aconstraintinthisprocesswastoensurethatthecombinations(length,width)wereintegermultiplesofthegriddimensions.After?vedaysofsingleplanesearching,theprobabilitydistributionfunctionisshownbelow:

Figure11:ProbabilityDensityDistributionaftera5-daysearch.

Thisdistributionresemblesthatofthe?vedaysquaresearch,butitleaveslessgaps,clearlyshowingthatarectangularsearchpathisgenerallymoree?ectivethanasquaresearchpath.Thecumulativeprobabilityofsuccessisalsoshownbelow:

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

17

Team#32879

Single Plane Rectangular Search ModelCumulative Probability of SuccessDaily Probability of SuccessPage18of35

0.80.70.60.5Probability0.40.30.20.1002468Search Day101214161820Figure12:CumulativeProbabilityofSuccessaftera20-daysearch.

Thissearchpathmodeldoesanexcellentjobofoptimization.Thisoptimizationcomesatacosthowever,asthemodelismuchmorecomputationallyintensivethanthesimplesquaremodel.Onetime-stepofoptimizationtakesabout20-30secondstorun,comparedwithlessthanasecondforthesquaremodel.

3.5SpiralSquareSearchModel

Thenextsearchmodelisanexpandingsquarespiral.Thefollowing?guredescribesthe“spiral”shapedsearchpath:

Figure13:“SpiralSweep”throughasearchsquare[12].

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

18

Team#32879Page19of35

Thederivationoftherelationshipbetweenthesearchpatternareaandthearclengthtraveledinsideismoreinvolvedthanthatofeitherthesimplesquareoroptimizedrectangle.Considernowthefollowing?gure:

Figure14:Symmetryofthe“SpiralSweep”.

Thesymmetryofthepathaboutthediagonalsimpli?estheapproachtothisderivation.Eachsetoftwoturnsinthesearchis2Wlongerthantheprevious.ThesesetsoftwoturnsbeginfromthecenterasthearrowsshowinFigure14.Additionally,thespiralsearchpatternhasbeendesignedtoconsistentlyendatthebottomrightcornerofthesearchpattern.Extraallowabledistanceintheoptimizationofthesquareregiontobesearchedmaybeinterpretedasasafetyfactorforthefuelconsumptionofthesearchplane.To?ndthetotallengthofthesearch,thesesegmentscanbesummedasnecessary:

z=(W+W)+(2W+2W)+···+((l?1)W+(l?1)W)+(l?1)W

l?1??

=2W(i)+(l?1)W

i=1

(23)

l=(l+1)(Wl?1)+√2??1√

→l=(?2+18?16z))(24)

4

Thesimpli?cationofW=1hasbeenmadeinEquation24tore?ectourmodel.Theterm(l?1)Waccountsfortheeventofthepathendingatthebottomrightofthesquarewithoutextendingthesidelengthofthesquare.Asthesesidelengthsareadded,apatterndevelopswithinthesumthatcanbereducedtotheaboveequation,withthepreviouslyexplained(l?1)Wtermfactoredin.The?nalexpressionofpathlengthzasafunctionofsquaresidelengthlwastheninvertedsuchthatanoptimallforamaximumpossiblezcouldbeobtained.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

19

Team#32879Page20of35

Usingthisrelationshipandthesameoptimizationprocessdetailedearlier,theoptimalspiralsearchover?vedaysandthecumulativeprobabilityofsuccessareshownbelow:

Figure15:ProbabilityDensityDistributionaftera5-daysearch.

Single Plane Square Spriral Search ModelCumulative Probability of SuccessDaily Probability of Success0.80.70.60.5Probability0.40.30.20.1002468Search Day101214161820Figure16:CumulativeProbabilityofSuccessaftera20-daysearch.

Thismodel’sstrengthisinitse?ciency.However,asitislessspatiallye?cientthantheparallel-sweepsquarepath,itwillneverperformbetterthantheparallel-sweep.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

20

Team#32879Page21of35

3.6OctagonalSectorSearchModel

Thelastsearchmodelthatwillbepresentedisanoctagonal“sectorsearch,”whichcanbevisualizedinthefollowing?gure:

Figure17:“SectorSearch”inaregion[12].

Althoughtheoutlininggeometryisnolongerasquare:westillseekarelationshipbetweenzandl,wherelisthesidelengthoftheregularoctagon:

Figure18:Parametersforthe“SectorSearch”.

Here,thepathlengthzisindependentofthechoiceofgridsizeW.Inonefullsearch,theplanetravelsalongtheperimeteronceandeveryinteriorpathtwice,meaningthatthecenterispassedovereighttimes.Therelationshipbetweenlandz,derivedfrombasicgeometry,isshownhere.

zsin(67.5?)l=

8(cos(67.5?)+1)

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

(25)

21

Team#32879Page22of35

Theoptimizationforthismethodisslightlydi?erentduetotheinteriorsectionsofthepatternleftunsearched.Forthesquareorrectangularpaths,theprobabilityoverthefullareacouldbecalculatedusingasimpledoublesum.Forthispath,however,interiorsectionsarenotsearchedsoitwouldnotbevalidtooptimizethedoublesumofthefullsquare.Instead,thesearchlocationisprioritizedbasedonthecentralarea,asitispassedovereighttimes.

Whenlookingforthebestgridsquareonwhichtocenterthesearch,themodellooksforthehighest3-by-3doublesumofprobabilities,whichwouldtheoreticallyrepresenttheoptimalcenterofthegrid.However,sincecertainsearchareasaremuchfurtherfromtherunway,theremaybelessusablesearchrange,whichmakesthatsearchlesse?cient.Tobalancetheusablerangeforthewholesearchwiththehighestprobabilitysumforthecentergrid,theproductofthesetwoquantitiesisoptimized.Thismethodisrudimentaryatbest,asitoperatesnaivelyontheassumptionthatasimpleproductofthesetwoquantitiestrulymodelstheactuale?ciencyofthesearchpath.Inthefuture,amorerealisticoptimizationmodelshouldbeimplemented.

Theprobabilityfunctionafter?vedaysandthecumulativeprobabilityovertimearebothshownbelow:

Figure19:ProbabilityDensityDistributionaftera5-daysearch.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

22

Team#32879

Single Plane Octagonal Sector Search ModelCumulative Probability of SuccessDaily Probability of SuccessPage23of35

0.60.50.4Probability0.30.20.1002468Search Day101214161820Figure20:CumulativeProbabilityofSuccessaftera20-daysearch.

Thismodelisalsoverycomputationallye?cient.Theweaknessesofthismodelhowever,aresigni?cant.Asdiscussedpreviously,theoptimizationisonlybasedonthecentralarea,whichdoesnotgloballyoptimizethesearchareaandlocation.

3.7ModelVariationandComparison

Withenoughresources,asearchoperationforalostaircraftmayconsistofdozensofplanesoverthecourseofweeksormonths,ifnotlonger.Itisveryimportanttooptimizetheuseofalloftheresourcesallottedtothesearchoperation.Inthecontextofourmodel,thismeanssimulatingmanydi?erenttypesofscenarios,fromnumberofdaysspentsearchingtotypeofsearchplaneavailable,andevenvariationsinsearchpatternschosenfordi?erentplanesbaseduponthatplane’scapabilities.Thee?ciencyofeachofthedi?erentmodelswillbecomparedthroughtheircumulativesuccessprobabilities.Theoptimalsearchpatternandplanecombinationshouldideallyresultinthegreatestaccumulatedprobabilityof?ndingthemissingaircraftonanygivenday.

Inthefollowingsections,theresultsfordi?erentvariationsofourmodelarepresented:?Onesearchaircraft?Multiplesearchaircraft?Highprobabilityofstall?Shorter-rangesearchaircraft

?Utilizingmultiplesearchpatternsfordi?erentsearchaircraft

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

23

Team#32879Page24of35

?Searchaircraftthathavedi?erente?ectiveness(sensors,electronics,numberofsearchers)?Missingaircraftthatareeasier/hardertosee?Di?erentparametersforthemissingaircraft

Thesevariationsdemonstrateoneofthemajorstrengthsofourmodel:theeaseofmodi?-cation.3.7.1

SinglePlaneSearchModelComparison

Resultsfromeachofthefourmodelshavebeenpresentedseparately,butitismorehelpfultodirectlycomparethee?ectivenessofeachmodel.Shownbelowarethecumulativeproba-bilitiesofsuccessforasingleplanesearchoverthecourseof20days.Thisisthebestdirectcomparisonofthe?ightpathsbecauseitmodelsthesimplestcase.0.9Single Plane Model Comparison - Cumulative Success ProbabilitySimple Square ModelSpiral Square ModelOctagonal Sector ModelRectangular Model0.80.70.6Probability0.50.40.30.20.1002468Search Day101214161820Figure21:DirectModelComparison.

Therectangularsearchpatternisthebestpatternconsistently,followedverycloselybythesquaresweepandthesquarespiral.Therectangleisageneralizedcaseofthesquare,sotheprobabilityofsuccessshouldalwaysbethesameifnotbetterthanforthesquare.Thesquarespiralisslightlylesse?cientthanthesquaresweepduetotheincreasedsearchlengthrequiredtosearchthesamearea.Theoctagonalsectorsearchismuchlesse?ective,partiallyduetothenatureofthesearchandpartiallyduetotheshortcomingsofthemodel.Thesearchleaveslargetrianglesun-searched,andonsubsequentdays,thereisnowayto

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

24

Team#32879Page25of35

e?ectivelysearchthesetriangles.Also,themodelislikelynotidentifyingtheexactoptimalsearchpath.Therearemanyine?cienciesassociatedwiththissearchpaththatmakeitmuchlesse?ective.3.7.2

FivePlaneModelComparison

Todeterminehowthenumberofsearchplanesa?ectstheresults,themodelswererunusing?veplanesperdayinsteadofone.Ine?ect,thisisnodi?erentthansearchingwithoneplanefor?vetimesthenumberofdays.Itmakessensethatthesameresultsarefoundfor?veplanesasforoneplane:therectangularsearchisbest,closelyfollowedbythetwosquarepaths.ThisisshownbelowinFigure22:1Five Plane Model Comparison - Cumulative Success ProbabilitySimple Square ModelSpiral Square ModelOctagonal Sector ModelRectangular Model0.90.80.7Probability0.60.50.40.30.202468Search Day101214161820Figure22:ComparisonofSearchPatternsfor5LargePlanesover20Days.

3.7.3HighLikelihoodofStall

Todemonstratethee?ectofadi?erentinitialprobabilitydistribution,wemodelacasewherethereishighlikelihoodofstall.Theinitialprobabilitydistributioncouldbevariedbasedonadditionalinformationaboutthemissingaircraft.Inthiscase,weconsiderahighlikelihoodofstallbasedonpastoccurrencesofstallinthemissingaircraft.Intheprobabilitydensityfunctionforθ,pcrashisweightedmoreheavily,resultinginthefollowingpriorprobabilitydistribution:

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

25

Team#32879Page26of35

Figure23:InitialProbabilityDistributionifaStallisMoreLikely.

Eachofthefourmodelswasrunwiththisinitialprobabilitydistribution,yieldingthefollowingresults:0.9Stall Likely Model Comparison - Cumulative Success ProbabilitySimple Square ModelSpiral Square ModelOctagonal Sector ModelRectangular Model0.80.70.6Probability0.50.40.30.20.1002468Search Day101214161820Figure24:ModelComparisonforLikelyStallScenario.

Thesametrendspersistinthismodel:therectangularsearchisthemoste?ectiveandtheoctagonalsectorsearchistheleaste?ective,whilethetwosquarepatternslieinthemiddle.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

26

Team#328793.7.4

ShortRangeSearchAircraft

Page27of35

Next,shortrangesearchaircraftareconsidered.InsteadofthebasecaseC-130searchaircraft,aV-22Ospreyisconsidered,whichhasarangeofonly1011miles[13].Forasingleoneoftheseaircraft,thecumulativesuccessprobabilitiesforeachsearchpatternareshownbelow,?rstover20daysandthenzoomedtoshowonlythe?rst?vedays:

0.20.180.160.140.035Small Plane Model Comparison - Cumulative Success ProbabilitySimple Square ModelSpiral Square ModelOctagonal Sector ModelRectangular Model0.05Small Plane Model Comparison - Cumulative Success ProbabilitySimple Square ModelSpiral Square ModelOctagonal Sector ModelRectangular Model0.0450.040.12ProbabilityProbability0.030.10.080.0250.020.060.040.0200.0150.0102468Search Day1012141618200.00511.522.5Search Day33.544.55(a)ComparisonofSearchPatternsforSingleSmallPlaneover20Days.(b)ComparisonofSearchPatternsforSingleSmallPlaneover5Days.

Theseplotsshowseveralinterestingtrends:

?Thecumulativesuccessprobabilityismuchmorelinearthanwhenusinglongerrangesearchaircraft.Thisisbecausethesearchareasaremuchsmaller,sothesearchoneachdaycanbenearlyase?ectiveasthesearchonthepreviousday.

?Foranincreasednumberofdaysthesimplesquaresearchpathisdemonstratedtooutperformallotherpatterns.Inthe?rstfewdays,therectangularsearchisoptimal,butastimecontinues,therectanglesbecomelesse?cientbecauseprecedingrectangularsearcheshavepartitionedtheprobabilitydistributioninawaythatfuturerectangleshavedi?cultycovering.Thisphenomenaseemsstrange,andshouldbeexploredfurtherinfuturedevelopments.

Theresultsfromtheprevioussectionsdescribeafewveryimportanttrendsthatpersistthroughouteachofoursimulationsregardlessoftypeofsearchplane,initialdistribution,ornumberofsearchplanes:

1.Theoptimizedrectangle,simplesquare,andspiralsquareareallrelativelyconsistentandsimilarintheirabilitytomaximizecumulativeprobabilityof?ndingtheplane.2.Theoptimizedrectangleisconsistentlythemostsuccessfulforthelargeplane(largerange)searches,followedcloselybythesimplesquareandspiralsquare,inorderofdecreasingsuccess.Theoctagonalsectorsearchisfarlesse?ective.3.Itisalsousefultonotethatallsearchesdoapproachacumulativeprobabilityof1,suggestingthatgivenenoughtimetheplanewouldinevitablybefound.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

27

Team#328793.7.5

ComparisonofVariedSearchPatterns

Page28of35

Wenowmovebeyondthecomparisonofdi?erentsearchpatternsandthedi?erentsearchair-crafttoinvestigatethee?ciencyofdi?erentsearchpatternsbeingemployedsimultaneouslybytwoaircraft.Theplotbelowdisplaysthecumulativeprobabilityofatwoplanesearchovertwentydays.Bothscenariosutilizealongrange(C-130)andashortrange(Osprey)searchplane.Inonescenariobothplanesutilizedthesimplesquaresearchmethod,whileintheotherscenariothelongrangeplaneperformedasimplesquaresearchwhiletheshortrangeplaneperformedanoctagonalsectorsearch.0.9Two Plane Model Comparison - Same vs. Different PatternsTwo Square PathsOne Square and One Octagonal Path0.80.70.6Probability0.50.40.30.20.102468Search Day101214161820Figure26:ComparisonofSameandDi?erentPaths.

Afterobservinghowrelativelyine?ectivetheoctagonalsectorsearchis,itmayseemasurprisingresultthatthecombinationofasquareandsectorsearchisnearlycomparabletothatofbothsquares.Thiscanbeexplainedbyobservingwhatoccurswiththeprobabilitydistributionmodeloverthecourseofmultiplesearchdaysandhoweachsearchpatternworks.Thesimplesquareseeksoutthelargestpossiblesquareofgreatestprobabilitytosearch,whilethesectorpatternlooksforasmallconcentrationofhighprobabilityandbuildsawideperimeteraboutthisconcentrationtosearch.Byusingthesetwopatternsinconjunction,thesquaresearchpatternisabletoreducelargeuniformregions,andthesectorpatternwilltargetregionsofhighprobabilitybutsmallarea.Thus,usingtwosquaresearchpathsisstillpreferabletoonesquarepathandoneoctagonalsectorpath,butonlyslightly.Thisisour?rstattemptattestingcombinationsofsearchpaths;inthefuture,wewouldliketotestmorecombinationsusingdi?erentquantitiesandtypesofaircraft.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

28

Team#328793.7.6

TheE?ectivenessParameter

Page29of35

Afteranalyzingthevariouscombinationsofsearchplanerangesandsearchpatterns,weintroducedanotherparametertocreateamorerobustmodel:thee?ectivenessparameter.This“e?ectivenessparameter”isusefulinmodifyingthesimulationtomorepreciselymodelarealisticscenario.Thee?ectivenessparameterλisde?nedbelowinEquation26astheproductoftwootherparameterswhicharedeterminedbythespeci?csearch.

λ=α?β

(26)

Theαparameter,avaluecenteredaround1,describestheeaseof?ndingalostplane.Forinstance,amissingplanesuchasthelargeBoeing747wouldhavealargerαthanaCessnabecauseitistheoreticallyeasierto?nd.Theβparameter,alsocenteredaround1,describesthee?ectivenessofthesearchaircraft.Forinstance,asmallplanewithasinglesearcherperformingavisualscanforsignsofthelostplanewouldhavealowerβvaluethanaC-130Herculesequippedwithmultipleobserversandelectronicsensorssuchassonarandinfra-reddetection.

Usingthede?nitionofλ,wecanre-deriveamodi?cationofEquation14.Becauseλrepresentshowwellanareaissearched,thismodi?esEquation11:

λWh

(27)

A

Thehigherthevalueofλis,themorelikelytheplanecouldbefoundinthatincrementalarea.Wethenplugthisexpressionforg(h)backintoEquation12toget

g(h)=

λW

(28)

A

Thesolutiontothisdi?erentialequationisnodi?erentthanfrombefore,exceptthattheexponentnowcontainsthee?ectivenessparameter:

b??(z)=[1?b(z)]q=1?e

?λzWA(29)

Inessence,wehavebeenusingane?ectivenessparameterofoneforalloftheprecedingmodels.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

29

Team#32879Page30of35

Theplotbelowshowstheresultofdoublingthee?ectivenessparameterbetweentwosquaresearcheswhereeveryotherparameterisheldconstant:

1Effectiveness Model Comparison - Cumulative Success ProbabilityUnit Effectiveness Square SearchDouble Effectiveness Square Search0.90.80.7Probability0.60.50.40.30.20.102468Search Day101214161820Figure27:ComparisonofDi?eringE?ectivenessParameters.

Thisillustratesthefollowingresultsfordoublingthee?ectivenessparameter:

?Thereisanoticeableincreaseofcumulativeprobabilityoverthecourseofa20daysearch.

?Thegreatere?ectivenessparameterdoesnotfullydoublethecumulativeprobabilityofthesearchwithlowere?ciency.

Theseresultsareconsistentwithwhatwouldbeexpected.TheLawofDiminishingReturnsstatesthatifonlyonefactorisincreasedcontinually,thereturnratewilldecreaseovertimeduetotheincrementalincreaseofthisfactor[8].AsshownaboveinEquation29,qdecreasesnon-linearlywithanincreaseofzorλ.Thismeansthatthelongerthepath(orthelongerthesearchduration),thelessprobabilityofsuccesswillbeaccumulatedonanygivendayofsearching.

Tomodelarealworldapplicationofthee?ectivenessparameter,weconsiderthedisap-pearanceofa747vs.thedisappearanceofaCessna172.TheCessnahasacruisealtitudeofonly13000ftandalift-to-dragratioof7.5[14].Thisnotonlychangesthee?ectivenessparameter,butalsotheinitialprobabilitydistribution.Ane?ectivenessparameterof1isusedforthe747searchand0.5isusedfortheCessnasearch,basedonthehypothesisthataCessnawouldbeabouttwiceashardforsearcherstosee.Thecumulativeprobabilityofsuccessforbothofthesecasesisshownbelow:

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

30

Team#32879

Missing Aircraft Type Comparison - Cumulative Success Probability747 CrashCessna 172 CrashPage31of35

10.90.80.7Probability0.60.50.40.30.20.102468Search Day101214161820Figure28:ComparisonofSearchforSmallandLargeMissingAircraft.

Thisplotshowsapotentiallysurprisingresultofourmodel:itismorelikelythatasearchwillresultinthe?ndingofasmallaircraft,suchasaCessna172,thanalargeaircraft,suchasaBoeing747.Thoughthee?ectivenessparameterfortheBoeingsearchislargerthanthatoftheCessnasearch,thesearchareafortheCessnaismuchsmallerthanthesearchareafortheBoeing,duetothelowercruisingaltitudeandlowerlifttodragratio.Thisshowsthatwhilethee?ectivenessparameterdoesin?uencetheprobabilityofsuccessofasearch,theinitialconditionsofthesearcharealsoimportantwhenconsideringtheoverallprobabilityofsuccess.Itisalsoimportanttonotethatthevaluesforthee?ectivenessparametersusedinthesesimulationswereentirelyhypothetical.Tomodelthismoreaccurately,abetterestimateofthee?ectivenessparameterwouldbeneeded.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

31

Team#32879Page32of35

4

4.1

FinalRemarks

StrengthsandWeaknesses

Ourmodelisaprobabilisticapproachtodesignatinglikelylocationsforadownedaircraftaswellasanattempttooptimizesearchpatternsandsearchregionsinlightofphysicalcon-straints.Thismodelwaspurposefullydesignedwiththeintentionofbeingeasilycustomiz-ableandapplicabletoavarietyofscenarios.Thisintentionaluseofmodularprogrammingandgeneralizationleadstoasetofstrengthsandweaknessoftheoverallmodel.Strengths:

?Theinitialprobabilitydistributioncanbeeasilyvariedbasedonthepropertiesofthemissingaircraft.

?Di?erenttypes,numbers,ande?ectivenessofsearchaircraftcanbeeasilyconsidered.?Di?erenttypesofmissingaircraftcanbeeasilyconsidered.

?Theglobaloptimumsearchlocationandsize/shapeisfoundforthesquareandrect-angularsearchmodels.

?Ourmodelcanbepracticallyimplementedinthe?eld.Byvaryingtheinitialparam-etersbasedonthespeci?ccase,optimalsearchpathscanbedetermined.Weaknesses:

?Theoptimizationfortherectangleiscomputationallyintensive.?Theoctagonalsectorsearchmethodisnotgloballyoptimized.

?Themodelreliesonmanyassumptions.Inordertomodelarealworldscenario,theseassumptionswouldneedtoberemovedandincorporatedintothemodel.

?Wedonotconsiderthecost-e?ectivenessofthesearch.Weonlymodelan“all-out”searche?ort.

4.2FutureModelDevelopment

Asdiscussedintheprevioussection,manyoftheissuesarisingfromsuchageneralizedsimulationisthatthemoreuniquefactorsofthescenarioareoverlooked.Also,manyoftheassumptionsofthemodelarenotrealistic.Inthefuture,wewouldfurtherdevelopthemodelinthefollowingways:

?Furtherexploretheoptimizationofsearchingwithmanydi?erentplanesanddi?erentpatternssimultaneously.

?Determinemorerealisticvaluesforcertainsearchparameters,suchasthee?ectivenessparameter.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

32

Team#32879Page33of35

?Consideraprobability-of-successtocostratiosothatthesearchcanbe?nanciallylimitedwhenitisappropriate.

?Considertheplane/debrissinkingandunderwatersearche?orts.?Accountforweatherandoceancurrents.

?Reworktheoptimizationalgorithmssothattheyaremorecomputationallye?cient.?Considermultiplesearchandrescuestaginglocations,aswellasmid-airrefuelingforthesearchaircraft.

4.3Conclusions

Wemodeledthedisappearanceofanaircraftoverwaterbydividingtheproblemintoparts:theinitialprobabilitymodelandthesearchmodels.Todeveloptheinitialprobabilitymodel,weconsideredthetypeofaircraftthatdisappearedandthelikelihoodofdi?erentcrashtra-jectories.Wedevelopedfourseparatemodelsforaircraftsearchpatternsbasedoncommonlyusedsearchtechniques.WethenusedBayesianSearchTheorytocalculateandoptimizetheprobabilityofasuccessfulsearchforeachofthedi?erentsearchpaths,updatingourproba-bilitydistributioncontinuallyasareasweresearchedandnoaircraftwasfound.Finally,wetestedvariationsofourmodels,includingcombinationsofsearchpatterns,multiplesearchaircraft,moree?ectivesearchaircraft,anddi?erenttypesoffailuresthatwouldcauseloss-of-signal.Overall,ourmodelshowedthattooptimizethesearch,squareandrectangularparallel-sweepsearchpatternsshouldbeusedbecausetheymoste?cientlycoveranareaandleavetheun-searchedareasreadytobesearchedbysimilarpatternsonfuturedays.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

33

Team#32879Page34of35

References

[1]“AirFrance447-FinalReport.”(n.d.):n.pag.BEA,July2012.Web.8Feb.2015.[2]‘’MissingMalaysiaPlane:WhatWeKnow.”BBCNews.BBC,30Jan.2015.Web.02

Feb.2015.[3]Anderson,JohnDavid.IntroductiontoFlight.NewYork:McGraw-Hill,1985.Print.[4]“747Family.”Boeing:747FunFacts.Boeing,n.d.Web.08Feb.2015.

[5]Pike,John.“Boeing747.”Military.GlobalSecurity,7July2011.Web.9Feb.2015.[6]Ross,SheldonM.AFirstCourseinProbability.NewYork:Macmillan,1976.Print.[7]“WorkingoutaPartoftheBayesianSearchTheoryEquation.”Weblogpost.Math

Crumbs.N.p.,25Dec.2012.Web.9Feb.2015.[8]Stone,LawrenceD.TheoryofOptimalSearch.NewYork:Academic,1975.Print.[9]Lenk,Peter.“BayesianInferenceandMarkovChainMonteCarlo.”UniversityofMichi-gan,1Nov.2001.Web.9Feb.2015.[10]“C-130Hercules.”U.S.AirForce,1Sept.2013.Web.8Feb.2015.

[11]“TheTheoryofSearch:ASimpli?edExplanation.”Soza&Company,Ltd.Web.8Feb.

2015.[12]“VisualSearchPatterns.”WashingtonStateDepartmentofTransportation.13Jan.

1997.Web.8Feb.2015.[13]“BellBoeingV-22Osprey-History,SpecsandPictures-MilitaryAircraft.”BellBoeing

V-22Osprey.29Jan.2015.Web.8Feb.2015.[14]“Cessna172.”Cessna.us.CessnaAirplanesRSS,n.d.Web.08Feb.2015.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

34

ConvergentIndustries,L.L.C.*LettertoCommercialAirlines2/9/15

Towhomitmayconcern:

FollowingtheeventsofMH370andothercommercialaircraftdisappearances,wewouldliketopresentaplantoallairlinesforfutureopen-wateraircraftsearches.Weunderstandtheurgencythataccompaniesatragedyofthismagnitudetoyourorganiza-tion,aswellasthedesiretobefullypreparedforanysuchemergency.Tothisend,wehavedevelopedafar-reachingmodeltoaccommo-dateandsupplementanyoperationconcern-ingthelossofanaircraftatsea.

Wepresentageneric,?exiblemathemat-icalmodelthatwillaccountforthevariouspossiblesearchandrescuescenariosthatmaybeencounteredwithinyoursphereofopera-tions.Asyourcompanyspansasigni?cantportionoftheglobe,thismodelisspeci?callydesignedtoaccommodatethemyriadofpos-sibleincidentsthatmayoccur.Thebreadthofourmodelincorporatesavarietyofthesepossibleincidents,rangingfromafullandim-mediatepowerlosstoasustainedglideofthea?ectedaircraft.Ourmodelbeginswiththeproductionofamapoflikelylocationsforthedownedair-craft.Thismapisconstructedthroughtheuseofspeci?cationsthatyouwouldbefullyquali?edtoprovide,suchasthemakeoftheplane,standardcruisingaltitudes,and?ightpathoftheplaneatpointoflastcontact.Withthisinformationastrongpredictionofaircraftlocationwillbeproducedtobeginthesearche?ort.

Furthermore,asthesearchprogresses,thismodelwillcontinuouslyupdateprobableplanelocationswiththegatheringofinfor-mationanddatafromthesearch.Thedy-namicmodelallowsforyoursearche?ortstobefullyoptimized,bothwithrespecttotimeandavailableresources.

Additionally,thesearchpathsusedbyyourpilotsinthesearche?ortwillbecom-monlyusedpatternsthataremostlikelyfa-miliartopersonnelalready.Thesestandardpatternsincludetheparallelsweepmethods,spiralsquaremethod,andoctagonalsectorsearch.Afurtherbene?tofourmodelisthatthesimpleconversionofcoordinatesfromthesimulationscanbeeasilytranslatedto?ightpathsandgeographiccoordinatesfortheuseofyourpilots.

Wehopethatthismodelissu?cientinmeetingyourneedsinanyfurthersearchandrescueendeavors.

*

Thiscompanyispurelyaworkof?ction.

也许大学四年，我们会一直在迷茫中度过，因为生活总是难以言说。赛氪APP与您相伴！

本文来源：https://www.bwwdw.com/article/8t13.html