Even though there exists many solutions for navigation on land routes, we don’t have similar tools for maritime routes. Maritime routes are not as regularized as land routes. In land, we have predefined roads and crossroads, on the contrary, a ship can always change its direction at any point at sea. This possibility makes finding the optimal route problem harder.
Our goal was to find an algorithm to estimate the ideal route in a reasonable amount of time and make a web based user friendly interface to visualize the route. We started with a literature review and looked at the existing solutions for finding the shortest path problems that would be applicable to our particular problem, which is finding the shortest path on sea.
Last year, a group proposed a model and an algorithm to estimate the routes taken by maritime vessels. This model takes into account that the sailing ships travel at different speeds depending on the wind’s direction and speed and this fact may alter the best path from a straight line to a more curved path. We decided to build on this model and assumptions and make further decisions to improve both the performance and the usability of the existing work. We chose and implemented a new algorithm for finding the shortest path and offer our motivations for these choices and results in this post.
We wanted to visualize our solution path for the cities entered by user on the map based on the historical data of the sea current and wind of medieval times. Unfortunately, there are no sources containing exact marine data for earlier than 19th century. Modern records of climate only began in the 1880s. We have found some research to provide a means for scientists to determine climatic patterns before record-keeping began. So, we had only one choice of using the data available and assume that the wind and current patterns in medieval times did not significantly differ from contemporary weather conditions.
We used available hydroclimate data for our calculations from QuickSCAT. QuikSCAT mission by NASA is intended to record sea-surface wind speed and direction data under all weather and cloud conditions over Earth’s oceans. They use satellite based sensors which can provide measurements over the entire globe. More precisely, we have quite large data available for the weather conditions such as wind speed , sea current etc. encompassing the years of 1997-2008. We averaged the data and found the year that has the similar data to it and used that year in representation. In our case the year was 2004. The motivation for this was to prevent unusual wind changes in an arbitrary day to introduce possible errors or bias.
Shortest path finding algorithms
As mentioned,in order to find optimal path between two nodes on graphs there exists many different algorithms. These algorithms are called shortest path finding algorithms. Among shortest path finding algorithms different algorithms have different pros and cons over others depending on the situation and problem statement, so for path finding algorithms usually there is not any optimal algorithm that we can say always works better than others if we have not further details.
In simple dense graphs, we can run deterministic algorithms which will find the shortest path between two vertices or nodes in a graph. For example, DFS, BFS, Dijkstra, Floyd-Warshall, etc. But the problem is when you switch from simple dense graphs to our map representation, which are dense graphs with at least 8 edges from every node, the search space dramatically increases because the number of ‘edges’ and ‘vertices’ are extremely big in our problem. We can’t run these deterministic algorithms on our maps because it consumes a lot of memory for long distances and the program takes a long time to run. In dense graphs, optimization algorithms which do not find the shortest path deterministically but estimate some short path, is preferred.
There exists different kinds of optimization algorithms for finding the best path in graphs. The algorithm that was used last year was ‘Ant-colony optimization’ algorithm. In short, this algorithm is based on swarm intelligence methods and it is composed of some metaheuristic optimizations.
One of the frequently used algorithms other than ‘Ant colony optimization’ is A* search algorithm. A* is largely used in pathfinding and graph traversal, because of its performance and accuracy. It plots an efficiently traversable path between multiple points, called nodes, which are the vertices of the graph. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, although some other investigations has found A* to be superior to other approaches. We applied A* algorithm to our shortest path finding problem.
The heuristic function is the main component of A* algorithm. It guesses how we can reach the goal by informing the search algorithm. In mathematical terms, the heuristic function h is defined by taking values of vertices and returning a real number as h:V->R, where R is for real numbers and V is the vertices of graph. For using this function we need to have some information on graphs, so this function can not be always used. If you have no idea how close you are to your target – you cannot use any heuristic function, since you have no information. Depending on how we choose the heuristic function there is a tradeoff between running time and optional solution. In our problem, the heuristic function can be the manhattan distance – which is calculated by h(v) = |t.latitude – v.latitude| +|t.longitude – v.longitude|, given the destination port t and starting port v. At one extreme, if h(n) is 0, which means we don’t have heuristic values for the nodes in graph, A* optimization algorithms turns into Dijkstra’s algorithm, which is guaranteed to find a shortest path.
Comparison of algorithms
Although both A* and Ant colony optimization try to find the shortest path between two nodes, there is a fundamental difference in their core idea. Ant-colony optimization is kind of modified version of Depth First Search. Each ant tries individually to find route and other ants join to the route if they think it is more optimal path. That is the main reason why ‘Ant-colony’ algorithm takes too much time (in some cases it did not even finish evaluating the solution in our problem) to search for nodes if the distance is very long. The situation is different in A* search algorithm, because it is a modified version of Dijkstra algorithm, and each node have a calculated heuristic value. This means that no matter what kind of graph we have, A* search algorithm will converge and find “some” solution. But, with the time cost of Ant colony optimization algorithm usually provide a more optimal solution than A*. Figure 1 shows the different results between these two algorithms for the same inputs (source, destination and wind).
Figure 1.Difference in routes with different algorithms
As we already discussed above, the main advantage of the A* algorithm over ant colony optimization was A* had a shorter running time. In general, when some algorithm is slow in a single instance computer scientists try to parallelize or distribute the algorithm. However, parallelizing graph search algorithms is not a trivial task. In literature there is some research on parallelizing A* search algorithm. We did not parallelize our program for several reasons. First of all, it was very to hard to implement and secondly, we would have to even further sacrifice path quality for speed.
For our code in the backend and for comparing the results you can refer to .
The previous group did not have a good way to visualize the data after it was computed once. The program took its inputs from a map and showed the changes at each iteration but it required Matlab plugins that were not easy to setup for non technical people. We decided to have a web interface for visualization because it was available on all possible computing platforms. We also provided a list of ports that Venetian ships were known to trade in, so that the users wouldn’t choose their destinations inaccurately. A problem with pre-defined ports was that the locations of these harbors changed through the history and the modern ports were not accurate. We used “Geodatabase of Ancient Ports and Harbors” for relatively accurate locations. Although these configurations were specific to our project, we modified it so that the visualization interface can be easily configured to display maritime routes in completely different settings.
We initially planned to let the user add other obstacles and constraints to the calculated route but we removed those features as the computations were taking too much time for doing everything on the fly.
Finally, we noticed that there were interesting data regarding the intermediate points of the route that the previous group did not show. We added the wind condition at every intermediate point as a chart. The working interface for our project can be checked in . Figure 2 shows a sample path visualization in our interface.
In short, we have applied various algorithms and chose the most applicable one among them for finding the best path between port cities in the Mediterranean sea. We compared our alternative algorithms with the previous algorithm. We also developed a web based interface for visualizing the routes with user interaction where users can choose different ports and depending on the conditions of the weather the best path is calculated and is visualized on the map.
- Richard Seager,et al., Blueprints for Medieval hydroclimate.
- Sparse and Dense Graphs http://en.wikipedia.org/wiki/Dense_graph
- Graph algorithms http://en.wikipedia.org/wiki/Category:Graph_algorithms
- Parallel A* path finding algorithm. http://spcl.inf.ethz.ch/Teaching/2013-dphpc/final/5.pdf
- Digital Atlas of Roman and Medieval Civilizations “Geodatabase of Ancient Ports and Harbors” http://darmc.harvard.edu/icb/icb.do
- A* search algorithm http://en.wikipedia.org/wiki/A*_search_algorithm
- Engineering route planning algorithms. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation.
- “Finding shortest paths on real road networks: the case for A* “. International Journal of Geographical Information Science
- Manhattan distance http://en.wiktionary.org/wiki/Manhattan_distance
- Ant colony optimization algorithms. http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms