Route Planning Algorithms For Car Navigation Computer Science Essay

Published:

Routing has been one of the greatest demands since decades. The techniques in finding a route improved drastically since decades with the advancement in technology. We have several routing algorithms like Dijkstra and A* to find a shortest path between two locations. Since there are millions of nodes and ways which constitute a real road network, these algorithms are supported by various techniques in improving search time, reducing the memory size and cost. We form a graph structure using the nodes and ways and implement them through the algorithm designed to find the shortest path between two locations. The output is thus shown on a User Interface application. The basis of this project is from the thesis report on route planning algorithms for car navigation.

There are many geographical applications on World Wide Web for mapping technology. One of the striking and emerging web mapping application is OpenStreetMap. The aim of OpenStreetMap is to create and provide digital map of the world to everyone through World Wide Web at free of cost. Wikipedia sets as a benchmark to OpenStreetMap in collecting information from various parts of the world through its registered (free registration through the website www.openstreetmap.org) users which also resembles a software development project developed by a set of people.

Introduction

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

In this section we are going to look into the basic idea of the project, aim, project description, motivation, challenges and objectives.

1.1 Brief idea

In ancient times, developing a route map is done only by high skilled engineers using many tools for accuracy. These maps were mainly used for adventures in the medieval period and are developed from heavy survey reports. And then for quite some time, it became the role of geographers, cartographers and surveyors to map the world and transcribe it into a paper or a computer [1]. But the technology has changed dramatically over the past 10years where every individual, small business and community organisations are bound with maps and mapping technology. Although there are many user-generated mapping projects, OpenStreetMap (OSM) is probably a most extensive, inexpensive and effective project currently under development which aims to get mapping information, use and edit them as required at free of cost. OSM emerged from the inspiration of the way Wikipedia developed. OSM was founded by Steve Coast in July 2004 at University College London (UCL). There were nearly 200,000 users registered with OSM by the end of the year 2009 [2].

Aim

The main aim of the project is to develop a stand-alone application for mapping the world much like Google maps but open for everybody to modify and add features on it. Interestingly, we are also going to trace a route from one location to the other using routing algorithms.

1.3 Project Description

OpenStreetMap is an open source map available for any individual who would like to get the information about the locations, street maps, geographical data, features etc., round the world. It gives a free access to all the necessary geographical information and an opportunity to edit, add, delete and update the map features according to the user's choice. Unfortunately, most of the maps as we think of as free will actually have either technical or legal restrictions on their usage, restricting many people in using them in different ways like applying creative thoughts, business, learning etc.

Motivation

In this modern world, the usage of maps to locate places & routes has become more extensible. People planning for longer trips would definitely need the support of some kind of maps to plan their trip in a systematic way which would save their precious time. They also need help finding the hotels, garages, hospitals, ATMs etc., on their way. It should be amazing to find all these features on one single application. On the other hand, planning a route on a road network has been a part of everyday life. There is a wide range of GPS systems online, offline and stand-alone form in use to find the routes across many countries, cities, towns in the world. This shows the optimum edge of a technical innovation. It is quite difficult to find transportation without these GPS systems in this modern world. This routing concept is much relevant in many gaming applications like racing, action, adventure etc., where the specimen in the game races against its opponents across various tracks (routes) or finds a destination by overcoming the enemies etc. Robotics is also an advanced technology where we use these routing concepts.

Main Challenges

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

Understanding the data sets provided by open street map.

Understanding the concepts of Geographical Information Systems (GIS).

Researching on the valuable data provided by OpenStreetMap.

Developing the logic for routing algorithm.

Creating a graph structure with respect to a OSM file.

Building a stand-alone application

Objectives

Learning and understanding the concepts of various routing algorithms and implementing one among them.

Designing the algorithm for the routing logic.

Traversing from one node to the other on a map depends on building an efficient graph structure.

Implementing logic of the algorithm with the graph structure.

Extracting and accessing data from OSM file.

Map Loading

Project Work Plan

Index

Task

Description

Dates

Days

1

Start of project

Spent on learning project basics

21st June- 26th June

6

2

Preliminary Report

Completed the report and planned project proceedings

28th June - 2nd July

5

3

Milestone1

Researched on theoretical information related to project

5th July - 16th July

12

4

Worked on Coding part related to algorithm

