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.
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.
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.