The first task associated with the project this semester was to decide how the algorithm would specifically work and which algorithm would be used. Because this is a path based optimization that must be completed, there are many potential algorithms suited for solving this type of problem. We started research by investigating methods to solve other path optimization problems such as the traveling salesman problem, delivery routing problems, shortest path in video games, etc. Our research pointed to three general algorithms: A*, Dijkstra’s algorithm, and Ant Colony Optimization. Simply stated, Ant Colony Optimization was chosen because it is more flexible than the other algorithms listed. Technically, the reason was that, unlike the other two, Ant Colony Optimization allows for bidirectional travel with asymmetric costs which is needed so that the program can evaluate some of the complexities that arise due to wind and ocean currents.1 Ant Colony Optimization is a clever path optimization algorithm that was inspired based upon how ant colonies find food. Our research has indicated that the best variation of the algorithm for this problem is a MAX-MIN Ant Colony Optimization.1
Ant Colony Optimization allows for the somewhat easy implementation of geographical data, ocean currents, and wind currents. Geographical data, which have already been implemented, only allow for the fictitious ants to operate within the sea. Ocean and wind data are implemented in the form of a cost for a given path traveled by the ants. The ocean data are treated as a simple translational vector which moves the ship in a given direction at a given kilometers per hour. The wind data are also added in the form of a vector, but determining this vector requires the use of a sailing polar. A sailing polar is a chart used by sailors to calculate a sailing speed in a given direction based upon the wind speed and direction. We will be finding and using sailing polars for all the ships that we will be simulating for this project.
What has been completed
Besides detailed planning, we have also made progress in the writing of the algorithm. So far not only have we found data bases for all of the geological, ocean,3 and wind data,4 but we have also written the code to import the geographical and wind data into our chosen programming language, MATALB.
The following tasks to be completed in the next three weeks include implementation of the current data and most of the completion of the Ant Colony Optimization algorithm. We will also be finding realistic sailing polars for the ships used in ancient Venice and will begin converting the historical data that we have into a format that can be easily interpreted by our algorithm.
1Ant Colony Optimization. Dorigo and Stützle, 2004.