Pathfinding for Autonomous Sailboats

Find out what goes on under the hood in the brain of an autonomous sailboat.

Introduction

People can learn how to sail after only a few lessons. But as an engineering challenge, sailing is not so simple. The aerodynamics and hydrodynamics of the entire system are highly non-linear and difficult to model. There are so many factors to take into account at any single moment: wind direction, ocean wave conditions, boat speed, sail position, rudder angle, avoiding collisions with other boats…

This begs the question: What would it take to build a sailboat that could sail by itself?

In this article, you will learn what goes on under the hood in the brain of an autonomous sailboat.

What would it take to build a sailboat that could sail by itself?

Context and Background

My name is Tyler and I am a Control Software Lead for UBC Sailbot. UBC Sailbot is a student engineering design team that builds fully-autonomous sailboats.

In 2016, our team launched Ada, a fully-autonomous sailboat with the goal of being the first fully-autonomous sailboat to cross the Atlantic Ocean. While she still broke many records, she was not able to complete the full journey. You can read more about Ada’s journey here.

UBC Sailbot decided to go back to the drawing board and continue the endeavor of building ocean-going autonomous vessels. With the wealth of experience gained in the testing and validating of Ada, we began a new project named Raye, which will be the first fully autonomous vessel to ever participate in the Vic-Maui Yacht Race.

With the wealth of experience gained in the testing and validating of Ada, we began a new project named Raye, which will be the first fully autonomous vessel to ever participate in the Vic-Maui Yacht Race.

Problem

Once Raye is built, she must chart her course from Victoria to Maui! How should she approach this problem?

Figure 1: How difficult is pathfinding for autonomous sailing?

As with any engineering problem, we first look at the simplest solution. Can we just draw a straight line? Unfortunately, it is not that simple.

Challenge 1: Raye needs to avoid colliding with the hundreds of other boats in the same waters.

Figure 2: There are hundreds of other boats between Victoria and Maui. This is a screenshot from https://www.vesselfinder.com/ that shows vessel positions from live AIS data.

Challenge 2: Raye needs to take into account the changing wind conditions when charting her course.

Figure 3: The wind conditions vary substantially on the journey from Victoria to Maui, which will impact how well Raye can sail. The arrows show wind vectors in different regions, with their size and direction indicating the wind speed and heading.

Challenge 3: Raye needs to minimize the total length of the path she generates so that she can reach her destination in a timely manner.

Figure 4: The straight line distance from Victoria to Maui is over 4000km. This sailing journey typically takes fifteen days to complete.

Solution

Our solution is to create two connected pathfinding modules: Global Pathfinding and Local Pathfinding.

Figure 5: Global pathfinding works on a larger distance scale to chart the overall course. Local pathfinding works on a smaller distance scale to connect the global waypoints together.

Global Pathfinding

Global pathfinding works on a large distance scale to chart the overall course from the boat’s current position to Maui. It ensures that the path that has sufficient wind conditions throughout the journey, while also minimizing the total path length. It will run on an onshore server and will send the global path output to the boat through satellite

Local Pathfinding

Local pathfinding works on a smaller distance scale to find the best path from the boat’s current position to the next global waypoint. It ensures that the path avoids obstacles and avoids upwind/downwind sailing, while also minimizing the total path length. It will run on the boat, using the boat sensors and global path as input.

Figure 6: This diagram shows Raye’s control data flow, starting from input data to pathfinding to the boat controller. The scope of this article will be focused on the global and local pathfinding modules.

Note before continuing: True pathfinding in a continuous space is very hard! The general problem is a PSPACE problem, which means that the problem scales very poorly with more dimensions and complexity.

Figure 6: True continuous pathfinding is a PSPACE problem, making it a much more complex than sorting a list or solving a sudoku puzzle. Source: https://en.wikipedia.org/wiki/PSPACE

However, things need to get done! To solve this problem, we turn to approximate pathfinding solutions that help us achieve the pathfinding quality that we need while remaining computationally tractable.

