Navigation Algorithms

During simulation, every vehicle in the system is driving through a route from its source to its destination. The route is computed using saved statistics and heuristics. The statistics represent the expected time it takes to drive on each road or wait on each traffic-light at every time of the day.

The heuristics are the minimal time it can take to drive from one road in the map to every other road. These heuristics are obtained using Floyd-Warshall algorithm for APSP, and the graph weights are the minimal time (when there is no traffic) it takes to pass every road and every traffic-light.

Using these heuristics and the saved statistics, we can run an A* algorithm to find the shortest possible route from every two points in the map, where the real weights in the graph are the expected time to pass every road and traffic-light when the vehicle stars driving.

That is exactly how the naive navigation (choose NaiveNavigationManager in the application) is done.

The problem with this algorithm, is that it does not take into account the progress of the vehicles and the changing traffic during driving.

For this purpose, we designed the smart navigation algorithm (choose StatisticsNavigationManager in the application):

---

1) partialRoute <- [sourceRoad]

2) time <- timeToStartDriving

3) statistics <- getStatisticsForTime(time) 

4) while partialRoute[last] != destinationRoad

   4.1) tmpRoute <- A*(partialRoute[last], destination, statistics)

   4.2) nextRoad <- tmpRoute[2]

   4.3) partialRoute <- partialRoute + [nextRoad]         (appending)

   4.4) nextTime <- statistics.getExpectedTimeOnRoadAt(nextRoad, time)

   4.5) time <- time + nextTime

   4.6) statistics <- getStatisticsForTime(time)

5) return partialRoute 

---