Intelligent In-Car Navigation System

Narayanan Ramanathan
Project Manager
GIS &GPS CoE
[email protected]

Ravi B
Software Engineer
[email protected]

Vadivelan P
Software Engineer
[email protected]

Abstract
In current scenario, the road speed limit stored in map data has been used for optimum route calculation purposes. In the peak hour, the vehicle speed would be less compared to the speed at the noon time or late evening. Thus, the real time scenario shows speed of the vehicle depends on the time. Hence, the optimum route between two or more places would not be same both in the peak and non-peak hour. The current/available system does not have an intelligent mechanism to consider the traffic congestions instantaneously and to identify the optimum route at that time.

This paper devises a theory/methodology to store the vehicle speed at pre-defined time intervals in the map attribute data and compute the optimal route using the corresponding speed information in the time interval at the time of request. It uses map matching method to find the road segment and retrieve speed data from GPS/Speedometer. The speed would be stored in the attribute data for the corresponding time intervals (eg, 8:00-9:00AM, 9:00 -10:00AM etc). The proposed system will use this stored speed for the optimum route analysis. Thus, for the same inputs (Origin and Destination), the system would give different optimal routes at different times on the same day.

Introduction
An automotive navigation system is a satellite navigation system designed for use in automobiles. Unlike other GPS systems, these use position data to locate the user on a road in the unit’s map database. (encyclopedia).

The introduction of Geospatial Information System within the car dash board is one of the advancements of Geospatial technology. In-Car navigation system allows better understanding of the user’s current position as well foresee any upcoming manoeuvres actions and points of interest. One of the notable features of Navigation system is finding the optimum route for the given origin and destination and also providing navigational instructions. As the navigation systems becomes more ubiquitous, makers like Lexus LS, Tom-Tom, Siemens, Blaupunkt and many more have started to provide in-car navigation systems.

The emergence of new products in the market is so rapid and today’s navigation package will be out of date in few months. In the short term, the sensitive information such as traffic congestion, new road updates and point of interests should be updated frequently. The statistics (adapted from The Global market for Navigation Systems) say 50% of the cars will have telematics by 2006. The market will first grow first in Japan, followed by Europe and US.

The following sections deals with the functionalities of the Navigation systems, speed calculation, optimum routing algorithm, map data structure and the implementation methodology of the proposed system.

Functionalities in Navigation System

The common functionalities or features in In-Car Navigation systems are,

• Map Navigation tools (zoom in/out, pan etc)
• Display of POI (Point of Interest) along the roads
• User queries
• Optimum route calculation
• Route guidance & directions to reach the destination(s)
• Integrated map display (labels, one-way, flow of direction, ferries etc)
• Voice recognition
• Audio/Video player
• Bluetooth Capability

Vehicle Speed
GPS velocity is calculated based on the frequency shift (or Doppler shift) in the carrier band. Accuracy of the velocity depends on the effect of multi-path, city sky-scrappers, DOP etc. The comparison of Speed data from GPS and Speedometer or Tachometer has been studied detailed by many researchers. The GPS speed is accurate than speed from speedometer/tachometer. Witte et al, has studied that the speed determined by the GPS receiver was within 0.2 ms(-1) of the true speed measured for 45% of the values with a further 19% lying within 0.4 ms(-1). Hence, it can be interpreted that there isn’t much difference in the speed rendered by GPS and the Speedometer. However, the preference could be given to GPS speed data. In addition, the implementation methods given in this paper does not depend on the accuracy of the speed data.

Optimum route analysis
Path finding algorithms fall into one of two main categories, matrix algorithms and tree-building algorithms, of which the latter is the one mostly used in Geospatial. Tree-building algorithms find the shortest path from an origin node to all other nodes, producing a tree of shortest paths with branches emanating from the origin (Lombard and Church 1993). The most commonly used tree-building procedure was developed by Djikstra (1959), of which to date many modifications and improvements have been made for specific applications. The working of the Djikstra’s shortest path algorithm is briefed by an example of five nodes (Figure1-a) that are all connected by a road and contains a weight represented by travel time in minutes. The source node or starting location of the shortest path to each node is “A”. The arrows represent the direction of travel between the edges. The numbers near the arrows represent the weight (travel time). Figure1-b shows the algorithm pointing to red nodes with the total weight from node “A”. As the red nodes are found not to have any other edges coming into them such as node “B”, they are coded orange. The orange indicates that the lowest cumulative weight has been assigned to that node. Searches continue for other nodes (“C”, “D”, “E”, and “F”) until the algorithm establishes that all nodes have been assigned the shortest cumulative weight (Figure1-c). Figure1-d shows the final result and the shortest time between all nodes (Ravi. B, et al, 2005).

