Developing an Open Pedestrian Landmark Navigation Model
40 views
Formal Metadata
Title 
Developing an Open Pedestrian Landmark Navigation Model

Title of Series  
Part Number 
52

Number of Parts 
193

Author 

License 
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. 
Identifiers 

Publisher 
FOSS4G, Open Source Geospatial Foundation (OSGeo)

Release Date 
2016

Language 
English

Content Metadata
Subject Area  
Abstract 
Today's publicly available pedestrian navigation systems still use paradigms developed for car navigation. In this paper, we present a novel landmarkbased pedestrian navigation model using open source tools and open data from OpenStreetMap, which is available globally and free of charge. This approach ensures that our landmark navigation model is widely applicable, rather than restricted to a certain area with exceptional data sources. Our contributions cover algorithms for extraction, weighing, and selection of landmarks based on their suitability, as well as the generation of landmarkbased navigation instructions for a given pedestrian route. The system has been implemented using PostGIS as a data store and QGIS for algorithm development. First field tests with pedestrians show promising results by confirming that our weighted landmark selection outperforms a simple baseline approach by reducing the number of navigation errors and revealed future challenges for the generation of intuitive pedestrian navigation instructions.

00:00
Metropolitan area network
Asynchronous Transfer Mode
Computer animation
Projective plane
Units of measurement
Open set
Mathematical model
00:33
Mobile Web
Point (geometry)
Metropolitan area network
Asynchronous Transfer Mode
Computer font
Scaling (geometry)
State of matter
Graph (mathematics)
Point (geometry)
Projective plane
Computer font
Graph (mathematics)
Open set
Mathematical model
Revision control
Computer animation
Hill differential equation
Local ring
02:03
Fibonacci number
Computer animation
Information
Database
Linker (computing)
Graph (mathematics)
Programmable readonly memory
Geometry
Attribute grammar
Bus (computing)
Separation axiom
Physical system
02:51
Slide rule
Graph (mathematics)
Graph (mathematics)
Disintegration
Attribute grammar
Mass
Computer font
Rule of inference
Connected space
Preprocessor
Computer animation
Database
Personal digital assistant
Linker (computing)
Square number
Scripting language
Information
Square number
03:55
Metropolitan area network
Algorithm
Touchscreen
Graph (mathematics)
Electric generator
Graph (mathematics)
Disintegration
Gradient
Sound effect
Bit
Line (geometry)
Mereology
Cartesian coordinate system
Skeleton (computer programming)
Computer animation
Root
Bit rate
Square number
Right angle
Subtraction
Routing
Square number
04:57
Curve
Graph (mathematics)
Graph (mathematics)
Direction (geometry)
Disintegration
Open set
Connected space
Computer simulation
Computer animation
Vertex (graph theory)
Square number
Selectivity (electronic)
Routing
Square number
Wide area network
05:47
Complete graph
Block (periodic table)
Graph (mathematics)
Polygon
1 (number)
CAN bus
Medical imaging
MKS system of units
Computer animation
Linker (computing)
Square number
Vertex (graph theory)
Implementation
Subtraction
06:26
Area
System call
Graph (mathematics)
Twin prime
Graph (mathematics)
Line (geometry)
Graph (mathematics)
Bit
Emulation
Computer animation
4 (number)
Uniform resource name
Electronic visual display
Moving average
Implementation
Library (computing)
Wide area network
07:02
Point (geometry)
Polygon
Implementation
Building
Line (geometry)
Graph (mathematics)
Multiplication sign
Vector potential
Moving average
Subtraction
Multiplication
Metropolitan area network
Default (computer science)
Series (mathematics)
Link (knot theory)
View (database)
Point (geometry)
Polygon
Dimensional analysis
Set (mathematics)
Vector potential
Computer animation
Function (mathematics)
Order (biology)
Data type
09:03
Graph (mathematics)
Venn diagram
Network operating system
Multiplication sign
Projective plane
Electronic mailing list
Expert system
Weight
Vector potential
Maxima and minima
Computer animation
Root
Network topology
Database
Information
Data type
Routing
Wide area network
10:31
Metre
Point (geometry)
Algorithm
Electric generator
Decision theory
Model theory
Decision theory
Direction (geometry)
Point (geometry)
Heegaard splitting
Roundness (object)
Computer animation
Database
Right angle
Information
Descriptive statistics
11:47
Metre
Point (geometry)
Building
1 (number)
Sheaf (mathematics)
Thresholding (image processing)
Hypermedia
Computer network
Database
Uniqueness quantification
Selectivity (electronic)
Right angle
Router (computing)
Category of being
Rule of inference
Metropolitan area network
Algorithm
Mapping
Decision theory
Artificial neural network
Building
Uniqueness quantification
Point (geometry)
Allegory
Element (mathematics)
Line (geometry)
Category of being
Voting
Computer animation
Angle
String (computer science)
Convex hull
Right angle
Quicksort
Resultant
15:07
Point (geometry)
Algorithm
Decision theory
Allegory
Point (geometry)
Polygon
Mereology
Distance
Inflection point
Maxima and minima
Summation
Category of being
Uniform resource locator
Computer animation
Root
Network topology
Computer configuration
Uniform resource name
Buffer solution
Moving average
Right angle
17:18
Point (geometry)
Polygon
Building
Curvature
Propositional formula
Function (mathematics)
Mereology
Mathematical model
Representation (politics)
Right angle
Router (computing)
User interface
Constraint (mathematics)
Sine
Point (geometry)
Polygon
Model theory
Projective plane
Electronic mailing list
Bit
Category of being
Computer animation
Angle
Uniform resource name
Resultant
19:17
Raw image format
Musical ensemble
File format
Robot
Multiplication sign
File format
Electronic mailing list
Sheaf (mathematics)
Control flow
Electronic mailing list
Mereology
Hand fan
Open set
Summation
Sign (mathematics)
Computer animation
Personal area network
Resultant
Row (database)
Form (programming)
Wide area network
20:43
Point (geometry)
Service (economics)
Polygon
Line (geometry)
Field (computer science)
Prototype
Computer animation
Field (mathematics)
Linearization
Software testing
Implementation
Prototype
Linear map
21:23
Point (geometry)
Computer animation
Presentation of a group
Square number
Grass (card game)
Thermal conductivity
Position operator
22:17
Metropolitan area network
Graph (mathematics)
Graph (mathematics)
Decision theory
Polygon
Line (geometry)
Open set
Computer animation
Dedekind cut
Multiagent system
Personal digital assistant
Square number
Vertex (graph theory)
Physical law
Data structure
Implementation
Router (computing)
Conditionalaccess module
Sinc function
Position operator
Wide area network
23:50
Metre
Point (geometry)
Slide rule
Building
Context awareness
State diagram
Direction (geometry)
1 (number)
Chaining
Summation
Goodness of fit
Root
Arithmetic mean
Computer configuration
Atomic number
Ranking
Selectivity (electronic)
Router (computing)
Area
Metropolitan area network
Algorithm
Standard deviation
Decision theory
Allegory
Point (geometry)
Projective plane
Mathematical analysis
Cartesian coordinate system
Maxima and minima
Category of being
Computer animation
Personal digital assistant
Lie group
Order (biology)
Text mining
Object (grammar)
Abelian category
Routing
Probability density function
27:38
Point (geometry)
Polygon
Line (geometry)
Graph (mathematics)
Decision theory
Multiplication sign
Direction (geometry)
1 (number)
Vector potential
Table (information)
Medical imaging
Sign (mathematics)
Mathematics
Linker (computing)
Row (database)
Selectivity (electronic)
Vertex (graph theory)
Implementation
Position operator
Descriptive statistics
Metropolitan area network
Default (computer science)
Link (knot theory)
Process (computing)
Wavelet
Mapping
View (database)
Point (geometry)
Electronic mailing list
Attribute grammar
Weight
Junction (traffic)
Connected space
Uniform resource locator
Computer animation
Database
Function (mathematics)
Right angle
5 (number)
Film editing
Routing
Resultant
31:07
Point (geometry)
Greedy algorithm
Algorithm
Group action
Multiplication sign
Projective plane
1 (number)
Planning
Travelling salesman problem
Cartesian coordinate system
Distance
Prototype
Word
Uniform resource locator
Computer animation
Mixed reality
00:08
but from I that's what pleasure
00:11
being here and as I introduce my name is isn't the
00:13
cost you probably know me from the q project and from GIS that exchange they're trying to give support for at your eyes GIS questions today I want to talk to you about a research project that I'm currently working on which is dealing with pedestrian routing so from the Farm With really
00:34
cars we are now back down to earth we have to walk on our own active mobility
00:40
and we talk a bit about pedestrian routing and navigation what's the
00:46
point of departure for this project these wanted to calculate realistic pedestrian we wanted to compute a landmark navigation instructions I won't get into detail what that means and how they look like and we wanted to do all this with commonly available data which basically means we are doing it OpenStreetMap brighter than any national dataset which we might use together with from local point of interest state because that just doesn't scale and this is in European project so you want to that your partners can also use it in Germany or in other countries of the EU version outlineable be talking 1st about the issue of pedestrian routing graphs which are not as straightforward as 1 might think then I will be talking about the whole issue of extracting landmarks from OpenStreetMap so how can you get to the point where you can say walk straight ahead and then turn left off after the church do you find that church or whatever place it is that you want to you use in your navigation instructions and then of course the whole thing of algorithmically constructing the navigation instructions so
02:05
1st of all the pedestrian routing if unless we cannot put it in any other way in OpenStreetMap you
02:15
have places where the mappers decided to put the sidewalks separate links then you can extract the sidewalks and you can theoretically ruled on those in other places the members didn't do do that and instead they will mark the role with the tag that says this world also has a sidewalk but there is no separate geometry for the sidewalk so if you wanted to make a pedestrian routing which seeks suicide once you have the 1st system extracts those sidewalks like we were trying to do here so we have information for this world there's a sidewalk
02:53
on both sides so we can draw the sidewalk in preprocessing step and because we are not mean we also want the best and to be able to go from 1 side of the road to the other side for example if there is a shot that they want to go to so we also introduced those connections between the different sides of the road so that you have a way to cross the street that's the case where the normal rules and then you have the case of wonderful pedestrians careers and I will get into detail about this topic on on the next slides also really interesting currently that the rules that you get if you try to rule that was there is there ridiculous and nonsensical and they just follow the outline of this square because that's what the simple preprocessing
03:45
scripts do they take all the road links and then they take the square of the use Outline of despair inserted into the rope graph and say and then the pedestrian has
03:56
to walk along the outside of Rockefeller Plaza to to get to the other side of the screen this also leads to effects of air the algorithm completely avoids the square because the root gets so long that it actually thinks it can get to the destination on other routes much faster so I've been looking as part of this work at different algorithms for preprocessing the OpenStreetMap they put those players to get a better pedestrian routing graph to work with and from the left to the right you can see different approaches that I tried so the 1st 3 of something that you can find quite readily GIS literature you can extract the medial axis or straight skeleton use of both
04:42
very well describe a bit hard to find generate very simple to generate art different rates it can be a square grid you can make a triangle grades are hexagonal grids and but not all of these
04:57
approaches have in common is that they who will not result in a rout that I will take if I was a pedestrian if I'm a pedestrian and there's an open square in front of me and I want to go from 1 side to the other I will choose the most direct path or something very close to it so it would make no sense for me to see a route which goes like this with this corner in or these curve here so what I ended up selecting is something that is very well known from game development and from pedestrians simulations it's called a visibility graph and in the visibility graph you connects all the nodes of the political you
05:44
create those connections and then you remove connections which are
05:49
some block for example by
05:51
building that's in the middle of the square that's actually a very nice example in the center of the image difference plants and do it shows variable that there's a lot of links that you have to to insert for the solution have because you generate the complete graph then you remove all the links which are partially outside the polygon either because they're just at the borders or because they're crossing something that's inside of the square and the remaining ones you could be integrated in the world
06:27
and graph and it works is an experiment I did in GIS if the network analysis of a library
06:34
that is building huge areas for other purposes and you can see here i'm
06:39
starting to call the roll out on the regular routine graphs and then I started to enter the display and it continues along the gray lines which are the visibility graph of these careers if you are interested to learn more about this topic this paper has already been published and it's open access so you can read about the whole story there
07:02
again because the 2nd topic I want to get to what is the topic of landmarks how can I get to the point where I can say to her left the church there are so many potential feet so many features in OpenStreetMap about potential landmarks and for the 1st thing that around the of implementations that I wanted to drive I just import the whole OpenStreetMap them for the and my example interpose JRC is of the order of the and then I constructed landmark use so these fuels are later they contain all the potential landmarks that I've identified and how are they identified this quite
07:47
huge series because I have to go through a lot of different Jesus and text to see everything that could be a potential landmark what comes in very handy is that H support in and post yeah yes because you can access all those tags that OGR are put into that other texts by default but if you have questions about how is virtue can go into detail of course you can control that with everything is thrown into the other texts already on import but I decided against that and just use the default settings that's why I have to do so much better attack work at this point in time so I do this for the points as well as for the polygons because many things are mapped in different ways and OpenStreetMap for example if there's 1 building and this building is a shock it's usually a polygon but it's the same shop is within a bigger building and this building contains multiple shocks than it might just be 1 point represented as a point that's why you have to have both of these the feature types as potential landmarks another step that is
09:07
necessary except for filtering is also waiting because some types of features are just more useful as a landmark so I basically have a small expert workshop at the conference there asked people which things are more useful as landmarks and which are less useful and I generated the list and I can always I used well yes from 0 to 100 but suitability of a certain kind of that landmark and I'm also constructing some more useful names from OpenStreetMap India per so
09:46
if both of these things are in place the routing graph and I have to state the base these fuels full of potential landmarks I can go ahead and try to generate landmarkbased pedestrian instructions I'm skipping hear the whole topic of how to generate the root for the protested it back until there is the simple shortest route or like our project partners do they try to make the find the most suitable route for pedestrian so maybe not next to a big role of if noisy cars and instead go in the parallel role that there nice trees and shade and it's much more pleasurable to walk I don't have time to go into that but we can get this wrong and we try to describe it to the pedestrian so that they can
10:31
follow the navigation instructions and we have to find the most suitable landmarks to do that so
10:41
to generate navigation instructions we have these basic steps in our algorithm 1st we take the whole throughout and the splintered into episodes between socalled decision points a decision point is when you have to change direction you can also define a decision point of other places but the most important decision point is when you have to change direction then at this decision points you compute the turn instructions will be after laughter you have to turn right to you go straight ahead then you have to select the most suitable landmark then you try to compute is the landmark is before or after death decision point and in the end if you have to computed that all those things you can't create eroding description what are the challenges when you try to do that it's already started the 1st point of splitting into those episodes between decision points because what we found in the 1st round is that we get way too many decision points it's like go 5 meters and then you turn left and 5 meters and then you turn right
11:47
and the issue is as shown here and as 1 example you have super short section of just a few meters and automatic things you have to turn twice because it's just above the threshold of this turning angle that you find votes 1st turn left and then immediately turn right again even tho it's completely useless for the best candidate should just look straight over this crossing uh but it's maps in OpenStreetMap that way so how do we deal with that and 1 idea is that you have another of processing steps on the right which finds those really short of elements and tries to replace them so if you take out this middle section the really short replace it by the red points and you connect the remaining points and this way it is the exact thing is gone as all the works for turning as you see in the example B and it also can work for a more complex stuff like shown in c there I defined that you must not remove short sections if terrorists zebra crossing because I want to keep the zebra crossing of want to be able in the final instructions to tell people use the CVaR crossing there so they must produce a removed that 1 but I'm removing that horizontal line on and this horizontal line so again you just go straight crossing on for crossing then you have to come due turning instruction that's rather simple it's just a matter of taste how many of these sections you have you could just have straight left right or having them but more finegrained like this also how widespread angle is 4 straight there are discussions in dozens of papers what this angle all 4 should be but really there is no right and wrong here is you can test it if your users if they have a certain preference but it's just that permit the foot of gets really interesting is the selection of landmarks so I have here just 5 different papers over the last 15 years of how it has been done in the past and there really simple ones may have building databases and you just select the name buildings that are within the past 4 of the router that's can be done that's simple and then they have built on the use results to find the most unique buildings like year in bond you have this example that churches are really close by it would be confusing to say turn left after the church because user church and there's a church and members opposed to go so you might want to find the most unique buildings then there an approach which is the 1 which we are basically using which is rulebased using categories you sort of before and a few definitions up there is the category shop which is quite suitable there's the category museum which is great on charges of data and then there are other algorithms which have also been tried up to a neural networks which are trained to fight social media data for example
15:08
so if you remember I have want you with points and you would this political landmarks and from both of these users select 10 nearest points and the 10 nearest polygons and then I'm making dinner this formal which
15:23
and looks a bit involved but there's just a few parts in it of 1 important part is the distance between the decision point the landmark so obviously you want something that's close to the decision point simple then we have pursued abilities so we want something that's but not really well visible that can be distinguished as a landmark so we have this category suitability in then we decided but there is 1 option to that considered side of the landmark impact some papers they say that at landmark in stands out more if it's on the same side so that your turn into so if the instructions turn right you would be looking for landmark that's on the right side and instructions to turn left you will be looking for landmark that's on the left side you can use that are you can all you can leave it out and then you want the location of the landmark relative to the root so is it before or after the decision point do you say to her left after the charges it turn right before the supermarket and where it gets really tricky is the visibility of the the landmark how can you make sure that the person can actually see the landmark going to get to decision point and really OpenStreetMap data alone I haven't figured it out I don't know for sure how you can ensure that you can actually see it of course you can do some raycasting algorithms and you can see theoretically is this visible but there might be trees or something that you cannot see all this they should raise the point landmarks they are inside polygons so so simple right would say you cannot see the point because it sends out a political so some colleagues went ahead and made buffers around the points and then check if you could see the buffers from outside of how big is the buffer supposed to be so it's really I guess the main thing
17:20
is the visibility and I think we would need additional data to really make sure that something is visible we also income that the issue like OK great that's really close by a whole that should be visible but then it turns out that the people tried the navigation instructions that it was the back the back side of the whole it didn't look like anything from the back side is that we have approached it from the front it would have been clear that's the model blahblahblah but since they were coming to it from the behind the had no notion that this year the building was a models of the failed again unfortunately if you have that is how to determine which side of the polygon is the from flatness of here so the river that the outer parts that we need we also need to prepare the propositions of do you turn before after or it's a point for the points of simple you can just calculate the angle is the router for polygons it's a bit trickier because as you can see I could select any of the corner points and they would give sometimes could come confusing our results because they end up in different categories so I decided to use the centroid which works well for smaller polygons if it's a really big building on the other hand the polygon other centroid might not be a good representation of the polygon at the preposition might be a bit odd so that's a lot of point that you can think more about what we could do the and then the constraint is all up the can make a list of which edge to have to walk on what's the turn instruction at which landmark and was the prepositions and you lose those things out and someone was good in user interface design and has to figure out how to communicate this stuff to the end user because that was on my part of the
19:14
project I basically have this output in q
19:18
GIS merit excesses all that they post chairs that the Bayes thus the routing and computes these instructions which I details before by that I use q GIS obviously because I wanted to but the results and that's the best way I know how hard to see if it chose a landmark that is obvious source of for you server and what's there and tried to estimate is the turning instructions record of computed correctly and I was too lazy to implement the rubber bands to follow exactly the relative you have to imagine that the robot and here place
20:01
and it is also a list of 4 of those instructions of course it makes sense to have a standard format of how to exchange those instructions other part parties so with the breaking this form of quite a long time and time and that's why we have published it online we haven't found anything similar so far this covers not only the pedestrian routing pardon the navigation instructions it also has some sections for all of public transport droughts entitled to and communicate that to other people and every it would be very happy if other people would be interested in using this format as well it's an architect and if you need to have any details just
20:43
contact me about it what if seen so far as the prototype that have implemented in q JS in future work they're planning to also investigate the issue of linear landmarks so besides points polygons you could also look at lines for example if a river is modeled as a line of our railways could be also landmarks because you can easily follow them everything has been implemented in Python is a prototype 1st and this will not be migrated to service which can be used to
21:16
get a different path and they are also planning to field tested Indiana about the book next summer if you have any
21:26
questions about any of those that was getting conduct positive answers to the questions that I posted a presentation that would love to hear thank you few
21:40
thank you much on must be some question about interesting work anyone hi beyond working and also and yeah pedestrian routing and always sucks like as he's shown with the with the squares that's terrible I have a question around the square so 1 in 1 of the examples you had 2 squares were neighboring each of our that how do you select the uh intrasexual between like where to put the point over how cross between them and how do you handle
22:17
it structures inside of squares both them very good questions and In the case of these tool neighboring us careers I was in the lucky position that someone had also cheating the lines of what the US careers so that ordinary pedestrian routers can cross the street so governed nodes here which I didn't have to insert but I could just connect to and another colleague at the 4 skills in science books this year presented that actually you 1st have to do the step of merging those neighboring polygons and then computes the visibility graph for the merged political instead of separately which I skipped here because I didn't stumble on the issue since someone had already so far and the other thing that the obstacles on the street is in this case it's again simple because the square was modeled with this hole in the middle already so the stem from storm was cut out of the and if that's not modeled in that way you have to 1st are subtracted from the polygon to really just get the open area and be able to compute the visibility graph correctly the what do you do you movement landmarks
23:48
decision wounds due to changes in
23:51
rooms have bit 1 option is a very good question and of course we are using an area of analysis which has a lot of landmarks because we are more interested in finding a good loan amongst a lot of landmarks if there's really no landmark the fall back is to use the standard navigation instructions to the left of the 300 meters and there would be 1 intermediate things like turn left at the crossing but I thought about it and counting those crossings and everyone constant differently is pretty challenging as well so in case there are no landmarks anywhere to be seen I think I would just resorts to the simple approach of telling them to turn the left after a certain distance and but there are also in the literature you find many other algorithms which don't take the rout as a given and instead they might implement the routers that is most easy to describe if the landmarks that you know so you go 1st of this landmark and then to the next landmark and then it's just a short route to the destination but that's a completely different algorithm than the 1 we are working with here yeah do you think my text mining the name of the landmark is the plant McDonald's atoms can recognize that the say some local bakery the no one's heard of after all you mean to text mine out of the street but they don't know what to do during the reach of the landmarks will prevail known by the public I that's a good point of you haven't covered that in our project so far but it's it's a completely valid objection it also depends a lot on who are you are expected to end users is the touristic application that you cannot use any local brands probably or it Florida the local school know all those little coffee chains that are specific for certain cities to you problem to do it for the tourists I think another pair for most of the stuff that's around given up once again there's selection of landmarks you have chosen these other algorithms at the following here some some so
26:23
what comes Fernando and more it's based on context of out of OpenStreetMap and some geometric and in what order nongeometric properties of a landmark in your algorithm that long geometric 1 is the category which tells you and and if it's restaurant or if it's church this 1 this 1 this is not geometric and everything else is geometric versus geometric isomers because of out of the rankings the features of all the other thing that I know that you killed care could take on Wikipedia of cost and uh and rank high you this kind of light and must which have an entry in the future some yeah that would go into the direction of the militaristic ones are historically important buildings and you could give them an extra bonus but in many places you don't want to have anything that has a bigger PDF entries so you have to fall back on other stuff to and from the from the side of the roots and can you showed slide value preprocess the OpenStreetMap we and and and cut out the
27:40
suggestions the position this
27:43
1 with with so you say yeah Europe you have taken the sidewalks north on roads but also wrote about but this is showing a road with outside and inside that blue onesided sidewalks and the connections between sidewalks and the black ones the original world and and
28:04
wavelet only deliver routing on the blue ones and then what about all those routes which which have no assigned sidewalks if there is no side of the you have to run out on the road because people can walk along the road it's just not very comfortable I assume that many OpenStreetMap routes have sidewalks walks but the some effect of such and that depends a lot on the location you're looking at India and other members are very careful and there's a lot of sidewalks and some of course if you are applying this to a location that you have to expect that most sidewalks missing you probably defaults to the assumption that there is a sidewalk on both sides so that's what we have done you you really are looking on signs data set aside for this Heider either on its own or as allowed and and thing that is so you and the how do you consider crosswalks um on on the streets of it is is is the crosswalk along along the road so here you have a crossing and these will be the the regular crosswalks that that that you couldn't set by default and then we have all these extras for crossing the road as we often don't give you the distinguished between the the regular across crossroads but we entered here and so you alone once it would look different if there was like a safer crossing which is mapped disappointing OpenStreetMap than it would look different but this crossing doesn't have any of those things it's just as a regular 1 and and for a general description of the of the alliance that in map uh you often have to make here and there to make 2 ways which image of our just rights 1 of the other so you would like to merge its before the before you generates you were you're routs descriptions so so you have to merge it for profit from getting and mosses the smallest moves because most description because if you have some just technical technical cut of 2 ways which are 2 ways but in fact it's 1 street 1 standing 1 description that makes no difference because in our definition of a decision point it's on the decision point if there is a certain change of direction involved so if it's just split tiered link it doesn't end up in the list of Decision Points anyway so that doesn't influence the results so it so it so you will have never something like uh a change from 1 of from and almost all set to bond of just because they are in a lot of time and doesn't happen and decision point selection process as the have you looked into are traveling
31:07
salesman problem with transition algorithms so when when applied to display you would have to Our calculates distances between all pairs of words like you could still get truly and optimized whose this way but somehow to the landmarks play into this so traveling salesman things all supposed so you know you want to go through all the all the landmarks on here like like getting a poor for a tourist who wants to certainly as a sets as like you have 2 hours and you want visit as many when Marxist possible we if you if you choose the the best landmark in each point to go next so then this is called a greedy algorithm and is usually quite 1 and holes for like 50 per cent longer than the optimal ones so it's difficult do that was a very interesting idea and I think there are some tourism focused projects to do this tour planning for a given time to this sensor locations and but that's a completely different focus than over there just try to describe the given out as best as we can but it's super interesting application as well as and you can also imagine I want to spend an hour of time and just show me the CT but what can I see I asked is to an algorithm is also very challenging actually in Switzerland you can try it out my prototype it's called 42 were both ch and it does exactly like something like this and it's just a prototype because it that we have very different challenges so when you say I'd like an actual receipts uh so fountains all viewpoints then and then what is the mix between pulled in and viewpoints and and fountains and as of so the algorithm didn't take a nice neat and and and suggested to you turn fountains and and 1 human point something as this and really difficult stored at all to have such an answer but it's a showcase point toward of CH and not the but the different problem actually this 1 any other questions some thank you very much and adult