In this blogpost, we summarize what we have done after publishing the first progress report of ‘Algorithm models for maritime routes’ project. The following consists of 2 main parts including work done in front end and back end parts.
Path finding Algorithm
Finding the best route between start and destination points in the map is the same as finding the shortest path in the graph. At its core, a pathfinding method searches a graph by starting at one vertex and exploring adjacent nodes until the destination node is reached, generally with the intent of finding the shortest route. There are many famous algorithms such as Breadth First Search, Depth First Search and Dijkstra algorithm. However these algorithms are proportional to the number of vertices and edges of the graph. In the case of maps, these algorithms become impossible to use, because of the graph size. So, for the problems in maps it is more convenient to use the optimization algorithms – it is not guaranteed to get the shortest path, but the solution in average will be very good.
The current algorithm is an ant colony optimization algorithm. An ant colony algorithm is the algorithm for finding optimal paths that are based on the behavior of ants searching for food. At first, the ants wander randomly. When an ant finds a source of food, it walks back to the colony leaving “markers” (pheromones) that show the path has food. When other ants come across the markers, they are likely to follow the path with a certain probability. If they do, they then populate the path with their own markers as they bring the food back. As more ants find the path, it gets stronger until there are a couple streams of ants traveling to various food sources near the colony. Because the ants drop pheromones every time they bring food, shorter paths are more likely to be stronger, hence optimizing the “solution.” In the meantime, some ants are still randomly scouting for closer food sources.
Now we are implementing another optimization algorithm called ‘bidirectional search’. Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet in the middle.
After finishing this algorithm we will able to compare both algorithms. This also will find out which algorithm is more preferable for which case. Because, it is not only finding the shortest path but finding the path such that it considers wind, currents, sailing polars. For testing purposes we will run both algorithms in the same data.
We have quite large and informative dataset available for testing our progress. The important part of data is sea data and data containing geographical information of the given area. Also from previous project we have annual means of a sample drifter. We may use some part of this available data.
The interactive map, feature editing, and path drawing is completed on the front end. The only remaining tasks are to add the source/destination input mechanism, and the integration of the backend and the frontend. After these essential tasks are finished, a week can be spent on making the overall user interface prettier.
Overall, in the current stage we are adding new algorithm to the backend and it is going to take some time to test it and compare it with other algorithms. Also, in the frontend part we are going to implement ORBIS like system. In this stage, we are not sure whether we will have enough time to connect these two ends.
The code related to the front end can be found at following link :