Designing an Autonomous Route Planning Algorithm Prototype

by Rodrigo Blaustein and Yasmeen Akbari

In order to implement a complex pathfinding algorithm such as the one that is required for our transatlantic crossing, it is necessary to divide the task into stages.

The motivation behind the development of the Pathfinder GUI tool was to provide a tool which would facilitate the work of the UBC SailBot Software team by providing them a way to specify test scenarios, run the test scenarios and display the result of the test scenarios in a meaningful way.

The tool utilises a 2D array in order to represent the scenarios like a map. Currently, each element in the 2D array can represent one of five possible values. From the users point of view each of these five possible values is represented by a specific color in the GUI. The possible values are as follows:

start: Represents where the boat starts and is represented in the GUI by the color red

target: Represents where the boat wants to go and its color in the GUI is green

obstacle: Represents an obstacle the boat cannot visit and has color brown in the GUI

visited: Represents a node that has already been analysed by the algorithm and is represented by the color dark gray on the GUI

new: The default value of a node, it represents open space that the boat can travel and has not been analysed by the algorithm yet. It is represented by the color light gray in the GUI.

Input of prototype route-planning. The red dot represents our vessel, the green dot is the destination, and the brown boxes and line are all obstacles.

Input of prototype route-planning. The red dot represents our vessel, the green dot is the destination, and the brown boxes and line are all obstacles.

The user can specify the initial state of the scenario and then run the tool which would simulate the path according to the specific heuristic function. The heuristic function is used to inform the algorithm what neighbour node the boat should visit next.  Some algorithms are dynamic and require extra data to be stored on each node.

Showing the menu for how to create nodes. By choosing Run the algorithm will figure out the best path to take to avoid the different obstacles.

Showing the menu for how to create nodes. By choosing Run the algorithm will figure out the best path to take to avoid the different obstacles.

Output of the prototype route planning. The vessel (red dot) will travel in the dark grey area to reach the destination (green dot).

Output of the prototype route planning. The vessel (red dot) will travel in the dark grey area to reach the destination (green dot).

The current heuristic implemented, which was used in the demonstration, chooses the next node to visit based on that node’s euclidean distance to the target. The euclidean distance to the target is calculated using pythagoras theorem.  We aim for a heuristic function which will always underestimate the distance to the goal, also called an admissible heuristic.  For each neighbour of the current node which has a value of new, we calculate the distance of that neighbour to the target node and then choose the neighbour that has the shortest euclidean distance. All other neighbours are marked as visited nodes.

If we improve the heuristic function, we could improve the amount of time it takes for the algorithm to run.  Because this algorithm ignores visited nodes, the boat could get stuck, blocked by its own path. This is why it is necessary to try and test several heuristics, and improve the algorithm to work in all cases by revisiting nodes.

The next steps will involve implementing and testing different heuristics and algorithms in order to determine which one produces the most efficient path. Another feature that needs to be implemented is moving obstacles. The user should be able to draw an obstacle and specify its velocity, both magnitude and direction. In future versions the tool should also be able to include other parameters such as weather data, getting entangled on debris, etc.

About these ads

2 thoughts on “Designing an Autonomous Route Planning Algorithm Prototype

  1. The problem here is that the objects are defined. Which is fine if this is a land mass or oil rig or other obstacle that has previously been tracked. Once an object has been determined and a path chosen are you at the stage where you can add another object on the fly?

    When one or two or three objects are determined and too be avoided, would a route with one tack (two tops) not be more efficient. For Sailbot to due east, and then due south after one tack, we would have our most simple and efficient route. Not only for time and energy spent, but for wear on moving parts.

    Very cool what you guy are doing. Godspeed.

    • Hi there!

      To answer your first question, we are recalculating the route probably over 1000 times on our trip. We absolutely have to, and will be able to add objects on the fly as most of our data (weather, boat) is retrieved on the fly.

      To answer your second question, the winding route that is seen in the prototype won’t all be sent to the lower level logic. The example route in the blog post isn’t very realistic as the obstacles shown are, few, random, and large. In reality every single node on this graph is an obstacle, they all just have different levels of danger. Regardless, if you were to only take every 10th point, or just adjust your perspective and believe that each box was 100km wide, the path would not look nearly as windy. For the most part the boat heading would change by only a few degrees. The idea here is that the boat will try to get itself to a number of dynamically produced points. The distance between those points will be determined when we begin testing, however I imagine that it will be quite large.

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