Relating OSM file with Graph Structure and algorithm

19th July - 23rd July

5

5

Interim report/Worked on algorithm coding

Writing Interim report, arranging interview with 2nd marker and developing algorithm code

26th July - 30th July

5

6

Milestone2/ algorithm coding

Preparing interview with second marker and implementing algorithm code.

2nd Aug - 6th Aug

5

7

Designing Graph structure and GUI application

Developing Graph structure and implementing it on a OSM file with the algorithm designed

9th Aug - 20th Aug

12

8

Dissertation Draft/Implementing graph structure

Writing Dissertation Draft

23rd Aug - 27th Aug

5

9

Dissertation/Implementing GUI application

Writing Dissertation and Implementing GUI application with Graph structure

30th Aug - 3rd Sep

5

10

Dissertation

Making final conclusions /Submitting Dissertation

6th Sep - 10th sep

5

11

Viva

Preparing Power Point Presentation and preparing for interview

Depends on the day of Interview

-

Literature Survey

This section speaks about the background and technical concepts which are being used in this project.

We start this with introduction to maps in section 2.1. Section 2.2 gives a brief idea about routing concepts. Then the technologies used in this project are explained in Section 2.3

2.1 Literature pertaining maps

2.1.1 Maps in general

Mapping technology is being used since decades. Initially maps were used only on a piece of paper but due to the advancement in technology, now maps are being used on websites, mobile phones, navigation devices, etc. Embedding maps into websites is termed as web mapping. The process of implementing, designing, delivering and generating maps on World Wide Web and its products is called as web mapping. Mobile maps are the special case of web maps where maps are displayed on mobile phone displays and smart phones.

http://en.wikipedia.org/wiki/Web_mapping

2.1.2 Existing maps

There are various maps provided by various vendors are in use on a day to

day life. Some of them are: http://en.wikipedia.org/wiki/Web_mapping

MapQuest: American based web mapping service owned by AOL.

MapGuide: An open source web mapping service.

Google Maps: A web mapping service provided by google.

Wikimapia: A privately owned service for commercial usage.

Ovi Maps: A free mapping service provided by Nokia for its mobile phones.

Paper based maps: Apart from all the above web maps, we still have paper based maps in usage on a considerable scale. Example: London tube station

2.2 Literature pertaining Routing

Finding path from one place to the other is considered as Routing in general terms. On a computer application, it is of plotting a shortest path between two points. Unknowingly, everyone come across this concept in video game applications where the hero or a moving entity overcomes many obstacles and finds a route to the destination. This importance of routing concept is growing rapidly as the games and its environment is becoming complex in the real time strategy video games. Robotics is another interesting field which involves the concept of routing for a robot to move from point A to point B taking a shortest path without running into the objects.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

Navigation systems are mainly designed for use in automobiles. It uses the Global Positioning System (GPS) signals to determine the present location of a user on a road from the unit's map database. The concept behind a navigation system are positioning and routing, by first finding the location of vehicle on the road network and then the shortest path from source to desired destination. The map embedded into the navigation system's database is called a vector map. Navigation systems receive information from a Travel Message Channel (TMC) and provide the current traffic information with alternate routes to avoid traffic (if applicable). http://www.2carpros.com/how_does_it_work/navigation_system.htm

Route planning systems used in all the navigation systems are supported by some routing algorithms to determine the path from source to destination. Performance of all the networks is completely dependent on these routing algorithms and is considered as the brain of the network. Dating back 1736, Euler's questioned "Was it possible to find a path through the city crossing each of its seven bridges once and only once and then returning to the origin?" and is considered as the initial era of modern path finding. Graph theory is a result of Euler's methods and this theory paved the way for route finding algorithms. Implementing the route planning on a long distance road network needs finding an optimal path from source point to the destination point. Here "optimal" refers to shortest time or shortest distance or least total cost of a path. Several algorithms are known to find a shortest path between two points. But Dijkstra shortest path algorithm forms a basic platform to the rest of the shortest path algorithms. http://www.globaljournals.org/vol_9_issue_5_ver_2.0/Vol_9_Issue_5_Ver_2_14.pdf

