Automated Routing: Basic Principles

On-board computers offer undeniable advantages. One of these advantages is automated routing, i.e. the calculation of a sailing path based on weather forecasts. The navigator first provides the computer with a starting and a finishing point, then a minimum-time route is calculated for each of the weather scenarios. The computer presents as many routes as there are weather models. These calculations are extremely useful for analyzing possible routes.

Automated routes are calculated using applications such as OpenCPN, which is free (but requires a lot of fine-tuning), or PredictWind, which requires a monthly subscription (but is easier to use). There are other applications offering similar functionality (qtVlm, saildocs, etc).

This text shows how computers find optimal routes. It also bridges the gap between the different mathematical methods used for calculations, highlights the usual warnings – particularly concerning safety – and discusses some practical dimensions. The good news is that all that is required to understand this text is the ability to do summations and a bit of judgment.

Basic Principles

Any automated routing software identifies the route that takes the least time. They do nothing more, nothing less!

To anchor ideas, we will use the image above, where the starting point is point 1 and the end point is point 31. The image represents a rudimentary chart (the yellow cloud represents an island).

We often think of sailing in a romanticized way. We dream of the great freedom it brings, allowing us to choose our own path across a vast expanse of water. We dream of the infinite number of possible routes linking the point of departure (point 1) to the point of arrival (point 31).

The computer is much more down-to-earth. It builds itself a grid of intermediate points and only examines paths that pass through this grid. The restriction imposed by the computer may seem restrictive at first, but its grid has so many points that it has no practical impact. On the other hand, this approach structures the problem.

Since the aim is to understand how the onboard computer works, I will reduce the grid size to only 29 intermediate (and somewhat randomly choosen) points. This simplification is illustrated below. Intermediate points are numbered from 2 to 30, and intermediate routes are represented by arrows. It is therefore possible to navigate from point 5 to point 7, but impossible to navigate from point 8 to point 9 (no arrows).

I will also going to assume that the weather is stable for the duration of the navigation. In this way, the calculations can be presented on a single image. Otherwise, a movie would be required for the purpose of demonstration, which requires more time than I have to produce the example.

Of course, onboard computers do not assume that the weather is constant. Instead, they calculate the travel time based on the weather weather at the moment the boat is on on a transit route. In doing so, the computer presents a minimum-time trajectory with a video, illustrating the effect of weather at each transit period.

With this simplification, the travel time for each of the intermediate route can be estimated in hours can and shown on the picture. For example it takes 0.5 hours (30 min) to sail from point 1 to point 2, or 0.4 hours (24 min) to navigate from point 7 to point 11.

Total navigation time is, of course, cumulative, meaning that to get from one point to another, you need to add up all the time required on the route taken. For example, to get from point 1 to point 15, you need a total of 0.8 h (48 min), i.e. the sum of 0.3 hour and 0.5 hour.

If you feel like it, try to identify manually which route takes the least time between point 1 and point 31. The number of paths is small enough to be identified manually. The solution, using the intermediate points 2, 5, 7, 12, 20, 26 and 30, is shown in the image below (in green). It requires 2.8 hours of navigation (2h 48 min). Any other route will necessarily take longer!

People can quickly identify a solution manually when the route options are small. However, it quickly becomes impossible when the number of intermediate paths increases. This is where computers shine. They are very fast, and if we show them how to use a fundamental characteristic of any minimum-time route, they will systematically identify the exact solution in a very short time. This principle, which is much more general than this text suggests, can be summed up in one sentence.

A Minimum Path Is Necessarily Minimal Between Each Point

This sentence means that if we take any two points along the minimum-time path, then the path between these two points must also be minimum-time. If, on the other hand, there were a path that took less time between these two points, then the original path could be shortened by replacing this shorter path. The original path would then not be minimum-time. (Read again if needed: this is key).

In doing so, any minimum-time path must necessarily consist of a sequence of minimum-time paths between each point on the path. The principle is illustrated in the image above, which focuses on finding the path between point 5 and point 12.

Several possible routes can be identified:

• Route 5→6→9→12 (in orange, for 1 h 12 min);
• Route 5→8→12 (in red, for 54 min);
• Route 5→7→12 (in green, for 48 min);
• Route 5→6→8→12 (mixed color, for 1 hr);
• Route 5→7→11→12 (green and black, for 1 h 12 min);
• Route 5→7→10→11→12 (green and black, for 1 h 24 min);