Figure 7: When computation gets too hard to find exact solutions, we can turn to approximate solutions.

To solve this problem, we turn to approximate pathfinding solutions that help us achieve the pathfinding quality that we need while remaining computationally tractable.

Global Pathfinding

Algorithm

Global Pathfinding uses the A* search algorithm, which looks very similar to a breadth-first search in that it creates a graph by discretizing the world into grid cells and then performs a search through the graph. The key difference is that it has an admissible heuristic function that helps guide the search in the right direction. A heuristic function is admissible when it is optimistic, in that it will never overestimate the cost to reach the goal from a given position. If the heuristic function is chosen correctly, it will always find the optimal path. One thing to note is that A* does not scale well to more complex problems with more dimensions.

Figure 8: The A* search algorithm discretizes the world into cells, and is guided by a heuristic function to find the optimal path to the goal.

The A* search algorithm looks very similar to a breadth-first search in that it creates a graph by discretizing the world into grid cells and then performs a search through the graph. The key difference is that it has an admissible heuristic function that helps guide the search in the right direction.

Cost Function Objectives

Global pathfinding’s cost function is set up so that it minimizes path length and optimizes for wind between 10–25 knots. The exact cost functions can be found in the figure below.

Figure 9: The global pathfinding tries to find a path that has a short total path length and avoids low/high wind regions.

Figure 10: The global pathfinding cost function plots.

Local Pathfinding

Algorithm

Local Pathfinding uses the RRT* search algorithm, which stands for rapidly-exploring random tree. It creates a tree structure rooted from the starting point, then branches outwards towards the goal by sampling random points from the state space and then connecting them to the existing tree. This algorithm asymptotically approaches the optimal solution, which means that it will approach the optimal solution if it is given enough time. RRT*’s simple but effective approach scales well to complex problems with more dimensions.

Figure 11: The RRT* algorithm can be visualized here. Source: https://www.youtube.com/watch?v=nsl-5MZfwu4

The RRT* algorithm creates a tree structure rooted from the starting point, then branches outwards towards the goal by sampling random points from the state space and then connecting them to the existing tree

Figure 12: The RRT* algorithm in more detail. The tree expands by sampling random points from the state space and then connecting them to the existing tree. This requires an “isValid(state)” method to check if the randomly sampled states are valid.

Cost Function Objectives

Local pathfinding’s cost function is set up so that it minimizes path length while avoiding large turns, obstacles, and upwind/downwind sailing (sailing in a direction parallel to the wind).

Figure 13: Our custom local pathfinding visualizer is shown in the image above. It shows that the local pathfinder is able to avoid upwind sailing, avoid obstacles, and keep a short path to the goal waypoint.

Figure 14: Sailboats avoid upwind/downwind sailing by tacking. This means that the boat does not move parallel to the wind, but at 30 degree angles with respect to the wind to avoid bad sailing situations. Source: Reactive path planning for autonomous sailboat by Clement Petres and Frederic Plumet

Closing Thoughts

Raye is a huge engineering project and there is still a large amount of work to be done. On the pathfinding side, this includes integrating the simulation with real AIS data to perform virtual practice Vic-Maui Yacht Races, performing end-to-end testing of the global pathfinding, local pathfinding, and boat controller, and improving the AIS boat representation in local pathfinding to more accurately reflect their effect on available paths. We also need to develop more sophisticated testing for global pathfinding to ensure it will avoid storm situations.

I am excited to continue improving Raye’s pathfinding capabilities and reliability leading up to our launch in the summer of 2021 and sharing more content about how Raye works.

UBC Sailbot is an amazing team of hard-working, talented students that dream big and execute effectively. I am thankful to be a part of this team and to have the opportunity to contribute to this project.

To learn more about UBC Sailbot and Raye’s journey, check out the links below:

UBC Sailbot website: https://www.ubcsailbot.org/

Vic-Maui Yacht Race website: https://www.vicmaui.org/

Local pathfinding