A communication network is generally made up of nodes and links. Nodes are connecting points in the network while the links are referred to a path connecting two nodes. Links are also termed as edges in the networking terminology. Traffic flows from one node to the other in a communication network. Traffic originating from a node is referred to as a start node or a source node while the traffic destined to a particular node is termed as an end node or a destination node. Basic requirement of any communication network would be routing traffic from a start node to an end node. In order to do this we need to determine the route, which is a path from start node to an end node. One way of doing this is by setting a route from one node to the other manually which is called a static route. But complexity matters while using a huge network to use a static route from one node to the other. On the other hand, determining route from a start node to an end node can also be done efficiently by using a routing algorithm. A routing algorithm can be designed according to the requirement of a network by imposing specific conditions on it depending on service provider interest.

One of the basic routing algorithms is Dijikstra algorithm. Dijikstra algorithm can also be called as shortest path routing algorithm. That is, the task of this algorithm is to find a shortest path from a source node to a destination node from all the possible paths available. The term shortest path on a general road network is termed as a shortest distance between two cities (nodes). Sometimes shortest path also refers to time. Since there are many unit of measurements which can be considered on a general basis, it would be outstanding if our algorithm works independent of measuring unit by just considering any measuring unit in terms of cost (link cost).

Figure 2.2.1: A simple network with 6nodes

From the above Fig2.2.1, the entry shown next to the link is the cost of the links between the nodes connecting it on either side. By simple observation we can identify a shortest path between any two set of nodes. When we consider the shortest path between node4 and node6, we get 4-3-6 with a distance of 2 although there is a direct link between node4 and node6. In this way shortest path from a source node to a destination node is computed by adding link costs of all the edges on a path considered until destination node.

Network Routing; Algorithms, protocols and architectures; Deepankar Medhi, Karthikeyan Ramasamy

2.2 Literature pertaining Routing Algorithms

Routing algorithms are use to find a shortest path between two locations. Study of various algorithms is as follows:

2.2.1 Dijkstra Algorithm

Dijkstra algorithm is computed as follows:

Assign some initial distance values to every node in the graph and the values are further revised if any other shortest distance is available.

Set the initial distance value to zero for source node and infinity to every other node in the graph as shown in the above figure.

Consider all the unvisited neighbours of a Current (Source) node & calculate its tentative distance from the Current node & update the minimal distance by overwriting.

After calculating the distance to all the neighbour nodes, mark them as Visited. These Visited nodes are never checked again & the distance calculated is confirmed to be minimal.

When all the nodes on a graph are considered to be visited, finish. Else repeat the above process for any other unvisited node.

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Further Dijkstra algorithm is explained in detail in the Section 3.1

2.2.2 A* Algorithm

A* algorithm implements the approach of Dijkstra algorithm to find the shortest path and the Heuristic approach of Greedy Best-First-Search algorithm to estimate the cost from the current node to the destination. Only the basic idea of this algorithm is illustrated in this paper and is as follows:

First we divide our search area into a square grid. Further, A* algorithm starts with usage of simple terms like "open list & closed list". The nodes which we are currently working with are considered to be in an open list & the nodes which were already explored are considered to be in a closed list. We begin our search at a source point A & add it to the open list as we are working on this point to explore the path. Then we find all the reachable squares adjacent to the source point ignoring the squares with walls, water etc and add them to the open list. Then we add the point A to the closed list after exploring all the squares around it & adding them to open list. Determining the next square in the path is done by the following equation:

F = G + H

Where,

G = the exact cost to the current square from the starting square.

H = the estimated or Heuristic cost from the current square to the destination.

F = total cost (G + H).

G cost: G cost of the current square is calculated from the G cost of its parent square. We just consider the G cost of its parent square and add 10 if it is a horizontal or a vertical move and add 14 if it is a orthogonal move.

H cost: H cost is estimated by calculating the total number of squares from the current square to the destination square using only the horizontal & vertical moves ignoring any obstacles. We them multiply the total by 10.

Continuing search: Then we select the square with the lowest F cost square adjacent to the current square and perform the following with the selected square:

Add the selected square to the closed list by dropping it from open list

Ignoring the closed list squares & any obstacles, check all the adjacent squares

If an adjacent square is already on the open list, check to see if the G score for that square is lower if we use the current square to get there. If not, don't do anything. 

  On the other hand, if the G cost of the new path is lower, change the parent of the adjacent square to the selected square. Finally, recalculate both the F and G scores of that square. http://www.policyalmanac.org/games/aStarTutorial.htm

