Beyond the prototype – Designing a Route Making Algorithm to Cross the Atlantic Ocean

by UBC SailBot Software Team

In late November we posted about our design of a pathfinding algorithm prototype for navigating around simple obstacles in order to get to a destination. Since then we have transformed this from a prototype into an expandable weather routing algorithm that fits into our sailing logic architecture.

Control System Architecture

Image 1 - Control System Architecture

Image 1 – Control System Architecture

Our goal in designing the software for the transatlantic boat is to have two main systems.  The first of those systems is the low level control system.  Similar to our design for the International Robotic Sailing Regatta competition in Massachusetts last year, we want our transatlantic boat to be an expert on getting from one point on earth to another. What drives this is a robust autonomous control system that takes inputs and uses sailing logic to produce desired output on the rudder and sail position. In prior years, this was the key piece in the puzzle. For crossing the Atlantic Ocean, however, we have the additional challenge of obstacles. This is where the second system comes in to play.

The route making system (system two) is designed to plan a route across the Atlantic Ocean given that there will be obstacles that gets in our way, and that the obstacles change over time.  As we moved from the route making prototype and started developing a design to take into account crossing the Atlantic ocean we decided to give the route making algorithm design a makeover.

Route making architecture makeover

Our first design for a route making system incorporated all data into one three dimensional pathfinding algorithm, the third dimension being time.  Through testing we have realized many limitations to this original design and developed a new design with a more robust architecture.  The main driver for this change is the large scale patterns that weather systems display which are imperceptible at smaller scales.  Because the boat navigates at a small scale, and thus also receives sensor data of its surroundings on a small scale, we decided the boat requires a two layer architecture – one for the entire Atlantic Ocean, and one for the foreseeable future.

A one layer structure – combining both large scale and small scale datasets – could be done if we only looked into the near future, however the algorithm would suffer from not being able to see the entire Atlantic. We illustrate this in Image 2, as seen below, where the goal of our boat is to make it to Target 2. Imagine that we only look east as far as Target 1.  We would not see that there is an obstacle just following Target 1 and in this case after we reached Target 1 we would have to backtrack to make it to Target 2.  If we instead looked east all the way to Target 2 we would realize that the fastest way to get to Target 2 is to avoid the obstacle all together.  This sort of situation is very applicable to some of the situations we encounter when analyzing data gathered on the Atlantic. As a result, we separate the different scale datasets into a two layer system. The small scale layer relies on the large scale layer to know the path that is best suited over the entire Atlantic, and then calculates the best direction for the next 10km.

Image 2 - Large versus small scale sailing scenario

Image 2 – Large versus small scale sailing scenario

We have documented each layer in better detail below.

Large Scale Layer:

Image 3 - Route-making from the Gulf Of Mexico, avoiding areas with large waves.

Image 3 – Route-making from the Gulf Of Mexico, avoiding areas with large waves.

Scale: each cell will be 1×1 degree or ~100km

Inputs: weather from an online repository, a preset target (Ireland), a preset bias route that the boat should ideally travel.

Outputs: a 2D grid of weights

Description: At this layer, we plot the long term trend of the route that the boat should take, taking into consideration large scale weather systems while trying to keep as close as possible to the pre-set ideal route. The output of this layer will be a 2D grid of weights representing the long term route which will be fet to the small scale layer.

Small Scale Layer:

Scale: ~10km

Inputs: the output of the Large scale Layer, AIS data, other small scale obstacle data.

Outputs: a set of coordinates ~10km apart

Description: This layer will plot a route for the short term obstacle avoidance taking into consideration smaller obstacles such as boats. It will receive a 2D grid of weights which will serve as a bias for the long term route from the large scale layer. This way, the small scale layer will plot a route that will resemble the the large scale route unless there is an obstacle preventing it, in which case it will plot the next best route. The output of this layer will be a set of coordinates which represent the path calculated by this layer and which will be fet to the control system.

There are a number of challenges going forward that we are focusing on to improve the route making system.  We are actively looking for good data to base our weather routing off of, and with multiple datasets we also need to define how we are going to weight the datasets against each other.  When routing we also need to determine a good resolution for each layer.  This is integral for us to ensure that we can fit the “good” data for the entire time span we are route making over.

Advertisements

One thought on “Beyond the prototype – Designing a Route Making Algorithm to Cross the Atlantic Ocean

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s