| dc.description.abstract | This research is part of a study of autonomous tugboats. The study is a cooperation between two students, but the projects are separate. The common goal for the study is to develop a working prototype of an autonomous tugboat swarm.
In this part of the study, algorithms for planning the shortest paths for the tugboats have been developed.
A literature review has been conducted to find the best algorithms and framework for the path planning system. The environment has been simplified by using a road map approach called ''visibility graph''. The shortest path within this graph is found by using A* search algorithm. This will give the shortest path within the non-simplified environment, if one exist.
Algorithms from external libraries have been adjusted to fit the tugboat framework. Some additional algorithms have also been developed, for instance a new method to find paths around a ship in real-time, only knowing its dimensions, position and orientation.
In addition, a speed-up and memory saving version of the shortest path algorithm has been developed, by calculating all shortest paths to and from all points offline. The speed-up was measured in five different test environments, and was measured to be on average 12.3 times faster than ordinary A* search in a visibility graph. The speed-up becomes even more impressive as the complexity of the environment increases.
The path planning system and communication has been implemented using the ''Robot Operating System''. This system has been tested successfully on a physical test setup.
The physical test setup is a starting-point for future research of autonomous tugboats. With this setup, the development in the study can be conducted using a bottom-up approach. Rather than starting off by creating a system seeming to perfect in theory, this setup can be used for rapid testing of smaller features. | |