Literature pertaining technologies

XML

XML is abbreviated as Extensible Markup Language. It is a set of rules to convert documents into machine readable language. XML serves as a basis to use highly structured documents over the web. It is a markup language for all the documents that contain structures information. Here the markup represents that its content in a document starts with a character "<" and ends with a character">". XML documents consist of tags, elements and attributes. XML documents starts with declaring some information about themselves like <?xml version="1.0" encoding="UTF-8" ?>. Below shown is a small file which uses all the constructs of an XML file.

<?xml version="1.0" encoding="UTF-8" ?>

<learning>

<img src="art.jpg" alt='Stuart, by Lisa'/>

<caption>This is Lisa's "Map" Map, downloaded in

<date>2805</date>-<date>2301</date>.

</caption>

</learning>

Understanding XML document is an important task in this project as we perform all the operations on it.

http://www.xml.com/pub/a/98/10/guide0.html?page=2 &

http://en.wikipedia.org/wiki/XML

Windows Forms

It is a graphical application programming interface used in Microsoft framework. It is just equivalent to Java API providing GUI components. It has a set of managed libraries simplifying the task of reading a file system. It uses visual forms to display information to users. We can generate various Windows Forms easily by adding controls to the form while developing responses to user actions. It has rich User Interface controls to develop high-end applications. http://msdn.microsoft.com/en-us/library/8bxxy49h.aspx

Design of Algorithm and Concept of Graph Structure

In this section we are going to look into algorithm description and the

concept of graph structure. Section 3.1 gives a detailed explanation of Dijikstra algorithm which is being used in this project and Section 3.2 explains the concept of graph structure.

3.1 Dijikstra Algorithm

Consider a node i from a list of N nodes in network. Let i be the source node from where we want to find the shortest path to all other nodes in the network. Let j (i ≠ j) be a destination node in the network. And let N = {1, 2, 3,..., N} represent a list of N nodes. We consider the following terms:

dij = link cost between nodes i and j

Dij = minimum link cost between nodes i and j

In this algorithm, we consider list of N nodes into two lists of categories: visited & not visited. The list of visited nodes is represented as A and list of not visited nodes is represented as B. Initially we have list A = {i} and list B = {all nodes in N except i}. As the algorithm advances with implementation, list A keeps expanding with the new nodes adding to it while the list B shrinks with the nodes deleting from it. Hence the algorithm stops when the list B is empty.

The basic implementation of the algorithm constitutes of two parts: 1. Expanding list A with new nodes adding to it. 2. Computing shortest path to neighbours of all the nodes in the list A. After each iteration, list A is expanded by considering a neighbouring node k of node i with minimum cost path from node i. After each iteration, the neighbouring nodes of k are then considered to check to see if the least cost to the node i changes from the last iteration.

Let's implement Dijikstra algorithm to Figure 2.2.1 and check how it works. Consider node1 as a source node and find shortest path to all the remaining nodes in the network. So initially, A = {1} and B = {2, 3, 4, 5, 6}. Only the neighbouring nodes of node1 have the link costs known whereas the remaining nodes are considered as infinity.

i.e, D12 = D13 = 1, D14 = D15 = D16 = ∞

So, after certain number of iterations, the shortest path from node1 to all the remaining nodes is computed & is shown in the following table:

Network Routing; Algorithms, protocols and architectures; Deepankar Medhi, Karthikeyan Ramasamy

Iteration

List (A)

D12, Path

D13, Path

D14, Path

D15, Path

D16, Path

1

{1}

1, 1-2

1, 1-3

∞ -

∞ -

∞ -

2

{1,2}

1, 1-2

1, 1-3

3, 1-2-4

∞ -

∞ -

3

{1,2,3}

1, 1-2

1, 1-3

2, 1-3-4

2, 1-3-5

9, 1-3-6

4

{1,2,3,4}

1, 1-2

1, 1-3

2, 1-3-4

2, 1-3-5

3, 1-3-4-6

5

{1,2,3,4,5}

1, 1-2

1, 1-3

2, 1-3-4

2, 1-3-5

3, 1-3-4-6 or 1-3-5-6

6

{1,2,3,4,5,6}

1, 1-2

1, 1-3

2, 1-3-4

2, 1-3-5

