COMAP,Inc.TheUMAPJournal40:2July17,201910:04p.m.D1924801.texpage135TimetoLeavetheLouvre135TimetoLeavetheLouvre:AComputationalNetworkAnalysisVinitRanjanJunmoRyangAlbertXueDukeUniversityDurham,NCUSAAdvisor:DavidKrainesAbstractIncreaseinterrorattackshasraiseddemandforsafeemergencyevac-uationplansworldwide.WefocusonevacuatingtheLouvre,theworld’slargestartmuseum.Evacuationismadedifficultbythevolumeandvarietyofvisitors;theLouvremanagementdesiresevacuationplansoverabroadsetofconsiderations.WepartitiontheLouvreintosectionsandbuildanagent-basedmodeltosimulateevacuationsineachsection.Werunsimulationsovereachsectiontodeterminearatebywhichagentsexited.Toconnectsections,werepresentthebuildingasagraph,therebyposinganetworkflowproblem.Thestrongdualitypropertyidentifiesbottleneckedgesinthegraph.Simulatingblockedpassagesornewsecretexitsissimplyremovaloradditionofedgestothegraph.Bottleneckidentificationisourhighestpriorityforpublicsafety.OurmodelpredictsthatanevacuationplanusingallfourpublicexitscouldevacuatetheLouvrein24minutes.Furthermore,whilemanybottle-neckssurroundthePyramidentrance,theentranceitselfisnotabottleneck.ThispropertyofthePyramidiscrucialinemergencies,sinceitallowsac-cessforemergencypersonnel.Additionally,securingthePassageRichelieuiscriticaltoevacuation,sinceitssafetyisdirectlylinkedtothePyramid’ssafety.Keepingtheseentrancesopenandusefulisimperativetobothspeedandsafetyofanevacuation.Ourmodelispowerfulduetoitsabilitytomodelindividualhumanbe-havior,followedbyanadaptableabstractionofbuilding-flowdynamics.Oneweaknessofourmodelisthatweconsiderworst-casescenarios,buttheirevacuationtimesareanupperboundforarealevacuation.TheUMAPJournal40(2–3)(2019)133–159.c!Copyright2019byCOMAP,Inc.Allrightsreserved.Permissiontomakedigitalorhardcopiesofpartorallofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnotice.Abstractingwithcreditispermitted,butcopyrightsforcomponentsofthisworkownedbyothersthanCOMAPmustbehonored.Tocopyotherwise,torepublish,topostonservers,ortoredistributetolistsrequirespriorpermissionfromCOMAP.
COMAP,Inc.TheUMAPJournal40:2July17,201910:04p.m.D1924801.texpage136136TheUMAPJournal40.2–3(2019)RestatementoftheProblemWearetaskedwiththebroadproblemofdesigninganevacuationmodelfortheLouvrethatallowsexplorationofarangeofoptions.Ourprimarygoalsareto:determineameanstoassesstheefficiencyofagivenevacuationplan,developanoptimalevacuationplanwithoutcompromisingsafety,identifykeybottlenecksandotherobstaclestosafeandefficientevacu-ation,determinetheeffectofadditionalexitsorblockedroutesontheevacua-tion,andcommunicateaclearplanofimplementation.Secondarily,wearealsotoconsider:theeffectofthediversityofvisitors(language,grouping,disability)onevacuation;potentialbenefitsoftechnologyinaidingevacuation;deploymentroutesforemergencypersonnel;andadaptabilityofthemodeltootherbuildings.GeneralAssumptionsSelf-interest.Evacueeswillnotconsideragloballyoptimalsolutionforeveryonebutwillinsteadchoosealocally“greedy”solution.Naturalflow.Individualsleavebytheclosestexit,unlessdirectedotherwise.Adherencetoprocedure.Individualsfollowtheevacuationplanpro-videdbyLouvremanagement.Safetyoutside.Securingthesafetyofpeopleonceoutsideofthebuild-ingisoutsideofthescopeofourtask.Importanceofpanic.Increasingpaniccausessuboptimalorirrationalchoices.Elevatorsusedonlybyemergencypersonnelanddisabledpeople.Elevatorscanbedangerousinemergencysituations.Appropriatesignageandtechnologyinmultiplelanguages.ManyoftheLouvre’scurrentsignageisnotinFrenchbutrathercontainsuniversally-comprehensiblesymbolicinstructions.Moreover,softwarepackagesandphoneappsgivingevacuationdirectionsareeasilywrittenfordifferentlanguages.
COMAP,Inc.TheUMAPJournal40:2July17,201910:04p.m.D1924801.texpage137TimetoLeavetheLouvre137Introduction:DefinitionsandRoadmapAnevacuationplanisacollectionofpathingproceduresforevacuees,conditionalonthelocationandstateofeachevacuee.Thesimplestevacua-tionplanwouldadhereto“naturalflow,”inwhichevacueesmovetowardsthenearestexit.Tomeasuretheefficiencyofeachevacuationplan,wecouldestimatethetimetofullyemptythebuilding.However,thismeasureissomewhatna¨ıve,sinceitdiscountssafetyandishighlydependentoninitialcondi-tions.Forexample,withunusuallymanyvisitorsclusteredaroundtheMonaLisa,attemptingtofunnelallofthemthroughoneexitcouldresultinovercrowding,trampling,andmobpanicrisks.Asanalternative,weconsiderthemaximumexitrateor,mathematically,themaximumofthetimederivativeofexitingevacuees.Thiswouldseemstobeanidenticalmeasure,sinceadecreaseintotaltimewouldmeananin-creaseinaverageexitrate.However,theexitratereachesapeaksometimeduringthemiddleofevacuation,asinFigure1.Figure1.Exitedevacueesvs.timeelapsed.OptimizingformaximumexitrateoptimizesthethroughputofevacueesthroughtheLouvreratherthantheminimumtotaltimetoevacuate.Thevalueistwofold:IftheLouvreisathighoccupancy,averageexitratesshouldapproachmaximumexitrates.IftheLouvreisatlowoccupancy,higherthroughputshoulddecrease
COMAP,Inc.TheUMAPJournal40:2July17,201910:04p.m.D1924801.texpage138138TheUMAPJournal40.2–3(2019)crowdingrisks.Asaresult,maximizingthroughputisdirectlycorrelatedwithmaximizingpublicsafety.ModelingRoadmapWeimplementatwo-stagemodel:Thefirststageusescomputationalagent-basedmodelingtounderstandlocalevacueeflowdynamicswithinsectionsoftheLouvre.Thesecondstagecombinesinformationfromthesectionsintoaflownetworkforwhichwecanassessandoptimizeevacuationplans.Toclarify,aroadmapforourmodelis:PartitioneachflooroftheLouvreintosmallersubsections.Developacomputationalagent-basedmodeltostudylocalevacuationphenomenaandevacueeflowforeachsubsection.Developaglobalnetworkthatmodelseachsubsectionasanode,pas-sagewaysasedges,andevacueeflowasweights.Applygraphalgorithmstomaximizeevacueeflowandpredicttheeffectofaddingorremovingedges.Interpretresultsintoreal-worldtermsandusefulpolicysuggestions.PartI:TheLocalSectionModelPartitioningSectionsTheLouvreconsistsofnestedgallerylayouts,severalaccesspointstootherfloors,andmultipleexitpoints[LouvreMuseum2016].Bypartition-ingthemuseumintosmaller,less-complexsubsectionstomodelindividu-ally,wereducecomplexity.Wesplittingeachfloorintothefivesubsections(Figure2)andlabelthesectionsAtoE(forexample,thebottom-leftsectiononthegroundfloorislabeled“groundfloorA”).TheNapoleonHall,denoted“NapoleonP,”hasthePyramidentrance(asshownbyFigure3),whichistheonlyrelevantsubsectiononthatfloor.DevelopmentWedevelopourlocalevacuationmodel(theLocalSectionModel)inNetLogo,agent-basedmodelingsoftware.Themainideaofagent-based
COMAP,Inc.TheUMAPJournal40:2July17,201910:04p.m.D1924801.texpage139TimetoLeavetheLouvre139Figure2.EachflooroftheLouvreissplitintofivesubsections,labeledAtoE,startingfromthebottomandmovingcounter-clockwise.Figure3.TheNapoleonHallcontainsaPyramidalsubsectionuniquetoitsfloor.
COMAP,Inc.TheUMAPJournal40:2July17,201910:04p.m.D1924801.texpage140140TheUMAPJournal40.2–3(2019)modelingisthatagentsaresingleunitswithspecific,well-definedgoals.Whileanindividualagent’sbehavioristypicallysimple,thecomplexbe-haviorofasystemofagentsisusuallymorethanthesumofitsparts.Sinceeachpersonactssolelyintheirownself-interesttoevacuate,anagent-basedmodelishighlyapplicable.Figure4showstheresultantinterfaceinNetLogo,whichiseasytouseandinterpret.ThebottomofthefigureshowssectiongroundfloorDwithitscomplexgallerysystem.Thewhiteagentsactingonagridofgreen(passable)andblack(impassable)patchesrepresentevacueesfindingtheirwaythroughgalleries.Bluepatches(suchastheverticallinesegmentatextremeupperright)represententrywaysthroughwhichevacueesenter,andredpatches(suchastheverticallinesegmentatextremeupperleft)representexitsthroughwhichevacueesleave.ThespecificbehaviorlogicoftheagentsisshowninFigure5.Weequipeachagentwithavariablepanicattributeandfixedspeedattribute.Fur-therinformationonthespeedattributeiscontainedinthefollowingsec-tion,whilethepanicattributeisexplainedhere.