A COMPARATIVE STUDY OF UNDERWATER ROBOT PATH PLANNING ALGORITHMS FOR ADAPTIVE SAMPLING IN A NETWORK OF SENSORS

Monitoring lakes, rivers, and oceans is critical to improving our understanding of complex large-scale ecosystems. We introduce a method of underwater monitoring using semi-mobile underwater sensor networks and mobile underwater robots in this thesis. The underwater robots can move freely in all dimension while the sensor nodes are anchored to the bottom of the water column and can move only up and down along the depth of the water column. We develop three different algorithms to optimize the path of the underwater robot and the positions of the sensors to improve the overall quality of sensing of an area of water. The algorithms fall into three categories based on knowledge of the environment: global knowledge, local knowledge, and a decentralized approach. The first algorithm,VoronoiPath, is a global path planning algorithm that uses the concept of Voronoi Tessellation. The second algorithm, TanBugPath, is a local path planning algorithm, inspired from the Tangent Bug method for obstacle avoidance. Finally, the third path planning algorithm, AdaptivePath, optimizes the path by balancing the distance covered by the underwater robot and maximizing the sensing efficiency of both the sensor and the robot. It is based on an adaptive decentralized algorithm and plans the path of the underwater robot by assigning robot waypoints along the depth of the water column, and then adapting them alongside the sensor nodes to obtain the path of the robot. It uses a stable gradient-descent based controller which, we show, converges to a local minimum. We verify the algorithms through simulations and experiments. The VoronoiPath algorithm, generally, results in more efficient sensing paths. However, it is difficult to implement in real world as it needs global information and results in longer robot paths. The TanBugPath algorithm, on the other hand, has good sensing and it plans paths which are a usually shorter under varying conditions. However, all the processing takes place on-board the mobile robot, hence, this approach needs a more advanced robot than other algorithms. Finally, in case of the AdaptivePath algorithm, the in-network sensors calculate the path of the mobile robot in a decentralized manner. A major advantage of this approach is that the the positions of the sensors in the water column also get optimized depending on the path of the mobile robot. However, this algorithm can get stuck in a local minima, and is also dependent on the starting positions of the robot waypoints. For each of the algorithms we perform a detailed analysis and comparison. We identify limitations of each, and provide framework for future improvements. Adviser: Carrick Detweile