Calculating the time on each of these routes is extremely simple. We can immediately identify that the minimum time is 48 minutes by the green route. We can therefore immediately deduce the following fact: if the route with the minimum time takes points 5 and 12, then it necessarily passes through the path 5→7→12. We’ve just shown that the opposite is not possible: any other path between 5 and 12 is necessarily longer! The minimum-time route must also be minimum-time locally. It’s so simple it’s almost redundant!

This fundamental idea is extremely useful because it takes a general, complicated problem – identifying the minimum-time path over all points – and breaks it down into small, easy-to-solve problems: identifying the minimum-time path over small intermediate segments. In so doing, the computer can concentrate on identifying paths over a small number of points – neighboring points, for example – to identify local solutions. It can then solve the more complicated problem, on all the points, by gluing these local solutions together.

If you understand this principle, its almost over. All that is missing is a starting point, a running tab… and a lot of patience! The computer is fast. We are not.

The Running Tab

At the beginning of the calculation, the computer assigns a value of zero to the first point, meaning that it takes no time to get there. For all other points, it assigns a temporary infinite time (denoted ∞) and it assigns an empty path. These assigned values – time and path – constitute the running tab. These values will change as the computer evaluates intermediate points.

The running tab is illustrated in the image below, where the duration is shown inside each node (paths are not shown). It is also summarized in a (partial) table after the image, which corresponds to the information stored in the computer’s memory.

From the starting point, the computer evaluates the minimum time required to to each point where it can navigate by a direct path (an arrow). From point 1, it can therefore evaluate the time to get to point 3 and to point 2. Below, it starts (arbitrarily) at point 2.

To get to point 2, it must take 0.5 hours (30 min) of time to which he must add the accumulated time in the running tab of the point by which it arrived. From point 1, the cumulative time is zero and the total transit time is therefore 0.5 + 0, i.e. 0.5 hour (30 min). It evaluates this calculated time and compares it with the time stored at the intermediate point of arrival (point 2).

The computer then selects the smaller of the two numbers, since that by the local minimum principle, the travel time between these two points must be the smallest. The time recorded in the running tab at point 2 is currently infinite (∞). It therefore replaces the value with 0.5 hours (30 min), as it is smaller, and it notes the point by which he arrived (point 1).

Similarly, the minimum time to reach point 3 is 18 minutes minutes (0.3 h). The running tab is thus updated with time 0.3 and point 1. The updated tab is illustrated in the image below and in the subsequent table.

The computer then repeats the process, this time starting from one of the two points it has just evaluated. It can arbitrarily start at point 3 or point 2, and I illustrate here with point 2 (image below). From point 2, circled in green, it can navigate to either point 4 (circled in orange) or point 5 (circled in red).

The time calculated to get to point 4 is 0.9 hours (54 min), i.e. the transit time from point 2 (0.4 h) plus the minimum time to get to point 2 (0.5 h). As the time in the running tatb is infinite for point 4, it is updated to the value of 0.9 h (54 min) and the arrival point is also noted (unillustrated). Similarly, it updates the running tab for point 5 with a value of 0.9 hours and the arrival path via point 2. The updated table is just after the image.

So far, the computer has only evaluated single routes. Under these circumstances, route identification is fairly straightforward, because there’s no comparison to be made with an alternative route. It always replaces the infinity stored in the running tab with the calculated transit time.

When a route has already been calculated to reach a point, things are however different. The tab already contains a calculated transit time and a point at which the computer has arrived. In this case, it is possible that the running tab will contain a smaller value than the calculated one. In accordance with the local minimum principle, the computer always keeps the smallest number. Of course, it will keep in the tab the point of origin that is consistent with this time.

This is the case when the computer evaluates the transit time from point 5 (circled in red in the image below). When evaluating the route to point 6 (circled in green), it calculates a minimum time of 1.2 hours (1 h 12 min) to get there. In fact, the time in the running tab to get to point 5 is 0.9 hours (54 min), to which must be added a travel time of 0.3 hours (18 min) between the two points.

However, for point 6, the time in the running tab is calculated at 1.1 hours (1 hr 6 min) when coming from point 4. By the principle of local minimum, it is impossible for the minimum path between point 1 and point 6 to pass through point 5. In so doing, the computer does not replace the value in the running tab, retains the minimum value of one hour and six minutes hour six minutes (1.1 hours) and retains point 4 as the point of origin to point 6. The updated table is shown after the image.

