Logo TIB AV-Portal Logo TIB AV-Portal

Developing an Open Pedestrian Landmark Navigation Model

Video in TIB AV-Portal: Developing an Open Pedestrian Landmark Navigation Model

Formal Metadata

Developing an Open Pedestrian Landmark Navigation Model
Title of Series
Part Number
Number of Parts
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.
Release Date

Content Metadata

Subject Area
Today's publicly available pedestrian navigation systems still use paradigms developed for car navigation. In this paper, we present a novel landmark-based 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 landmark-based 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.
man unit modes Computer animation projects open subsets mathematical modeling
mobile point man modes font scale states Graph point projects graphs font open subsets mathematical modeling Computer animation hill localization
fibonacci series Computer animation information link Graph PROM Databases attributes BUS several systems geometric
script Slides Graph link Graph Integrationen Databases attributes Mass font rules Arm van connections preprocessing Computer animation case square information square
man algorithm screens Graph generate Graph Integrationen graded effects bits lines part applications skeleton Computer animation root rates different square Right Routing square
curve Graph Graph directions Integrationen simulations open subsets connections Computer animation square selection Routing square WAN
complete graphs link Blocks Graph polygons ones CAN-bus image MKS-System Computer animation different square vertices implementation
area system call Graph twin Graph graphs lines bits Emulation CAN-bus Computer animation 4th URN Display Rolling implementation libraries WAN
point polygons implementation building lines Graph time potential Arm different Rolling series multiple man default link views point polygons dimension sets potential Types Computer animation functions orders
management Graph Venn diagrams network OS NET time projects experts The list maximal Databases potential Types Computer animation root topology information Routing WAN
meter point algorithm generate models decision decision directions point Databases Arm splitting round Computer animation Right information descriptions
point meter building sheaf ones threshold elements hypermedia unique selection Right Router category rules man algorithm mapping decision neural network building unique point Allegory workgroup Databases lines category voting Computer animation angles string convex hull Right sort Results
point algorithm decision Allegory point polygons maximal part distances sun van Wendepunkt category Location Computer animation root configuration URN topology buffer Rolling Right sum
point polygons building proposition functions part sun mathematical modeling models Representation Right Router user interfaces management constraints sin point polygons projects The list bits category curves Computer animation angles URN Results
CAP formating time formating The list sheaf Continuation The list part fan open subsets sign Computer animation robotics WPAN band sum Results record form WAN
point services polygons fields lines fields prototype Computer animation linear testing implementation prototype linear
point presentation Computer animation square GRASS conduct position
man Graph Graph decision polygons lines open subsets CAN-bus Computer animation completion Multi-Agent case square law structure implementation Router CAMS position since WAN
meter point Slides Context building Statechart directions ones maximal Arm goods root means configuration atomic selection Router sum area man algorithm standards decision Allegory point projects analysis applications category Computer animation case lies chain orders Text Mining objects Rank abelian Routing PDF
point polygons table link NET lines Graph decision time directions ones Databases potential mathematics sign record selection vertices implementation position descriptions man default link wavelets mapping views point The list attributes Menu junctions connections CAN-bus Location processes Cut Computer animation functions Right 5th Routing Results
point Greedy algorithm Actions time projects ones plan TSP distances applications Location prototype words Computer animation mix
but from I that's what pleasure
being here and as I introduce my name is isn't the
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
cars we are now back down to earth we have to walk on our own active mobility
and we talk a bit about pedestrian routing and navigation what's the
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
1st of all the pedestrian routing if unless we cannot put it in any other way in OpenStreetMap you
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
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
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
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
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
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
create those connections and then you remove connections which are
some block for example by
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
and graph and it works is an experiment I did in GIS if the network analysis of a library
that is building huge areas for other purposes and you can see here i'm
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
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
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
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
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 landmark-based 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
follow the navigation instructions and we have to find the most suitable landmarks to do that so
to generate navigation instructions we have these basic steps in our algorithm 1st we take the whole throughout and the splintered into episodes between so-called 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
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 fine-grained 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 rule-based 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
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
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 ray-casting 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
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 blah-blah-blah 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
project I basically have this output in q
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
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
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
get a different path and they are also planning to field tested Indiana about the book next summer if you have any
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
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
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
decision wounds due to changes in
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
what comes Fernando and more it's based on context of out of OpenStreetMap and some geometric and in what order non-geometric 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
suggestions the position this
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 one-sided sidewalks and the connections between sidewalks and the black ones the original world and and
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
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