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