And then? Rince and repeat! The computer evaluates the newly reachable points and calculates the cumulative transit time, always keeping the lowest value.

I skip a few steps and present in the image below the state of the running tab at intermediate point 20 (circled in green). The points in purple correspond to those visited by the computer.
and the values shown correspond to the status of the running tab. As an example, the minimum time to reach point 18 (circled in pink) is calculated at 1.3 hours (1 h 18 min).

At point 20, the running tab is calculated at 1.9 hours (1h 54 min). His poin of origin is also filled (point 12).

In exploring the time required of the points that the sailboat can reach (25 circled in orange, 26 circled in yellow and 21 circled in red), the computer calculates respectively a transit time of 2.2 hours (2 h 12 min), 2.1 hours (2 h 6 min) and 2.3 hours (2 h 18 min). These times correspond to the minimum time to get to point 20 (1.9 h) plus the time of each segment (resp. 1.9 + 0.3, 1.9+0.2, 1.9+0.4).

Since the time in the running tab for the orange point is less (2.0 h), we can deduce that point 20 is not on the minimum path to the orange point. It therefore replaces nothing in the running tab. On the other hand, the point circled in yellow has until now had an infinite minimum time. As the calculated time of 2.1 hours is lower, the account book is amended to reflect this value and point 20 is also noted, signifying where the computer arrived. The updated table is shown below.

Ultimately, the computer will have visited all possible intermediate points (image below). When this is the case, the values entered in the ledger will show, for each point, the minimum travel time from point 1 to that point. Each point in the ledger will also show the previous point by which it was reached. For example, the image below shows that the minimum time to reach point 31 is 2.8 hours (2 h 48 min).

All that’s left to do is to look in the account book to identify the backward path, using the point of origin column. The computer then knows that it arrived at point 31 from point 30, then from point 26 and so on, all the way back to point 1. It can then find the minimum time path and display it on the onboard computer screen (image below).

The explanation of how the onboard computer works took a good four or five pages – about 20 minutes of reading – … and we left out a few steps. But make no mistake: the onboard computer’s computational processor is so powerful that it can come up with solutions of this kind in a fraction of a second.

What About the Simplifying Assumptions?

Remember that at the start of this text, I made it clear that I was simplifying the environment by assuming a limited number of possible paths. I also simplified by assuming constant weather conditions. These simplifications allowed me to illustrate the operating principle in pictures throughout the text.

In practice, the computer uses an arbitrarily large number of points and calculates all possible paths from one neighboring point to another. The image below shows a grid with just under 150 points. This grid contains just under 12,000 possible intermediate paths. I will leave to someone else the burden of illustrating them!

The minimum-time path on this grid still takes the computer a fraction of a second to calculate, but we now have a much less restrictive grid for identifying the minimum-time path. Because the distance between the points is smaller, the minimum-time path is much closer to the true freedom of action available to a sailboat. It takes longer to calculate (and it’s not a pleasant exercise to do manually!), but the solution is identified using exactly the same principle as illustrated on these pages.

Not precise enough? Simply increase the number of points! Eventually, the grid will be so tight that it won’t make any practical difference…. at the cost of a slightly longer calculation time.

As far as the weather is concerned, it makes no difference to the computer. I have assumed constant weather to illustrate the travel times between points on a single image. It is easier to visualize for humans. For its part, the computer does not have to produce any supporting image, so it can calculate travel times based on the weather at the moment the boat arrives at any intermediate point. For the computer, it is just a calculation to be made at each stage, rather than at the beginning. This is obviously a much more general approach, but it’s harder to put into pictures!

Some Advanced Comments

This section bridges the gap between different mathematical methods used to identify the optimal path in different disciplines. Those less familiar with advanced mathematics should skip this section and move on to the next.

The algorithm illustrated in this text goes back to Disjktra and is one of the “founding” algorithms of computer science (or decision science). It is the solution to an optimal trajectory problem on a graph, and has the main advantage of requiring only an understanding of addition, the local minimum principle… and repetition.

Alternatively, Disjktra’s algorithm can be seen as a solution to a standard optimal control problem where the optimal trajectory s(p_0,p_T) satisfies:

s(p_0, p_T) = \min_j[D(p_0, p_j) + s(p_j, p_T)].