3, 1-3-4-6 or 1-3-5-6

Table 3.1: Iterative steps for Figure 2.2.1 using Dijikstra algorithm

The shortest path from node1 to the remaining nodes using Dijikstra algorithm is illustrated in the following Figure 3.1

Figure 3.1: Shortest Path illustrated based on Table 3.1

Graph Structure

3.2.1 What is a Graph?

A graph is a collection of a set of dots which are interconnected with each other by lines. In the graphical terms, dots are called as vertices and the lines connecting set of dots is called as edges. Vertex is also called as a node. Vertices may be of any size and any shape. Similarly edges may be of any length and are of straight lines, curved lines or squiggly. A set of vertices can be connected by only one edge. Using the graph data structures, each edge can also be represented with an edge value in terms of a numeric value for attributes like cost, distance, capacity, etc.

Figure 3.2: A graph of 6vertices and 7edges

In the field of computer science, a graph is considered to be an abstract data structure which implements the graph concept from mathematics. An abstract data structure or an abstract data type is a mathematical model for certain class of data structures of one or more programming languages that have similar semantics.

A graph can be represented in two types: directed and undirected. In a directed graph (G, x,y), we can traverse only in one direction, that is from node x to node y. These kinds of graphs are also called as unidirectional graphs. In a undirected graph (G, x,y), we can traverse from one node to the other in either directions. That is, we can traverse from node x to node y and vice versa.

A simple illustration of a graph data structure is shown in the following figure:

Figure 3.2.1(a): Input Figure 3.2.1(b): Output

3.2.2 OSM files with respect to Graph Structure

Open Street Map (OSM) files can be extracted from openstreetmap.org for any certain region in the world. So, in this way we extract an OSM file of our interest, display it on windows form and find shortest path from one place to the other on that map. Surprisingly, at the backend we need to create a graph structure for a selected OSM file such that we can traverse from one place to the other to find shortest path. So, initially let us see what kind of information is available in OSM file and how it is useful to us. OSM files are in XML format. Basic elements in an OSM file are nodes, ways, latitude and longitude which afre explained below. There are many other attributes in an OSM file but we are not interested in those terms with respect to our project.

3.2.2.1 node

A node represents a basic element, a building block of an OSM scheme. It consists of longitudinal and latitudinal parameters. Nodes are always helpful in defining a way. Any unconnected point like cell phone tower can also be termed as a node. A node may or may not have a tag. Node ids takes integer values greater than or equal to one.

<node id='26462971' timestamp='2007-03-10T18:02:04Z' uid='2851' user='morwen' visible='true' version='1' changeset='233252' lat='52.6264706' lon='-1.1141909'>

3.2.2.2 way

It represents an ordered interconnection of at least two nodes and at most 2000 nodes. way represents a sequence or a series of nodes interconnected to form anything such as street, footpath, river, fence etc. way id is considered as any integer greater than or equal to one. A way id can be same as a node id. A closed way is a way that contains the first and the last nodes identical. http://wiki.openstreetmap.org/wiki/Data_Primitives

<way id='4344843' timestamp='2007-12-30T16:22:42Z' uid='2851' user='morwen' visible='true' version='3' changeset='480842'>

<nd ref='26462975' />

<nd ref='26463014' />

<nd ref='26463013' />

<nd ref='26463012' />

<nd ref='197707443' />

<nd ref='26463011' />

<nd ref='132169862' />

<nd ref='197707440' />

<nd ref='26463010' />

<nd ref='197707437' />

<nd ref='26463009' />

<tag k='highway' v='secondary' />

<tag k='name' v='East Park Road' />

<tag k='ref' v='B6416' />

<tag k='source:ref' v='NPE' />

</way>

3.2.2.3 latitude and longitude

Every location on the earth is specified or indicated by two parameters namely latitude and longitude. These parameters also help us to locate a specific location on map. Latitude is a horizontal line on the earth sphere and is defined with respect to an equatorial reference plane. This plane passes through the equator located at the centre C of the earth sphere. Latitude ranges from -90 to +90.

Longitude is a vertical line on the earth sphere and is defined as an angle that a plane containing the meridian passing through a point P subtends with respect to the plane containing the prime meridian. Longitude ranges from -180 to +180.

3.2.3 Concept of creating a Graph Structure

