Definition of a Route Guidance System for Android Smartphones


Introduction Framework Installation Options Path computation
 About

Introduction



Pedestrian is a free GPS navigation application for pedestrian in urban area that has the advantage of being permanently connected to a system taking advantages of an up to date street data base (OpenStreetMap).


This application can be used in any city of the world and can, moreover, in case of network interruption for several minutes, continue to assist the user. One of the innovations of this application is that the route computation is achieved by our algorithms in an iterative way to make it more dynamic.

It is therefore not a roadmap but an evolutionary itinerary that proposes this application


Advertissement: the work presented has been achieved during the training period of Benjamin Vincent in a rather short delay and some bugs could remain unfixed. Let us note that some interruptions of services could appear in the server.

 

Framework


In a client-server architecture the functions of the application are achieved on a remote server in order to make the user's application less expensive in CPU time and memory space. Moreover, such an architecture requires a network and therefore network connection problems between the application and the server may cause undesired operation. To compensate as much as possible this problem, our architecture includes management of the loss of connection as long as it is temporary.

The architecture in conventional mode is based on three parts illustrated by the diagram below :

  • A client part  : that supports a user friendly interface with the user.

  • A server part   which is in charger of managing traffic data from OSM (2) and (3) to perform shortest path.

  • OSM server : that provide the necessary data for road trip computation.

 principe

 


Computer scientists can refer to the API which offer services for shortest path compuation : 

http://www.isima.fr/~lacomme/ORWebServices/GPS4pedestrian/index.php

 
 

Installation


NB : : This application requires Android version 3.0 or higher. (API level 11 +)
 

Once the application file Gps_android.apk downloaded, we must ensure that the smartphone allows installation of an application that is not from the Android market. You must go to the Security tab and allow Unknown sources.

Then just install it on the mobile and enjoy... 		installation


Options


The application requires to activate GPS and mobile data on the device: gps_reseau



 The functionalities of the application are available from the menu:


My position :  Center the map on the GPS location of the device

Destination : Specify a postal address /td>




Guide : Starts computation of the trip



Language : It is possible to switch the application in English or French. (the default language is the language of the smartphone.)


About : Some information on the application 		 d m


Path computation



The route calculation is achieved iteratively.
On the example, in reducing the zoom on the map it is possible to note that the route is not fully available (the green dot in the upper left is the destination), it will end when the user has covered a part of the first proposed route.

References



Dijkstra E.W. A note on two problems in Connexion with graph. Numerische Mathematik, Vol. 1, pp. 269-271. 1959.

Golden B. Shortest Path Algorithms: A comparison. Operations Research, Vol. 24(6), 1976.

Pallottino S. Shortest-Path methods: complexity, interrelations and new propositions. Networks. Vol 14(2). 1984.

Gerhard Ert. Shortest Path calculation in large road networks. OR Spektrum. Vol 20. pp. 15-20. 1998.

Wagner F. and T. Willahalm. Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparce Graphs. Konstanzer Scheriften in Mathematik. N. 183. ISSN: 1430-3558. 2003.

Willahalm T. Engineering Shortest Paths and Layout Algorithms for Large Graphs. Dissertation. Doktors der Naturwissenschaften der Fakultat fur Informatik der Universitat Fridericiana zu Karlsruhe. 2005.

Jung S. and Pramanik S. An Efficient Path Computation Model for Hierarchical Structured Topographical Road Maps. IEEE Transactions onKnowledge and Data Engineering. Vol. 14(5), October 2012.

Wagner D. and Willahalm T. Geometric Containers for Efficient Shortest-Path Computation. ACM Journal of Experimental Algorithmics. Vol 10 (1.3.). pp. 1-30. 2005.


About

Author

Benjamin VINCENT                                    
benjamin.vincent023@gmail.com                  

Persons in charge of the training period:

Libo REN
ren@isima.fr

Philippe LACOMME                                     Nikolay TCHERNEV
placomme@isima.fr                                        tchernev@isima.fr


Ackowledgements:

The team is grateful to ISIMA engineers for their help during this project.

Fundings:

This research was funded by the LABEX IMOBS3(Innovative MOBility: Smart and Sustainable Solutions)


Extra information

Cartography : Mapquest / OpenStreetMap
Shortest path : Benjamin Vincent
Server provided by: LIMOS
Server JEE : Glassfish


                          Top