In this expression, D(p_i,p_j) is the transit time between two intermediate points. This expression will of course satisfy the discrete version of Bellman’s condition, and the formulation explicitly refers, through recursive additivity, to the local minimum principle: the function is globally minimal if it is the minimum-time path connecting an additional point to an already minimized path.

We can also represent the problem on max-plus semi-rings, which has the advantage of linearizing the problem. In this way, the optimal solution is the eigenvector associated with the unit eigenvalue of the matrix associated with the problem. This approach performs extremely well on embedded computers, as linearity implies that calculations are parallelized.

Finally, most empirical work on regatta tactics and optimal sailing trajectories works with the Euler-Lagrange equations (probably because most tacticians come from the physical sciences). The approach is conceptually more attractive because it models the sailing trajectory as a continuous, differentiable function and avoids the conversation of “simplifying” the environment by imposing a restricted number of paths. On the other hand, the approach requires an understanding of differential equations and numerical solvers.

In practice, we solve the Euler-Lagrange equations with the associated differential equation (and using Beltrami’s identity), subject to the terminal conditions of starting point and end point. Any numerical solver will discretize the space over which the differential equation is represented. By the principle of duality, the solution identified will be exactly the same as that of Disjktra’s algorithm (if the discretization is the same). I have therefore illustrated here a different representation of this approach, which leads to the same solution, but is simpler to understand.

Back to the main program.

What the Computer Does not Do

Basically, the computer does one thing and one thing only: it evaluates the minimum-time path between two points. It does this on the basis of one (or more) weather models and in a relatively simplified river environment. In particular, the computer makes little assessment of the risks associated with the calculated route. Warnings (high winds, dead times, etc.) will be presented on some software programs, but these are very rarely interfaced with official nautical charts, let alone with any navigational warnings. It’s essential to check your route with regard to winds and surrounding hazards.

In fact, it’s not uncommon to see minimum-time routing software skip to distances arbitrarily close to the coast, without assessing the associated risks, and where weather models will be far less reliable. In the (hypothetical) minimum-time trail below, a serious assessment of the risk of a close passage along the coast would be in order.

Application

An important component used in weather routing applications was deliberately left out of the previous sections: polar speed curves. To be able to calculate the time a sailboat takes between two points, you need not only an estimated wind speed, but also a way of converting this wind speed into sailboat speed at the given point of sail.

This conversion is usually done by means of a polar curve of a sailboat (example below), where each curve represents the sailboat’s speed as a function of the wind angle. Each curve designates a wind speed. Without this curve, it would be impossible to calculate the time spent on an intermediate route!

It goes without saying that the validity of the results of a minimum-time trajectory also depends on the reliability of this curve. Routing software requires either a complete curve characterizing the yacht (OpenCPN), or a few identified speeds for a few points of sail (PredicWind). This information is available when you buy a modern sailboat, but economic incentives can turn these curves into advertising pamphlets showing the “best possible conditions”. It’s much better to make your own empirical assessment.

When this is done, the application of routing software is relatively straightforward. All you have to do is select the point of departure, the point of arrival and the weather models on which you want to perform the calculations. The calculation is then either performed on the computer from which you’re working (OpenCPN), or transferred via the network to the application’s servers (PredictWind). The latter means that high-resolution weather models don’t have to be downloaded to the on-board computer, a precious saving in bandwidth (and time!) if you’re working with a satellite modem (deep-sea navigation).

Weather models will generally offer different trajectories when forecasts differ. Reliable routes therefore depend on the reliability of the underlying weather model. We can therefore evaluate the chances of a weather model coming true when choosing a route, or weight routes according to the risks implicit in each model. In a previous text, I stressed the importance of a practical technique for identifying “win-win” scenarios, i.e. routes that work well under more than one weather scenario.

Conclusion

Computers are powerful instruments for rapidly calculating tons of data. However, it’s important to bear in mind that they don’t do anything magical, reasoned or thoughtful, but only obey a few rules providing an efficient response under a single criterion (minimizing time). It’s up to the people who use these results to assess whether they are reasonable in context.

In the first instance, road safety should be assessed in the light of information available from other sources. And, of course, nothing says that the road that takes the least time is the most pleasant! So think of your instruments as inputs to your navigation plan, rather than as a panacea. Given that they are inexpensive, much quicker than humans at calculating different information and make few errors in producing the results for which they were designed, however, we’d be foolish to do without them.

Did you enjoy this text? You can read the others related to navigation.