OpenGPScout
(Open Source Navigation-Project)

 Here the latest informationens about the present state of the Open Source Navigation Project
"OpenGPScout" are published.


To the phpBB Discussion Forum concerning OpenGPScout and GPS-Navigation in general

The work on the Yellow Paper about the ideas and concepts behind OpenGPScout are in progress.
See the latest drafts here
pdf-document 1 (main document)
pdf-document 2 (Appendix concerning some integer-routines)
pdf-document 3 (ini-file)

Basic idea
The project includes three parts:

a) The programming of the device and operating system independent routines:

The principal algorithm to calculate the routes, the algorithm to follow the calculated routes and also the necessary serching routines have to be
at the most extend possible independent of the used device and the operating system. The only thing, which have to be fullfilled is the condition,
that the same programming language (e.g. C++) is possible for these devices or operating systems.

Concerning the routing algorithm, my idea presently is to divide the data in tiles of appr. 0.0008 x 0.0008 radians (corresponding to about 3.5 x 5 km in our latitudes). Every tile would include 4-5 detail-levels for the road-segments and the nodes (for more details see pdf-document 1).
Because the implementation shall work also on devices having a limited amount of RAM and CPUs e.g. without Floating-Point-Unit (this is common for many mobile devices like PDAs), it is crucial to do the whole implementation to the extend possible using integer-arithmetics and reducing the amount of data to a degree, which can be managed by these devices.

b) Programs to convert the data materials of the maps to a unified format adapted to use for the routings under point a:

The choice of the data simply depends only on the existence of a suitable algorithm to convert the data in a format, which can be used by OpenGPScout . Possible data-material could stem from commercial navigational enterprises like Navteq/Teleatlas. However, using this, the licensing questions would have to be solved. Alternatively it would be also possible to use Open Source navigational material like "OpenStreetMap"  - this would avoid eventually the licensing questions, but at present time in this material there are stll some missing parameters, which would be of importance for the calculation of the routes.

c) device-dependent porting 

The success or failure of the project depents on the use of the algorithm on different plattforms/devices. The porting comprehends device dependent parts like the representation
of the maps. the Graphical User Interface (GUI) for the input of start and destination or the choice of various routing options), the device dependent programming of the interfaces (GPS over a serial port or Bluetooth, perhaps TMC or incorporation of other traffic services over a mobile connection or public wireless LAN) etc.  For Linux/MacOS there exists already an Open Source Project "GPSDrive", which covers nearly all of these aspects. For other devices (PalmOS, Symbian, WinMob etc.) it would be necessary to find developers, who would be interested to do the porting.


Actual status (Date: 19 Nov 2007)
Im still graceful for every comment, proposal etc. about OpenGPScout. Furthermore I am still looking for interested developers to support the project. All people interested are kindly requested to send me an e-mail to OpenGPScout@leupinfo.ch .
Definition of the data-format, especially for the Interfaces between the different modules (first proposal, to be reviewed ;-) ):

a) road-segments (minimum data - additional data to be stored in other files)

- node reference at the "beginning" of the segment ("0"-end):   3 bytes (2 bytes actual node reference, 1 byte for the relativ definition of the tile, on which the node is)
- node reference at the "end" of the segment ("1"-end):   3 bytes (2 bytes actual node reference, 1 byte for the relativ definition of the tile, on which the node is)
- Definition of the position of the segment within the nodes: 1 byte (this information is used for a faster execution of the routing algorithm)
 - velocity- and road category: 1 byte ( 4 bites respectively)
- length or driving time for the segment: 1.5 bytes (resolution appr. 5m or 5 s, to be discussed)
- allowed direction, driving restrictions, suitable vehicle categories etc.: 1.5 bytes
- reserved for additional informations: 1 Byte

11 bytes in total per segment (fixed length)


b) nodes (minimum data), 

fixed length:
- number of incoming/outgoing road segments: 1 byte (3 bits for the number of segments (maximum of 8), 5 bits for the type of node (e.g. turn-about etc.))
- coordinates of the node: 3 bytes (together with the tile reference the position is defined to about  2.5 m)
- Adjacent end of the road segments: 1 byte (1 bit per segment, 0 = "0"-end, 1 = "1"-end)

variable length:
- reference to a incoming/outgoing segment: 2 bytes per segment
- Which other segments can be reached from the actual segment:  1 byte per incoming/outgoing segment  (used for coding turn-restrictions etc.)
- Definition of the tile on which the segment is mainly located: 1 byte per 2 incoming/outgoing segments (??)

 Between 9 (correspondign to one segment, dead-end) and 39 bytes (corresponding to 8 segments))

Actual status of the source-code (Header file, in a very early status)

1.6.2007:  neue erweiterte Version des Source-Codes mit den Funktions-Prototypen für die bis jetzt vorgesehenen Funktionen
                  OpenGPS_gen.ini-Datei aufgeschaltet, welche die Initialisierungsparameter für die Routenberechnungen enthält
5.6.2007: Anpassung der struct-Definitionen: neu existieren nur noch zwei struct-Strukturen, welche mit dem New-Operator initialisiert werden.
12.6.2007: einige marginale Fehlerkorrekturen, Grobstruktur der Implementierung des eigentlichen Routenberechnungsalgorithmus, Teil Rückwärtsrechnung vom Ziel zum Start
19.6.2007: Neuer ftp-Zugang zu den Source-Files eingerichtet - interessierte Entwickler können sich bei mir per E-Mail melden...
19.11.2007: Translation of most of the website to english - new pdf-Files, containing the present concepts proposed for the project.
20.11.2007: Description of the criterion of ending the loops for A* and my alternativ proposal changed in the PDF-file


© 2007, A. Leupin (last changes 19.11.2007) 

You are visitor number: