Hello everyone!
My name is Francisco Albacete Chicano (but feel free to call me Paco!) I am a second year Computer Science student at the University of Murcia (a city at the southeast of Spain) and recently I have been selected for the Google Summer of Code with OpenStreetMap to work on the Valhalla Enhance Pedestrian Routing project with Kevin Kreiser and Christian Beiwinkel as my official mentors, and Nils Nolde helping out as well!
The main focus is to improve how Valhalla handles the pedestrian navigation. Stay tuned for this project as I expect to take pedestrian routing a step forward !
I will be documenting the whole journey through my OSM diary and in my personal blog (which is in my profile). If you want to know a bit more about me and the project you should definitely check it! → Paco’s OSM Diary
Very excited to be part of this huge community, see you!
9 Likes
Quick update!
I’ve just published a new diary entry, going into detail about this project and all the interesting information I’ve collected about the main issue we’re aiming to solve.
Make sure to check it out!
Area routing in Valhalla: comparing algorithms to cross open spaces
3 Likes
Nice work! It’s a very interesting subject which could lead to significant changes in mapping behaviour. It’s been discussed many times before, and most of the time I get lost in techspeak; you diary entry OTOH is clear to me.
I get that there is a workable solution for the area-crossing problem, which requires that the area is properly mapped and that the entrances/exits are available to the routing algorithm. I think area mapping is sort of ok in OSM, but entrances… pedestrian squares usually have them, but say meadows and sandy areas which are to be crossed for hiking, not so much.
I wonder if the pruned medial axis approach could handle area shapes with obstructions, holes for housing blocks, and weird tentacles. I’ve come across pedestrian areas following interconnecting streets, connecting several pedestrian squares and even with side alleys and back alleys.
Apart from crossing the area to an exit, I think routing should also be able to route to an adress or geolocation within the area.
Thanks! really glad it reads clearly, that was the goal 
You are right, entrances are indeed one of the trickier parts, we have to keep a lot of possible cases in mind,so we’ll start with a safe, scalable version and then handle more difficult cases.
On complex shapes the medial axis handles holes and concave forms quite well since it follows the skeleton. Here is one example of a more interesting/complex area where I tested pruned medial axis:
About routing to a point inside the area, we haven’t really discussed it yet since there are a lot of things that come first, but it’s definitely something to think about.
Lots of these answers (and more questions) will come as we move forward with the implementation. Thanks for sharing your thoughts!
1 Like
Nice one! It’s also an example of the need for further pruning, I think. Or some form of weight value. A space between adjacent buildings is often not a passway, and if it is it should probably get a very low weight.