Figure1. Working of Djikstra’s algorithm

We have seen about the general approach of the Djikstra’s algorithm for optimum route analysis. This algorithm could be implemented in network analysis (roads, pipelines, transmission lines etc), which has the nodes and arcs with constraints. The constraint could be length, distance, time, travel time or the combinations of any assumed cost.

Map Database – Road Network Data
In this section, we will discuss the road network and its attributes other than the geometry. The common attribute information in the road network data and attributes which are used for optimum route analysis are described in the following table 1 & 2. The number of fields would depend on the map data vendor. The format of the map data would never be addressed in this paper. This paper tends to provide general approach for dynamic speed storage and its usage.

Table 1:

Table 2:

The “weight” used in the sample Djikstra’s implementation (as described in the above section) could be replaced with the “length of the road” or “travel time” for optimum route analysis as given in the above table.

Proposed System
The proposed system would consist of few more fields with the available map attribute data. The fields would be used to store the speed of the vehicle in that interval of time. The speed of the vehicle would be captured from the GPS or Speedometer and it will be stored in the corresponding field.

The proposed system consists of three systems:

• Map matching
• Collecting and Storing the GPS/Speedometer Speed
• Optimum routing based on the dynamic speed information

Map Matching and Storing Speed data
The following flowchart describes the work flow in collecting/storing the speed in the attribute table. The map matching algorithm would be implemented in such way that, it will find the vehicle’s position on the road of travel. The GPS time or system time would be used to retrieve the speed stored in the corresponding field of the attribute table. A tolerance limit would be used to check/filter whether the current speed should be updated in the attribute data or not. The tolerance would be used to eliminate the unexpected speed data say, at the time of traffic jam, the speed would be near zero. At that time, this speed data should not be stored. This process will be repeated, whenever the vehicle is in motion.

Figure 3

Optimum routing
When a user requests an optimum route by keying origin and destination(s), at the time of 10.00 AM, the road length and the dynamic speed stored (in the field 10.00 AM to 11.00 AM) in the attribute against the request time range would be retrieved and the travel time would be calculated. The optimum route would be calculated based on this dynamic speed data (say the output as dynamic route1).

Similarly, when served the same request at 8.00 PM, the road length and dynamic speed in the attribute data (field 8.00 PM to 9.00 PM) would be used for optimum route analysis (say the output as dynamic route2). Conventionally, a Navigation system would deliver the same result at both instances. In real time scenario, the output should be different which is addressed by the proposed system. The proposed system has incorporated the dynamic changes, as the speed data used in both the queries are different. Finally, the proposed system would produce an output more closely to the real time scenario. A simple flow diagram of the optimum routing of the proposed has been given.

Figure 2

Limitations
The system depends on the positioning accuracy of the GPS. In this segment, there are more chances to identify the wrong or nearest road segment instead of the right one. The multi-path and high rise building would also affect the accuracy. Since Galileo is to be launched in the near future, the above limitations would be reduced.

In case of a traffic jam, the speed of the vehicle would be nearly zero. It may not be a regular occurrence or one-off incident where the vehicle speed is not the true representation for a long term basis. Hence, the value should not be used for storing the attribute data. An option could be provided to the user, to inform the system, whether the speed data should be included or not.

Benefits of the system
In the developed countries, the sign board along the roads show the time required to reach the predefined destinations. But, this information could not be used for optimum route analysis. Because, the information would be the travel time needed to reach the airport, railway stations etc. The driver/user would need the optimum route between origin and the destination(s). At present in the developing countries, there is no available system as described above. The proposed would address these issues efficiently, because there is no need of traffic congestion details from outside the system.

We have seen that, the market available navigation system gives solution of optimum route with the static travel time stored in the map data. The proposed will help to improve the navigation system and to act with the real time data. In the area of fleet management and logistics, this system would support planning their services.

Conclusion
We have detailed discussion on calculation of speed in the GPS, accuracy of the speed from GPS, comparison of GPS speed and Speedometer, and its usage in the proposed system of the In-Car Navigation system. The proposed system will improve the geo-spatial applications in telematics. The proposed system is an important alternative to the existing static systems.

References

1. Witte TH, Wilson AM. “Accuracy of non-differential GPS for the determination of speed over ground”, 2004
2. Massimo Dragan, Michele Fernetti and Vassilis Spitadakis “Geographical Awareness for Modern Travellers: A GIS Application for Maritime Transportation in the Mediterranean Sea”, 2004
3. Street, S. “Dijkstra’s Algorithm. SCC181 – Data Structures and Algorithms”, 2005