西工大数模公园内道路设计问题 16页

FormversusFunction:WalkingtheLineAmrishDeshmukh,NikoStahl,TarunChitraNovember18,20081 AbstractTheArtsquadisaspacethatissubjecttoseveralcompetinginterests.Itsdesignisexpectedtooffertheopportunityforanindividualtomoveconvenientlyfromoneendtoanother,tokeepgeneralmaintenancecostsfeasibleandtoallowforactivitiesrangingfromlecturestosnowballfights.Thispaperproposesamathematicalmodel,whichprovidesawayofintelligentlydesigningthepathnetworkofthequad.Thecenterpieceofourmodelisacostfunction,whichevaluatesthefeasibilityofagivenpathconfiguration.Toexplorethesetoffeasiblepathconfigurationwewroteanalgorithmthatrandomlygeneratessamplesofthisset.WethenimprovedonthissearchbyconstructinganoptimizationalgorithminspiredbyMarkovchainMonteCarlomethods.Webelievethisimprovedsearchhasfoundalocalminimumpathconfiguration,asitappearsstableunderperturbation.2 ContentsIIIIIIIVVVIProblemStatementTheArtsQuadrangleasaGraphTheLengthofaPathUnofficialPathInducedbyHumanBehaviorTheCostFunctionAssumptions:446789VIIVIIIIXAlgorithmsforFindingOptimalPathConfigurationsResults:RecommendedSolution91011XXIFutureWorkBibliography31516 PartIProblemStatementThetaskistoredesigntheArtsquadwalkwaysusingamathematicalmodelthatwillhelpusdetermineapreferreddesign.Beyondthegeneralfactthatminimizingthetotallengthofthepathsandmaximizingtheareasofcontiguouslawnsarepreferable,weareaskedtoconsiderthefollowingcriteria:·Pathmaintenancecosts·Landscapingcosts·Pedestriantrafficandbehavior·Thecreationofunofficialpathsanditsimpactonthelawn·ThegeneralappealofthequadToimplementthesecriteriainourmodel,weareprovidedwiththefollowingprinciples:·Thepathmaintenancecostisproportionatetothetotalpathlength.·Thelandscapingcostdependsonthenumberofcontiguouslawns,thecreationofunofficialpaths(asaresultofpedestriansleavingthepavedpathstoarriveattheirdestinationmorequickly)andthegeometryofcontiguouslawn.·Ifthepathbetweentwopointsis15%longerthanthestraightlineconnectingthepoints,apedestrianwillleavethepathandcutacrossthequad.·Anaveragepedestrianmightleavethepathifitimpliessavingmorethan10%ofthetotallengththepath.PartIITheArtsQuadrangleasaGraphGraphtheoryhasbeenanimportanttoolinexploringproblemswhichrangefromdeterminingtheneuralnetworkofnematodeC.eleganstofindingthecauseoffailureinelectricalpowergrids1.Byframingourwalkwaydesignprobleminthelanguageofgraphs,wecanreadilyextractthekeyrelationshipsbetweenstructureandfunction.WedescribetheArtsquadrangle(herebyreferredtoastheArtsquadorsimplyquad)asagraphof10nodes,whichrepresentthemostcommonpointsofentryandexittothequad(seefigure1below).1See[1]4 Figure1:CornellArtsQuadLetthesetofnodesbeA={x|x∈{1,2,...,10}}.Nowwecandefineapathtobeanorderedpair(a,b)andthesetofallpathsastherelationR={(a,b)|a,b∈A,a=b}(1)sinceeverypairofdistinctnodeswilldefinealinesegment,orone-waypath,intheplane.ThenthesetofallpossibleconfigurationsofpathsisgivenbythepowersetP(R).Thissethas290elements(thecardinalityofapowersetofasetwith90elements)Thispresentsanoverwhelmingsetofpossibilities,butfortunatelytherearethreeconstraints,whichweimposedtomakeoursetlessunwieldy.Wewillonlymodel:1.Non-directedgraph:Currentlythespace(1,3)isdistinctfromthepath(3,1).Wefindthistobeunreasonableaspedestrianpathsareveryrarely“one-way”2.Connectedgraph:Aestheticallyandfunctionallyitmakeslittlesensetoallowabuildingtobesurroundedcompletelybygrass.Furthermore,wepickedthetennodesbecauseweconsideredthemtobeessentialcirculationpointsofthequad.Therefore,havingoneofthemdisconnectedfromthenetworkwouldbeunreasonable3.Graphsincludingtheperimeter:Thisisagainchoseninlinewithouropinionsonaestheticsandutility.Whilepedestriansarelikelytoacceptlongerdistancesthanastraightlinetoremainontheofficialpath,itseemsunlikelythatapersongoingfromAtoBwillabidewithapaththatstrictlyincreasesthedistancetoBbeforeallowingthepedestriantoactuallyapproachB(seefigure2below).5 Figure2:Inthefirstgraph,weseethattravellingfrom(0,1)→(1,0)neverincreasesthedistancefrom(1,0),whereasinthesecondgraph,goingfrom(0,0)→(1,0)incursthiscostOncewehaveattainedpotentiallyoptimalconfigurationsthatsatisfythesethreeconstraints,wewillremovetheconstraintsandshowthatthereislittleornoimprovementtobegainedbyrelaxingthem.Noticethatthethirdconditionimpliesthesecondinthegeometrythatwehavechosen,whereallnodesareplacedontheperimeter.However,inageometrywherenodesintheinteriorareconsideredaswell,thisimplicationdoesnothold.Therefore,wehavemadebothconstraintsexplicit.IfwetakeB⊆P(R)tobethesetofallpossibleconfigurationsofpaths,whichdonotsatisfy(1)−(3),ourmodelconsidersthesetP(R)B.Havingthusdefinethesetofpossibleconfigurationsofpathswecanusesoursite-specificgeometricinformationtodescribetheimportantfeaturesofagivenconfigurationofpaths.PartIIITheLengthofaPathAgivenconfigurationofpaths(a∈P(R)B)andthelocationofitsnodes(seeTable1below)definesasetoflinesegmentsrepresentingpathsintheplane.Table1:LocationsoftheNodesintheCartesianPlaneEmployingsimplegeometrywecandetermineli,thelengthoftheithpathasafunctionofthethpathpiwhichisgivenbythecoordinatesofthetwonodesitconnects.Thereforewehave:li=ip2i=||p||2(2)a={p1,p2,...,pn}pi=(a,b)(3)wherea,barethenumbersofnodeswithcoordinates(a1,a2),(b1,b2)respectively.Thetotallengthofthepathsisthengivenbysummationoveri:L=6ili(4)Node12345678910Location(0,0)(0,3)(0,9)(0,15)(0,18)(5.6,18)(7,18)(7,14)(7,6)(7,0)SWMorrillHallMcGrawHallWhiteHallTjadenHallSibleyHallNELincolnHallGSHallSEi Bydefinition,wecandefineametriconthegraphby:||L||=infL=infiiili(5)whereListheminimallengthofallthepaths.PartIVUnofficialPathInducedbyHumanBehaviorFunctionalityisakeyaspectofanydesign.Tomeasurethefunctionalityofapathconfiguration,wehavetobeabletomodelthebehaviorofthepeoplewhowilluseit.Afailuretobefunctionalresultsinbothawasteofasphaltandatraffic-damagedlawn.Theproblemstatementprovidesuswiththefollowinginformationtomodelhumanbehavior:·Ifthepathbetweentwopointsis15%longerthanthestraightlineconnectingthepoints,apedestrianwillleavethepathandcutacrossthequad·Anaveragepedestrianmightleavethepathifitimpliessavingmorethan10%ofthetotallengthofthepathSoifagivenconfigurationofpathsistoosparse2,peoplewillchoosetosavetimeandcutacrossthelawn.Noticethatthehumanbehaviorwearemodelingconsidersthequadasaspacethatistobetraversedasquicklyaspossible.Inotherwords,weareignoringtrafficfrompeoplewhogotopointsonthequad,suchassunbathersorfrisbeeplayers.Thereforewecangeneralizeourassumptionsofhumanbehaviortobethefollowing:·Individualsviewtimespentwalkingasadetrimenttotheirutility.Theytrytocrossthequadasquicklyaspossible·Individualsdonotwishtodeviatetoogreatlyfromsociologicalnorms.Therefore,weareabletoassumethattherewillbeacertainpropensitytouseanofficialpatheventhoughthedistanceitentailsislongerthanastraightlinepathtothedestination.Thesecondconditionisdiscussedinmodelsofhumantrailformation3inwhichindividualsdecidehowtochooseapathbasedonthecollectivebehavior.Studentswanttogetwheretheyaregoing,yettheymaytemperthisdesireifitmakesthemthelone-maninthemiddleofthefield.Soanindividual’sbehaviorwillbeafunctionofthepathconfiguration.Weinterpret“might,”asstatedintheinformationgivenintheproblemstatement,asa50%chancethatanindividualwillleavethemapfinally,ifapathcoincideswiththestraightlinebetweentwonodes,noutilitymaximizerwouldhaveincentivetoleavethepath.Wefitthesethreedatapointswithalogisticcurvewhichthendescribesthepropensityofanindividualtocutasafunctionoftherelativecostincurredbystayingonanofficialpath.Theamountofdamagedonetothegrasswillthenbegivenbymultiplyingthispropensitytocutbythelengthofthestraightlinepath.Wedeterminez,therelativeincurredcostofremainingonanofficialpathbycomparingDijkstra’salgorithm4ontwographs:anyconfigurationofpathsbeingconsideredandthepath2Asparsegraphisagraphinwhicheverysubgraphhasanumberofedgesthatisfarlessthanthemaximalnumberofedgesinthegraph,[2]3See[5],[6],[7]4Analgorithmthatsolvesthesingle-sourceshortestpathproblem(see[2],[3]).Thevariantthatweusedinparticularis[9]7 configurationinwhichallnodesareconnectedtoallothernodes,thecompletegraph.Oncezisdeterminedforeverypairofnodes,thelogisticfunctionggivesthepropensityofanindividualtoleavetheofficialpathforeachofthesepairs.ThelengthofcutpathscanagainbeobtainedviaDijkstra’salgorithm.Finallythetotaldamage,Csubcutbypath-desertingtrafficcanbeobtainedbytakingtheproductofthepropensitytocut,g(z),withthelengthofthecutpath,summedoverallpaths.PartVTheCostFunctionWeproceedbyidentifyingthetwomaincostsofaconfigurationofpaths:1.Maintenancecostsforpath2.LandscapingcostsfortreatingunofficialpathsThustheoverallcostofadesignbecomesafunctionofbothformandfunctionality.Ourfirstcostpenalizessimplypavingtheentirequad,whichissuggestedbytheproblemstatement.Thesecondpreventsusfromleavingitasanunadulteratedpasture.ForsimplicitywedefinethecostfunctionC,tobeasimplelinearcombinationofthesetwocosts:C(L,Csubcut)=L+kCsubcut(6)wherekistherelativeperlengthcostofmaintainingasphalttorevivingtraffickedgrass.ThusgivenaconfigurationofpathsontheArtsquadrangle,wecanevaluateitscost.Wedefineanoptimalconfigurationasonethatwillminimizethecostinadditiontosatisfyingthefollowingconstraints:1.Theconfigurationshouldnotcallforpathswhichintersectatreeorstatue2.Theconfigurationwillnotresultinlawnswithsharpanglesorwildgeometries3.Theconfigurationwillnotmakethequadoverlyfragmented,aswewanttopreventahighnumberofcontiguouslawnsOptimally,theseadditionalconstraintswouldbeimposedonthedomainofourcostfunctionP(A)Bandthusreducethespaceoverwhichwemustsearchforanoptimumsolution.However,webelievethattheseconstraintswillnotsubstantiallyreducethesetofpossiblepathsbecause:·Weareconsideringafinitenumberofpossiblepathsandarenotattemptingtospanthequadwithrandomly-generatedpaths.Ifthepathbetweentwoofourfixednodesintesectswithatree,wecansimplymoveoneofthenodes·Thecompletepathconfigurationdoesnotresultinanoverwhelminggeometryorextremelysharpangles·ThecompletepathconfigurationdoesnotfragmentthequadtoanunreasonableamountThusinordertosavetimerequiredforcomputingthenewdomain,weimposethattheoptimalsolutionwefindmustsatisfytheaboveconstaints,post-processing.Ifitdoesnot,weselectthenextbestsolutioninoursetofoptimumsolutions5thatsatisfiestheconstraints.5Sincewearerandomizingthepathswearetaking,wecanalwaysmakethesolutionsetequaltotheoptimalsolution±kσ,whereσisthestandarddeviationoftheprobabilitydistributionweimposeonourMarkovchains.See[3]8 Itispossiblethatonemaywanttoincludetheseciteriaaspartofthecostfunction.Whileitispossibletodeterminethenumberofcontiguousregionsdeterminedandtheanglesofthoseregions,itisdifficulttosaywhatis“toosharp”or“toofragmented.”Nonetheless,ourmethodislargelycompatiblewithmodifyingthecostfunctionifanobjectivemeasureoftheseconstraintswasknown.Thoughwehavesignificantlyreducedourdomainofconsideration,itisstillquitelarge.Inadditionourcostfunctionisexpensivetoevaluateasitisanonlinearfunctionof90variables(10nodes·10nodes=100path-10(pathstoself)=90).AsaresultwecannothopetoperformanoptimizationanalyticallyorviamethodicallyexploringallofP(R)B.WethereforeturntotwoalternativemethodsoutlineinthesectionVIII.PartVIAssumptions:PartVIIAlgorithmsforFindingOptimalPathConfigurationsWeattempttofindouroptimalsolutionviatwomethods:·BruteForceSampling-generated30,000randomconfigurationsfromwhichweselectthelowestcostsolutionastheoptimum.Therandomconfigurationsweregeneratedfromthesetofallpossiblepairsofnodes(i.e.R)usingtherand()functioninMatlab6·APrimitiveVersionofaMarkovChain-MonteCarlo(MCMC)method6WeacknowledgetheinaccuraciesintherandomnumbergeneratorinMatlab;however,duetotimerestrictionswewereforcedtousethebuilt-inrandomnumbergenerator.Luckily,swappingouttheMatlabrandomnumbergeneratorforanotherrandomnumbergeneratorthatiscodedinMatlabisasimpleexercise9AssumptionImplicationJustificationThetennodesontheperimeterofferareasonabledescriptionofthegeneraltraversalsofthequadWeconfineoursearchfortheoptimumtopathconfigurations,whichconnectthesetenpoints.Wechosethepointsstrategicallyinfrontoftheentriesofbuildingpositionsandatthecornersofthequad.ApersongoingfromAtoBwillnotabidewithapaththatstrictlyincreasesthedistancetoBbeforeallowingthepedestriantoactuallyapproachBAllconfigurationsincludetheperimeterIntuitionPeopletryingtotraversethequadformoneedgetoanotherWedonotconsidernodesintheinteriorofthequadThemajorityofpeoplecrossthequadTheword“might”asstatedintheproblemstatementisassumedtomeana50%chancethatanindividualwillleavethepathDefinequantitativelyusingtheLogisticfunctionOrganizationssuchastheIPCCusesimilarinterpretationsThecostfunction,C,isasimplelinearcombinationofthepathmaintenancecostandthelandscapemaintenancecostOurdefinitionofthecostfunction.Simplicity –Inspiredbymuchmorecarefulandeffectiveoptimizationmethods,wedevelopedaprim-itiveMCMCmethodwhichmimicsseveralkeyfeaturesofthesealgorithms.Webeginbyrandomlyselectinganinitialconfigurationforthequad’swalkways.Fromthiscurrentstatewerandomlyperturb(removeoradd)arandomnumberofedges(between1and5).Thecostofthisnewstateisthenevaluatedandcomparedtothecurrentstate.Ifthenewstateissuperiortothecurrentstate,itreplacesthecurrentstate.Ifitisaninferiorstate,itwillreplacethecurrentstatewitha15%probabilityandisdiscardedotherwise.Again,asinthebruteforcesampling,werestrictoursearchdomaintoP(R)B.PartVIIIResults:Wefind,asexpected,thatourprimitiveMCMCsearchyieldsabetterminimalcostsolutionthanthosefoundinthebruteforceapproach.AlongwiththetwosolutionsobtainedviatheMCMCapproachweconsiderthe10bestsolutionsfromthebruteforcesearch.UsingasimilarprocedureasintheMCMCalgorithm,werandomlyperturbedeachofthesesolutionsbyoneedgemultipletimes.Ifinanysingleperturbtionwefindthatthecostimproves,thenewstateisrecorded.Asexpected,thesolutionsthatwerefoundasaresultofthebruteforcealgorithmwerenotallstableunderperturbation.Fourofthese10solutionswereimprovedandofthesenonehadacostreductiongreaterthan15%.Encouragingly,neitherofthetworesultsobtainedfromtheprimitiveMCMCsearchwereimprovedin1000randomperturbations.Thisindicatesthatthesesolutionsmaybealocalminimum,ifnotaglobalminimumofthecostfunctioninthedomainweconsider(SeeFigure3below).FromthesetwosolutionswechoseonetorecommendbasedonwhichsolutionbestsatisfiedthesubjectiveconstraintsdiscussedonpartII.Intheabsenceofanobjectivewaytoevaluateasolutionbasedonthesecriteriaaspartofthecostfunctionwebelievethatthismethodofdemocraticvotingbytheconcernedpartiesisthemostreasonablealternative.10 Figure3:12optimalsolutions;thefirst10depictthesolutionsforthebruteforcemethod,whereasthelasttwodepictsolutionsfortheMCMCmethod.Thecostisthetitleofeachgraph.Note:Wechosethesecondtolastgraphasouroptimalsolution11 PartIXRecommendedSolutionThenetworkofpathsgivenbelowwouldmostlikelyminimizethecostsassociatedwithpathandlawnmaintenance:Figure4:Oursolution,left,andthecurrentArtsquadWealsofind,inlinewithourpredictions,thatthesolutiondoesnotintersectanytreesofstatues.Thisisdepictedbelowinfigure5:12 Figure5:Ourplaninred,whichdoesnotintersectwithanytreesorstatuesUsingourmodelwecanthendeterminetowhatextentthesepathswillleadtounofficialtrailformation.Wefindthattheseformationsareminimal,andthisisexpressedinthefollowingfigurewhichdisplaysthenewquadaftersignificantuse.13 Figure6:Ouroptimalsolution,withthe(estimated)unofficial,treadedpathsdrawnin.Theiropacityisproportionaltothepropensitytocut,asdefinedinsection2Ourfinalreccomendationisfortheplacementofspecialhardierseeds.Wereccomendthattheseseedsbeusedinthehighlightedregionswhereunofficialpathwaysaremostdetrimentalandwherelargecontinuousareaswillattractfrisbeeplayersandthelike.Thisisportrayedbelow:14 Figure7:OurrecommendationforwherethemoreexpensiveseedingshouldbeplacedPartXFutureWorkTheflexibilityofourapproachgivesrisetoacopiousnumberoffuturedirectionsinwhichourmethodcouldbeextended.Herewecatalogseveralpossibilities:1.Developorfindaproperoptimizationroutine:Clearlybeforeproceedingtocomplicatetheabovescheme,itwouldbebesttohaveanappropriatemethodtoperformtheoptimizationcrucialtoouranalysis.2.Addadditionalnodes:Insomesensewehavedrasticallylimitedthespaceofpossiblesolutionsbydemandingthatallnodesofourgraphliveontheperimeterofthegraph.Inadditiontosimplyconsideringaddingalargesetofinternalandperimeternodes,wenotethatcertainspecialadditions,suchasSteinerpoints,mayresultinlargecostreduction.3.Inthisanalysiswehavedividedtheimportantfeaturesofthesystemintotwocategories,conditionsandconstraints.Oftenforthesakeofavoidingsubjectivecomparisions,wehavede-scribedfeaturessuchasaestheticappealorangularityofthequadasconstraints.Whilewebelieveobjectivelydeterminingtherelativeimportanceofsuchcharacteristicswouldbedifficult,thereisnoprohibitioninexpandingtheconsiderationsofourcostfunction.Onceestablishedthe15 optimizationwithrespecttoacostfunctioncouldproceedasbefore.4.Thecurrentdescriptionofhumanbehaviorcontainsperhapsthemostsimplificationsmadebyourmodel.Therealreadyexistseveralmodels7whichquantitativelyreflectthecollectivebehaviorofhumanswithrespecttotrailfomation.Employingthesemodelswouldresultinabetterestimateofthemaintenancecosts.5.Wehaveassumedthattheperimeterofthequadshouldnecessarilyhavepaths.Animportanttestofthisassumptionistorelaxitandperturbanyoptimalsolutionstoseeiftherelaxationwillresultinamorecosteffectivesolution.6.Finally,wehaveassumedthatouroptimalsolutionwillhaveastraightlinegeometry.Theuseofcurvedwalkwaysmayprovidesignificantlylessexpensiveconfigurations.PartXIBibliography[1]Strogatz,S.H.."ExploringComplexNetworks."Nature438(2001):268-276.[2]Roberts,John,S..GraphTheoryandItsApplicationstoProblemsofSociety.SIAM,1987.[3]Gamerman,Dani.MarkovChainMonteCarlo:StochasticSimulationforBayesianInference.CRCPress,1997.[4]Gross,Jonathan,andYellen,Jay.GraphTheoryandItsApplications.BocaRaton:CRCPress,1999.[5]Helbing,Dirk,Schweitzer,Frank,Keltsch,Joachim,andMolnar,Peter."ActiveWalkerModelfortheFormationofHumanandAnimalTrailSystems."PhysicalReview.56(1997):2527-2539.[6]Helbing,Dirk,Keltsch,Joachim,andMolnar,Peter."ModellingtheEvolutionofHumanTrailSystems."Nature388(1997):47-50.[7]Helbing,D.QuantitativeSociodynamics.StochasticMethodsandSocialInteractionPro-cesses(KluwerAcademic,Dordrecht,1995).[8]Dynkin,Eugene.MarkovProcess:VolumeI,1sted.Berlin:Springer-Verlag,1965.[9]Kirk,Joesph.“Djikstra’sAlgorithm.”May2008,MatlabCentral.[10]Holz,Sebastian.“CurveIntersection.”November2005,MatlabCentral.7See[5],[6],[7]16