Algorithm models for maritime routes

Navigation on land is now a solved problem with many free solutions available on the web. Maritime routes are different from land routes; there are no pre-defined roads and arbitrary crossroads, lights. In order to model this different behaviour and find optimal choices for contemporary or historical paths, we propose a new model. In this model, zones that ships can’t travel or unlikely to travel are named obstacles and can be defined as polygons on a map. Simple examples for these obstacles could be rocks and coastlines, or areas where it was not safe to travel due to piracy, warfare or weather conditions. We leave the possibilities for obstacles and our model as broad as possible so that it can be used with different historical contexts or places so that historians can use our software to create routes that considers other conditions that we did not think of during the implementation.

There was some work on this project last year. The previous group did a great job of implementing different algorithms and considering many conditions that affect maritime routes such as winds, currents, and speeds known for the ships used. We will extend the project to add more functionality discussed as above and fixing the shortcomings of the current state.

Analysis

We will start the project by analyzing details of the work done by previous groups and other proposed systems that try to tackle the problem of finding maritime routes. We will investigate the different approaches and their outcomes. Learning about proposed solutions and the pros and cons of these proposals will formulate a general idea about the project difficulty, and the direction we should take for solving algorithmic problems and planning our time in later stages.

Project design

As we pointed out in the introduction section, the last year’s group have implemented very large set of functionalities. However, the main disadvantages were lack of a user-friendly interface and well-organized code base. We already studied a different kind of system and found out an interesting project implemented by Stanford University. ORBIS – The Stanford Geospatial Network Model of the Roman World reconstructs the time cost and financial expense associated with a wide range of different types of travel in antiquity [1]. The project ORBIS covers huge variety of possibilities for users to find out different routes considering weather conditions or route priorities (fastest/cheapest/shortest).  We are planning to design a new system that contains two parts :

  1. Backend: it would be more advanced version that had been implemented last year. Depending on the need, we will add new algorithms, redesign existing ones or make a more abstract model design for better coverage.
  2. Frontend: we want to have a user-friendly program that will cover most of the ORBIS functionalities.

Modularizing our project design will help us to organize our code base, and introduce the possibility to work at the same time on independent parts simultaneously. Deciding on which platform to implement the project is another important point. We have some source code in Matlab, however Matlab is not particularly useful for creating a visual platform. We should investigate other high level programming languages and their integration with existing GIS systems.

Algorithm design

The shortest path between two points can be found using many heuristic algorithms, like the Genetic algorithms, Memetic algorithm, Dynamic relaxation, Differential Search algorithm, Differential evolution, Particle swarm optimization, Hill climbing, Nelder-Mead simplicial heuristic, Tabu search, Artificial bee colony optimization, or Simulated annealing [2]. We already have source code for Dijkstra’s algorithm for path finding. This implementation considers sailing polars, however, it is really slow (approx. 90 minutes for a superfine path). Our first goal is to understand current implementation and find out possible bugs that cause this slow running time.  We are certain that current performance can be improved, maybe with a variation on the Dijkstra’s algorithm to account for bidirectional paths. Moreover, our implementation would be obstacles oriented such that every user can add different kinds of obstacles while current state of the project was developed.  No matter which decision we will make, either to continue improving the existing algorithm or trying a new one, in all cases implementation should consider future obstacle additions from the end user.

Data

We will gather data so that we can apply our model to a real historical setting. We will choose a suitable location and time period (for example, 1450-1455 CE Adriatic Sea) to narrow down the extent of this phase because the aim of this project is to have a working algorithm and the implementation will be just for demonstration purposes.

 

Testing and Validation

Testing is an important part of the project and needs to be considered very carefully.  As it is a very time consuming process, we should plan our strategy beforehand. We will create a set of tests before starting every development stage. In other words, we are going to use unit-testing. This will guarantee the correctness of each stage and any later modification can be tested quickly. Of course, there are disadvantages of using unit-testing; for instance, all test cases can’t be covered. However, it is trade-off between complete correctness and time. Our project is not focused on correctness like some banking or trading system, thus we can afford some error rate in unit-testing to gain some time for developing other features.

Presentation Preparation 

The final stage of the project will contain detailed documentations on how to use or modify our resulting tool and a well-organized Git repository for code base, so that the users and researchers who may investigate our project later will have a clear understanding of the work done, and the capabilities of our tool.

DHplan

 

References :

  1. http://orbis.stanford.edu
  2. http://veniceatlas.epfl.ch/algorithm-models-for-maritime-routes-s5-project-description/