Glem den korteste rute gennem en by; Ny algoritme finder den smukkeste

Den måde, vi navigerer på i byer, er blevet revolutioneret i de sidste par år af fremkomsten af ​​GPS-kortlægningsprogrammer. Indtast din start- og slutplacering, og disse vil give dig den korteste rute fra A til B.

Det er normalt det bedste bud, når du kører, men at gå er en anden sag. Ofte vil fodgængere have den roligste eller smukkeste rute, men hvis de henvender sig til en kortapplikation, får de lidt hjælp.

Det kan ændre sig nu takket være arbejdet fra Daniele Quercia hos Yahoo Labs i Barcelona, ​​Spanien, og et par venner. Disse fyre har fundet ud af, hvordan man måler skønheden af ​​specifikke steder i byer og har derefter designet en algoritme, der automatisk vælger en rute mellem to steder på en måde, der maksimerer skønheden langs den. Målet med dette arbejde er automatisk at foreslå ruter, der ikke kun er korte, men også følelsesmæssigt behagelige, siger de.

Quercia og co begynder med at oprette en database med billeder af forskellige dele af Londons centrum taget fra Google Street View og Geograph, som begge har rimelig konsistente standarder for billeder. Derefter crowdsourcede de meninger om skønheden ved hver lokation ved hjælp af et websted, der hedder UrbanGems.org .

Hver besøgende på UrbanGems ser to fotografier og vælger det, der viser den smukkeste placering. Det giver holdet en crowdsourcet mening om skønheden ved hver lokation. De plotter derefter hver af disse steder og deres skønhedsscore på et kort, som de bruger til at give anvisninger.

Ideen her er, at brugeren indtaster et start- og slutsted, og en algoritme finder derefter den smukkeste rute, frem for den korteste. Det gør den ved at søge gennem alle mulige ruter, tilføje skønhedsscore for hver og vælge den, der rangerer højest.

Quercia og co siger, at disse ruter i gennemsnit viser sig at være blot 12 procent længere end de korteste ruter, hvilket gør dem til rimelige alternativer for en fodgænger.

For at finde ud af, om de ruter, der er valgt af algoritmen, virkelig er smukkere, rekrutterede Quercia og co 30 personer, der bor i London og kender området, til at vurdere de anbefalede stier. Og faktisk var de enige om, at ruterne valgt af algoritmen var smukkere end de korteste ruter.

Men det er kun begyndelsen. Crowdsourcing-udtalelser for alle mulige steder i en by er helt klart en tidskrævende og potentielt dyr forretning. Så Quercia og co har automatiseret denne proces ved hjælp af fotos fra Flickr og de data og tags, der er knyttet til dem.

De valgte omkring fem millioner billeder taget de samme steder som deres originale fotos og minede derefter de data, der var knyttet til dem, for at se, hvilke parametre der korrelerede med skønhed.

Faktorer, der viser sig at være en god indikator for skønhed, er ting som antallet af billeder taget af en bestemt scene og kommentarer forbundet med positive følelser. Så leder du efter steder på Flickr, der opfylder dette krav, burde det give en liste over smukke steder i enhver by.

Quercia og co testede denne idé i Boston for at finde smukke steder på Flickr og brugte derefter deres algoritme til at finde den smukkeste vej mellem to lokationer. De bad derefter 54 personer om at evaluere disse veje. Sikkert nok følte deltagerne generelt, at ruterne valgt af algoritmen var smukkere end de korteste dele.

Hvis du selv kender Boston eller London, kan du selv vurdere de ruter, som algoritmerne har valgt, ved at undersøge kortene i papiret.

Selvfølgelig er der potentielle problemer. Nogle steder er mindre attraktive på bestemte tidspunkter af dagen, for eksempel i myldretiden, hvor trafikken er tungere, eller om natten, hvor karakteren af ​​nogle dele af byen kan ændre sig dramatisk. Algoritmen kan ikke tage højde for disse forskelle

Ikke desto mindre er dette en interessant tilgang, der har potentialet til at ændre den erfaring, folk har i interaktion med byen. Det er ikke svært at forestille sig, at turistmyndigheder kan bruge en applikation som denne til at hjælpe besøgende med at opleve de bedste dele af en by til fods.

Quercia og co har sådan en plan. Deres næste mål er at bygge en mobilapp og teste den i naturen på tværs af forskellige byer i Europa og USA. Hold øje med det.

Ref: arxiv.org/abs/1407.1031 : Den korteste vej til lykke: Anbefaler smukke, rolige og glade ruter i byen

skjule