Path assigned to the drivers, represented by [ ]
Plot of the time taken with and without the optimization for a 4x4 map and 50 drivers
Path assigned is taken as vector and a basic bot was built, which moves exactly as that vector and hence reach src to dest in shortest time
The 21st century ushered with it the age of smart and predictive technology with the optimum use of resources to make life easier and take preventive measures against predicted mishaps. In accordance with this trend, the proposal is an automated (SAE level 5) mode of transport using a modified Dijkstra’s algorithm with concepts of Ant Colony Optimization, big data analytics and cloud computing for number crunching to arrive at the destination based on the traffic and the number of drivers on the road, in the shortest time possible instead of the usual shortest distance algorithms. The analysis of the time saved by the drivers for different map types is recorded and compared and the results are found to be more efficient with respect to time as compared to the time taken by the original Dijkstra’s algorithm.
What it does
Start: the user is logged into the system as soon as the car is turned on. Choose the destination: The source and destination are chosen based on the current position as identified by the GPS system and the input by the user respectively. The path is set for the shortest travel time: Using the proposed modified algorithm, based on all the users currently logged onto the system and their current position and destination the route that takes the shortest time to travel is set. Automated transport: Using the grid based system where the inaccessible roads are blocked out by giving a very high value and the weight is taken in accordance with the speed the car can achieve on the particular road, the user is transported from source to destination. Arrive at destination: With minimal sensors, this automated mode transport uses big data analytics and cloud computing to ferry people from one place to another safely. Stop: Once the car is stopped, the user has logged off the system. The first part of the prototype consists of the modified Dijkstra’s algorithm in which the shortest path is determined based on the time taken and not on the distance between the source and destination. (how many people own cars) (statistically how many people would want to go to the same place at the same time in a particular place) If the shortest route is to take the I-16 and turn north towards the bridge, and all 100 people take the I-16 and turn north, then imagine the traffic jam a vehicle would be stuck in with the agonising honking and bumper to bumper traffic The whole ground can be represented as a grid or a matrix. A path can then be plotted based on the parts of the grid that are free. For example, if there is a pothole then that part of the grid can be made as inaccessible and will not show as a viable route that can be taken. Similarly to all the places that are on either side of the road.
How we built it
We built it using C++.
Challenges we ran into
To identify the parameters that were required to be considered and to make sure that the time complexity of the algorithm is as less as possible.
Accomplishments that we're proud of
The trial runs performed for a number of matrices of varying sizes and the time saved by each of the drivers were taken as an output and for a small map size of 10x10, the combined time taken was reduced by close to 26%. As the map size increases, we can observe that the time saved for each driver is increased. This shows that with the increase in map size that the real world scenario will have, the time saved will increase thus proving the efficiency of the modified algorithm and ensuring high performing automated cars.
What's next for Modified Dijkstra algorithm for optimal navigation
The future work would be to build a prototype of the model and go over the safety features in the case of a failure with a fine comb and to build a real-time web version of it.