Before we could start creating a graph structure, let us consider the following syntax from an OSM file.

<node id="9922705" lat="52.6280917" lon="-1.1208633" user="smsm1" uid="6871" visible="true" version="3" changeset="804029" timestamp="2009-03-13T23:29:11Z">

<tag k="highway" v="traffic_signals"/>

</node>

In OSM file, every syntax starting with the tag "<x" and ending with tag "</x>" is considered as a NODE for our future reference. And syntax starting with tag "<x" and ending with tag "/>" is considered as a sub NODE for our future reference. Example: In the above syntax, <node id=.... </node> is called as a NODE and

<tag k="highway"v="traffic_signals"/> is called as sub NODE.

Elements like minlat, minlon, maxlat, maxlon are called as attributes in an OSM file.

The reason behind considering the above process is: when we try to get or read or retrieve a NODE from OSM file, we get all the attribute values (minlat, minlon, maxlat, maxlon) of a node, which is helpful to us in locating the location of a node. In this way we read the values of all attributes from all the NODES.

Now, the first step in creating graph structure is to read a NODE called "Bounds" from an OSM file. The reason behind this is, "bounds" specifies map boundaries (for a selected OSM file).Based on this information we form a URL.

Now our task is to get all the ways from an OSM file. That is, we get all the NODES which start with "ways". Then we process each and every way, read all the node ids corresponding to each and every way and store them in an array. At the same time we calculate the distance of subsequent nodes and store them in array. After processing and reading all the ways and storing the nodes in an array, we get the total number of nodes available. So, now we get to know the total count of nodes present in array and thus we can declare this array as a two dimensional array which in turn forms an n x n array.

We have read all the ways and its node ids from an OSM file. Now we need to link all the ways together to form a graph structure. This can be done by the following method: When we observe the ways in an OSM file, every way has at least one node id which is a part of another way. In case, if there is any way which doesn't have a node id being a part of some other way, we place that way as independent. In this way we form a graph structure by reading all the ways, nodes and calculating distance between subsequent nodes. The graph structure which is being implemented in this project is considered to be dynamic. That is, it works with any OSM file loaded into it.

This graph structure is thus processed into the algorithm logic stated in section 3.1.1 to compute the shortest path between source node and destination node. The node ids which we already read from OSM file helps us to show a path between source and destination.

System Design

Implementation plays a key role in any project. For a successful implementation we need to plan a considerable system design. Here, identifying main blocks of the system and designing them separately is very important. In Section 4.1, we are going to look into the requirements needed for a system design and in Section 4.2; we describe the overall system design.

4.1 Requirements

There are some requirements needs to be satisfied by end product of the project. Typically, this can be classified into two types: Functional and Non Functional requirements. Functional requirements pertain to actual functionalities needed to implement the project properly. Functioning of a software system and its components is generally defined by functional requirement. Functional requirements define specific functionalities (technical details, calculations, processing, data manipulation, etc.) about what a system is supposed to accomplish. Whereas Non functional requirements describe specific functionalities about how a system is supposed to work. Non functional requirements are otherwise called as quality requirements.

The functional requirements are as follows:

Accessing and reading the XML file.

Create Graph structure for the specified OSM or XML file.

Compute shortest path.

Design using windows form.

Display Map and show route.

The non functional requirements are as follows:

Interoperability: Synchronisation of all the tasks is highly demandable quality for a smooth and perfect running of an output.

Performance: It depends on how well the output is represented.

Quality: It depends on the feel and look of the outcome.

Maintainability: The data and the logic need to be maintained in such a way that they can be modified easily whenever it is necessary.

Usability: It depends on the ease of handling the tool.

Confirm ability: Verification of output generated.

Reliability: Functionality of the outcome should be efficient and consistent to handle errors.

Apart from the above two requirements, it is also important to consider the user requirements. User requirements define all low level and high level requirements and are listed as follows:

Loading an OSM file

Navigation on Map

Submit Selection

Select source point

Select Destination point

Perceive Path information

The use case diagram for User requirements is shown in the below figure.

Figure 4.1: Use Case diagram for User Requirements

Overall System Design

System design gives a complete idea of the project through its architecture, components, interfaces and data by satisfying the desired requirements. Thus, the system architecture is shown in the following figure.

Graph

Structure

Front End (GUI Layer)

Logical

