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

FormversusFunction:WalkingtheLineAmrishDeshmukh,NikoStahl,TarunChitraNovember18,2008TheArtsquadisaspacethatissubjecttoseveralcompetinginterests.Itsdesignisexpectedtooffertheopportunityforanindividualtomoveconvenientlyfromoneendtoanother,tokeepgeneralmaintenancecostsfeasibleandtoallowforactivitiesrangingfromlecturestosnowballfights.Thispaperproposesamathematicalmodel,whichprovidesawayofintelligentlydesigningthepathnetworkofthequad.Thecenterpieceofourmodelisacostfunction,whichevaluatesthefeasibilityofagivenpathconfiguration.Toexplorethesetoffeasiblepathconfigurationwewroteanalgorithmthatrandomlygeneratessamplesofthisset.WethenimprovedonthissearchbyconstructinganoptimizationalgorithminspiredbyMarkovchainMonteCarlomethods.Webelievethisimprovedsearchhasfoundalocalminimumpathconfiguration,asitappearsstableunderperturbation.IProblemStatement4IITheArtsQuadrangleasaGraph4IIITheLengthofaPath6IVUnofficialPathInducedbyHumanBehavior7VTheCostFunction8VIAssumptions:9VIIAlgorithmsforFindingOptimalPathConfigurations9VIIIResults:10IXRecommendedSolution11XFutureWork15XIBibliography16PartIProblemStatementThetaskistoredesigntheArtsquadwalkwaysusingamathematicalmodelthatwillhelpusdetermineapreferreddesign.Beyondthegeneralfactthatminimizingthetotallengthofthepathsandmaximizingtheareasofcontiguouslawnsarepreferable,weareaskedtoconsiderthefollowingcriteria:•Pathmaintenancecosts•Landscapingcosts•Pedestriantrafficandbehavior•Thecreationofunofficialpathsanditsimpactonthelawn•ThegeneralappealofthequadToimplementthesecriteriainourmodel,weareprovidedwiththefollowingprinciples:•Thepathmaintenancecostisproportionatetothetotalpathlength.•Thelandscapingcostdependsonthenumberofcontiguouslawns,thecreationofunofficialpaths(asaresultofpedestriansleavingthepavedpathstoarriveattheirdestinationmorequicklyandthegeometryofcontiguouslawn.•Ifthepathbetweentwopointsis15%longerthanthestraightlineconnectingthepoints,apedestrianwillleavethepathandcutacrossthequad.•Anaveragepedestrianmightleavethepathifitimpliessavingmorethan10%ofthetotallengththepath.PartIITheArtsQuadrangleasaGraphGraphtheoryhasbeenanimportanttoolinexploringproblemswhichrangefromdeterminingtheneuralnetworkofnematodeC.eleganstofindingthecauseoffailureinelectricalpowergrids1.Byframingourwalkwaydesignprobleminthelanguageofgraphs,wecanreadilyextractthekeyrelationshipsbetweenstructureandfunction.WedescribetheArtsquadrangle(herebyreferredtoastheArtsquadorsimplyquadasagraphof10nodes,whichrepresentthemostcommonpointsofentryandexittothequad(seefigure1below.1See[1]Figure1:CornellArtsQuadLetthesetofnodesbeA={x|x∈{1,2,...,10}}.Nowwecandefineapathtobeanorderedpair(a,bandthesetofallpathsastherelationR={(a,b|a,b∈A,a=b}(1sinceeverypairofdistinctnodeswilldefinealinesegment,orone-waypath,intheplane.ThenthesetofallpossibleconfigurationsofpathsisgivenbythepowersetP(R.Thissethas290elements(thecardinalityofapowersetofasetwith90elementsThispresentsanoverwhelmingsetofpossibilities,butfortunatelytherearethreeconstraints,whichweimposedtomakeoursetlessunwieldy.Wewillonlymodel:1.Non-directedgraph:Currentlythespace(1,3isdistinctfromthepath(3,1.Wefindthistobeunreasonableaspedestrianpathsareveryrarely“one-way”2.Connectedgraph:Aestheticallyandfunctionallyitmakeslittlesensetoallowabuildingtobesurroundedcompletelybygrass.Furthermore,wepickedthetennodesbecauseweconsideredthemtobeessentialcirculationpointsofthequad.Therefore,havingoneofthemdisconnectedfromthenetworkwouldbeunreasonable3.Thisisagainchoseninlinewithouropinionsonaestheticsandutility.Whilepedestriansarelikelytoacceptlongerdistancesthanastraightlinetoremainontheofficialpath,itseemsunlikelythatapersongoingfromAtoBwillabidewithapaththatstrictlyincreasesthedistancetoBbeforeallowingthepedestriantoactuallyapproachB(seefigure2below.Figure2:Inthefirstgraph,weseethattravellingfrom(0,1→(1,0neverincreasesthedistancefrom(1,0,whereasinthesecondgraph,goingfrom(0,0→(1,0incursthiscostOncewehaveattainedpotentiallyoptimalconfigurationsthatsatisfythesethreeconstraints,wewillremovetheconstraintsandshowthatthereislittleornoimprovementtobegainedbyrelaxingthem.Noticethatthethirdconditionimpliesthesecondinthegeometrythatwehavechosen,whereallnodesareplacedontheperimeter.However,inageometrywherenodesintheinteriorareconsideredaswell,thisimplicationdoesnothold.Therefore,wehavemadebothconstraintsexplicit.IfwetakeB⊆P(Rtobethesetofallpossibleconfigurationsofpaths,whichdonotsatisfy(1−(3,ourmodelconsidersthesetP(R\B.Havingthusdefinethesetofpossibleconfigurationsofpathswecanusesoursite-specificgeometricinformationtodescribetheimportantfeaturesofagivenconfigurationofpaths.PartIIITheLengthofaPathAgivenconfigurationofpaths(a∈P(R\Bandthelocationofitsnodes(seeTable1belowdefinesasetoflinesegmentsrepresentingpathsintheplane.Node12345678910Location(0,0(0,3(0,9(0,15(0,18(5.6,18(7,18(7,14(7,6(7,0SWMorrillHallMcGrawHallWhiteHallTjadenHallSibleyHallNELincolnHallGSHallSEEmployingsimplegeometrywecandetermineli,thelengthoftheithpathasafunctionoftheithpathpiwhichisgivenbythecoordinatesofthetwonodesitconnects.Thereforewehave:li=ip2i=||p||2(2a={p1,p2,...,pn}pi=(a,b(3wherea,barethenumbersofnodeswithcoordinates(a1,a2,(b1,b2respectively.Thetotallengthofthepathsisthengivenbysummationoveri:L=ili(4Bydefinition,wecandefineametriconthegraphby:||L||=infiL=infiili(5whereListheminimallengthofallthepaths.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]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(6wherekistherelativeperlengthcostofmaintainingasphalttorevivingtraffickedgrass.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]Itispossiblethatonemaywanttoincludetheseciteriaaspartofthecostfunction.Whileitispossibletodeterminethenumberofcontiguousregionsdeterminedandtheanglesofthoseregions,itisdifficulttosaywhatis“toosharp”or“toofragmented.”Nonetheless,ourmethodislargelycompatiblewithmodifyingthecostfunctionifanobjectivemeasureoftheseconstraintswasknown.Thoughwehavesignificantlyreducedourdomainofconsideration,itisstillquitelarge.Inadditionourcostfunctionisexpensivetoevaluateasitisanonlinearfunctionof90variables(10nodes·10nodes=100path-10(pathstoself=90.AsaresultwecannothopetoperformanoptimizationanalyticallyorviamethodicallyexploringallofP(R\B.WethereforeturntotwoalternativemethodsoutlineinthesectionVIII.PartVIAssumptions:reasonabledescriptionofthegeneraltraversalsofthequadfortheoptimumtopathconfigurations,whichconnectthesetenpoints.strategicallyinfrontoftheentriesofbuildingpositionsandatthecornersofthequad.abidewithapaththatstrictlyincreasesthedistancetoBbeforeallowingthepedestriantoactuallyapproachBincludetheperimeteroneedgetoanothernodesintheinteriorofthequadcrossthequadproblemstatementisassumedtomeana50%chancethatanindividualwillleavethepathusingtheLogisticfunctiontheIPCCusesimilarinterpretationscombinationofthepathmaintenancecostandthelandscapemaintenancecostcostfunction.PartVIIAlgorithmsforFindingOptimalPathConfigurationsWeattempttofindouroptimalsolutionviatwomethods:•BruteForceSampling-generated30,000randomconfigurationsfromwhichweselectthelowestcostsolutionastheoptimum.Therandomconfigurationsweregeneratedfromthesetofallpossiblepairsofnodes(i.e.Rusingtherand(functioninMatlab6•APrimitiveVersionofaMarkovChain-MonteCarlo(MCMCmethod6WeacknowledgetheinaccuraciesintherandomnumbergeneratorinMatlab;however,duetotimerestrictionswewereforcedtousethebuilt-inrandomnumbergenerator.Luckily,swappingouttheMatlabrandomnumbergeneratorforanotherrandomnumbergeneratorthatiscodedinMatlabisasimpleexercise–Inspiredbymuchmorecarefulandeffectiveoptimizationmethods,wedevelopedaprim-itiveMCMCmethodwhichmimicsseveralkeyfeaturesofthesealgorithms.Webeginbyrandomlyselectinganinitialconfigurationforthequad’swalkways.Fromthiscurrentstatewerandomlyperturb(removeoraddarandomnumberofedges(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.Figure3:12optimalsolutions;thefirst10depictthesolutionsforthebruteforcemethod,whereasthelasttwodepictsolutionsfortheMCMCmethod.Thecostisthetitleofeachgraph.Note:WechosethesecondtolastgraphasouroptimalsolutionPartIXRecommendedSolutionThenetworkofpathsgivenbelowwouldmostlikelyminimizethecostsassociatedwithpathandlawnmaintenance:Figure4:Oursolution,left,andthecurrentArtsquadWealsofind,inlinewithourpredictions,thatthesolutiondoesnotintersectanytreesofstatues.Thisisdepictedbelowinfigure5:Figure5:Ourplaninred,whichdoesnotintersectwithanytreesorstatuesUsingourmodelwecanthendeterminetowhatextentthesepathswillleadtounofficialtrailformation.Wefindthattheseformationsareminimal,andthisisexpressedinthefollowingfigurewhichdisplaysthenewquadaftersignificantuse.Figure6:Ouroptimalsolution,withthe(estimatedunofficial,treadedpathsdrawnin.Theiropacityisproportionaltothepropensitytocut,asdefinedinsection2Ourfinalreccomendationisfortheplacementofspecialhardierseeds.Wereccomendthattheseseedsbeusedinthehighlightedregionswhereunofficialpathwaysaremostdetrimentalandwherelargecontinuousareaswillattractfrisbeeplayersandthelike.Thisisportrayedbelow:Figure7:OurrecommendationforwherethemoreexpensiveseedingshouldbeplacedPartXFutureWorkTheflexibilityofourapproachgivesrisetoacopiousnumberoffuturedirectionsinwhichourmethodcouldbeextended.Herewecatalogseveralpossibilities:1.Clearlybeforeproceedingtocomplicatetheabovescheme,itwouldbebesttohaveanappropriatemethodtoperformtheoptimizationcrucialtoouranalysis.2.Addadditionalnodes:Insomesensewehavedrasticallylimitedthespaceofpossiblesolutionsbydemandingthatallnodesofourgraphliveontheperimeterofthegraph.Inadditiontosimplyconsideringaddingalargesetofinternalandperimeternodes,wenotethatcertainspecialadditions,suchasSteinerpoints,mayresultinlargecostreduction.3.Inthisanalysiswehavedividedtheimportantfeaturesofthesystemintotwocategories,conditionsandconstraints.Oftenforthesakeofavoidingsubjectivecomparisions,wehavede-scribedfeaturessuchasaestheticappealorangularityofthequadasconstraints.Whilewebelieveobjec