Link

Roshit Anand (@roshit-anand)

My own Google Map

Introduction

MY maps aplication is based on the basic A* algorithm with some changes to increase the speed and efficiency of the algorithm.

Stored Data

First of all what will be the data and from where will we get it.

The data will the maps and the basic routes that all the from large cities to others that are already known like national highways,interconnecting cities highways/flyovers etc.

The maps will formed by merging the data obtained by road detection algorithms on satatlite images and data obtained from Govt. organisations. All this data will be improved and upgraded with the help of gps used by normal drivers.

The data attained by the gps can be used in many ways. As the gps uses the time delay in the signal from phone to the corresponding towers we can calculate the speed and an average speed on a road can used to get a tentative idea of speed limit on that specific path. Different speeds can also help us in finding paths like walking pathways(speed btw 2km/hr to 7km/hr), cycling pathways(speed btw 10km/hr to 18km/hr) and with keeping some error in mind we can also find which in direction the drivers are allowed to drive on a specific road.Gps can also help us in finding newly contructed roads as we can use a threshold like if about 20 cars per day passes through as route that is known in maps we can improve the maps.

Talking about stored routes,the routes will be stored region wise in different servers all connected with a single network. For eg for India only we will have 2 servers which will further have different bifractions in which all the data of a specific region will be stored.The as the app searches any new shortest path for which it took more than a specific timelimit the new shortest path from A to B it will be stored in the servers so when ever it is needed can be used. Describe the data attributes involved.

Computing Quickest/Shortest Path

We will be using the well known A* algorithm with some changes which will help us to get the shortest paths and the fastest path.For this first A* algorithm. In this algorithm the path finding is preffered in the direction of by using a new variable that is euclidean or manhattan distance from the position we are standing and we have to go .There is a cost calculated by adding the distance btw the nodes and the euclidean distance btw that node and the final node and the algo aims for the lowest cost to reach there.

But if we use the gps to attain the average speed of a road or path at a specific time interval and we use the time=distance/(avg speed) instead of the distance btw nodes and the euclidean distance/(avg speed of that car) instead of euclidean distance(so to keep all the data in same measuring terms) we can find the fastest and mostly the shortest path. In total every one choses shortest path to get to destination as fast as possible.

We can use the already found paths and shortest distance btw two loactions . We can search them while we run anytime-A* algorithm in background to get the get the fastest results and as we can terminate the algorithm anytime we can use the stored found paths to join the paths eg if someone wants to go to A to C and B,C cames in btw them so when we get that we have to go through B we can add the path (already found and stored in server) from B to C to quickly provide the solution. But this implementation is pretty difficult and should only be used when we have a large database of routes.

We can use the anytime A* alorithm instead of simple A* with all the changes mentioned above as it provides an early answer too(on cost of accuracy) and can also help in a situation like mentioned below.

Will you be able to reroute quickly if the user takes a different turn?

With the help of anytime-A* algorithm we can terminate it anytime and use the previous found info to find the new path if the user takes a different turn and it will be faster as we have the info from previous operation that which path to take and which not to.

Efficiency and Feasibility

The implementation is pretty difficult but if implemented correctly can provide a good output.

Theoretically, how would it perform? Who am i to say, well as per my knowledge it should work. Do you think it can work on the scale of the globe? It will take a lot of time to as there are different kinds for informations that it requires to work and this needs first of all to collect a lot of informations.But yeah it can work on global scale.