Layer

Data (OSM File)

Figure 4.2: System Architecture

The components of the System Architecture are explained as follows:

The Front End layer is a Graphical User interface application, which gives the visualization of output. Here, the map is displayed and the shortest path is shown.

The Logical layer is the part where the algorithm implementation takes place for the graph structure of a specific OSM file.

Graph structure is created for a selected OSM file.

The complete operation is done on this data which is an OSM file extracted from openstreetmap.org. This OSM file is in XML format.

Front End

Front end is a User Interface application.

A user interface (UI) allows user to interact with programs easily through images rather than text commands. The first user interfaces to computer were not graphical, instead they are text and keyboard oriented which involves a lot of commands which we had to remember in order to respond to computer. DOS prompt in a computer is a typical example of a user-computer based interface before GUIs existed. The evolution after the command line interface is also a non graphical menu based interface which helps us to interact with a mouse rather than using a keyboard to type in the commands. Today major operating devices or appliances are based on GUI which makes user to access computer easily http://searchwindevelopment.techtarget.com/sDefinition/0,,sid8_gci213989,00.html

. It makes user tasks easier by combining the technology and devices to gather and produce information through its application. The ease depends on the way of handling different activities on the computer, queries to and from the computer using graphical elements like icons, pull-down menus, scroll bars, windows and dialog boxes which are controlled by a mouse click. In this way GUI uses various graphical elements to represent the information in a fully fledged manner to a user. It depends on individual skills that how beautiful you represent the information using GUI application. Everyone in this world keeps using GUI devices in a daily life. Simple examples of such devices are mobile phones, mp3 players, office equipments, gaming devices, household appliances etc. World Wide Web is another example of a GUI application which is supported through some browsers. GUI is commonly used on two-dimensional displays.

In our project, front end layer is a windows form showing the map display. As stated in the requirements section, the front end tool should perform the following tasks:

Loading an OSM file

Navigation on Map

Submit Selection

Select source point

Select Destination point

Perceive Path information

Logical Layer

Logical layer pertains to the implementation of Dijikstra algorithm which is explained in the Section 3.1.

Graph Structure

Graph structure is also explained previously in section 3.2.

Implementation Process

Here we are going to discuss the implementation of several phases which were discussed in System Design.

Technical specifications

Operating Systems: Windows Vista

Technologies: Windows Forms

Programming Language: C#.net

Software Development Kits (SDKs): Microsoft Visual Studio 2008

We need to make sure all the necessary tools are installed into the system before we could start implementing.

System Implementation

System implementation is the implementation of System Design discussed in the Section 4.2. The main focus of system implementation is divided as follows:

Algorithm implementation

Game Structure implementation

User Interface

5.2.1 Algorithm Implementation

The logic for algorithm is designed and implemented as follows:

http://shobhitsharda.wordpress.com/2010/07/31/implement-dijkstras-algorithm-in- c/

for (int index = 0; index < noOfNodes; index++)

{

visitedNodes[index] = index;

nodesDistance[index] = PathArray[minimumNode, index];

if (PathArray[minimumNode, index] > 0)

{

tPath[index] = Convert.ToString(minimumNode) + "," + Convert.ToString(index);

}

}

visitedNodes[sourceNode] = -1;

for (int j = 0; j < noOfNodes; j++)

{

double minValue = double.MaxValue;

for (int k = 0; k < noOfNodes; k++)

{

if (visitedNodes[k] >= 0)

{

if ((nodesDistance[k] > 0) && (nodesDistance[k] < minValue))

{

minValue = nodesDistance[k];

minimumNode = k;

}

}

}

visitedNodes[minimumNode] = -1;

for (int l = 0; l < noOfNodes; l++)

{

if (visitedNodes[l] >= 0)

{

if (PathArray[minimumNode, l] > 0)

{

if (nodesDistance[l] < 0)

{

nodesDistance[l] = PathArray[minimumNode, l] + minValue;

tPath[l] = tPath[minimumNode] + "," + Convert.ToString(l);

}

else if((PathArray[minimumNode, l] + minValue) < nodesDistance[l])

{

nodesDistance[l] = PathArray[minimumNode, l] + minValue;

tPath[l] = tPath[minimumNode] + "," + Convert.ToString(l);

}

}

}

}

}

Graph Structure Implementation

