Sailing Strategies
An Application Involving Stochastics, Optimization, and Statistics
(SOS)
If the Java applet fails to start due to Java Security issues,
click
here.
Introduction
Consider a sailor who wishes to sail from one point (A) to another (B) in
the shortest possible time (for example, in a race). To create a simple
model of such a situation,
suppose that the lake is represented by a 2-dimensional square
n-by-n grid of
waypoints. Every path from A to B consists of a sequence of legs,
the endpoints of which must be waypoints.
Suppose further that the only legs that the
sailor considers are legs connecting one waypoint to one of
its 8 neighbors
(found by sailing N, S, E, W, NE, SE, SW, or NW from the current point).
Time as a Function of Wind Angle
The boat's speed depends on the relative angle between the boat's heading and
the wind's direction.
For example, the boat cannot sail directly into the wind. If, however, the
wind is at 45 degrees to the boat's heading, we say that the boat is on an
upwind tack. On such a tack, it takes 4 minutes to sail from one
waypoint to a nearest neighbor. But, if the wind is at 90 degrees to the
boat's heading, the boat moves faster through the water and can reach the next
waypoint in only 3 minutes. Such a tack is called a crosswind tack.
If the wind is a quartering tailwind, we say that the boat is on a
downwind tack---such a tack takes 2 minutes. Finally, if the boat is
sailing directly downwind, we say that it is on an away tack.
Starboard Vs. Port Tacks
If the wind is hitting the left side of the sails (as in the picture) we say
that the boat is on a port tack. If, on the other hand, the wind is
on the right-hand side, we say that it is a starboard tack. Changing
from a port to a starboard tack (or vice versa) takes time since it involves
stearing the boat straight into the wind and moving the sails from one side of
the boat to the other.
Expert sailors can do this with great finesse, but, for beginners, the boat
might come dead in the water and it can take awhile to get it going again. We
assume that our sailor wastes 3 minutes for every such change of tack.
This time is refered to as the tacking delay.
Deterministic Vs. Stochastic Models
If the wind blows constantly from one direction, then it is fairly
straightforward to use the information given above to find the best path from A
to B. Such a path would involve just one change of direction.
But, winds have a tendency to change (both in direction and in intensity).
To keep our model simple, we assume that the intensity is constant but
its direction can change from one leg to the next (we assume, rather
artificially, that the wind only changes when the boat is at a waypoint).
The new wind comes from one of three directions: either from the
same direction as the old wind, or from 45 degrees to the left or to the right
of the old wind. We allow the user (i.e., you) to set the probabilities for
each of these scenarios.
Stochastic Optimization
The data described above can be put into a precise mathematical model, called a
dynamic programming model, and solved on a computer. By pushing the
button at the bottom of this page you can solve this problem on your computer.
Simulation
Once the problem has been solved, it remains an issue as to how to present
it since the optimal strategy depends on four independent pieces of
information: (i) the current latitude, (ii) the current longitude, (iii) the
wind direction for the next leg, and (iv) whether the previous leg was a port
tack or a starboard tack. A table showing all possibilities would be
huge even for a small lake. Therefore, we prefer to show some
specific realizations generated using your computer's random number generator.
The process of generating these realizations is called a simulation.
The simulations are produced in such a manner that, if a large number of them
are generated, the empirically observed wind change probabilities will
eventually approach those given as input to the model.
When you press the button below, your computer will calculate the optimal
solution to the dynamic programming problem and then produce one simulation
which will be shown graphically. To generate subsequent simulations, press
either the "Simulate" button to generate them 1 at a time or the
"Simulate 100" button to do 100 all at once.
Statistics
At any time, you can push the "View Stats" button to get a graphical summary of
all the simulations done since the last "Calculate". In addition,
the following statistics are shown:
the minimum time, the maximum time, the mean time (i.e., average time), and the
median time.
Stochastics, Optimization, and Statistics at Princeton
If this example seems interesting to you and you are a student looking for a
place to do your undergraduate or your graduate studies, then you might want to
consider our undergraduate program in
Engineering Managment Systems
or our graduate program in
Statistics and Operations Research.
In addition to learning about these neat things, you can also take up sailing
on nearby Lake Carnegie.