A new pedestrian GPS navigator providing the shortest-cost safest-crossing route on the basis of Open Street Map (OSM) cartographic data is proposed. Also, Java implementation and use case example are discussed. Satellite navigation algorithms are used everywhere in modern life. Every computing system, even a smartphone, is equipped with some kind of navigation application (at least, Google Maps). Such an application is able to build a route from one point to another, show it on a map, etc. Each navigation application can be proprietary or open-source. Among wide variety of open-source projects, Open Street Map (OSM) project seems to be the most interesting. I've decided to study this format in more details. I know that the best way to understand a new technology better is to apply it for something useful. I'm fond of walking the streets of my city. So I decided to develop a simple pedestrian navigator based on OSM data.
Each navigation application contains implementation of some routing algorithm as it’s main building block.
General routing problem has the following setting. Input: starting and target location points given by their GPS coordinates and topographic map of the search area, defining restrictions over feasible routes. The goal is to determine the optimal (shortest w.r.t some predefined metric) route.
For instance, a car driver navigator constructs a minimum trip-time route subject to given road map and traffic constraints.
Traditional approach to mathematical solution of the above problem consists
of two stages. On the first stage, the initial problem is reduced to well-known
Shortest Path Problem (SPP), which is defined on the appropriate weighted
graph. On the second stage, SPP is solved by one of classical combinatorial
optimization algorithms: Dijkstra [
Nowadays, there are many open-source applications based on OSM data
format. Among them, the following applications seem to be the most popular:
a Open Source Routing Machine is a nice online routing application. It’s
seems to be [
As can be seen from Fig. 1 there is no OSM-based routing application providing full service to pedestrians (no safest-crossings support). In this paper we describe our OSM-based Java implemented standalone application, providing this type of service.
Let us recall some basics of the OSM format structure. First of all, OSM file [7] is just a special type of an XML document and contains hierarchical collection of elements. Some of these elements may have attributes and additional data. Basic elements of any OSM file are called nodes and ways. A node is just a model of some location point, defined by geographic coordinates (latitude and longitude). In the OSM format, each spacial topographical object is presented by some way element containing a collection of nodes and accompanied by informational elements. Each informational child element can be considered as a (key, value)-pair, presenting some feature of the containing way element (see Fig. 2).
Reduction to the Shortest Path Problem in Weighted Graph As we’ve seen above, in the OSM format, every topographical object (street, bicycle path, footpath, building, etc.) is presented by a piecewise linear way consisting of nodes. Here’s an another reason for usage exactly the OSM format for the construction of the graph corresponding to the current navigation problem.
During the reduction to SPP, these nodes are just taken as vertexes of the constructed graph. Further, we assume two vertexes to be adjacent if they correspond to neighboring nodes of the same way on the map.
Because of our intention to develop the pedestrian (safest crossing) navigation
application, we should consider only such ways, that describes special types
of roads, among them footways, sidewalks, pedestrian crossings, etc. During
the graph construction we use only these ways. When the weighted graph is
constructed, we apply an heuristic extension of well-known Dijkstra algorithm
the A* algorithm [
We implement the mentioned above application in object-oriented Java application[8]. Let’s describe the main classes. Main - the main class that runs an application. Footway - the ”footpath” class, it contains an array of nodes from OSM file. AStar - the class that implementing an A* search algorithm. MapReader - this class is intended for parsing OSM file. RouteWriter - this class appends the calculated route (in osm-file) in XML-format so the augmented map could be visualized. WeightedPoint - this class determines the coordinates of nodes. 3.3
Suppose, we are asked to construct a shortest pedestrian path from the main building of Institute of Mathematics and Computer Science (IMCS) UrFU to the main entrance of Belinsky public library. First we need to know GPS-coordinates of both way-points. Second we need a special OSM file that contains required piece of map. Then using the AStar class, our application constructing a shortest path and using a RouteWriter class, application write down an XML file with the shortest pedestrian route. To get the constructed route, we can open this updated XML file by any text-reading application. In our case (see Fig.3), we use JOSM (Java Open Street Map, Java implemented OSM editor) for graphical visualization.
We conduct a specific numerical experiment consisting of constructing of 100 routes for independently chosen random location points on the Ekaterinburg city map. Expected relative value of graph construction run-time is equal to 97.8% of total run-time within standard deviation of 0.3%. 4
A new type of OSM-based routing application for constructing shortest-cost safest-crossing pedestrian paths is proposed. The application is Java-implemented and can run on every Java-compatible platform. Run-time of the application can be significantly reduced by leveraging some of standard cashing techniques for a previously constructed graph. 4. CycleStreets application page. http://www.cyclestreets.net 5. GraphHopper application page. http://graphhopper.com 6. OSM-based routing applications comparison matrix.
http://wiki.openstreetmap.org/wiki/Routing/online routers 7. Jonathan Bennett. OpenStreetMap. Packt Publishing. Birmingham. 2010. 8. Daniel Y. Liang. Introduction to Java programming: comprehensive version. Pearson Education, Inc. 2007. Аннотация Предлагается новое приложение GPS-навигатор, находящее кратчайший маршрут с учетом правил дорожного движения по данным OpenStreetMap (OSM). Обсуждаются программная реализация на языке Java и пример использования. Ключевые слова: GPS-навигатор, обработка OSM данных, алгоритм кратчайшего пути.