This section describes the implementation of a Graph structure for a given OSM file.

Once we are ready with the algorithm logic, we proceed further by creating a graph structure and find the shortest path by implementing algorithm logic on this graph structure.

Here we are going to create a Data Table without the help of any database. This is done by using various .Net classes to retrieve data from an XML file and form a graph structure. Perhaps, .Net classes are capable of accessing XML files faster. Creating a graph structure starts with creating a DataTable and accessing data from it. It is as follows: http://www.dotnetfunda.com/articles/article131.aspx

-$- We start creating a DataTable by defining,

DataTable sDataTable = new DataTable("Locations");

-$- Then we start adding the node ids and way names from an OSM file into DataTable as follows:

sDataTable.Columns.Add("vertexId");

sDataTable.Columns.Add("WayName");

-$- In this way we extract all the ways from an OSM file by using XmlNodeList ways = xmlDoc.GetElementsByTagName("way");

foreach (XmlNode way in ways)

{

XmlNodeList vertices = way.SelectNodes("nd");

foreach (XmlNode vertex in vertices)

{

if (!verticesArray.Contains(vertex.Attributes["ref"].Value))

{

verticesArray.Add(vertex.Attributes["ref"].Value);

}

}

size = verticesArray.Count;

graph = new double[size, size];

for (int i = 0; i < size; i++)

{

for (int j = 0; j < size; j++)

{

graph[i, j] = -1;

}

}

foreach (XmlNode way in ways)

{

XmlNode prevVertexNode = null;

XmlNodeList vertices = way.SelectNodes("nd");

foreach (XmlNode vertex in vertices)

{

XmlNode currVertexNode = xmlDoc.SelectNodes("osm/node[@id=" + vertex.Attributes["ref"].Value + "]")[0];

if (way.SelectNodes(@"tag[@k=""name""]").Count != 0)

if (!ht.ContainsKey(currVertexNode.Attributes["id"].Value)) ht.Add(currVertexNode.Attributes["id"].Value, way.SelectNodes(@"tag[@k=""name""]")[0].Attributes["v"].Value);

if (prevVertexNode != null)

{

CalculateDistance(prevVertexNode, currVertexNode);

}

prevVertexNode = currVertexNode;

}

}

Further Graph structure implementation is shown in the above program. Here, we get all the distinct nodes from the OSM file and store them in the array. Thus we declare the array size here and form an n x n array. Then we process through each way one by one, to read all the node ids in each way. Initially we assign the value -1 to the whole array assuming that there is no path between any two nodes (1st for loop in the above program). Then once again we process through all the nodes in each way to calculate the distance between the subsequent nodes in a way and store it in our n x n array (third foreach loop in the above program illustrates this).

In this way as explained in the section 3.2.3, we create a graph structure using .Net classes as shown in the above program.

6. Conclusions and Future Work

6.1 Conclusion

OpenStreetMap is based on the thesis report submitted by Ingrid C.M. Flinsenberg, on route planning algorithms for car navigation system. It states that the combination of routing algorithms with open street maps defines the routing for open street maps. We all use the mapping services on a regular basis to plan our travel. In the same way, even I am closely related to the mapping services like Google & Nokia Ovi maps(on my mobile) to find route between locations. I thought it would be interesting to know what is happening behind the map to provide us such an excellent map service. And hence, this interest drove me into this project.

The aim of this project is to use the free data provided by openstreetmap.org and implement the routing concepts to show a shortest path. Initially, I have started implementing the routing algorithm which took considerably more time than expected to implement the logic perfectly. First, I thought of implementing Dijkstra algorithm which forms as a basis for any other routing algorithm and try to implement some higher level algorithms like A*. But since I got stuck with Dijkstra algorithm for a while, I restricted myself to implement Dijkstra algorithm for this project considering the time factor to implement several other things in this project. Then as I understood that OpenStreetMap works on the basis of spatial database, I thought of implementing this project through a simple Sql database. But I found that it is much easier to access and read an XML file through various .Net classes, I made use of this technology to save a considerable time. The shortest path need to be shown on a User Interface application by displaying a map, which I am working on it now through Windows Forms (.Net).

6.2 Further Work

So far I was successful in implementing the routing algorithm and the graph structure. Right now I am working on GUI application to show the map display and the shortest path from one place to other.